Combinatorial Theory Seminar

Random geometric graphs have been well studied over the last 50 years or so. These are graphs that

are formed between points randomly allocated on a Euclidean space and any two of them are joined if

they are close enough. However, all this theory has been developed when the underlying space is

equipped with the Euclidean metric. But, what if the underlying space is curved?

The aim of this talk is to initiate the study of such random graphs and lead to the development of

their theory. Our focus will be on the case where the underlying space is a hyperbolic space. We

will discuss some typical structural features of these random graphs as well as some applications,

related to their potential as a model for networks that emerge in social life or in biological

sciences.

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)

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.

This game has a chequered history with several false `winning strategies' before Besicovitch finally gave a genuine winning strategy.

We ask the surprising question: can both players win?

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.

Joint work with Oliver Riordan.

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.

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ő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ő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.

We shall discuss how the algebra norm can be used to identify structure in groups. No prior familiarity with the area will be assumed.

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.

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).

Hex was discovered independently by Piet Hein in Copenhagen in 1942 and byJohn Nash in Princeton in 1948.  The game is interesting because its rules are very simple, yet it is not known how to play best possible.  For example, a winning first move for the first player (who does have  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:  How to play Reverse Hex (joint work with Ryan Hayward and Phillip Henderson).