Past Events

 

 

Past Combinatorics Seminars

 

2016/17

On the number of cycles covering distinct vertex sets.

Abstract not available

Subdivisions in C_4-free graphs.

Abstract not available

Scaling limits of critical random trees and graphs.

Abstract not available

Hereditary quasirandomness without regularity

Abstract not available

Computability and Finite Forcibility of Graph Limits

Abstract not available

Random walk on dynamical percolation

Abstract not available

Finite reflection groups and graph norms

Abstract not available

Forbidden vector-valued intersections

Abstract not available

Large deviations in random graphs

Abstract not available

Counting extensions in random graphs

Abstract not available

Minimum number of edges that occur in odd cycles

Abstract not available

Generalised Colouring Numbers of Graphs

The well-known colouring number of a graph is one more than the smallest k for which there exists an ordering of the vertices in which each vertex has at most k neighbours that come earlier in the ordering. The colouring number is a trivial upper bound for the chromatic number of the graph. But it also contains structural information of the graph, for instance regarding the edge density of any subgraph. When instead of neighbours we count vertices that come earlier in the ordering and can be reached by a path of length at most r, we get the generalised colouring numbers. Depending on conditions for the internal vertices of such paths (disjoint or not; where they can appear in the ordering), we actually can define different types of those generalised colouring numbers. Variants of these generalised colouring numbers were mostly introduced to study specific types of graph colourings. In the last couple of years it has been realised that the generalised colouring numbers are closely related to many structural properties of graphs (such as tree-depth and tree-width). In this talk we give an overview of some aspects of the generalised colouring numbers: mutual relations, relations with structural properties of graphs, relations with specific types of colouring, and bounds for these numbers for for specific classes of graphs (such as planar graphs).

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.

Galton-Watson trees and Apollonian networks

In the analysis of critical Galton-Watson trees conditional on their sizes, two complementary approaches have proved fruitful over the last decades. First, the so-called size-biased tree allows the study of local properties such as node degrees. Second, the global scaling limit, the Continuum Random tree, provides access to the study of average or extreme node depths. In this talk, I will discuss the approximation of the tree by subtrees with bounded node degrees. Here, the so-called “heavy subtrees” play an important role. An application will be given in terms of uniform Apollonian networks.

The talk is based on joint work with Luc Devroye (McGill, Montreal) and Cecilia Holmgren (Uppsala).

Designs beyond quasirandomness

In a recent breakthrough, Peter Keevash proved the Existence conjecture for combinatorial designs, which has its roots in the 19th century. In joint work with Daniela Kühn, Allan Lo and Deryk Osthus, we gave a new proof of this result, based on the method of iterative absorption. In fact, `regularity boosting ’ allows us to extend our main decomposition result beyond the quasirandom setting and thus to generalise the results of Keevash. In particular, we obtain a resilience version and a minimum degree version. In this talk, we will present our new results within a brief outline of the history of the Existence conjecture and provide an overview of the proof.

Mathematics Colloquium: Containers in Combinatorics

Abstract not available

Branchings in Digraphs: Structural Results and Algorithms

An out-tree (in-tree) is an oriented tree in which only one vertex of in-degree (out-degree) zero. A leaf in an out-tree is a vertex on out-degree zero. An out-branching (in-branching) in a digraph D is a spanning subgraph of D which is an out-tree (in-tree). We will overview some structural and algorithmic results obtained for out- and in-branching in directed graphs. We will mainly focus on out-branchings with maximum and minimum number of leaves and on minimizing intersection between an out-branching and in-branching in a digraph. In particular, we will discuss in some detail recent solutions by Felix Reidl, Magnus Wahlstrom and the speaker of two open parameterized problems by Bang-Jensen et al. where one is to decide whether a digraph has an out-branching and in-branching which differ in at least k arcs.

The Local Cut Lemma

The entropy compression method is an algorithmic technique that was invented by Moser and Tardos in order to give an effective proof of the Lovasz Local Lemma (the LLL for short). It turns out that avoiding the LLL and applying the entropy compression method directly can lead to improvements, sometimes significant, in combinatorial bounds. The Local Cut Lemma (the LCL for short) is a generalization of the LLL that implies these new combinatorial results. It hides technical details of the method and thus makes the arguments simpler and shorter. Although the LCL was inspired by the entropy compression method, it has a direct probabilistic proof (similar to the classical proof of the LLL ); in particular, not only does the LCL show that a certain probability is positive, but it also provides an explicit lower bound for that probability. In this talk, I will present the LCL and explain how to use it.

Monochromatic Cycle Partitioning

The problem of partitioning a graph into few monochromatic cycles, first formulated explicitly in the beginning of the 80s, has lately received a fair amount of attention. This talk is meant to give an introduction to the field. I will present some of the central problems, the ideas that lead to recent advances and a couple of interesting open questions.

Rigid combinatorial objects

Random models of many combinatorial objects are difficult to analyse because their components exhibit dependence between each other (although, morally, only to a very small extent). Examples include random regular graphs (the event that two vertices are adjacent affects all other adjacencies), random Latin squares (the presence of a certain small substructure influences all other entries), random designs and decompositions. I will present a method that overcomes these difficulties and give a very short and simple proof to a longstanding open problem.

Optimal Resistor Networks

Given a graph on n vertices with m edges, each of unit resistance, how small can the average resistance between pairs of vertices be? There are two very plausible extremal constructions—graphs like a star, and graphs which are close to regular—with the transition between them occurring when the average degree is 3. However, we show that there is a rather surprising construction which is better.

Edges not in any monochromatic copy of a fixed graph

For a family of fixed graphs H_1,...,H_k, denote by f(n;H_1,..., H_k) the maximum number of edges not contained in any monochromatic copy of H_i in colour i, in a k-edge-colouring of K_n. It is easy to see that $f(n;H,H)\ge\ex(n,H)$. In this talk, we introduce a new variant of Ramsey number, which determines f(n;H_1,..., H_k) asymptotically for non-bipartite graphs H_i. For the 3-colour case, an exact result is obtained for a subfamily of colour-critical graphs, including cliques. The special case f(n;K_3,K_3,K_3) answers a question of Ma affirmatively.

For bipartite graphs, Keevash and Sudakov showed $f(n;C_4,C_4)=\ex(n,C_4)$; recently Ma extended their result to an infinite family of bipartite graphs. We provide a larger family of bipartite graphs for which $f(n;H,H)=\ex(n,H)$. For general bipartite graphs, we prove an upper bound with an additive error term, i.e. $f(n;H,H)\le \ex(n,H)+O(1)$.

Covering and tiling hypergraphs with tight cycles

Given an hypergraph F, a perfect F-tiling in a hypergraph H is a spanning collection of disjoint copies of F. A related notion is that of an F-covering, where we cover every vertex of the host graph H with copies of F, but we no longer insist that the copies are disjoint. The problem of determining the least value of the minimum degree in a graph that ensures the existence of a perfect F-tiling (or F-covering) is well understood in the case of graphs. The situation is different for general uniform hypergraphs, where determining these thresholds is an active field of research. In this talk I will review some of the known results for hypergraphs and present some new results in the case where F is a tight cycle, which is a natural generalization of cycles for uniform hypergraphs. Joint work with Jie Han and Allan Lo.

Strategy Stealing in Avoidance Games

Let H be a hypergraph. In the achievment game on H, two players take it in turns to colour vertices of H in their own colour. The player who first achieves an edge of H in their colour wins. The well known strategy stealing argument shows that for any H this game is either a first player win or a draw.

We consider the avoidance (or misere) version of this game in which the first player to achieve an edge of H in their colour loses. A plausible hope (implicit in a remark of Beck) is that when H is transitive, the avoidance game is either a second player win or a draw. We show that this is false and investigate what possible extra conditions on H may make it true.

Joint work with Imre Leader and Mark Walters.

Degree versions of some classical results in Extremal Combinatorics

In this talk, I will prove a degree version of the celebrated Erdos-Ko-Rado theorem: given n>2k, for every intersecting k-uniform hypergraph H on n vertices, there exists a vertex that lies on at most $\binom{n-2}{k-2}$ edges. A degree version of the 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.

Domination in structured tournaments

There exists tournaments, such as random tournaments, for which the domination number is arbitrarily large. One can naturally ask what happens if we add some structure on the tournament, for instance if the tournament can be represented using a bounded number of partial orders. Alon et al. showed that k-majority tournaments have bounded domination number. Gyarfas and Palvolgyi conjectured that the following is true : If a tournament admits a partition of its arc set into k quasi orders, then its domination number is bounded in terms of k. We provide a short proof that the following more general conjecture due to Erdos, Sands, Sauer and Woodrow: If the arcs of a tournament T are colored with k colors, there is a set X of at most g(k) vertices such that for every vertex v of T, there is a monochromatic path from X to v.

(joint work with William Lochet and Stéphan Thomassé)

Inversions in random node labeling of random trees

Inversions in labeled trees generalize inversions in permutations. We study the number of inversions in trees labeled uniformly at random. The three types of trees that we considered – complete b-ary trees, split trees and conditional Galton-Watson trees – cover a wide range of tree models. For all of these trees, we show that both the distribution and the moment generating function of inversion numbers (after normalization) converge to a limit. In particular, by revealing the connection between inversions and the total path length, our proof for Galton-Watson trees is much shorter and gives stronger result comparing to previous work by Panholzer and Seitz. Joint work with Cecilia Holmgren, Svante Janson, Tony Johansson and Fiona Skerman.

Previous seminars: Autumn 2006, Spring 2007, Autumn 2007, Spring 2008, Autumn 2008, Spring 2009, Autumn 2009, Spring 2010. 2010-2016,