1 citations · 2 across the 14 of their papers we have counts for
19 papers
Intersecting Families of Spanning Trees of
Gordian C. Bruns, Dheer Noal Desai, Alexander L. Gavrilyuk +2
A family of spanning trees of a graph is -intersecting if any pair of spanning trees in the family has or more edges in common. For sufficiently large and $t \leq n/C\lo…
Forbidden Intersection Theorems for Matrix Spaces
Esty Kelman, Nathan Lindzey, Ohad Sheinfeld
A family of matrices is {-intersection-free} if for all . A \em…
An Eventown Result for Permutations
Nathan Lindzey
A family of permutations is even-cycle-intersecting if has an even cycle for all . We show that if $\mathcal{F} \subseteq…
Intersecting Families of Spanning Trees
Peter Frankl, Glenn Hurlbert, Ferdinand Ihringer +4
A family of spanning trees of the complete graph on vertices is \emph{-intersecting} if any two members have a forest on edges in common. We prove an…
Jack Derangements
Nathan Lindzey
For each integer partition we give a simple combinatorial expression for the sum of the Jack character over the integer partitions of with no singleton part…
Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings
Gilad Chase, Neta Dafni, Yuval Filmus +1
We give a characterization of the largest -intersecting families of permutations of and of perfect matchings of the complete graph for all …
Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems
Yuval Filmus, Nathan Lindzey
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…
Complexity Measures on the Symmetric Group and Beyond
Neta Dafni, Yuval Filmus, Noam Lifshitz +2
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, decisi…
On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations
Yu Hin Au, Nathan Lindzey, Levent Tunçel
We explore some connections between association schemes and the analyses of the semidefinite programming (SDP) based convex relaxations of combinatorial optimization problems in th…
On the Algebraic Combinatorics of Injections and its Applications to Injection Codes
Peter J. Dukes, Ferdinand Ihringer, Nathan Lindzey
We consider the algebraic combinatorics of the set of injections from a -element set to an -element set. In particular, we give a new combinatorial formula for the spherical…
A Tight Lower Bound for Non-coherent Index Erasure
Nathan Lindzey, Ansis Rosmanis
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…
Intersecting Families of Perfect Matchings
Nathan Lindzey
A family of perfect matchings of is - if any two members share or more edges. We prove for any that every -intersecting family o…
Stability for Intersecting Families of Perfect Matchings
Nathan Lindzey
A family of perfect matchings of is if any two of its members have an edge in common. It is known that if is family of intersecting perfect ma…
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
Radu Curticapean, Nathan Lindzey, Jesper Nederlof
For even , the matchings connectivity matrix encodes which pairs of perfect matchings on vertices form a single cycle. Cygan et al. (STOC 2013) showed that th…
Erdős-Ko-Rado for Perfect Matchings
Nathan Lindzey
A perfect matching of a complete graph is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if $…
Speeding Up Graph Algorithms via Switching Classes
Nathan Lindzey
Given a graph , a vertex switch of results in a new graph where neighbors of become nonneighbors and vice versa. This operation gives rise to an equivalence rel…
Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
Nathan Lindzey, Ross M. McConnell
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…
Simple DFS on the Complement of a Graph and on Partially Complemented Digraphs
Benson Joeris, Nathan Lindzey, Ross M. McConnell +1
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 is a…
On Finding Lekkerkerker-Boland Subgraphs
Nathan Lindzey, Ross McConnell
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…