Seminars and Colloquia by Series

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 Yepremyan – Emory 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 Liu – ECOPRO, 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 Skerman – Uppsala University / Simon'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 Weilacher – Carnegie 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 Bowen – McGill 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 McCarty – University 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 Herscovici – Georgia 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 Zhukovskii – Moscow 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 Swanson – Ashland 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 Liebenau – UNSW 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

Pages