Addressing Johnson graphs, complete multipartite graphs, odd cycles and\n other graphs

Noga Alon, Sebastian M. Cioabă, Brandon D. Gilbert, Jack H. Koolen, Brendan D. McKay

This paper, authored by a "dream team" of combinatorists including Noga Alon and Brendan McKay, dives into the addressing problem for graphs—a classic challenge in algebraic graph theory that bridges the gap between discrete geometry and communication networks.

TL;DR

The authors provide new optimal addressing lengths for Johnson graphs and multipartite graphs while using computational evidence to disprove a long-standing conjecture by Ron Graham. They prove that, contrary to previous intuition, most large graphs can be "addressed" with strings significantly shorter than the theoretical maximum of $n-1$.

What Problem Does This Paper Address?

In the 1970s, Graham and Pollak showed that any graph $G$ with $n$ vertices can be assigned "addresses" (strings of symbols) such that the distance between any two vertices in the graph is exactly equal to the distance between their addresses.

The standard alphabet is $\{0, 1, *\}$, where the distance between two strings is the number of positions where one has a 0 and the other has a 1. The symbol * acts as a wildcard: it doesn't contribute to the distance regardless of what it's paired with. An addressing is "optimal" if the length of these strings ($N$) is as small as possible.

While it was known that $N \le n-1$ for any connected graph, finding the exact minimum length $N_2(G)$ is notoriously difficult for specific graph families. Furthermore, Ron Graham famously conjectured that for almost all graphs, the minimum length is exactly $n-1$. This paper sets out to find optimal addresses for complex symmetric graphs and to test Graham's conjecture.

Methods

The authors employ a multi-pronged approach:

  1. Explicit Construction: For Johnson graphs $J(n, k)$, they define a specific function to generate addresses based on subset intersections.
  2. Eigenvalue Bounds: They utilize Witsenhausen’s lower bound, which relates the addressing length to the number of positive and negative eigenvalues of the graph's distance matrix.
  3. Exhaustive Computation: The team used custom backtracking algorithms to calculate the exact addressing lengths for every connected graph with up to 10 vertices. This required roughly 16 hours of CPU time and clever pruning of the search space using graph automorphisms.
  4. Probabilistic Method: To tackle the "almost all graphs" question, they used the properties of Erdős-Rényi random graphs $G(n, 0.5)$.

Datasets

The "dataset" in this study is the complete set of non-isomorphic connected graphs for small $n$:

  • $n \le 9$: Exhaustive distribution of $N_2(G)$ for all 261,080 connected graphs.
  • $n = 10$: A random sample of 1/1000 of the ~11.7 million connected graphs to estimate the distribution.
  • Specific Families: Johnson graphs $J(n, k)$, complete multipartite graphs $K_{a,b,c}$, and odd cycles $C_{2n+1}$.

Key Insights and Ideas

  • The Power of the Wildcard: The * symbol is what allows the addressing length to be shorter than the number of vertices. It effectively allows the graph to be "squashed" into a lower-dimensional hypercube.
  • Johnson Graph Sub-optimality: While the authors found a general addressing of length $k(n-k)$ for Johnson graphs, they discovered via computer search that for $J(6, 3)$, the length is 8—shorter than their general construction's 9. This reveals that even highly symmetric graphs have "hidden" efficiencies.
  • Graham's Intuition was Wrong: For decades, it was suspected that "random" graphs were hard to address ($N = n-1$). The authors' data for $n=9$ and $n=10$ showed a clear trend: as $n$ increases, the percentage of graphs requiring $n-1$ symbols drops sharply.

Key Results

  • Random Graphs: The authors proved that for almost all graphs on $n$ vertices, $N_2(G) \le n - (2 - o(1))\log_2 n$. This formally disproves Graham's conjecture that $N_2(G) = n-1$ for almost all graphs.
  • Johnson Graphs: Established that $N_2(J(n, k)) \le k(n-k)$. They proved this is optimal for $k=1$ and several small cases of $k=2$.
  • Odd Cycles: They investigated the addressing of odd cycles with a larger alphabet $\{0, 1, 2, *\}$. They found that a previously observed pattern ($N_3(C_{2n+1}) = n+1$) holds for small cycles but fails starting at $C_{13}$.
  • Multipartite Graphs: They provided exact values for $N_2(K_{a,b,1}) = a+b-1$ and established tighter upper and lower bounds for larger multipartite structures.

Limitations and Future Work

  • The Johnson Gap: While the authors provided a general construction for Johnson graphs, the $J(6, 3)$ result shows their construction isn't always optimal. Determining the exact value of $N_2(J(n, k))$ for general $n, k$ remains an open problem.
  • Computational Ceiling: The exhaustive search was limited to $n=10$. While the trend is clear, the exact behavior of the distribution for $n=20$ or $n=100$ is still based on asymptotic proofs rather than exact counts.
  • Alphabet Expansion: The study of $r$-symbol addressings ($r > 2$) is still in its infancy compared to the binary case, with many patterns (like those in odd cycles) appearing and then disappearing as $n$ grows.

Summary updated

Abstract

Graham and Pollak showed that the vertices of any graph $G$ can be addressed\nwith $N$-tuples of three symbols, such that the distance between any two\nvertices may be easily determined from their addresses. An addressing is\noptimal if its length $N$ is minimum possible.\n In this paper, we determine an addressing of length $k(n-k)$ for the Johnson\ngraphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when\n$k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem\nas well as a variation of it in which the alphabet used has more than three\nsymbols, for other graphs such as complete multipartite graphs and odd cycles.\nWe also present computations describing the distribution of the minimum length\nof addressings for connected graphs with up to $10$ vertices. Motivated by\nthese computations we settle a problem of Graham, showing that most graphs on\n$n$ vertices have an addressing of length at most $n-(2-o(1))\\log_2 n$.\n
BibTeX
@article{alon2021addressing,
  author = {Noga Alon and Sebastian M. Cioabă and Brandon D. Gilbert and Jack H. Koolen and Brendan D. McKay},
  title = {{Addressing Johnson graphs, complete multipartite graphs, odd cycles and\textbackslash\{\}n other graphs}},
  journal = {Exp. Math.},
  year = {2021},
  doi = {10.1080/10586458.2018.1542643},
}

Loading related content...

Figure