Forthcoming events in this series
Let $A$ be a finite set in some ambient group. We say that $A$ is a $K$-approximate group if $A$ is symmetric and if the set $A.A$ (the set of all $xy$, where $x$, $y$ lie in $A$) is covered by $K$ translates of $A$. I will illustrate this notion by example, and will go on to discuss progress on the "rough classification" of approximate groups in various settings: abelian groups, nilpotent groups and matrix groups of fixed dimension. Joint work with E. Breuillard.
The Gilbert model of a random geometric graph is the following: place points at random in a (two-dimensional) square box and join two if they are within distance $r$ of each other. For any standard graph property (e.g. connectedness) we can ask whether the graph is likely to have this property. If the property is monotone we can view the model as a process where we place our points and then increase $r$ until the property appears. In this talk we consider the property that the graph has a Hamilton cycle. It is obvious that a necessary condition for the existence of a Hamilton cycle is that the graph be 2-connected. We prove that, for asymptotically almost all collections of points, this is a sufficient condition: that is, the smallest $r$ for which the graph has a Hamilton cycle is exactly the smallest $r$ for which the graph is 2-connected. This work is joint work with Jozsef Balogh and B\'ela Bollob\'as
There are many theorems concerning cycles in graphs for which it is natural to seek analogous results for directed graphs. I will survey
recent progress on certain questions of this type. New results include
(i) a solution to a question of Thomassen on an analogue of Dirac’s theorem
for oriented graphs,
(ii) a theorem on packing cyclic triangles in tournaments that “almost” answers a question of Cuckler and Yuster, and
(iii) a bound for the smallest feedback arc set in a digraph with no short directed cycles, which is optimal up to a constant factor and extends a result of Chudnovsky, Seymour and Sullivan.
These are joint work respectively with (i) Kuhn and Osthus, (ii) Sudakov, and (iii) Fox and Sudakov.
A graph homomorphism is a mapping of vertices which takes edges to edges. The endomorphisms of a graph (homomorphisms to itself) form a submonoid of he full transformation monoid on the vertex set. In the other direction, there is a construction of a graph from a transformation monoid, which will be described in the talk. Composing these maps gives closure operators on graphs and on monoids which have some interesting properties. There are also connections with finite automata and permutation groups.
The conjecture was made by Pemantle that a forest chosen uniformly at random from all forests in any finite graph G has the edge-negative association property. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices and derive related results for random trees.
Consider the Erdos-Renyi random graph $G(n,p)$ inside the critical window, so that $p = n^{-1} + \lambda n^{-4/3}$ for some real \lambda. In
this regime, the largest components are of size $n^{2/3}$ and have finite surpluses (where the surplus of a component is the number of edges more than a tree that it has). Using a bijective correspondence between graphs and certain "marked random walks", we are able to give a (surprisingly simple) metric space description of the scaling limit of the ordered sequence of components, where edges in the original graph are re-scaled by $n^{-1/3}$. A limit component, given its size and surplus, is obtained by taking a continuum random tree (which is not a Brownian continuum random tree, but one whose distribution has been exponentially tilted) and making certain natural vertex identifications, which correspond to the surplus edges. This gives a metric space in which distances are calculated using paths in the original tree and the "shortcuts" induced by the vertex identifications. The limit of the whole critical random graph is then a collection of such
metric spaces. The convergence holds in a sufficiently strong sense (an appropriate version of the Gromov-Hausdorff distance) that we are able to deduce the convergence in distribution of the diameter of $G(n,p)$, re-scaled by $n^{-1/3}$, to a non-degenerate random variable, for $p$ in the critical window.
This is joint work (in progress!) with Louigi Addario-Berry (Universite de Montreal) and Nicolas Broutin (INRIA Rocquencourt).
We consider a natural generalisation of the independence and chromatic numbers and study their behaviour in Erdos-Renyi random graphs. The t-dependence number of a graph G is the size of the largest subset of the vertices of G whose induced subgraph has maximum degree at most t. The t-improper chromatic number of G is the smallest number of parts needed in a partition of the vertex set of G such that each part induces a subgraph of maximum degree at most t. Clearly, when t = 0, these parameters are, respectively, the independence and chromatic numbers of G. For dense random graphs, we determine the asymptotic ehaviour of these parameters over the range of choices for the growth of t as a function of the number of vertices.
This is joint work with Nikolaos Fountoulakis and Colin McDiarmid.
Random partial orders and random linear extensions
Several interesting models of random partial orders can be described via a
process that builds the partial order one step at a time, at each point
adding a new maximal element. This process therefore generates a linear
extension of the partial order in tandem with the partial order itself. A
natural condition to demand of such processes is that, if we condition on
the occurrence of some finite partial order after a given number of steps,
then each linear extension of that partial order is equally likely. This
condition is called "order-invariance".
The class of order-invariant processes includes processes generating a
random infinite partial order, as well as those that amount to taking a
random linear extension of a fixed infinite poset.
Our goal is to study order-invariant processes in general. In this talk, I
shall explain some of the problems that need to be resolved, and discuss
some of the combinatorial problems that arise.
(joint work with Malwina Luczak)
In the first part of the talk we will introduce the notion of property testing and briefly discuss some results in testing graph properties in the framework of property testing.
Then, we will discuss a recent result about testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: \newline an $a$-expander is a graph $G = (V,E)$ in which every subset $U$ of $V$ of at most $|V|/2$ vertices has a neighborhood of size at least $a|U|$. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately $O(n^{1/2})$.
We design a property testing algorithm that accepts every $a$-expander with probability at least 2/3 and rejects every graph that is $\epsilon$-far from an $a^*$-expander with probability at least 2/3, where $a^* = O(a^2/(d^2 log(n/\epsilon)))$, $d$ is the maximum degree of the graphs, and a graph is called $\epsilon$-far from an $a^*$-expander if one has to modify (add or delete) at least $\epsilon d n$ of its edges to obtain an $a^*$-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is $O(d^2 n^{1/2} log(n/\epsilon)/(a^2 \epsilon^3))$.
This is a joint work with Christian Sohler.
The homological Hall lemma is a topological tool that has recently been used to derive Hall type theorems for systems of disjoint representatives in hypergraphs.
After outlining the general method, we.ll describe one such theorem in some detail. The main ingredients in the proof are:
1) A relation between the spectral gap of a graph and the topological connectivity of its flag complex.
2) A new graph domination parameter defined via certain vector representations of the graph.
Joint work with R. Aharoni and E. Berger
How can one guarantee the presence of an oriented four-cycle in an oriented graph G? We shall see, that one way in which this can be done, is to demand that G contains no large `biased. subgraphs; where a `biased. subgraph simply means a subgraph whose orientation exhibits a strong bias in one direction.
Furthermore, we discuss the concept of biased subgraphs from another standpoint, asking: how can an oriented graph best avoid containing large biased subgraphs? Do random oriented graphs give the best examples? The talk is partially based on joint work with Omid Amini and Florian Huc.
Linear operators preserving non-vanishing properties are an important
tool in e.g. combinatorics, the Lee-Yang program on phase transitions, complex analysis, matrix theory. We characterize all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing when the variables are in prescribed open circular domains, which solves the higher dimensional counterpart of a long-standing classification problem going back to P\'olya-Schur. This also leads to a self-contained theory of multivariate stable polynomials and a natural framework for dealing with Lee-Yang and Heilmann-Lieb type problems in a uniform manner. The talk is based on joint work with Petter Brändén.
For any simple graph G and any positive integer lambda, let
P(G,lambda) denote the number of mappings f from V(G) to
{1,2,..,lambda} such that f(u) not= f(v) for every two adjacent
vertices u and v in G. It can be shown that
P(G,lambda) = \sum_{A \subseteq E} (-1)^{|A|} lambda^{c(A)}
where E is the edge set of G and c(A) is the number of components
of the spanning subgraph of G with edge set A. Hence P(G,lambda)
is really a polynomial of lambda. Many results on the chromatic
polynomial of a graph have been discovered since it was introduced
by Birkhoff in 1912. However, there are still many unsolved
problems and this talk will introduce the progress of some
problems and also some new problems proposed recently.
We call a family of permutations A in Sn 'intersecting' if any two permutations in A agree in at least one position. Deza and Frankl observed that an intersecting family of permutations has size at most (n-1)!; Cameron and Ku proved that equality is attained only by families of the form {σ in Sn: σ(i)=j} for i, j in [n].
We will sketch a proof of the following `stability' result: an intersecting family of permutations which has size at least (1-1/e + o(1))(n-1)! must be contained in {σ in Sn: σ(i)=j} for some i,j in [n]. This proves a conjecture of Cameron and Ku.
In order to tackle this we first use some representation theory and an eigenvalue argument to prove a conjecture of Leader concerning cross-intersecting families of permutations: if n >= 4 and A,B is a pair of cross-intersecting families in Sn, then |A||B|