Georgia Institute of Technology College of Sciences

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.

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.

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.

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