# Past 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
19 February 2013
14:30
Karen Johannson
Abstract
While usual percolation concerns the study of the connected components of random subgraphs of an infinite graph, bootstrap percolation is a type of cellular automaton, acting on the vertices of a graph which are in one of two states: healthy' or infected'. For any positive integer $r$, the $r$-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least $r$ infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected. As it is often difficult to determine precisely which configurations of initially infected vertices percolate, one often considers a random case, with each vertex infected independently with a fixed probability $p$. For an infinite graph, of interest are the values of $p$ for which the probability of percolation is positive. I will give some of the history of this problem for regular trees and present some new results for bootstrap percolation on certain classes of randomly generated trees: Galton--Watson trees.
• Combinatorial Theory Seminar
12 February 2013
14:30
Veselin Jungic
Abstract
I will describe how a search for the answer to an old question about the existence of monotone arithmetic progressions in permutations of positive integers led to the study of infinite words with bounded additive complexity. The additive complexity of a word on a finite subset of integers is defined as the function that, for a positive integer $n$, counts the maximum number of factors of length $n$, no two of which have the same sum.
• Combinatorial Theory Seminar
5 February 2013
14:30
David Ellis
Abstract
Results of Bourgain and Kindler-Safra state that if $f$ is a Boolean function on $\{0,1\}^n$, and the Fourier transform of $f$ is highly concentrated on low frequencies, then $f$ must be close to a ‘junta’ (a function depending upon a small number of coordinates). This phenomenon is known as ‘Fourier stability’, and has several interesting consequences in combinatorics, theoretical computer science and social choice theory. We will describe some of these, before turning to the analogous question for Boolean functions on the symmetric group. Here, genuine stability does not occur; it is replaced by a weaker phenomenon, which we call ‘quasi-stability’. We use our 'quasi-stability' result to prove an isoperimetric inequality for $S_n$ which is sharp for sets of size $(n-t)!$, when $n$ is large. Several open questions remain. Joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Weizmann Institute).
• Combinatorial Theory Seminar
29 January 2013
14:30
Mireille Bousquet-Melou
Abstract
<p>A self-avoiding walk on a lattice is a walk that never visits the same vertex twice.&nbsp; Self-avoiding walks (SAW) have attracted interest for decades, first in statistical physics, where they are considered as polymer models, and then in combinatorics and in probability theory (the first mathematical contributions are probably due to John Hammersley, from Oxford, in the early sixties). However, their properties remain poorly understood in low dimension, despite the existence of remarkable conjectures. <br /><br />About two years ago, Duminil-Copin and Smirnov proved an "old" and remarkable conjecture of Nienhuis (1982), according to which the number of SAWs of length n on the honeycomb (hexagonal) lattice grows like mu^n, with mu=sqrt(2 +sqrt(2)). <br /><br />This beautiful result has woken up the hope to prove other simple looking conjectures involving these objects. I will thus present the proof of a younger conjecture (1995) by Batchelor and Yung, which deals with SAWs confined to a half-plane and interacting with its boundary.<br /><br />(joint work with N. Beaton, J. de Gier, H. Duminil-Copin and A. Guttmann)<br /><br /></p>
• Combinatorial Theory Seminar
22 January 2013
14:30
Eoin Long
Abstract
Let $Q_n$ denote the graph of the $n$-dimensional cube with vertex set $\{0, 1\}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$. How long a path can we guarantee to find in $G$? My aim in this talk is to show that $G$ must contain an exponentially long path. In fact, if $G$ has minimum degree at least $d$ then $G$ must contain a path of length $2^d − 1$. Note that this bound is tight, as shown by a $d$-dimensional subcube of $Q^n$. I hope to give an overview of the proof of this result and to discuss some generalisations.
• Combinatorial Theory Seminar