Uniquely optimal codes of low complexity are symmetric
We formulate explicit predictions concerning the symmetry of optimal codes in compact metric spaces. This motivates the study of optimal codes in various spaces where these predictions can be tested.
Periodic words, common subsequences and frogs
Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. We show several results on the length of longest common subsequence (LCS) between $W^{(n)}$ and $R_n$; in particular, we show that its expectation is $\gamma_W n-O(\sqrt{n})$ for an efficiently-computable constant $\gamma_W$.
This is done by relating the problem to a new interacting particle system, which we dub “frog dynamics”. In this system, the particles (`frogs’) hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushASEP.
In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $\gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics.
In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS.
Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of $K_n$, which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builder’s goal is to locate a particular monochromatic structure in Painter’s coloring by revealing the color of as few edges as possible. The fewest number of turns required for Builder to win this game is known as the restricted online Ramsey number. In this paper, we consider the situation where this “particular monochromatic structure” is a large matching or a large tree. We show that in any $t$-coloring of $E(K_n)$, Builder can locate a monochromatic matching on at least ${n-t+1\over t+1}$ edges by revealing at most $O(n\log t)$ edges. We show also that in any $3$-coloring of $E(K_n)$, Builder can locate a monochromatic tree on at least $n/2$ vertices by revealing at most $5n$ edges.
How can $d+k$ vectors in $\mathbb{R}^d$ be arranged so that they are as close to orthogonal as possible? In particular, define $\theta(d,k):=\min_X\max_{x\neq y\in X}|\langle x,y\rangle|$ where the minimum is taken over all collections of $d+k$ unit vectors $X\subseteq\mathbb{R}^d$. In this paper, we focus on the case where $k$ is fixed and $d\to\infty$. In establishing bounds on $\theta(d,k)$, we find an intimate connection to the existence of systems of ${k+1\choose 2}$ equiangular lines in $\mathbb{R}^k$. Using this connection, we are able to pin down $\theta(d,k)$ whenever $k\in\{1,2,3,7,23\}$ and establish asymptotics for general $k$. The main tool is an upper bound on $\mathbb{E}_{x,y\sim\mu}|\langle x,y\rangle|$ whenever $\mu$ is an isotropic probability mass on $\mathbb{R}^k$, which may be of independent interest. Our results translate naturally to the analogous question in $\mathbb{C}^d$. In this case, the question relates to the existence of systems of $k^2$ equiangular lines in $\mathbb{C}^k$, also known as SIC-POVM in physics literature.
Classical questions in extremal graph theory concern the asymptotics of $\operatorname{ex}(G,\mathcal{H})$ where $\mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a “standard” increasing sequence of host graphs $(G_1, G_2, \dots)$, most often $K_n$ or $K_{n,n}$. Inverting the question, we can instead ask how large $e(G)$ can be with respect to $\operatorname{ex}(G,\mathcal{H})$. We show that the standard sequences indeed maximize $e(G)$ for some choices of $\mathcal{H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.
In this note, we present a fractional version of Haemers’ bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers’ bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers’ bound. We show also that this bound is multiplicative, unlike Haemers’ bound.
  • arXiv
  • IEEE Transactions on Information Theory
  • Jun 2019
  • Abstract
We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Tur&aacuten-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.
with Zhanar Berikkyzy, Mike Dairyko, Kirsten Hogenson, Mohit Kumbhat, Bernard Lidický, Kacy Messerschmidt, Kevin Moss, Katy Nowak, Kevin Palmowski and Derrick Stolee
All planar graphs are $4$-colorable and $5$-choosable, while some planar graphs are not $4$-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $\ell\in\{3,4,5,6,7\}$, a planar graph is $4$-choosable if it is $\ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k, s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4, 1)$-choosable, but there exist planar graphs that are not $(4, 3)$-choosable. It is an open question whether planar graphs are always $(4, 2)$-choosable. A chorded $\ell$-cycle is an $\ell$-cycle with one additional edge. We demonstrate for each $\ell\in\{5,6,7\}$ that a planar graph is $(4, 2)$-choosable if it does not contain chorded $\ell$-cycles.
with Esther Banaian, Steve Butler, Jeffrey Davis, Jacob Landgraf and Scarlitte Ponce
We consider a generalization of Eulerian numbers which count the number of placements of $cn$ rooks on an $n\times n$ chessboard where there are exactly $c$ rooks in each row and each column, and exactly $k$ rooks below the main diagonal. The standard Eulerian numbers correspond to the case $c=1$. We show that for any $c$ the resulting numbers are symmetric and give generating functions of these numbers for small values of $k$.
with Esther Banaian, Steve Butler, Jeffrey Davis, Jacob Landgraf and Scarlitte Ponce
Juggling patterns can be described by a closed walk in a (directed) state graph, where each vertex (or state) is a landing pattern for the balls and directed edges connect states that can occur consecutively. The number of such patterns of length $n$ is well known, but a long-standing problem is to count the number of prime juggling patterns (those juggling patterns corresponding to cycles in the state graph). For the case of $b=2$ balls we give an expression for the number of prime juggling patterns of length $n$ by establishing a connection with partitions of $n$ into distinct parts. From this we show the number of two-ball prime juggling patterns of length $n$ is $(\gamma-o(1))2^n$ where $\gamma=1.32963879259\ldots$. For larger $b$ we show there are at least $b^{n-1}$ prime cycles of length $n$.
For a $k$-uniform hypergraph $G$ with vertex set $\{1,\dots,n\}$, the ordered Ramsey number $\operatorname{OR}_t(G)$ is the least integer $N$ such that every $t$-coloring of the edges of the complete $k$-uniform graph on vertex set $\{1,\dots,N\}$ contains a monochromatic copy of $G$ whose vertices follow the prescribed order. Due to this added order restriction, the ordered Ramsey numbers can be much larger than the usual graph Ramsey numbers. We determine that the ordered Ramsey numbers of loose paths under a monotone order grows as a tower of height two less than the maximum degree in terms of the number of edges. We also extend theorems of Conlon et al. (2015) on the ordered Ramsey numbers of $2$-uniform matchings to provide upper bounds on the ordered Ramsey number of $k$-uniform matchings under certain orderings.
with Jess De Silva, Phil DeOrsey, Franklin Kenter, Troy Retter and Josh Tobin
The game of Hanabi is a multiplayer cooperative card game that has many similarities to a mathematical “hat guessing game.” In Hanabi, a player does not see the cards in her own hand and must rely on the actions of the other players to determine information about her cards. This article presents two strategies for Hanabi. These strategies use different encoding schemes, based on ideas from network coding, to efficiently relay information. The first strategy allows players to effectively recommend moves for other players, and the second strategy allows players to determine the contents of their hands. Results from computer simulations demonstrate that both strategies perform well. In particular, the second strategy achieves a perfect score more than 75 percent of the time.