Past Combinatorial Theory Seminar

21 February 2012
14:30
Mark Walters
Abstract
<p>Rado introduced the following `lion and man' game in the 1930's: two players (the lion and the man) are in the closed unit disc and they can run at the same speed. The lion would like to catch the man and the man would like to avoid being captured.<br /><br />This game has a chequered history with several false `winning strategies' before Besicovitch finally gave a genuine winning strategy.<br /><br />We ask the surprising question: can both players win?</p>
  • Combinatorial Theory Seminar
14 February 2012
14:30
Tobias Mueller, Amsterdam
Abstract
A dot product representation of a graph assigns to each vertex $s$ a vector $v(s)$ in ${\bf R}^k$ in such a way that $v(s)^T v(t)$ is greater than $1$ if and only $st$ is an edge. Similarly, in a distance representation $|v(s)-v(t)|$ is less than $1$ if and only if $st$ is an edge. I will discuss the solution of some open problems by Spinrad, Breu and Kirkpatrick and others on these and related geometric representations of graphs. The proofs make use of a connection to oriented pseudoline arrangements. (Joint work with Colin McDiarmid and Ross Kang)
  • Combinatorial Theory Seminar
7 February 2012
14:30
Imre Leader (Cambridge)
Abstract
If $A$ is a set of $n$ positive integers, how small can the set $\{ x/(x,y) : x,y \in A \}$ be? Here, as usual, $(x,y)$ denotes the highest common factor of $x$ and $y$. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set $A$ of $n$ points in the integer grid ${\bf Z}^d$, how small can $(A-A)^+$, the projection of the difference set of $A$ onto the positive orthant, be? Freiman and Lev gave an example to show that (in any dimension) the size can be as small as $n^{2/3}$ (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least $n^{2/3}$, and they asked if this holds in any dimension. After some background material, the talk will focus on recent developments. Joint work with B\'ela Bollob\'as.
  • Combinatorial Theory Seminar
31 January 2012
14:30
Lutz Warnke
Abstract
<p>In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such `local' modifications of the Erdös-Rényi random graph processes has received considerable attention during the last decade, so far only rather `simple' rules are well-understood. Indeed, the main focus has been on bounded size rules (where all component sizes larger than some constant B are treated the same way), and for more complex rules hardly any rigorous results are known. In this talk we will discuss a new approach that applies to many involved Achlioptas processes: it allows us to prove that certain key statistics are tightly concentrated during the early evolution of e.g. the sum and product rule.</p> <p>Joint work with Oliver Riordan.</p>
  • Combinatorial Theory Seminar
24 January 2012
14:30
Mihyun Kang (TU Graz)
Abstract
<p>The phase transition deals with sudden global changes and is observed in many fundamental random discrete structures arising from statistical physics, mathematics and theoretical computer science, for example, Potts models, random graphs and random $k$-SAT. The phase transition in random graphs refers to the phenomenon that there is a critical edge density, to which adding a small amount results in a drastic change of the size and structure of the largest component. In the Erd&#337;s--R\'enyi random graph process, which begins with an empty graph on $n$ vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches $n/2$ and a giant component emerges. Since this seminal work of Erd&#337;s and R\'enyi, various random graph processes have been introduced and studied. In this talk we will discuss new approaches to study the size and structure of components near the critical point of random graph processes: key techniques are the classical ordinary differential equations method, a quasi-linear partial differential equation that tracks key statistics of the process, and singularity analysis.</p>
  • Combinatorial Theory Seminar
15 November 2011
14:30
Wojciech Samotij
Abstract
We say that a hypergraph is \emph{stable} if each sufficiently large subset of its vertices either spans many hyperedges or is very structured. Hypergraphs that arise naturally in many classical settings posses the above property. For example, the famous stability theorem of Erdos and Simonovits and the triangle removal lemma of Ruzsa and Szemeredi imply that the hypergraph on the vertex set $E(K_n)$ whose hyperedges are the edge sets of all triangles in $K_n$ is stable. In the talk, we will present the following general theorem: If $(H_n)_n$ is a sequence of stable hypergraphs satisfying certain technical conditions, then a typical (i.e., uniform random) $m$-element independent set of $H_n$ is very structured, provided that $m$ is sufficiently large. The above abstract theorem has many interesting corollaries, some of which we will discuss. Among other things, it implies sharp bounds on the number of sum-free sets in a large class of finite Abelian groups and gives an alternate proof of Szemeredi’s theorem on arithmetic progressions in random subsets of integers. Joint work with Noga Alon, Jozsef Balogh, and Robert Morris.
  • Combinatorial Theory Seminar
8 November 2011
14:30
Diana Piguet
Abstract
An embedding of a graph H in a graph G is an injective mapping of the vertices of H to the vertices of G such that edges of H are mapped to edges of G. Embedding problems have been extensively studied. A very powerful tool in this area is Szemeredi's Regularity Temma. It approximates the host graph G by a quasirandom graph which inherits many of the properties of G. Unfortunately the direct use of Szemeredi's Regularity Lemma is useless if the host graph G is sparse. During the talk I shall expose a technique to deal with embedding trees in sparse graphs. This technique has been developed by Ajtai, Komlos,Simonovits and Szemeredi to solve the Erdos-Sos conjecture. Presently the author together with Hladky, Komlos, Simonovits, Stein and Szemeredi apply this method to solve the related conjecture of Loebl, Komlos and Sos (approximate version).
  • Combinatorial Theory Seminar
25 October 2011
14:30
Abstract
<p>Hex was discovered independently by Piet Hein in Copenhagen in 1942 and byJohn Nash in Princeton in 1948. &nbsp;The game is interesting because its rules are very simple, yet it is not known how to play best possible. &nbsp;For example, a winning first move for the first player (who does have &nbsp;a winning strategy) is still unknown. The talk will tell the history of the game and give simple proofs for basic results about it. Also the reverse game of HEX,sometimes called REX, will be discussed. New results about REX are under publication in Discrete Mathematics in a paper: &nbsp;How to play Reverse Hex (joint work with Ryan Hayward and Phillip Henderson).</p>
  • Combinatorial Theory Seminar
18 October 2011
16:00
Professor Geoff Whittle
Abstract
<p>&nbsp;</p><div><div>A canonical way to obtain a matroid is from a finite set of vectors in a vector space over a field F. A matroid that can be obtained in such a way is said to be representable over F. It is clear that when Whitney first defined matroids he had matroids representable over the reals as his standard model, but for a variety of reasons most attention has focussed on matroids representable over finite fields.</div><div></div><div></div><div></div><div> There is increasing evidence that the class of matroids representable over a fixed finite field is well behaved with strong general theorems holding. Essentially none of these theorems hold if F is infnite. Indeed matroids representable over the real-- the natural matroids for our geometric intuition -- turn out to be a mysterious class indeed. In the talk I will discuss this striking contrast in behaviour.</div></div><p>&nbsp;</p>
  • Combinatorial Theory Seminar

Pages