## Seminars and Colloquia by Series

### Two conjectures on the spread of graphs

Series
Combinatorics Seminar
Time
Friday, April 29, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael TaitVillanova University

Given a graph $G$ let $\lambda_1$ and $\lambda_n$ be the maximum and minimum eigenvalues of its adjacency matrix and define the spread of $G$ to be $\lambda_1 - \lambda_n$. In this talk we discuss solutions to a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs.

The first, referred to as the spread conjecture, states that over all graphs on $n$ vertices the join of a clique of order $\lfloor 2n/3 \rfloor$ and an independent set of order $\lceil n/3 \rceil$ is the unique graph with maximum spread. The second, referred to as the bipartite spread conjecture, says that for any fixed $e\leq n^2/4$, if $G$ has maximum spread over all $n$-vertex graphs with $e$ edges, then $G$ must be bipartite.

We show that the spread conjecture is true for all sufficiently large $n$, and we prove an asymptotic version of the bipartite spread conjecture. Furthermore, we exhibit an infinite family of counterexamples to the bipartite spread conjecture which shows that our asymptotic solution is tight up to a multiplicative factor in the error term. This is joint work with Jane Breen, Alex Riasanovsky, and John Urschel.

### Partitioning cubic graphs into isomorphic linear forests

Series
Combinatorics Seminar
Time
Friday, April 22, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Liana YepremyanEmory University

A cubic graph is one where every vertex has degree three. A linear forest is a disjoint union of paths. It is known that the edge set of every cubic graph can be partitioned into two linear forests where each path is short (of constant size). A conjecture of Wormald asks for such a partition where the two forests are isomorphic (we no longer insist on having short paths, although that is also an open question). Note that this also can be phrased as an edge-colouring question. Is it possible to colour the edge set of a cubic graph by red and blue such that the two monochromatic components induce isomorphic linear forests? Recently we proved this for all connected graphs on a sufficiently large number of vertices. I will talk about the result and give some idea of the proof method. This is joint work with Gal Kronenberg, Shoham Letzter and Alexey Pokrovskiy.

### Exponential decay of intersection volume and applications

Series
Combinatorics Seminar
Time
Friday, April 15, 2022 - 09:00 for 1 hour (actually 50 minutes)
Location
Zoom
Speaker
Hong LiuECOPRO, IBS

Please Note: Note the unusual time!

When do two balls in a metric space have small intersection? We give some natural conditions to guarantee an exponential decay on the volume of such intersections. Our proof is conceptually simple, making use of concentration of measure on a "slice." We will discuss a couple of applications of this volume estimate in coding theory. This is joint work with Jaehoon Kim and Tuan Tran.

### Incest and infanticide: a branching process with deletions and mergers that matches the threshold for hypercube percolation

Series
Combinatorics Seminar
Time
Friday, April 8, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Fiona SkermanUppsala University / Simon&#039;s Institute

We define a graph process based on a discrete branching process with deletions and mergers, which is inspired by the 4-cycle structure of the hypercube $\mathcal{Q}_d$ for large $d$. We prove survival and extinction under certain conditions on $p$ and $q$ that heuristically match the known expansions of the critical probabilities for bond percolation on the hypercube. Joint work with Laura Eslava and Sarah Penington. Based on https://arxiv.org/abs/2104.04407.

### Discrete vs. definable combinatorics of Schreier graphs

Series
Combinatorics Seminar
Time
Friday, April 1, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Felix WeilacherCarnegie Mellon University

We discuss the relationship between the Borel/Baire measurable/measurable combinatorics of the action of a finitely generated group on its Bernoulli shift and the discrete combinatorics of the multiplication action of that group on itself. Our focus is on various chromatic numbers of graphs generated by these actions. We show that marked groups with isomorphic Cayley graphs can have Borel/Baire measurable/measurable chromatic numbers which differ by arbitrarily much. In the Borel two-ended, Baire measurable, and measurable hyperfinite settings, we show our constructions are nearly best possible (up to only a single additional color). Along the way, we get tightness of some bounds of Conley and Miller on Baire measurable and measurable chromatic numbers of locally finite Borel graphs.

### Definable combinatorics in hyperfinite graphs

Series
Combinatorics Seminar
Time
Friday, March 18, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Matthew BowenMcGill University

We discuss a few new results concerning the descriptive combinatorics of bounded degree hyperfinite Borel graphs. In particular, we show that the Baire measurable edge chromatic number of $G$ is at most $\lceil\frac{3}{2}\Delta(G)\rceil+6$ when G is a multigraph, and for bipartite graphs we improve this bound to $\Delta(G)+1$ and show that degree regular one-ended bipartite graphs have Borel perfect matchings generically. Similar results hold in the measure setting assuming some hyperfiniteness conditions. This talk is based on joint work with Kun and Sabok, Weilacher, and upcoming work with Poulin and Zomback.

### 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.