ISU Discrete Math Seminar

How can one arrange \(d+k\) many vectors in \(\mathbb R^d\) so that they are as close to orthogonal as possible? Such arrangements are known as projective codes (or antipodal spherical codes) and are a natural generalization of balanced error-correcting codes. In this talk, we will consider the case when \(k\) is constant and \(d\to\infty\), i.e. when there is a “small excess” of vectors. In this realm, we show that there is an intimate connection to the existence of systems of \({k+1\choose 2}\) equiangular lines in \(\mathbb R^k\) and use this to obtain tight bounds for \(k\in\{1,2,3,7,23\}\) and outperform the Welch bound otherwise. To expose this relationship, we show how to “dualize” the problem and instead discuss bounding the first moment of isotropic probability masses (a.k.a. probabilistic tight frames) on \(\mathbb R^k\), which may be of independent interest.

While we will focus mainly on the real case in this talk, all of these results translate naturally to the complex case (and even to the quaternions), wherein the answer relates to Zauner’s conjecture on the existence of systems of \(k^2\) equiangular lines in \(\mathbb C^k\), also known as SIC-POVM in physics literature.

It is possible to obtain any simple graph \(G\) from any other graph \(H\) on the same set of vertices by performing a sequence of subgraph complementations. That is, we can iteratively replace induced subgraphs by their graph complements until we obtain \(G\) from \(H\). We ask for the minimum number of subgraph complementations in such a sequence. When \(H\) is the graph with no edges, we denote this parameter by \(c_2(G)\). Finding \(c_2(G)\) relates closely to the minimum rank problem. We show that \(c_2 (G) = \operatorname{mr}(G,\mathbb{F}_2)\) when \(\operatorname{mr}(G,\mathbb{F}_2)\) is odd or when \(G\) is a forest; otherwise, \(\operatorname{mr}(G,\mathbb{F}_2) \leq c_2 (G) \leq \operatorname{mr}(G,\mathbb{F}_2) + 1\). We then provide two conditions which are equivalent to having \(c_2(G) = \operatorname{mr}(G,\mathbb{F}_2) + 1\). In this case, we can still interpret \(\operatorname{mr}(G,\mathbb{F}_2)\) combinatorially using a variation of subgraph complementation. Finally, the class of graphs \(G\) with \(c_2(G) \leq k\) is hereditary and finitely defined for any natural number \(k\). We exhibit the sets of minimal forbidden induced subgraphs for small values of \(k\). This is joint work with Christopher Purcell and Puck Rombach.

Proving a 2009 conjecture of Itai Benjamini, we show: For any \(C\), there is \(a > 0\) such that for any simple random walk on an \(n\)-vertex graph \(G\), the probability that the first \(Cn\) steps of the walk hit every vertex of \(G\) is at most \(\exp[-an]\). A first ingredient of the proof is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of \(C\). Joint with Jeff Kahn.

Given two random words of the same length, what is the average value of their longest common subsequence? This turns out to be an incredibly difficult question to answer. A natural simplification of the problem asks the same question when only one of the words is random and the other is fixed. Bukh and Cox answered this question when the fixed word is periodic with base \(12\cdots k\) by introducing the Frog Dynamics. We extend this result to the base word \(12\cdots kk\cdots 21\) by introducing Frogs... with Hats!

Abstract: We refine a property of 2-connected graphs described in the classical paper of Dirac from 1952 and use the refined property to somewhat shorten Dirac’s proof of the fact that each 2-connected \(n\)-vertex graph with minimum degree at least \(k\) has a cycle of length at least \(\min\{n,2k\}\). This is joint work with Alexandr Kostochka and Ruth Luo.

The spread of a graph is the difference between the maximum and minimum eigenvalues of the adjacency matrix of the graph. Answering a question of Gotshall, O’Brien and Tait, we determine the maximum spread of an outerplanar graph on n vertices, for sufficiently large \(n\). Our methods also extend to determine the maximum spread of planar and \(K_{2, t}\)-minor-free graphs. I will additionally discuss possible extensions of our work. This is joint work with Zelong Li, Linyuan Lu and Zhiyu Wang.

For an infinite set \(D\) of positive integers, Landman and Robertson defined a \(D\)-diffsequence as an increasing sequence \(a_1<a_2<\dots<a_k\) where the consecutive differences, \(a_i-a_{i-1}\) all lie in \(D\). We say that \(D\) is \(r\)-accessible if every \(r\)-coloring of \(\mathbb{N}\) contains arbitrarily long monochromatic \(D\)-diffsequences. When \(D\) is \(r\)-accessible, we can define \(\Delta(D,k;r)\) as the smallest \(n\) such that every \(r\)-coloring of \(\{1,2,\dots,n\}\) contains a monochromatic \(D\)-diffsequence of length \(k\). This is analogous to the notion of van der Waerden numbers.

In this talk, we will demonstrate that it is possible for \(\Delta(D,k;r)\) to grow faster than polynomially in \(k\). We will also discuss a broad class of \(D\)’s which are not \(2\)-accessible.