The log concavity of two graphical sequences

Minjia Shi, Lu Wang, Patrick SoléarXiv 2025 · DOI · arXiv

Introduction

In the study of discrete structures, the distribution of properties often follows a predictable "one-peak" pattern. This paper investigates the structural properties of graphs and association schemes through the lens of log-concavity. A sequence $s_i$ is log-concave if $s_i^2 \geq s_{i-1}s_{i+1}$ for all $i$, a property that implies unimodality—the sequence rises to a single peak and then falls without local fluctuations. The authors specifically examine two fundamental sequences: valencies ($v_i$), representing the number of vertices at distance $i$ from a starting vertex, and multiplicities ($m_i$), representing the dimensions of the eigenspaces of a graph's adjacency matrix.

The Challenge of Log-Concavity in Symmetric Graphs

While highly symmetric structures like distance-regular graphs often exhibit log-concave sequences, this behavior is not universal. Even vertex-transitive and distance-degree regular graphs can fail this test, demonstrating that symmetry alone does not guarantee a smooth distribution of distances.

The TriangleReplacedPetersen Graph serves as a counterexample, showing that high symmetry does not guarantee log-concave valencies.

As shown in Figure 1, the TriangleReplacedPetersen Graph provides a striking counterexample. Despite its high degree of symmetry, its valency sequence (1, 3, 4, 6...) fails log-concavity at the second term ($3^2 < 1 \times 4$). This highlights the need for more robust conditions to guarantee such "well-behaved" distributions.

Algebraic Framework and P-Q Duality

The research employs algebraic graph theory and the theory of association schemes to bridge the gap between distance-based properties (valencies) and spectral properties (multiplicities). A central tool in this analysis is the concept of P-Q duality.

The P-Q duality table illustrates the symmetry between parameters of the P-polynomial (distance-regular) and Q-polynomial association schemes.

By leveraging the symmetry between the intersection numbers ($P$) of distance-regular graphs and the Krein parameters ($Q$) of $Q$-polynomial association schemes (see Figure 2), the authors translate known results about valencies into new insights regarding multiplicities. They introduce "Property M" (monotonicity of Krein parameters) as a sufficient condition for log-concave multiplicities in $Q$-polynomial schemes, providing a new tool for analyzing complex network spectra.

Key Theoretical Insights

The paper presents several significant findings derived through generating functions and analytic theorems:

  1. Asymptotic Log-Concavity: Theorem 3 establishes that for any graph $A$, the valency sequence of its $n$-th Cartesian power ($A^{\square n}$) eventually becomes log-concave as $n$ increases. This suggests that increasing complexity through product operations eventually "smooths" the distribution into a predictable bell-like curve.
  2. Bounds for Strongly Regular Graphs (SRGs): The authors derive a new lower bound for the number of vertices $v$ in an SRG with degree $k$: $v \geq k + 1 + \lceil\sqrt{k}\rceil$.
  3. Applications in Coding Theory: The research proves that for projective two-weight codes, the weight distribution must satisfy specific log-concave inequalities ($A_{w_1}^2 \geq A_{w_2}$), offering a new diagnostic tool for vetting the existence of certain error-correcting codes.

Conclusion and Future Work

While this work makes significant strides, particularly in identifying sufficient conditions for log-concavity in Johnson and Grassmann schemes (when diameter $d < \frac{n+1}{2}$), several mysteries remain. The general unimodality of multiplicities for $Q$-polynomial schemes has been conjectured since the 1980s; while this paper provides a path forward via log-concavity, the full characterization of structures satisfying "Property M" remains an open and fertile area for future research.

Summary updated

BibTeX
@misc{shi2025log,
  author = {Minjia Shi and Lu Wang and Patrick Solé},
  title = {{The log concavity of two graphical sequences}},
  year = {2025},
  eprint = {2501.03709},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.03709},
}
Figure