Nathan Lindzey
YOU?
Author Swipe
View article: Intersecting Families of Spanning Trees
Intersecting Families of Spanning Trees Open
A family $\mathcal{F}$ of spanning trees of the complete graph on $n$ vertices $K_n$ is \emph{$t$-intersecting} if any two members have a forest on $t$ edges in common. We prove an Erdős--Ko--Rado result for $t$-intersecting families of sp…
View article: A note on “Largest independent sets of certain regular subgraphs of the derangement graph”
A note on “Largest independent sets of certain regular subgraphs of the derangement graph” Open
Let $$D_{n,k}$$ be the set of all permutations of the symmetric group $$S_n$$ that have no cycles of length i for all $$1 \le i \le k$$ . In the paper mentioned above, Ku, Lau, and Wong prove that the set of all the large…
View article: Jack Derangements
Jack Derangements Open
For each integer partition $λ\vdash n$ we give a simple combinatorial expression for the sum of the Jack character $θ^λ_α$ over the integer partitions of $n$ with no singleton parts. For $α= 1,2$ this gives closed forms for the eigenvalues…
View article: Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings
Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings Open
We give a characterization of the largest $2$-intersecting families of permutations of $\{1,2,\ldots,n\}$ and of perfect matchings of the complete graph $K_{2n}$ for all $n \geq 2$.
View article: Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems
Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems Open
We give simpler algebraic proofs of uniqueness for several Erd\H{o}s-Ko-Rado results, i.e., that the canonically intersecting families are the only largest intersecting families. Using these techniques, we characterize the largest partiall…
View article: Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)
Complexity Measures on the Symmetric Group and Beyond (Extended Abstract) Open
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a f…
View article: Complexity Measures on the Symmetric Group and Beyond
Complexity Measures on the Symmetric Group and Beyond Open
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a f…
View article: On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations
On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations Open
We explore some connections between association schemes and the analyses of the semidefinite programming (SDP) based convex relaxations of combinatorial optimization problems in the Lovász--Schrijver lift-and-project hierarchy. Our analysi…
View article: Matchings, hypergraphs, association schemes, and semidefinite optimization.
Matchings, hypergraphs, association schemes, and semidefinite optimization. Open
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 …
View article: On the Algebraic Combinatorics of Injections and its Applications to Injection Codes
On the Algebraic Combinatorics of Injections and its Applications to Injection Codes Open
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}…
View article: A Tight Lower Bound For Non-Coherent Index Erasure
A Tight Lower Bound For Non-Coherent Index Erasure Open
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 Ω(√n) lower bound on the quantum q…
View article: On the Algebraic Combinatorics of Injections and its Applications to\n Injection Codes
On the Algebraic Combinatorics of Injections and its Applications to\n Injection Codes Open
We consider the algebraic combinatorics of the set of injections from a\n$k$-element set to an $n$-element set. In particular, we give a new\ncombinatorial formula for the spherical functions of the Gelfand pair $(S_k\n\\times S_n, \\text{…
View article: A Tight Lower Bound for Non-coherent Index Erasure
A Tight Lower Bound for Non-coherent Index Erasure Open
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 q…
View article: A Tight Lower Bound for Index Erasure
A Tight Lower Bound for Index Erasure Open
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-coh…
View article: Matchings and Representation Theory
Matchings and Representation Theory Open
In this thesis we investigate the algebraic properties of matchings via representation theory. We identify three scenarios in different areas of combinatorial mathematics where the algebraic structure of matchings gives keen insight into t…
View article: Intersecting Families of Perfect Matchings
Intersecting Families of Perfect Matchings Open
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)!…
View article: A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank Open
For even k ∊ ℕ, the matchings connectivity matrix Mk is a binary matrix indexed by perfect matchings on k vertices; the entry at (M, M‘) is 1 iff M ∪ M‘ forms a single cycle. Cygan et al. (STOC 2013) showed that the rank of Mk over ℤ is an…
View article: A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank Open
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 $Θ(\sqrt 2^…
View article: Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs Open
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 forbid…