We utilize association schemes to analyze the quality of semidefinite programming (SDP) based convex relaxations of integral packing and covering polyhedra determined by matchings in hypergraphs. As a by-product of our approach, we obtain bounds on t
he clique and stability numbers of some regular graphs reminiscent of classical bounds by Delsarte and Hoffman. We determine exactly or provide bounds on the performance of Lov{a}sz-Schrijver SDP hierarchy, and illustrate the usefulness of obtaining commutative subschemes from non-commutative schemes via contraction in this context.
We consider the algebraic combinatorics of the set of injections from a $k$-element set to an $n$-element set. In particular, we give a new combinatorial formula for the spherical functions of the Gelfand pair $(S_k times S_n, text{diag}(S_k) times S
_{n-k})$. We use this combinatorial formula to give new Delsarte linear programming bounds on the size of codes over injections.
The Index Erasure problem asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight $Omega(sqrt{n})$ lower bound on the quantum query complexity of the non-coherent case of
the problem, where, in addition to preparing the required superposition, the algorithm is allowed to leave the ancillary memory in an arbitrary function-dependent state. This resolves an open question of Ambainis, Magnin, Roetteler, and Roland (CCC 2011), who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. The proof is based on evaluating certain Krein parameters of a symmetric association scheme defined over partial permutations. The study of this association scheme may be of independent interest.
A family of perfect matchings of $K_{2n}$ is $t$-$intersecting$ if any two members share $t$ or more edges. We prove for any $t in mathbb{N}$ that every $t$-intersecting family of perfect matchings has size no greater than $(2(n-t) - 1)!!$ for suffic
iently large $n$, and that equality holds if and only if the family is composed of all perfect matchings that contain a fixed set of $t$ disjoint edges. This is an asymptotic version of a conjecture of Godsil and Meagher that can be seen as the non-bipartite analogue of the Deza-Frankl conjecture proven by Ellis, Friedgut, and Pilpel.
A family of perfect matchings of $K_{2n}$ is $intersecting$ if any two of its members have an edge in common. It is known that if $mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, then $|mathcal{F}| leq (2n-3)!!$ and if equality h
olds, then $mathcal{F} = mathcal{F}_{ij}$ where $ mathcal{F}_{ij}$ is the family of all perfect matchings of $K_{2n}$ that contain some fixed edge $ij$. In this note, we show that the extremal families are stable, namely, that for any $epsilon in (0,1/sqrt{e})$ and $n > n(epsilon)$, any intersecting family of perfect matchings of size greater than $(1 - 1/sqrt{e} + epsilon)(2n-3)!!$ is contained in $mathcal{F}_{ij}$ for some edge $ij$. The proof uses the Gelfand pair $(S_{2n},S_2 wr S_n)$ along with an isoperimetric method of Ellis.
For even $k$, the matchings connectivity matrix $mathbf{M}_k$ encodes which pairs of perfect matchings on $k$ vertices form a single cycle. Cygan et al. (STOC 2013) showed that the rank of $mathbf{M}_k$ over $mathbb{Z}_2$ is $Theta(sqrt 2^k)$ and use
d this to give an $O^*((2+sqrt{2})^{mathsf{pw}})$ time algorithm for counting Hamiltonian cycles modulo $2$ on graphs of pathwidth $mathsf{pw}$. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within $mathbf{M}_k$, which enabled a pattern propagation commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar pattern propagation when only a black-box lower bound on the asymptotic rank of $mathbf{M}_k$ is given; no stronger structural insights such as the existence of large permutation submatrices in $mathbf{M}_k$ are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes $p$) parameterized by pathwidth. To apply this technique, we prove that the rank of $mathbf{M}_k$ over the rationals is $4^k / mathrm{poly}(k)$. We also show that the rank of $mathbf{M}_k$ over $mathbb{Z}_p$ is $Omega(1.97^k)$ for any prime $p eq 2$ and even $Omega(2.15^k)$ for some primes. As a consequence, we obtain that Hamiltonian cycles cannot be counted in time $O^*((6-epsilon)^{mathsf{pw}})$ for any $epsilon>0$ unless SETH fails. This bound is tight due to a $O^*(6^{mathsf{pw}})$ time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes $p eq 2$ in time $O^*(3.97^mathsf{pw})$, indicating that the modulus can affect the complexity in intricate ways.
A perfect matching of a complete graph $K_{2n}$ is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if $mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, t
hen $|mathcal{F}| leq (2(n-1) - 1)!!$ and if equality holds, then $mathcal{F} = mathcal{F}_{ij}$ where $ mathcal{F}_{ij}$ is the family of all perfect matchings of $K_{2n}$ that contain some fixed edge $ij$. We give a short algebraic proof of this result, resolving a question of Godsil and Meagher. Along the way, we show that if a family $mathcal{F}$ is non-Hamiltonian, that is, $m cup m ot cong C_{2n}$ for any $m,m in mathcal{F}$, then $|mathcal{F}| leq (2(n-1) - 1)!!$ and this bound is met with equality if and only if $mathcal{F} = mathcal{F}_{ij}$. Our results make ample use of a somewhat understudied symmetric commutative association scheme arising from the Gelfand pair $(S_{2n},S_2 wr S_n)$. We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.
Given a graph $G$, a vertex switch of $v in V(G)$ results in a new graph where neighbors of $v$ become nonneighbors and vice versa. This operation gives rise to an equivalence relation over the set of labeled digraphs on $n$ vertices. The equivalence
class of $G$ with respect to the switching operation is commonly referred to as $G$s switching class. The algebraic and combinatorial properties of switching classes have been studied in depth; however, they have not been studied as thoroughly from an algorithmic point of view. The intent of this work is to further investigate the algorithmic properties of switching classes. In particular, we show that switching classes can be used to asymptotically speed up several super-linear unweighted graph algorithms. The current techniques for speeding up graph algorithms are all somewhat involved insofar that they employ sophisticated pre-processing, data-structures, or use word tricks on the RAM model to achieve at most a $O(log(n))$ speed up for sufficiently dense graphs. Our methods are much simpler and can result in super-polylogarithmic speedups. In particular, we achieve better bounds for diameter, transitive closure, bipartite maximum matching, and general maximum matching.
Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find one in any graph that is not an interval graph. Tucker characterized the minimal forbidden submatr
ices of binary matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find one in any binary matrix that does not have the consecutive-ones property.
A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. A partially complemented digraph $widetilde{G}$ is a digraph obtained from a sequence of vertex complement operations on $G
$. Dahlhaus et al. showed that, given an adjacency-list representation of $widetilde{G}$, depth-first search (DFS) on $G$ can be performed in $O(n + widetilde{m})$ time, where $n$ is the number of vertices and $widetilde{m}$ is the number of edges in $widetilde{G}$. To achieve this bound, their algorithm makes use of a somewhat complicated stack-like data structure to simulate the recursion stack, instead of implementing it directly as a recursive algorithm. We give a recursive $O(n+widetilde{m})$ algorithm that uses no complicated data-structures.
