Research

Coalescence Probabilities of Cycle Products

Generalizing a formula of Stanley, we prove combinatorially that the probability that \(1, 2, \dots, k\) are contained in the same cycle of a product of two random \(n\)-cycles is \[\frac{1}{k} + \frac{4 (-1)^n}{ \binom{2k}{k}} \sum_{\substack{1 \leq i \leq k-1 \\ i \not\equiv n \bmod 2}} \binom{2k-1}{k+i} \left(\frac{1}{n+i+1} - \frac{1}{n-i}\right).\]

(link)

Flip Graphs on Self-Complementary Ideals of Chain Products (with Serena An)

In this paper, we introduce a flip operation on self-complementary ideals of chain product posets and study the resulting flip graphs. We give asymptotics for the number of vertices in these graphs, compute their diameters, and give bounds for their radii. We also define similar flip operations on self-complementary ideals of the chain product \([2r] \times [2r] \times [2r]\) satisfying additional symmetries, and we achieve similar results for the resulting flip graphs.

(link)

The Upper Tail of Cycle Distributions in Sparse Erdős-Rényi Random Graphs (with Tomasz Ślusarczyk)

The distribution of subgraph counts in Erdős-Rényi random graphs is of great interest in extremal combinatorics. In this paper, we analyze the upper tail of the \(k\)-cycle count in the sparse (constant-degree) regime for fixed \(k\), in the limit as the number of vertices tends to infinity. We provide asymptotically sharp bounds for the probability the graph contains a large number of \(k\)-cycles via a coring argument; the logarithmic probability of containing \(t\) cycles is asymptotically equal to the logarithmic probability of containing \(t\) disjoint \(k\)-cycles or containing a clique with \(t\) cycles.

(link)

Symmetric Operations on Domains of Size at Most 4

To convert a fractional solution to an instance of a constraint satisfaction problem into a solution, a rounding scheme is needed, which can be described by a collection of symmetric operations with one of each arity. An intriguing possibility, raised in a recent paper by Carvalho and Krokhin, would imply that any clone of operations on a set D which contains symmetric operations of arities \(1, 2, \ldots, \lvert D \rvert\) contains symmetric operations of all arities in the clone. If true, then it is possible to check whether any given family of constraint satisfaction problems is solved by its linear programming relaxation. We characterize all idempotent clones containing symmetric operations of arities \(1,2,\ldots,\lvert D \rvert\) for all sets \(D\) with size at most four and prove that each one contains symmetric operations of every arity, proving the conjecture above for \(\lvert D \rvert \leq 4\).

(link)