JCJoshua Cooper

Joshua Cooper

*This is an algorithmically generated author record based on publicly available information.

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


Joshua Cooper has a total of 61 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Distance Critical Graphs

    by Joshua Cooper, Gabrielle Tauscheck

    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

    Permutations minimizing the number of collinear triples

    by Joshua Cooper, Jack Hyatt

    We characterize the permutations of $$\mathbb {F}_q$$ 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

    by Joshua Cooper, Utku Okur

    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

    Principal eigenvectors in hypergraph Turán problems

    by Joshua Cooper, Dheer Noal Desai, Anurag Sahay

    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

    Note on the Spectra of Steiner Distance Hypermatrices

    by Joshua Cooper, Zhibin Du

    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

    by Joshua Cooper, Dheer Noal Desai, Anurag Sahay

    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

    A generalization of the Graham-Pollak tree theorem to even-order Steiner distance

    by Joshua Cooper, Gabrielle Tauscheck

    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 k vertices in a graph is the fewest number of edges in any connected subgraph containing those vertices; for k = 2 , this reduces to the ordinary definition of graphical distance. Here we show that the hyperdeterminant of the k th order Steiner distance hypermatrix is always nonzero if k is even, extending their result beyond k = 2 . Previously, the authors showed that the k -Steiner distance hyperdeterminant is always zero for k odd, so together this provides a generalization to all k . We conjecture that not just the vanishing, but the value itself, of the k -Steiner distance hyperdeterminant of an n -vertex tree depends only on k and n .


  • Open Access

    Characteristic Power Series of Graph Limits

    by Joshua N. Cooper

    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

    by Rory Mitchell, Joshua Cooper, Eibe Frank, Geoffrey Holmes

    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.