## Seminars and Colloquia by Series

### 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
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
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
Speaker
Benjamin DoerrLaboratoire d&#039;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
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
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
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

### The minimum degree of minimal Ramsey graphs for cliques

Series
Combinatorics Seminar
Time
Friday, February 19, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
Speaker
Anurag BishnoiTU Delft

We prove a new upper bound of $s_r(K_k) = O(k^5 r^{5/2})$ on the Ramsey parameter $s_r(K_k)$ introduced by Burr, Erd\H{o}s and Lov\'{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r$-colouring of the edges of $G$ contains a monochromatic $K_k$, whereas no proper subgraph of $G$ has this property. This improves the previous upper bound of $s_r(K_k) = O(k^6 r^3)$ proved by Fox et al. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.

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

### Extremal stationary values for random digraphs

Series
Combinatorics Seminar
Time
Friday, February 12, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
Speaker
Guillem PerarnauUPC Barcelona

In this talk, we will discuss the minimum positive value of the stationary distribution of a random walk on a directed random graph with given degrees. While for undirected graphs the stationary distribution is simply determined by the degrees, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determining the mixing time of the walk, as shown by Bordenave, Caputo, and Salez. However, typical results provide no information on the minimum value, which is important for many applications. Recently, Caputo and Quattropani showed that the stationary distribution exhibits logarithmic fluctuations provided that the minimum degree is at least 2. In this talk, we show that dropping the minimum degree condition may yield polynomially smaller stationary values of the form n^{-(1+C+o(1))}, for a constant C determined by the degree distribution. In particular, C is the combination of two factors: (1) the contribution of atypically thin in-neighborhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" trajectories, controlled by large deviation rate functions. As a by-product of our proof, we also determine the hitting and cover time in random digraphs. This is joint work with Xing Shi Cai.

### The differential equation method in Banach spaces and the n-queens problem

Series
Combinatorics Seminar
Time
Friday, January 29, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location