Source author record

Nathan Lindzey

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics Computational Complexity math.GR math.RT quant-ph

Catalog footprint

Research overview

8works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

An Eventown Result for Permutations

A family of permutations $\mathcal{F} \subseteq S_n$ is even-cycle-intersecting if $σπ^{-1}$ has an even cycle for all $σ,π\in \mathcal{F}$ . We show that if $\mathcal{F} \subseteq S_n$ is an even-cycle-intersecting family of permutations, then $|\mathcal{F}| \leq 2^{n-1}$ , and that equality holds when $n$ is a power of 2 and $\mathcal{F}$ is a double-translate of a Sylow 2-subgroup of $S_n$ . This result can be seen as an analogue of the classical eventown problem for subsets and it confirms a conjecture of János Körner on maximum reversing families of the symmetric group. Along the way, we show that the canonically intersecting families of $S_n$ are also the extremal odd-cycle-intersecting families of $S_n$ for all even $n$ . While the latter result has less combinatorial significance, its proof uses an interesting new character-theoretic identity that might be of independent interest in algebraic combinatorics.

preprint2022arXiv

A Tight Lower Bound for Non-coherent Index Erasure

The Index-Erasure problem is a quantum state generation problem that asks a quantum computer to prepare a uniform superposition over the image of an injective function given by an oracle. We prove a tight $Ω(\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 et al., who gave a tight bound for the coherent case, the case where the ancillary memory must return to its initial state. To prove our main result, we first extend the automorphism principle of Høyer et al. to the general adversary method of Lee et al. for state generation problems, which allows one to exploit the symmetries of these problems to lower bound their quantum query complexity. Using this method, we establish a strong connection between the quantum query complexity of non-coherent symmetric state generation problems and the Krein parameters of an association scheme defined on injective functions. In particular, we use the spherical harmonics a finite symmetric Gelfand pair associated with the space of injective functions to obtain asymptotic bounds on certain Krein parameters, from which the main result follows.

preprint2022arXiv

Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems

We give simpler algebraic proofs of uniqueness for several Erdős-Ko-Rado results, i.e., that the canonically intersecting families are the only largest intersecting families. Using these techniques, we characterize the largest partially 2-intersecting families of perfect hypermatchings, resolving a recent conjecture of Meagher, Shirazi, and Stevens.

preprint2014arXiv

Erdős-Ko-Rado for Perfect Matchings

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}$ , then $|\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' \not \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.

preprint2014arXiv

Speeding Up Graph Algorithms via Switching Classes

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.

preprint2013arXiv

Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs

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 submatrices 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.

preprint2013arXiv

On Finding Lekkerkerker-Boland Subgraphs

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 submatrices of matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find one in any matrix that does not have the consecutive-ones property.

preprint2013arXiv

Simple DFS on the Complement of a Graph and on Partially Complemented Digraphs

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nathan Lindzey

Research overview

Is this your work?

8 publications

An Eventown Result for Permutations

A Tight Lower Bound for Non-coherent Index Erasure

Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems

Erdős-Ko-Rado for Perfect Matchings

Speeding Up Graph Algorithms via Switching Classes

Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs

On Finding Lekkerkerker-Boland Subgraphs

Simple DFS on the Complement of a Graph and on Partially Complemented Digraphs

See the researcher in context

Building this map preview