Seminars and Colloquia by Series

Vertex-minors and structure for dense graphs

Series
Combinatorics Seminar
Time
Friday, December 3, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCartyUniversity of Waterloo

Structural graph theory has usually focused on classes of graphs that are 'sparse' rather than 'dense' (that is, have few edges rather than many edges). We discuss this paradigm, focusing on classes with a forbidden vertex-minor. In particular, we discuss progress on a conjecture of Geelen that would totally characterize classes with a forbidden vertex-minor. This is joint work with Jim Geelen and Paul Wollan.

The degenerate Eulerian numbers and combinatorics behind them

Series
Combinatorics Seminar
Time
Friday, October 8, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Orli HerscoviciGeorgia Institute of Technology

In his works Carlitz defined and investigated a few generalizations of the Eulerian numbers and polynomials. For most of those generalizations he provided also a combinatorial interpretation. The classical Eulerian numbers and some of their generalizations are connected to combinatorial statistics on permutations. Carlitz intended to provide a combinatorial interpretation also to his degenerate Eulerian numbers. However since their introduction in 1979 these numbers had a pure analytic character. In this talk we consider a combinatorial model that generalizes the standard definition of permutations and show its relation to the degenerate Eulerian numbers.

Extremal independence and applications in random graphs.

Series
Combinatorics Seminar
Time
Friday, July 23, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/6673
Speaker
Maksim ZhukovskiiMoscow Institute of Physics and Technology

Let, for every positive integer d, a tuple of events A_1,...,A_d be given. Let X_d be the number of events that occur. We state new sufficient conditions for the following extremal independence property: |P(X_d=0)-\prod_{i=1}^d(1-P(A_i))|\to 0. These conditions imply a series of results on asymptotic distributions of certain maximum statistics. In particular, for the maximum number X_n of cliques sharing one vertex in G(n,p), we find sequences a_n and b_n such that (X_n-a_n)/b_n converges in distribution to a standard Gumbel random variable.

The Density of Costas Arrays Decays Exponentially

Series
Combinatorics Seminar
Time
Friday, May 28, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/6673
Speaker
Christopher SwansonAshland University

Costas arrays are useful in radar and sonar engineering and many other settings in which optimal 2-D autocorrelation is needed: they are permutation matrices in which the vectors joining different pairs of ones are all distinct.
In this talk we discuss some of these applications, and prove that the density of Costas arrays among permutation matrices decays exponentially, solving a core problem in the theory of Costas arrays. 
The proof is probabilistic, and combines ideas from random graph theory with tools from probabilistic combinatorics.

Based on joint work in progress with Bill Correll, Jr. and Lutz Warnke.

Two approximate versions of Jackson’s conjecture [Special time/day!]

Series
Combinatorics Seminar
Time
Thursday, April 15, 2021 - 18:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Anita LiebenauUNSW Sydney

A diregular bipartite tournament is a balanced complete bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree. 
In 1981, Jackson showed that a diregular bipartite tournament contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. 
We prove an approximate version of this conjecture: for every $\epsilon>0$ there exists $n_0$ such that every diregular bipartite tournament on $2n>n_0$  vertices contains a collection of $(1/2-\epsilon)n$ cycles of length at least $(2-\epsilon)n$. 
Increasing the degree by a small proportion allows us to prove the existence of many Hamilton cycles: for every $c>1/2$ and $\epsilon>0$ there exists $n_0$ such that every $cn$-regular bipartite digraph on $2n>n_0$ vertices contains $(1-\epsilon)cn$ edge-disjoint Hamilton cycles.

Base on joint work with Yanitsa Pehova, see https://arxiv.org/abs/1907.08479

Please note the special time/day: Thursday 6pm

Aldous-Broder theorem: extension to the non reversible case and new combinatorial proof

Series
Combinatorics Seminar
Time
Friday, March 26, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Jean-Francois MarckertUniversity of Bordeaux

Aldous-Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph G, but it is more general: it states that given a reversible M Markov chain on G started at r, the tree rooted at r formed by the steps of successive first entrance in each node (different from the root) has a probability proportional to $\prod_{e=(e1,e2)∈Edges(t,r)}M_{e1,e2}$ , where the edges are directed toward r. As stated, it allows to sample many distributions on the set of spanning trees. In this paper we extend Aldous-Broder theorem by dropping the reversibility condition on M. We highlight that the general statement we prove is not the same as the original one (but it coincides in the reversible case with that of Aldous and Broder). We prove this extension in two ways: an adaptation of the classical argument, which is purely probabilistic, and a new proof based on combinatorial arguments. On the way we introduce a new combinatorial object that we call the golf sequences.

Based on joint work with Luis Fredes, see https://arxiv.org/abs/2102.08639

Drift Analysis

Series
Combinatorics Seminar
Time
Friday, March 19, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
Speaker
Benjamin DoerrLaboratoire d'Informatique (LIX), École Polytechnique

Drift analysis is the name for a collection of tools that allow to translate information about the one-step progress of a randomized process into information about first hitting times. Drift analysis is successfully used in the mathematical analysis of randomized search heuristics, most notably, evolutionary algorithms, but (for unclear reasons) much less in discrete mathematics or other areas of algorithms.

In this talk, I will give a brief introduction to drift analysis, show some classic and recent applications, and describe some open problems, both concerning drift methods and the mathematical runtime analysis of randomized search heuristics.

On the jump of the clique chromatic number for binomial random graphs

Series
Combinatorics Seminar
Time
Friday, March 12, 2021 - 16:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Dieter MitscheInstitut Camille Jordan, Univ. de Lyon

Given a graph G, the clique chromatic number of G is the smallest number of colors needed to color the vertices of G so that no maximal clique containing at least two vertices is monochromatic.
We solve an open question proposed by McDiarmid, the speaker, and Pralat concerning the asymptotic order of the clique chromatic number for binomial random graphs.
More precisely, we find the correct order of the clique chromatic number for most values of the edge-probability p around n^{-1/2}. Furthermore, the gap between upper and lower bounds is at most a logarithmic factor in n in all cases.

Based on joint work in progress with Lyuben Lichev and Lutz Warnke.


(Please note the unusual time from 4-5pm, due to the Virtual Admitted Student Day in the School of Mathematics.)

Rotor-routing reachability is easy, chip-firing reachability is hard

Series
Combinatorics Seminar
Time
Friday, March 5, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
Speaker
Lilla TóthmérészEötvös Loránd University

Chip-firing and rotor-routing are two well-studied examples of Abelian networks. We study the complexity of their respective reachability problems. We show that the rotor-routing reachability problem is decidable in polynomial time, and we give a simple characterization of when a chip-and-rotor configuration is reachable from another one. For chip-firing, it has been known that the reachability problem is in P if we have a class of graphs whose period length is polynomial (for example, Eulerian digraphs). Here we show that in the general case, chip-firing reachability is hard in the sense that if the chip-firing reachability problem were in P for general digraphs, then the polynomial hierarchy would collapse to NP.

Talk based on https://arxiv.org/abs/2102.11970

The extremal number of surfaces

Series
Combinatorics Seminar
Time
Friday, February 26, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
Speaker
Andrey KupavskiiCNRS and MIPT (Grenoble and Moscow)

In 1973, Brown, Erdős and Sós proved that if H is a 3-uniform hypergraph on n vertices which contains no triangulation of the sphere, then H has at most O(n^{5/2}) edges, and this bound is the best possible up to a constant factor. Resolving a conjecture of Linial, also reiterated by Keevash, Long, Narayanan, and Scott, we show that the same result holds for triangulations of the torus. Furthermore, we extend our result to every closed orientable surface S.

Joint work with Alexandr Polyanskii, István Tomon and Dmitriy Zakharov, see https://arxiv.org/abs/2010.07191

Pages