Combinatorial Theory Seminar
|
Tue, 12/10/2010 14:30 |
Mary Cryan (Edinburgh) |
Combinatorial Theory Seminar  |
L3 |
| The problem of checking existence for an Euler tour of a graph is trivial (are all vertex degrees even?). The problem of counting (or even approximate counting) Euler tours seems to be very difficult. I will describe two simple classes of graphs where the problem can be solved exactly in polynomial time. And also talk about the many many classes of graphs where no positive results are known. | |||
|
Tue, 19/10/2010 14:30 |
Jean Cardinal (Universite Libre de Bruxelles) |
Combinatorial Theory Seminar |
L3 |
| We revisit the problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time sorting algorithm achieving this bound up to a constant factor. They established a crucial link between the entropy of the input partial order and the information-theoretic lower bound. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical. We develop efficient algorithms for sorting under partial information, derived from approximation and exact algorithms for computing the partial order entropy. This is joint work with S. Fiorini, G. Joret, R. Jungers, and I. Munro. | |||
|
Tue, 26/10/2010 14:30 |
Raphael Clifford (Bristol) |
Combinatorial Theory Seminar |
L3 |
| Combinatorial pattern matching is a subject which has given us fast and elegant algorithms for a number of practical real world problems as well as being of great theoretical interest. However, when single character wildcards or so-called "don't know" symbols are introduced into the input, classic methods break down and it becomes much more challenging to find provably fast solutions. This talk will give a brief overview of recent results in the area of pattern matching with don't knows and show how techniques from fields as disperse FFTs, group testing and algebraic coding theory have been required to make any progress. We will, if time permits, also discuss the main open problems in the area. | |||
|
Tue, 09/11/2010 14:30 |
David Ellis (Cambridge) |
Combinatorial Theory Seminar |
L3 |
| A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H in F, the intersection of G and H contains a triangle. Simonovits and Sos conjectured that such a family has size at most (1/8)2^{\binom{n}{2}}, and that equality holds only if Fconsists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycle-intersecting family of graphs, then |F| \leq (1/8) 2^{\binom{n}{2}}. Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will then discuss some related open questions. All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem). | |||
|
Tue, 16/11/2010 14:30 |
John Talbot (UCL) |
Combinatorial Theory Seminar |
L3 |
| How many triangles must a graph of density d contain? This old question due to Erdos was recently answered by Razborov, after many decades of progress by numerous authors. We will consider the analogous question for tripartite graphs. Given a tripartite graph with prescribed edges densities between each pair of classes how many triangles must it contain? | |||
|
Tue, 23/11/2010 14:30 |
Combinatorial Theory Seminar |
L3 | |
