Past Combinatorial Theory Seminar

11 February 2014
14:30
Abstract

We give a new proof of the Frankl-Rödl theorem on set systems with a forbidden intersection. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl. One consequence of our result is a Frankl-Rödl type theorem for permutations with a forbidden distance. Joint work with Peter Keevash.

  • Combinatorial Theory Seminar
28 January 2014
14:30
Peter Keevash
Abstract
A Steiner Triple System on a set X is a collection T of 3-element subsets of X such that every pair of elements of X is contained in exactly one of the triples in T. An example considered by Plücker in 1835 is the affine plane of order three, which consists of 12 triples on a set of 9 points. Plücker observed that a necessary condition for the existence of a Steiner Triple System on a set with n elements is that n be congruent to 1 or 3 mod 6. In 1846, Kirkman showed that this necessary condition is also sufficient. In 1853, Steiner posed the natural generalisation of the question: given integers q and r, for which n is it possible to choose a collection Q of q-element subsets of an n-element set X such that any r elements of X are contained in exactly one of the sets in Q? There are some natural necessary divisibility conditions generalising the necessary conditions for Steiner Triple Systems. The Existence Conjecture states that for all but finitely many n these divisibility conditions are also sufficient for the existence of general Steiner systems (and more generally designs). We prove the Existence Conjecture, and more generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition.
  • Combinatorial Theory Seminar
21 January 2014
14:30
Yufei Zhao
Abstract
<p>We introduce and develop a theory of limits for sequences of sparse graphs based on $L^p$ graphons, which generalizes both the existing $L^\infty$ theory of dense graph limits and its extension by Bollob\'as and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees.</p> <p>Joint work with Christian Borgs, Jennifer T. Chayes, and Henry Cohn.</p>
  • Combinatorial Theory Seminar
26 November 2013
14:30
Abstract
Nesetril and Ossona de Mendez introduced a new notion of convergence of graphs called FO convergence. This notion can be viewed as a unified notion of convergence of dense and sparse graphs. In particular, every FO convergent sequence of graphs is convergent in the sense of left convergence of dense graphs as studied by Borgs, Chayes, Lovasz, Sos, Szegedy, Vesztergombi and others, and every FO convergent sequence of graphs with bounded maximum degree is convergent in the Benjamini-Schramm sense. FO convergent sequences of graphs can be associated with a limit object called modeling. Nesetril and Ossona de Mendez showed that every FO convergent sequence of trees with bounded depth has a modeling. We extend this result to all FO convergent sequences of trees and discuss possibilities for further extensions. The talk is based on a joint work with Martin Kupec and Vojtech Tuma.
  • Combinatorial Theory Seminar
12 November 2013
14:30
Simon Griffiths
Abstract
The Ramsey number $R(K_s, Q_n)$ is the smallest integer $N$ such that every red-blue colouring of the edges of the complete graph $K_N$ contains either a red $n$-dimensional hypercube, or a blue clique on $s$ vertices. Note that $N=(s-1)(2^n -1)$ is not large enough, since we may colour in red $(s-1)$ disjoint cliques of cardinality $2^N -1$ and colour the remaining edges blue. In 1983, Burr and Erdos conjectured that this example was the best possible, i.e., that $R(K_s, Q_n) = (s-1)(2^n -1) + 1$ for every positive integer $s$ and sufficiently large $n$. In a recent breakthrough, Conlon, Fox, Lee and Sudakov proved the conjecture up to a multiplicative constant for each $s$. In this talk we shall sketch the proof of the conjecture and discuss some related problems. (Based on joint work with Gonzalo Fiz Pontiveros, Robert Morris, David Saxton and Jozef Skokan)
  • Combinatorial Theory Seminar
5 November 2013
14:30
Mark Jerrum
Abstract
<p>The Tutte polynomial of a graph $G$ is a two-variable polynomial $T(G;x,y)$, which encodes much information about~$G$. The number of spanning trees in~$G$, the number of acyclic orientations of~$G$, and the partition function of the $q$-state Potts model are all specialisations of the Tutte polynomial. Jackson and Sokal have studied the sign of the Tutte polynomial, and identified regions in the $(x,y)$-plane where it is ``essentially determined'', in the sense that the sign is a function of very simple characteristics of $G$, e.g., the number of vertices and connected components of~$G$. It is natural to ask whether the sign of the Tutte polynomial is hard to compute outside of the regions where it is essentially determined. We show that the answer to this question is often an emphatic ``yes'': specifically, that determining the sign is \#P-hard. In such cases, approximating the Tutte polynomial with small relative error is also \#P-hard, since in particular the sign must be determined. In the other direction, we can ask whether the Tutte polynomial is easy to approximate in regions where the sign is essentially determined. The answer is not straightforward, but there is evidence that it often ``no''. This is joint work with Leslie Ann Goldberg (Oxford).</p>
  • Combinatorial Theory Seminar
29 October 2013
14:30
Peter Keevash
Abstract
Perfect matchings are fundamental objects of study in graph theory. There is a substantial classical theory, which cannot be directly generalised to hypergraphs unless P=NP, as it is NP-complete to determine whether a hypergraph has a perfect matching. On the other hand, the generalisation to hypergraphs is well-motivated, as many important problems can be recast in this framework, such as Ryser's conjecture on transversals in latin squares and the Erdos-Hanani conjecture on the existence of designs. We will discuss a characterisation of the perfect matching problem for uniform hypergraphs that satisfy certain density conditions (joint work with Richard Mycroft), and a polynomial time algorithm for determining whether such hypergraphs have a perfect matching (joint work with Fiachra Knox and Richard Mycroft).
  • Combinatorial Theory Seminar
24 October 2013
11:00
Abstract
<p>Let $G$ be an addable minor-closed class of graphs. We prove that a zero-one law holds in monadic second-order logic (MSO) for connected graphs in G, and a convergence law in MSO for all graphs in $G$. For each surface $S$, we prove the existence of a zero-one law in first order logic (FO) for connected graphs embeddable in $S$, and a convergence law in FO for all graphs embeddable in $S$. Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface $S$. If $G$ is an addable minor-closed class, we prove that the closure of the set of limiting probabilities is a finite union of intervals, and it is the same for FO and MSO. For the class of planar graphs it consists of exactly 108 intervals. We give examples of non-addable classes where the results are quite different: for instance, the zero-one law does not hold for caterpillars, even in FO. This is joint work with Peter Heinig, Tobias Müller and Anusch Taraz. </p>
  • Combinatorial Theory Seminar

Pages