Combinatorics Seminar 2016-17
The seminars are held on Friday at 2pm-3pm |
Organisers:
|
Term 1 2016/17 - Room MS.04
| Date | Name | Title |
|---|---|---|
| 7 Oct | Felix Reidl (Aachen) | Characterising structural sparseness by neighbourhood complexity Or: If your neighbourhood is boring you probably live in a sparse region. |
| 14 Oct | David Ellis (QMUL) | Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems |
| 21 Oct | Maryam Sharifzadeh (Warwick) | Ramsey-Turan-type of extremal problems |
| 28 Oct | Ping Hu (Warwick) | Tilings in graphons |
| 4 Nov | Katherine Staden (Warwick) | The number of triangles in a graph with a given number of vertices and edges |
| 11 Nov | Alexey Pokrovskiy (ETH) | Rainbow cycles and rainbow expanders |
| 18 Nov | Agnes Backhausz (Eötvös Loránd University) | On the graph limit approach to eigenvectors of random regular graphs |
| 25 Nov | Richard Montgomery (Cambridge) | Subdivisions in C_4-free graphs |
| 2 Dec | Tim Netzer (Innsbruck) | Checking Inclusion of Polytopes and Spectrahedra |
| 9 Dec | Will Perkins (Birmingham) |
An occupancy approach to bounding graph polynomials |
Term 2 2016/17 - Room MS.04
| Date | Name | Title |
|---|---|---|
| 13 Jan | Christoph Koch (Warwick) |
Jigsaw percolation on random hypergraphs |
| 20 Jan | Mihyun Kang (TU-Graz) |
Homological connectivity of random hypergraphs |
| 27 Jan | Angelika Steger (ETH Zurich) |
Local resilience of almost spanning k-cycles in random graphs |
| 3 Feb | Tamas Makai (TU-Graz) |
Boostrap percolation on the binomial random graph G(n; p) |
| 10 Feb | Mark Jerrum (QMUL) |
Counting list H-colourings in hereditary graph classes |
| 17 Feb | Amin Coja-Oghlan (Frankfurt) |
Information-theoretic thresholds |
| 24 Feb | Peter Pach (Budapest) |
The cap set problem and the polynomial method |
| 10 Mar | Hong Liu (Warwick) | Proof of Komlos's conjecture on Hamiltonian subsets |
| 17 Mar | Matthew Fitch (Warwick) |
Rational Exponents for Hypergraph Turan Problems |
Term 3 2016/17 - Room MS.04
| Date | Name | Title |
|---|---|---|
| 28 April |
Timothy Budd (Paris-Saclay) NB: in B3.03 |
Winding of walks on the square lattice |
| 5 May | Lukasz Grabowski (Lancaster) |
Almost commuting matrices |
| 12 May | Ostap Chervak (Warwick) |
Hat games on graphs and digraphs |
| 19 May | Hao Huang (Emory) |
Degree versions of some classical results in Extremal Combinatorics |
| 26 May | Michal Przykucki (Oxford) |
On the critical density of a minor-closed class |
| 2 June | Olaf Parczyk (Frankfurt) | Embedding spanning bounded degree subgraphs in randomly perturbed graphs |
| 9 June | 10:30-15:40 in MS.05 |
One Day Birmingham-Warwick Combinatorics Meeting |
| 16 June | Adam Harper (Warwick) |
Inverse questions for the large sieve |
| 23 June | Janos Pach (EPFL) |
The translative covering conjecture |
7 Oct Felix Reidl (Aachen) Characterising structural sparseness by neighbourhood complexity
Or: If your neighbourhood is boring you probably live in a sparse region.
Structurally sparse graphs always had a special place in algorithm theory:
almost any problem becomes much more tractable if we restrict ourselves to
nice graph classes like trees, planar graphs, or graphs excluding a minor.
On the other hand, algorithms on such classes are only of limited use
in real-world settings---hardly any real-world network exhibits these stricter
notions of structural sparseness.
In this talk we will explore a notion of sparseness (so-called bounded expansion
classes introduced by Nesetril and Ossona de Mendez) that is general enough
to hold in real-world settings while still providing use with a rich algorithmic
toolkit. In particular, we will see a novel characterisation of bounded expansion
classes by 'neighbourhood complexity' that adds to the already diverse framework
of structurally sparse graphs.
14 Oct: David Ellis (QMUL) Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems
Erd\H{o}s-Ko-Rado type problems' are well-studied in extremal combinatorics; they concern the sizes of families of objects in which any two (or any $r$) of the objects in the family 'agree', or 'intersect', in some way.
If $X$ is a finite set, the '$p$-biased measure' on the power-set of $X$ is defined as follows: choose a subset $S$ of $X$ at random by including each element of $X$ independently with probability $p$. If $\mathcal{F}$ is a family of subsets of $X$, one can consider the {\em $p$-biased measure} of $\mathcal{F}$, denoted by $\mu_p(\mathcal{F})$, as a function of $p$. If $\mathcal{F}$ is closed under taking supersets, then this function is an increasing function of $p$. Seminal results of Friedgut and Friedgut-Kalai give criteria under which this function has a 'sharp threshold'. Perhaps surprisingly, a careful analysis of the behaviour of this function also yields some rather strong results in extremal combinatorics which do not explicitly mention the $p$-biased measure - in particular, in the field of Erd\H{o}s-Ko-Rado type problems. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric three-wise intersecting family of subsets of $\{1,2,\ldots,n\}$ has size $o(2^n)$, and some 'stability' results characterizing the structure of 'large' $t$-intersecting families of $k$–element subsets of $\{1,2,\ldots,n\}$. Based on joint work with (subsets of) Nathan Keller, Noam Lifschitz and Bhargav Narayanan.
21 Oct: Maryam Sharifzadeh (Warwick) Ramsey-Turan-type of extremal problems
Motivated by the fact that the extremal example for Tur\'an theorem has linear-sized independent sets, Erd\H os and S\'os initiated the so-called Ramsey-Tur\'an theory, where they studied the maximum size of an $H$-free graph $G$ with the additional condition that $\alpha(G)=o(|G|)$. During this talk, I will discuss the Ramsey-Tur\'an variation of some classical results, whose extremal graphs are close to the Tur\'an graph, including Corr\'adi-Hajnal theorem on triangle factors in graphs and Erd\H os-Rothschild problem on the number of edge-colorings with no monochromatic clique.
Joint work partly with J\'ozsef Balogh and Hong Liu, and partly with J\'ozsef Balogh and Theodore Molla.
28 Oct: Ping Hu (Warwick) Tilings in graphons
We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F be an edge gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings. As an application of our theory, we determine the asymptotically almost surely F-tiling number of inhomogeneous random graphs G(n,W). As another application, we give a strengthening of a theorem of Komlos, which gives minimum degree threshold that guarantees a prescribed lower bound on the fractional F-cover number of a graphon W.
Joint work with Jan Hladky and Diana Piguet.
4 Nov Katherine Staden (Warwick) The number of triangles in a graph with a given number of vertices and edges
The famous theorem of Tur\'an from 1940 states that every $n$-vertex graph with at least $n^2/4$ edges contains at least one triangle. Erd\H{o}s asked for a quantitative version of this statement: for every n and m, how \emph{many} triangles an must an n-vertex m-edge graph contain? This question has received a great deal of attention, and a long series of partial results culminated in an asymptotic solution by Razborov, extended to larger cliques by Nikiforov and Reiher. Currently, an exact solution is only known for a small range of edge densities, due to Lov\'asz and Simonovits. In this talk, I will discuss the history of the problem and recent work which gives an exact solution for almost the entire range of edge densities. This is joint work with Hong Liu and Oleg Pikhurko.
4 Nov: Richard Montgomery (Cambridge) Subdivisions in C_4-free graphs
Bollob\'as and Thomason, and independently Koml\'os and Szemer\'edi, showed in 1994 that any graph $G$ with average degree $d(G)$ contains a subdivision of a clique with at least $c\sqrt{d(G)}$ vertices, for some universal constant $c>0$. In 1999, Mader conjectured that $C_4$-free graphs $G$ in fact contain a subdivision of a larger clique, one with at least $c d(G)$ vertices, for some universal constant $c>0$. I will discuss a proof of this conjecture as well as a generalisation concerning $K_{s,t}$-free graphs.
This is joint work with Hong Liu.
11 Nov: Alexey Pokrovskiy (ETH) Rainbow cycles and rainbow expanders
A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. Andersen conjectured that every properly n-edge-coloured complete graph Kn has a rainbow Hamiltonian path. This seminar will be about a proof of an approximate version of this conjecture - that every properly edge-coloured Kn has a rainbow cycle of length n - O(n^{3/4}). One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured Kn formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular it has very good expansion properties.
This is joint work with Noga Alon and Benjamin Sudakov.
18 Nov: Agnes Backhausz (Eötvös Loránd University) On the graph limit approach to eigenvectors of random regular graphs
The goal of the talk is to show how the graph limit approach
can be used to understand spectral properties of large random
regular graphs. In our work, we consider eigenvectors of
random regular graphs of fixed degree. As the number of
vertices tends to infinity, as a "limit", we investigate
invariant random processes on the infinite tree that
satisfy the eigenvalue equation and that can be "modelled" on
random regular graphs. In this infinite setting, based on
certain entropy inequalities, we could prove that (under
appropriate conditions) all these processes are Gaussian.
As a consequence, we could prove that the distribution of
delocalized eigenvectors of finite random regular graphs
is close to the Gaussian distribution. Joint work with Balazs
Szegedy.
2 Dec: Tim Netzer (Innsbruck) Checking Inclusion of Polytopes and Spectrahedra
The question whether one polytope is contained in another arises in interesting applications. Its computational complexity depends on the type of the input, and reaches from polynomial time to co-NP-hard. Spectrahedra are generalizations of polyhedra, and appear as feasible sets in semidefinite programming. In many applications, one or both of the given sets are spectrahedra, and inclusion testing becomes even more complicated, even at a conceptual level. There are certain relaxations of the problem, that work well in practice. After introducing the necessary background, we show that these relaxations are only reliable for simplices, and we derive some quantitative error bounds in the general case. The results use methods from operator theory, and some nice elementary constructions.
9 Dec: Will Perkins (Birmingham) An occupancy approach to bounding graph polynomials
I will present a new method for proving tight bounds on graph polynomials and on the number of independent sets, matchings, and colorings in regular graphs. The method is based on optimizing various observables in relevant probabilistic models from statistical physics (e.g., the hard-core, monomer-dimer, and Potts models) via linear programming relaxations. No previous knowledge of statistical physics is needed for the talk, and I will present many related open problems. Based on joint work with E. Davies, M. Jenssen, and B. Roberts.
13 Jan: Christoph Koch (Warwick) Jigsaw percolation on random hypergraphs
Jigsaw percolation was introduced by Brummit, Chatterjee, Dey, and Sivakoff as a model for interactions within a social network. It was inspired by the idea of collectively solving a puzzle. The premise is that each individual of a group of people has a piece of a puzzle all of which must be combined in a certain way to solve the puzzle. The compatibility of different puzzle pieces and the information which pairs of people meet are stored in two graphs (on a common vertex set), the puzzle graph and the people graph. Bollobás, Riordan, Slivken, and Smith studied the process when both graphs are given by independent binomial random graphs. More abstractly the process can be seen as a notion of simultaneous connectedness of a pair of (random) graphs. We transfer the process to hypergraphs in the context of high-order connectedness. We provide the asymptotic order of the critical threshold probability for percolation when both hypergraphs are chosen binomially at random, extending the result of Bollobás, Riordan, Slivken, and Smith. The evolution of the process is closely related to the presence of traversable triples in the pair of random hypergraphs.
This is joint work with Béla Bollobás, Oliver Cooley, and Mihyun Kang.
20 Jan: Mihyun Kang (TU-Graz) Homological connectivity of random hypergraphs
We consider 2-dimensional simplicial complexes that are generated from the binomial random 3-uniform hypergraph by taking the downward-closure. We determine when this simplicial complex is homologically connected, meaning that its zero-th and first homology groups with coefficients in $\mathbb{F}_2$ vanish. Although this is not intrinsically a monotone property, we show that it nevertheless has a single sharp threshold, and indeed prove a hitting time result relating the connectedness to the disappearance of the last minimal obstruction.
(Joint work with Oliver Cooley, Penny Haxell, and Philipp Spr\"ussel)
27 Jan: Angelika Steger (ETH Zurich) Local resilience of almost spanning k-cycles in random graphs
The famous Posa-Seymour conjecture states that for any k ≥ 2, a graph G = (V, E) with minimum degree kn/(k+1) contains the k-th power of a Hamilton cycle. The conjecture was confirmed a couple of decades later by Komlos, Sarközy, Szemeredi for n large enough. Here we extend this result to a sparse setting. We show that for all k ≥ 2 and ε,α > 0, if p ≥ C(logn/n)1/k then any subgraph of a random graph Gn,p with minimum degree at least (k/(k + 1) + α)np, contains the k-th power of a cycle on at least (1 − ε)n vertices, improving upon the recent results of Noever and Steger for k = 2, as well as Allen, Böttcher, Ehrenmüller and Taraz for k ≥ 3.
3 Feb: Tamas Makai (TU-Graz) Boostrap percolation on the binomial random graph G(n; p)
Bootstrap percolation on a graph, with infection threshold a positive integer r, is an infection process which starts out from a set of initially infected vertices and in each further step every vertex with at least r infected neighbours becomes infected. The process stops once no further vertices can become infected.
We consider bootstrap percolation on the binomial random graph G(n; p), when the set of initially infected vertices has size a, which was investigated among others by Janson, Luczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of infected vertices at the end of the process.
This is joint work with Mihyun Kang.
10 Feb: Mark Jerrum (QMUL) Counting list H-colourings in hereditary graph classes
Suppose H is a fixed graph. H-colourings of a graph G (a.k.a. homomorphisms from G
to H) generalise familiar proper vertex colourings of G. More than 15 years ago, Dyer
and Greenhill considered the computational complexity of counting H-colourings,
and demonstrated a dichotomy, in terms of the graph H, between polynomial time
and #P-complete.
That result was for exact counting, and, even now, there is only a partial complexity
classification for approximate counting. However, the classification problem becomes
tractable if we look instead at _list_ H-colourings. In this talk, I’ll present
a classification (in fact a trichotomy) for the problem of approximately counting
list H-colourings of a graph. It turns out that some interesting hereditary graph
classes come into play in describing and proving the trichotomy result.
This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford).
17 Feb: Amin Coja-Oghlan (Frankfurt) Information-theoretic thresholds
In many discrete stuctures such as random error-correcting codes or random graph problems there occurs an information-theoretic phase transition. For example, for "noise levels" above a certain information-theoretic threshold decoding is impossible. In this talk I present a method for proving certain physics predictions on such information-theoretic phase transitions. Among other things this leads to proofs of certain conjectures on low-density generator matrix codes and the random graph coloring problem.
24 Feb: Peter Pach (Budapest) The cap set problem and the polynomial method
The cap set problem asks for the largest possible size of a subset of $\mathbb{F}_3^n$ free of (nonconstant) three-term arithmetic progressions. The best bound prior to 2016 was given by Bateman and Katz, who proved that this size is at most $O(3^n/n^{1+\varepsilon})$ with an absolute constant $\varepsilon>0$. Last year a much better bound, namely $o(2.756^n)$, was obtained with the help of a new variant of the polynomial method. I will talk about this method -- which was first applied for the analogous question about the largest possible size of a progression-free subset of $\mathbb{Z}_4^n$ -- and mention some further applications.
10 Mar: Hong Liu (Warwick) Proof of Komlos's conjecture on Hamiltonian subsets
Komlos conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle.
We prove this conjecture when $d$ is sufficiently large.
In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify.
This is joint work with Jaehoon Kim, Maryam Sharifzadeh and Katherine Staden.
17 Mar: Matthew Fitch (Warwick) Rational Exponents for Hypergraph Turan Problems
Given a family of k-hypergraphs F, ex(n,F) is the maximum number of edges a k-hypergraph can have, knowing that said hypergraph has n vertices but contains no copy of any hypergraph from F as a subgraph. I will discuss a result I have proved, which says for any rational r between 0 and k-1, there exists some finite family F of k-hypergraphs for which ex(n,F) is of order n^(k-r).
28 April: Timothy Budd (Paris-Saclay) Winding of walks on the square lattice
I'll discuss the combinatorics of simple walks on Z^2 when keeping track of the winding angle around the origin. This problem turns out to be closely related to the combinatorics of planar maps coupled to an O(n) loop model, and the enumeration of the latter has been solved in the literature. I'll explain the relation and present several applications, including a new way to count Gessel-type walks in the quadrant (OEIS A135404).
5 May: Lukasz Grabowski (Lancaster) Almost commuting matrices
I will report on a joint work with Gabor Elek about the
following problem: Let A_i and B_i, i=1,2,3,..., be n_i by n_i matrices
over complex numbers (typically n_i increases with i). Let us
assume that the rank of A_iB_i - B_iA_i is small relative to n_i, i.e.
that A_i and B_i almost commute. Is it true that we can find matrices S_i
and T_i which commute and such that the ranks of A_i-S_i and B_i -T_i
are small relative to n_i ? In other words, if A_i and B_i almost
commute, is it true that A_i and B_i are close to commuting matices?
I will give some motivation and fairly complete proofs that the answer
is yes in some important special cases, in particular when A_i and B_i
arise from a commutative algebra K by restricting generators
of K to larger and larger subspaces of K.
12 May: Ostap Chervak (Warwick) Hat games on graphs and digraphs
In this talk we will investigate a variant of the so-called Hat problems. A set of players called "gnomes" are given a hat coloured in one of $k$ different colours. Each gnome sees the colour of hat of it's neighbours in a visibility graph (or digraph). Later they simultaneously announce their guess for a colour of their own hat, if at least one gnome is correct they win the game, if neither are correct they lose. In "Minimal predictors in hat problems", C.Hardin and A.Taylor asked if there exists a visibility graph without a $k$-clique with a winning strategy for gnomes and, in particular, if there exist a winning strategy on a bipartite graph. In the talk we will prove that such a strategy in a polynomial-size bipartite graph indeed exists. Moreover there exists a linear-size graph without a $k$-clique and a winning strategy. To resolve another problem we will construct an infinite family of different minimal visibility digraphs with a strategy for $k$ colours for any $k>3$.
19 May: Hao Huang (Emory) Degree versions of some classical results in Extremal Combinatorics
In this talk, I will describe how to use algebraic methods to prove the following degree version of the celebrated Erd\H os-Ko-Rado theorem: given $n>2k$, every intersecting $k$-uniform hypergraph $H$ on $n$ vertices must contain a vertex that lies on at most $\binom{n-2}{k-2}$ edges. A degree version of Hilton-Milner theorem was also proved for sufficiently large $n$.
The talk is based on joint works with Peter Frankl, Jie Han and Yi Zhao.
26 May: Michal Przykucki (Oxford) On the critical density of a minor-closed class
Given a minor-closed class ${\mathcal{A}}$ of graphs, let $\beta_{\cA}$
denote the supremum over all graphs in $\cA$ of the ratio of edges to
vertices. We investigate the set $B$ of all such values $\beta_{\cA}$,
taking further the project begun by Eppstein. Amongst other results, we
determine the small values in $B$ (those up to 2); we show that $B$ is
'asymptotically dense'; and we answer some questions posed by Eppstein.
Joint work with Colin McDiarmid.
2 June: Olaf Parczyk (Frankfurt) Embedding spanning bounded degree subgraphs in randomly perturbed graphs
We study the model of randomly perturbed dense graphs, which is the union of any graph $G_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $G(n,p)$. For $p=\omega(n^{-2/(\Delta+1)})$, we show that $G_\alpha \cup G(n,p)$ contains any single spanning graph with maximum degree $\Delta$. As in previous results concerning this model, the bound for $p$ we use is lower by a $\log$-term in comparison to the bound known to be needed to find the same subgraph in $G(n,p)$ alone.
Joint work with Julia Böttcher, Richard Montgomery and Yury Person.
16 June: Adam Harper (Warwick) Inverse questions for the large sieve
Suppose $A$ is a subset of the natural numbers less than $N$, and $A$ occupies at most $(p+1)/2$ residue classes modulo all odd primes $p$. Then the large sieve inequality implies that $|A| \ll \sqrt{N}$, which is sharp because of the example where $A$ is a set of squares. The ''inverse conjecture for the large sieve'' proposes that the only examples of sets $A$ where the $\sqrt{N}$ bound is sharp are sets that ''look a lot like the squares''.
I will try to explain some results towards the inverse conjecture, that give (at least) a small power saving over $\sqrt{N}$ under extra assumptions on the structure of the residue classes occupied by $A$. This is joint work with Ben Green.
23 June: Janos Pach (EPFL) The translative covering conjecture
A slab (or plank) of width $w$ is a part of the $d$-dimensional space that lies between two parallel hyperplanes at distance $w$ from each other. According to the translative covering conjecture, any slabs $S_1, S_2,\ldots$ whose total width is divergent have suitable translates that altogether cover $\mathbb{R}^d$. We show that this statement is true if the widths of the slabs, $w_1, w_2,\ldots$, satisfy the slightly stronger condition $\limsup_{n\rightarrow\infty}\frac{w_1+w_2+\ldots+w_n}{\log(1/w_n)}>0$. This can be regarded as a converse of Bang's theorem, better known as Tarski's plank problem.
We apply our results to a problem on simultaneous approximation of classes $F$ of real functions. We say that a sequence of positive numbers $x_1\le x_2\le\ldots$ controls all elements of $F$ if there exist $y_1, y_2,\ldots\in\mathbb{R}$ such that for every $f\in F$, there exists an index $i$ with $|p(x_i)-y_i|\leq 1.$ We find necessary and sufficient conditions for a sequence to have this property for various function classes. Joint work with A. Kupavskii and G. Tardos.