Past Combinatorial Theory Seminar

15 October 2013
14:30
Andrew Thomason
Abstract
<p>An independent set in an $r$-uniform hypergraph is a subset of the vertices that contains no edges. A container for the independent set is a superset of it. It turns out to be desirable for many applications to find a small collection of containers, none of which is large, but which between them contain every independent set. ("Large" and "small" have reasonable meanings which will be explained.) <br /> <br />Applications include giving bounds on the list chromatic number of hypergraphs (including improving known bounds for graphs), counting the solutions to equations in Abelian groups, counting Sidon sets, establishing extremal properties of random graphs, etc. <br /> <br />The work is joint with David Saxton.</p>
  • Combinatorial Theory Seminar
28 May 2013
16:30
Po-Shen Loh
Abstract
<p>The first application of Szemeredi's regularity method was the following celebrated Ramsey-Turan result proved by Szemeredi in 1972: any K_4-free graph on N vertices with independence number o(N) has at most (1/8 + o(1))N^2 edges. Four years later, Bollobas and Erdos gave a surprising geometric construction, utilizing the isodiametric inequality for the high dimensional sphere, of a K_4-free graph on N vertices with independence number o(N) and (1/8 - o(1)) N^2 edges. Starting with Bollobas and Erdos in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about N^2 / 8.</p> <p>These problems have received considerable attention and remained one of the main open problems in this area. &nbsp;More generally, it remains an important problem to determine if, for certain applications of the regularity method, alternative proofs exist which avoid using the regularity lemma and give better quantitative estimates. &nbsp;In this work, we develop new regularity-free methods which give nearly best-possible bounds, solving the various open problems concerning this critical window.</p> <p>Joint work with Jacob Fox and Yufei Zhao.</p>
  • Combinatorial Theory Seminar
28 May 2013
14:30
Christina Goldschmidt
Abstract
Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal's algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal's algorithm and the Erd\"os-R\'enyi random graph in order to prove that $M_n$, the MST of the complete graph, possesses a scaling limit as $n$ tends to infinity. In particular, if we think of $M_n$ as a metric space (using the graph distance), rescale edge-lengths by $n^{-1/3}$, and endow the vertices with the uniform measure, then $M_n$ converges in distribution in the sense of the Gromov-Hausdorff-Prokhorov distance to a certain random measured real tree. This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).
  • Combinatorial Theory Seminar
21 May 2013
14:30
Paul Seymour
Abstract
The ``k-commodity flow problem'' is: we are given k pairs of vertices of a graph, and we ask whether there are k flows in the graph, where the ith flow is between the ith pair of vertices, and has total value one, and for each edge, the sum of the absolute values of the flows along it is at most one. We may also require the flows to be 1/2-integral, or indeed 1/p-integral for some fixed p. If the problem is feasible (that is, the desired flows exist) then it is still feasible after contracting any edge, so let us say a flow problem is ``critical'' if it is infeasible, but becomes feasible when we contract any edge. In many special cases, all critical instances have only two vertices, but if we ask for integral flows (that is, p = 1, essentially the edge-disjoint paths problem), then there arbitrarily large critical instances, even with k = 2. But it turns out that p = 1 is the only bad case; if p>1 then all critical instances have bounded size (depending on k, but independent of p), and the same is true if there is no integrality requirement at all. The proof gives rise to a very simple algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs.
  • Combinatorial Theory Seminar
14 May 2013
14:30
Maria Chudnovsky
Abstract
Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention, and only a few cases of that problem remain open for k-coloring when k>=4. However, little is known for 3-coloring. Recently we have settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 6-edge paths can be done in polynomial time. In this talk we will discuss some of the ideas of the algorithm. This is joint work with Peter Maceli and Mingxian Zhong.
  • Combinatorial Theory Seminar
7 May 2013
14:30
Joel Ouaknine
Abstract
<p>We consider two decision problems for linear recurrence sequences(LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). We show decidability of both problems for LRS of order 5 or less, and for simple LRS (i.e. whose characteristic polynomial has no repeated roots) of order 9 or less. Moreover, we show by way of hardness that extending the decidability of either problem to LRS of order 6 would entail major breakthroughs in analytic number theory, more precisely in the field of Diophantine approximation of transcendental numbers.<br />This talk is based on a recent paper, available at<br />http://www.cs.ox.ac.uk/people/joel.ouaknine/publications/positivity13abs.html<br /> joint with James Worrell and Matt Daws.</p>
  • Combinatorial Theory Seminar
23 April 2013
14:30
Robert Leese
Abstract
<p>The recently completed auction for 4G mobile spectrum was the most importantcombinatorial auction ever held in the UK. &nbsp;In general, combinatorial auctions allow bidders to place individual bids on packages of items,instead of separate bids on individual items, and this feature has theoretical advantages for bidders and sellers alike. &nbsp;The accompanying challenges of implementation have been the subject of intense work over the last few years, with the result that the advantages of combinatorial auctions can now be realised in practice on a large scale. &nbsp;Nowhere has this work been more prominent than in auctions for radio spectrum. &nbsp;The UK's 4G auction is the most recent of these and the publication by Ofcom (the UK's telecommunications regulator) of the auction's full bidding activity creates a valuable case study of combinatorial auctions in action.</p>
  • Combinatorial Theory Seminar
5 March 2013
14:30
Dan Hefetz
Abstract
We prove that if $\frac{\log^{117} n}{n} \leq p \leq 1 - n^{-1/8}$, then asymptotically almost surely the edges of $G(n,p)$ can be covered by $\lceil \Delta(G(n,p))/2 \rceil$ Hamilton cycles. This is clearly best possible and improves an approximate result of Glebov, Krivelevich and Szab\'o, which holds for $p \geq n^{-1 + \varepsilon}$. Based on joint work with Daniela Kuhn, John Lapinskas and Deryk Osthus.
  • Combinatorial Theory Seminar
26 February 2013
14:30
Oleg Pikhurko
Abstract
Razborov's flag algebras provide a formal system for operating with asymptotic inequalities between subgraph densities, allowing to do extensive "book-keeping" by a computer. This novel use of computers led to progress on many old problems of extremal combinatorics. In some cases, finer structural information can be derived from a flag algebra proof by by using the Removal Lemma or graph limits. This talk will overview this approach.
  • Combinatorial Theory Seminar

Pages