Joshua Cooper
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Joshua Cooper has a total of 61 co-authors. Here are the top co-authors by number of shared publications:
Joel Spencer
Courant Institute of Mathematical Sciences, New York University, New York, New York 10012-1185
5 shared publications- Aaron Dutle
Department of Mathematics, University of South Carolina, Columbia, SC, USA
3 shared publications Benjamin Doerr
Department 1: Algorithms and Complexity, Max-Planck-Institut für Informatik, Saarbrücken 66123, Germany
3 shared publications- Gábor Tardos
HUN‐REN Alfréd Rényi Institute of Mathematics Budapest Hungary
3 shared publications Aaron Dutle
2 shared publications- Anton Swifton
Department of Mathematics, University of South Carolina, Columbia, S.C., U.S.A.
2 shared publications
Latest Publications
- 1 January 2026
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 46 (3) , 677
Multigraphs with a unique partition into cycles
- 1 January 2026
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 46 (3) , 677
Multigraphs with a unique partition into cycles
- Open Access
- 27 July 2025
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 41 (4) , 1-14
Distance Critical Graphs
In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on n vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? Such worst-case graphs are known as “distance critical”, and were first studied by Erdős and Howorka. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions.
- 27 July 2025
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 41 (4) , 1-14
Open AccessDistance Critical Graphs
In 1971, Graham and Pollak provided a formula for the determinant of the distance matrix of any tree on n vertices. Yan and Yeh reproved this by exploiting the fact that pendant vertices can be deleted from trees without changing the remaining entries of the distance matrix. Considering failures of their argument to generalize invites the question: which graphs have the property that deleting any one vertex results in a change to some pairwise distance? Such worst-case graphs are known as “distance critical”, and were first studied by Erdős and Howorka. This work explores the structural properties of distance critical graphs, preservation of distance-criticality by products, and the nature of extremal distance critical graphs. We end with a few open questions.
- Open Access
- 23 April 2025
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 93 (8) , 3135-3142
Permutations minimizing the number of collinear triples
We characterize the permutations of $$\mathbb {F}_q$$ whose graph minimizes the number of collinear triples and describe the lexicographically-least one, confirming a conjecture of Cooper-Solymosi. This question is connected to Dudeney’s No-3-in-a-Line problem, the Heilbronn triangle problem, and the structure of finite plane Kakeya sets. We discuss a connection with complete sets of mutually orthogonal latin squares and state a few open problems primarily about general finite affine planes.- 23 April 2025
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 93 (8) , 3135-3142
Open AccessPermutations minimizing the number of collinear triples
We characterize the permutations of $$\mathbb {F}_q$$ whose graph minimizes the number of collinear triples and describe the lexicographically-least one, confirming a conjecture of Cooper-Solymosi. This question is connected to Dudeney’s No-3-in-a-Line problem, the Heilbronn triangle problem, and the structure of finite plane Kakeya sets. We discuss a connection with complete sets of mutually orthogonal latin squares and state a few open problems primarily about general finite affine planes. - Open Access
Multigraphs with Unique Partition into Cycles
Due to Veblen's Theorem, if a connected multigraph $X$ has even degrees at each vertex, then it is Eulerian and its edge set has a partition into cycles. In this paper, we show that an Eulerian multigraph has a unique partition into cycles if and only if it belongs to the family $\mathcal{S}$, ``bridgeless cactus multigraphs", elements of which are obtained by replacing every edge of a tree with a cycle of length $\geq 2$. Other characterizing conditions for bridgeless cactus multigraphs and digraphs are provided. Furthermore, for a digraph $D$, we list conditions equivalent to having a unique Eulerian circuit, thereby generalizing a previous result of Arratia-Bollobás-Sorkin. In particular, we show that digraphs with a unique Eulerian circuit constitute a subfamily of $\mathcal{S}$, namely, ``Christmas cactus digraphs".Open AccessMultigraphs with Unique Partition into Cycles
Due to Veblen's Theorem, if a connected multigraph $X$ has even degrees at each vertex, then it is Eulerian and its edge set has a partition into cycles. In this paper, we show that an Eulerian multigraph has a unique partition into cycles if and only if it belongs to the family $\mathcal{S}$, ``bridgeless cactus multigraphs", elements of which are obtained by replacing every edge of a tree with a cycle of length $\geq 2$. Other characterizing conditions for bridgeless cactus multigraphs and digraphs are provided. Furthermore, for a digraph $D$, we list conditions equivalent to having a unique Eulerian circuit, thereby generalizing a previous result of Arratia-Bollobás-Sorkin. In particular, we show that digraphs with a unique Eulerian circuit constitute a subfamily of $\mathcal{S}$, namely, ``Christmas cactus digraphs". - Open Access
- 23 October 2024
- Published by University of Wyoming Libraries in The Electronic Journal of Linear Algebra
- Vol. 40, 697-713
Principal eigenvectors in hypergraph Turán problems
For a general class of hypergraph Turán problems with uniformity $r$, we investigate the principal eigenvector for the $p$-spectral radius (in the sense of Keevash-Lenz-Mubayi and Nikiforov) for the extremal graphs, showing in a strong sense that these eigenvectors have close to equal weight on each vertex (equivalently, showing that the principal ratio is close to $1$). We investigate the sharpness of our result; it is likely sharp for the Turán tetrahedron problem. In the course of this latter discussion, we establish a lower bound on the $p$-spectral radius of an arbitrary $r$-graph in terms of the degrees of the graph. This builds on earlier work of Cardoso-Trevisan, Li-Zhou-Bu, Cioabă-Gregory, and Zhang. The case $1 < p < r$ of our results leads to some subtleties connected to Nikiforov's notion of $k$-tightness, arising from the Perron-Frobenius theory for the $p$-spectral radius. We raise a conjecture about these issues and provide some preliminary evidence for our conjecture.- 23 October 2024
- Published by University of Wyoming Libraries in The Electronic Journal of Linear Algebra
- Vol. 40, 697-713
Open AccessPrincipal eigenvectors in hypergraph Turán problems
For a general class of hypergraph Turán problems with uniformity $r$, we investigate the principal eigenvector for the $p$-spectral radius (in the sense of Keevash-Lenz-Mubayi and Nikiforov) for the extremal graphs, showing in a strong sense that these eigenvectors have close to equal weight on each vertex (equivalently, showing that the principal ratio is close to $1$). We investigate the sharpness of our result; it is likely sharp for the Turán tetrahedron problem. In the course of this latter discussion, we establish a lower bound on the $p$-spectral radius of an arbitrary $r$-graph in terms of the degrees of the graph. This builds on earlier work of Cardoso-Trevisan, Li-Zhou-Bu, Cioabă-Gregory, and Zhang. The case $1 < p < r$ of our results leads to some subtleties connected to Nikiforov's notion of $k$-tightness, arising from the Perron-Frobenius theory for the $p$-spectral radius. We raise a conjecture about these issues and provide some preliminary evidence for our conjecture. - Open Access
- 12 July 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (3) , P3.4
Note on the Spectra of Steiner Distance Hypermatrices
The Steiner distance of a set of vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices. The order-$k$ Steiner distance hypermatrix of an $n$-vertex graph is the $n \times \cdots \times n$ ($k$ terms) array indexed by vertices, whose entries are the Steiner distances of their corresponding indices. In the case of $k=2$, this reduces to the classical distance matrix of a graph. Graham and Pollak showed in 1971 that the determinant of the distance matrix of a tree only depends on its number $n$ of vertices. Here, we show that the hyperdeterminant of the Steiner distance hypermatrix of a tree vanishes if and only if (a) $n \geq 3$ and $k$ is odd, (b) $n=1$, or (c) $n=2$ and $k \equiv 1 \pmod{6}$. Two proofs are presented of the $n=2$ case - the other situations were handled previously - and we use the argument further to show that the distance spectral radius for $n=2$ is equal to $2^{k-1}-1$. Some related open questions are also discussed.- 12 July 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (3) , P3.4
Open AccessNote on the Spectra of Steiner Distance Hypermatrices
The Steiner distance of a set of vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices. The order-$k$ Steiner distance hypermatrix of an $n$-vertex graph is the $n \times \cdots \times n$ ($k$ terms) array indexed by vertices, whose entries are the Steiner distances of their corresponding indices. In the case of $k=2$, this reduces to the classical distance matrix of a graph. Graham and Pollak showed in 1971 that the determinant of the distance matrix of a tree only depends on its number $n$ of vertices. Here, we show that the hyperdeterminant of the Steiner distance hypermatrix of a tree vanishes if and only if (a) $n \geq 3$ and $k$ is odd, (b) $n=1$, or (c) $n=2$ and $k \equiv 1 \pmod{6}$. Two proofs are presented of the $n=2$ case - the other situations were handled previously - and we use the argument further to show that the distance spectral radius for $n=2$ is equal to $2^{k-1}-1$. Some related open questions are also discussed. - Open Access
Principal eigenvectors and principal ratios in hypergraph Turán problems
For a general class of hypergraph Turán problems with uniformity $r$, we investigate the principal eigenvector for the $p$-spectral radius (in the sense of Keevash--Lenz--Mubayi and Nikiforov) for the extremal graphs, showing in a strong sense that these eigenvectors have close to equal weight on each vertex (equivalently, showing that the principal ratio is close to $1$). We investigate the sharpness of our result; it is likely sharp for the Turán tetrahedron problem. In the course of this latter discussion, we establish a lower bound on the $p$-spectral radius of an arbitrary $r$-graph in terms of the degrees of the graph. This builds on earlier work of Cardoso--Trevisan, Li--Zhou--Bu, Cioabă--Gregory, and Zhang. The case $1 < p < r$ of our results leads to some subtleties connected to Nikiforov's notion of $k$-tightness, arising from the Perron-Frobenius theory for the $p$-spectral radius. We raise a conjecture about these issues, and provide some preliminary evidence for our conjecture.Open AccessPrincipal eigenvectors and principal ratios in hypergraph Turán problems
For a general class of hypergraph Turán problems with uniformity $r$, we investigate the principal eigenvector for the $p$-spectral radius (in the sense of Keevash--Lenz--Mubayi and Nikiforov) for the extremal graphs, showing in a strong sense that these eigenvectors have close to equal weight on each vertex (equivalently, showing that the principal ratio is close to $1$). We investigate the sharpness of our result; it is likely sharp for the Turán tetrahedron problem. In the course of this latter discussion, we establish a lower bound on the $p$-spectral radius of an arbitrary $r$-graph in terms of the degrees of the graph. This builds on earlier work of Cardoso--Trevisan, Li--Zhou--Bu, Cioabă--Gregory, and Zhang. The case $1 < p < r$ of our results leads to some subtleties connected to Nikiforov's notion of $k$-tightness, arising from the Perron-Frobenius theory for the $p$-spectral radius. We raise a conjecture about these issues, and provide some preliminary evidence for our conjecture. - Open Access
- 1 January 2024
- Published by Walter de Gruyter GmbH in Special Matrices
- Vol. 12 (1)
A generalization of the Graham-Pollak tree theorem to even-order Steiner distance
Graham and Pollak showed in 1971 that the determinant of a tree’s distance matrix depends only on its number of vertices, and, in particular, it is always nonzero. The Steiner distance of a collection of vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for , this reduces to the ordinary definition of graphical distance. Here we show that the hyperdeterminant of the th order Steiner distance hypermatrix is always nonzero if is even, extending their result beyond . Previously, the authors showed that the -Steiner distance hyperdeterminant is always zero for odd, so together this provides a generalization to all . We conjecture that not just the vanishing, but the value itself, of the -Steiner distance hyperdeterminant of an -vertex tree depends only on and .- 1 January 2024
- Published by Walter de Gruyter GmbH in Special Matrices
- Vol. 12 (1)
Open AccessA generalization of the Graham-Pollak tree theorem to even-order Steiner distance
Graham and Pollak showed in 1971 that the determinant of a tree’s distance matrix depends only on its number of vertices, and, in particular, it is always nonzero. The Steiner distance of a collection of vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for , this reduces to the ordinary definition of graphical distance. Here we show that the hyperdeterminant of the th order Steiner distance hypermatrix is always nonzero if is even, extending their result beyond . Previously, the authors showed that the -Steiner distance hyperdeterminant is always zero for odd, so together this provides a generalization to all . We conjecture that not just the vanishing, but the value itself, of the -Steiner distance hyperdeterminant of an -vertex tree depends only on and . - Open Access
Characteristic Power Series of Graph Limits
In this note, we show how to obtain a "characteristic power series" of graphons -- infinite limits of dense graphs -- as the limit of normalized reciprocal characteristic polynomials. This leads to a new characterization of graph quasi-randomness and another perspective on spectral theory for graphons, a complete description of the function in terms of the spectrum of the graphon as a self-adjoint kernel operator. Interestingly, while we apply a standard regularization to classical determinants, it is unclear how necessary this is.
Open AccessCharacteristic Power Series of Graph Limits
In this note, we show how to obtain a "characteristic power series" of graphons -- infinite limits of dense graphs -- as the limit of normalized reciprocal characteristic polynomials. This leads to a new characterization of graph quasi-randomness and another perspective on spectral theory for graphons, a complete description of the function in terms of the spectrum of the graphon as a self-adjoint kernel operator. Interestingly, while we apply a standard regularization to classical determinants, it is unclear how necessary this is.
- Open Access
Sampling Permutations for Shapley Value Estimation
Game-theoretic attribution techniques based on Shapley values are used to interpret black-box machine learning models, but their exact calculation is generally NP-hard, requiring approximation methods for non-trivial models. As the computation of Shapley values can be expressed as a summation over a set of permutations, a common approach is to sample a subset of these permutations for approximation. Unfortunately, standard Monte Carlo sampling methods can exhibit slow convergence, and more sophisticated quasi-Monte Carlo methods have not yet been applied to the space of permutations. To address this, we investigate new approaches based on two classes of approximation methods and compare them empirically. First, we demonstrate quadrature techniques in a RKHS containing functions of permutations, using the Mallows kernel in combination with kernel herding and sequential Bayesian quadrature. The RKHS perspective also leads to quasi-Monte Carlo type error bounds, with a tractable discrepancy measure defined on permutations. Second, we exploit connections between the hypersphere $\mathbb{S}^{d-2}$ and permutations to create practical algorithms for generating permutation samples with good properties. Experiments show the above techniques provide significant improvements for Shapley value estimates over existing methods, converging to a smaller RMSE in the same number of model evaluations.Open AccessSampling Permutations for Shapley Value Estimation
Game-theoretic attribution techniques based on Shapley values are used to interpret black-box machine learning models, but their exact calculation is generally NP-hard, requiring approximation methods for non-trivial models. As the computation of Shapley values can be expressed as a summation over a set of permutations, a common approach is to sample a subset of these permutations for approximation. Unfortunately, standard Monte Carlo sampling methods can exhibit slow convergence, and more sophisticated quasi-Monte Carlo methods have not yet been applied to the space of permutations. To address this, we investigate new approaches based on two classes of approximation methods and compare them empirically. First, we demonstrate quadrature techniques in a RKHS containing functions of permutations, using the Mallows kernel in combination with kernel herding and sequential Bayesian quadrature. The RKHS perspective also leads to quasi-Monte Carlo type error bounds, with a tractable discrepancy measure defined on permutations. Second, we exploit connections between the hypersphere $\mathbb{S}^{d-2}$ and permutations to create practical algorithms for generating permutation samples with good properties. Experiments show the above techniques provide significant improvements for Shapley value estimates over existing methods, converging to a smaller RMSE in the same number of model evaluations.