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.

The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous \(\frac{4}{3}\)-integrality-gap conjecture on the "subtour elimination" linear programming relaxation of the Metric TSP.

We prove that every simple 2-connected subcubic graph on \(n\) vertices with \(n_2\) vertices of degree 2 has a TSP walk of length at most \(\frac{5n+n_2}{4}-1\), confirming a conjecture of Dvořák, Král’, and Mohar. This bound is best possible and we characterize the extremal subcubic examples meeting this bound. We also give a quadratic time combinatorial algorithm to find such a TSP walk. In particular, we obtain a \(\frac{5}{4}\)-approximation algorithm for the Graphic TSP on cubic graphs. Joint work with Michael Wigal and Xingxing Yu

An \((n,k,t)\)- graph is a graph on \(n\) vertices in which every set of \(k\) vertices contain a clique on \(t\) vertices. Turán’s Theorem (complemented) states that the unique minimum \((n,k,2)\)-graph is a disjoint union of cliques. We prove that minimum \((n,k,t)\)-graphs are always disjoint unions of cliques for any \(t\) (despite nonuniqueness of extremal examples), thereby generalizing Turán’s Theorem and confirming two conjectures of Hoffman et al. This is joint work with Joseph Briggs.

Our originally scheduled speaker had to drop out, so I’ll be filling the time with some ramblings about whatever problem strikes my fancy! Of course, if any of you would rather give a last-minute talk, just let me know!

The chromatic number is one of the most studied graph invariants in graph theory. \(\chi\)-boundedness, for instance, studies the induced subgraphs present in graphs with large chromatic number and small clique number. Neumann-Lara introduced an analog directed version of this graph invariant: the dichromatic number of digraphs. In this talk, we start by seeing some analogous results from the field of \(\chi\)-boundedness in this context. In particular, we will talk about heroes. A hero \(H\) in a class of digraphs \(\mathcal{C}\) is a digraph with the property that \(H\)-free digraphs \(D\in \mathcal{C}\) have bounded dichromatic number. After going over the known results regarding heroes, we present a new result (obtained in collaboration with Hidde Koerts, Benjamin Moore, and Sophie Spirkl) which almost fully characterizes heroes in \({rK1+\vec{P_3}}\)-free digraphs.

In this preliminary presentation, I will very briefly visit the historical background of my research area followed by a review of the mathematical background necessary to understand the sequences I am working with, namely perfect necklaces and universal partial cycles.

I will present one major result from my collaboration with D. Fillmore, B. Goeckner, R. Kirsch, and D. McGinnis which proves that any universal partial cycle can be unfolded into a De Bruijn cycle provided a perfect necklace of appropriate size. I will mention another major result, without going into detail, which proves that using perfect necklaces one can construct infinite families of universal partial cycles from any starting universal partial cycle.

I will discuss my current research questions as well as my interests for future work in the area — how can nontrivial perfect necklaces be generated? what can be said about restricted partial universal cycles? and the current biggest question in the subfield: can there exist nontrivial universal partial cycles with more than one diamond per word-length window? Each of these questions I visit from especially a graphical perspective, using De Bruijn graphs, substructures thereof, and what is called the astute graph.

Given two simple graphs \(X\) and \(Y\) on \(n\) vertices, the friends-and-strangers graph \(\mathsf{FS}(X, Y)\) has as its vertices all \(n!\) bijections from \(V(X)\) to \(V(Y)\), with bijections \(\sigma, \tau\) adjacent if and only if they differ on two adjacent elements of \(V(X)\) whose mappings are adjacent in \(V(Y)\). These can be thought of as reconfiguration problems that generalize the famous \(15\)-puzzle. As such, two natural directions of inquiry are connectivity (which configurations are reachable from which other configurations) and diameters (worst-case guarantees on solution length for any particular solvable puzzle).

We explore a number of problems in both directions in this talk. We determine exactly which graphs \(Y\) guarantee that \(\mathsf{FS}(X,Y)\) is connected for any biconnected graph \(X\), leading to the resolution of a conjecture of Defant and Kravitz. We also discuss the diameters of friends-and-strangers graphs: friends-and-strangers graphs have small diameter whenever \(X\) or \(Y\) is taken to be a path or a cycle, but in general, diameters of connected components of friends-and-strangers graphs fail to be polynomially bounded in the size of \(X\) and \(Y\), settling a conjecture of Alon, Defant, and Kravitz in the negative. Our construction yields the existence of infinitely many values of \(n\) for which there are \(n\)-vertex graphs \(X\) and \(Y\) with the diameter of a component of \(\mathsf{FS}(X, Y)\) being at least \(n^{(\log n)/(\log \log n)}\). We conclude by discussing several exciting conjectures and problems for future research.