Source-linked AI summary
Kronecker Products, Polarity Quotients and Large Graph Constructions
Kelly Isham, Kartik Lakhotia, Laura Monroe, Fabrizio Petrini
TL;DR
The paper addresses how Kronecker products and polarity quotients interact for bipartite graphs admitting polarity. It proves structural and diameter results, then applies them to generalized polygons to construct graph families of diameters 2, 3, and 5 that approach the Moore bound, including new diameter-3 records at selected degrees.
Problem
Existing constructions seek large graphs for fixed degree and diameter, while the interaction between Kronecker products and polarity quotients requires structural treatment.
Method
The paper proves an isomorphism between composed-polarity quotients of Kronecker-product components and Kronecker products of factor polarity quotients, then applies the results to generalized polygons.
Results
The constructions yield families of diameters 2, 3, and 5 approaching the Moore bound, with new diameter-3 graphs larger than previously known for degrees 18, 19, and 20.
Takeaways & Limitations
Polarity-quotient and Kronecker-product constructions provide large low-diameter graphs, including examples relevant to degree-diameter constructions and high-performance network topologies.
Takeaways & Limitations
The constructions use connected bipartite factor graphs allowing self-loops and cover an infinite but sparse set of degrees; the authors also note that the Moore-bound interpretation may reflect specific exceptions.
Abstract
from arXiv · showhide
In this paper, we establish a structural compatibility between the Kronecker product of bipartite graphs that admit polarity and their polarity quotient, and provide a sharp upper bound on the diameter of these graphs. For certain factor graphs, the diameter of the Kronecker product meets the upper bound on diameter, among them the generalized polygons. Generalized polygons with their polarity quotients have been notably used in the past to construct very large graphs. We apply the structural theorems in the paper to generalized polygons $\mathbb{G}_n(q,q)$ used as factor graphs, and build three new families of graphs of large order covering an infinite but sparse set of degrees, one of diameter $2$, one of diameter $3$ and one of diameter $5$. These asymptotically approach a theoretical upper bound on graph size as orders $q$ and $r$ of the generalized polygon factors increase. As an example, we develop one such family, derived from generalized quadrangles, and construct new diameter-$3$ graphs of low degree that are larger than any previously known at their degrees.
1. Introduction
The paper proves that polarity quotients and Kronecker products are structurally compatible, derives diameter bounds, and applies these results to generalized polygons to construct large graphs approaching the Moore bound.
- Main Results: Theorem 1.1 shows that the polarity quotient of a Kronecker-product component is isomorphic to the Kronecker product of the factor polarity quotients.This establishes the paper’s central structural compatibility result.
- Main Results: Theorem 1.2 bounds the common diameter of these isomorphic graphs using the diameters of the factor graphs and their polarity quotients.Corollary 5.3 gives an exact diameter when each parent graph and quotient differ in diameter by 1.
- Applications to Generalized Polygons: For generalized polygons, the constructed quotient-product graphs have degree (q + 1)(r + 1) and diameter n − 1, approaching a fraction fq of the Moore bound as admissible r →∞.For thick generalized n-gons, the parent and polarity-quotient diameters are n and n − 1, respectively.
- Applications to Generalized Polygons: The resulting families cover diameters 2, 3, and 5 and asymptotically approach the Moore bound as q and r increase.The constructions apply to generalized polygons, including thin cases and digons treated to cover all generalized n-gons admitting polarity.
2. Notation and Conventions
The paper standardizes notation for graph products, generalized polygons, and self-loop handling. Its conventions retain self-loops during construction but delete them before comparisons with simple graphs.
- The paper uses “Kronecker product” for the direct, categorical, tensor, or graph-conjunction product, depending on terminology in prior work.
- Self-loops are allowed in connected factor graphs and can create extra Kronecker-product edges needed for the paper’s theorems.
- Self-loops are deleted only after constructions are complete, because they do not affect graph order or diameter but increase degree.
- Generalized n-gons are represented by bipartite point-line incidence graphs unless stated otherwise.
3. Preliminaries
The preliminaries place the paper’s results in prior work on graph quotients, polarities, and the degree-diameter problem. They motivate new constructions by the scarcity of near-Moore graphs and the sparse degree coverage of existing polarity-based families.
- Earlier work showed that quotients of graph products can form unspecified subdirect products, whereas this paper targets full direct-product structure.
- The degree-diameter problem seeks the largest simple graph for fixed maximum degree ∆ and diameter D, with the Moore bound giving a theoretical order upper bound.
- No Moore graphs exist for diameter D ≥3 and degree ∆≥3, and MB(∆, D) − 2 is the best known upper bound for most graph families.
- Polarity quotients of finite projective planes yield diameter-2 graphs asymptotically approaching the Moore bound for every degree q + 1 with q a prime power.
- Existing generalized-quadrangle and generalized-hexagon constructions approach the Moore bound but cover sparse degree families.
- Delorme’s reduced-Kronecker construction from a generalized quadrangle G4(s,t) has order (1+s)(1+t)(1+st)^2 and degree (1+s)(1+t).
4. Background: Products and Polarities
This section defines the Kronecker product, polarities, polarity quotients, and reversing automorphisms, then records structural facts about components, degrees, diameters, and vertex counts.
- The Kronecker Product: For graphs H and K, H ⊗ K has vertex pairs and adjacency exactly when both corresponding factor pairs are adjacent.
- The Kronecker Product: The Kronecker product of two bipartite graphs has two disconnected bipartite components with explicitly determined same-part and cross-part vertex sets.
- Polarities: A polarity is an involutional graph automorphism that exchanges the two parts of a bipartite graph.
- Polarities: A polarity quotient contracts polarity orbits into vertices, merges parallel edges, and retains self-loops.
- Polarities: After quotient self-loops are removed, the quotient has the original maximum degree exactly when some maximum-degree vertices are nonabsolute.
- Reversing Automorphisms: The two Kronecker components are isomorphic if and only if at least one factor has a bipartition-reversing automorphism; the reduced product is one such component.
- Reversing Automorphisms: For the full product G, degree, diameter, and order are ∆(H)∆(K), max(D(H),D(K)), and |A_H||A_K| + |B_H||B_K|, respectively.
- Reversing Automorphisms: If both factors admit polarity, then both their full and reduced Kronecker products admit the composed polarity.
5. Proofs of Structural Results
The proofs establish that polarity quotienting commutes with the reduced Kronecker product and derive diameter bounds for the resulting isomorphic graphs. Special factor families, including generalized polygons, attain the exact upper-bound case.
- Extensions and Applications: The same structural operations extend to any number of bipartite factors admitting polarity.
- Structural Isomorphism: Theorem 1.1 identifies P(H ⊙ K) with the direct product P_H(H) ⊗ P_K(K) via a bijection between composed-polarity orbits and pairs of quotient orbits.
- Structural Isomorphism: The full-product quotient consists of two disjoint copies of the factor-quotient product.
- Diameter Bounds: Theorem 1.2 bounds the common diameter of P(H ⊙ K) and P_H(H) ⊗ P_K(K) using factor and quotient diameters.
- Diameter Bounds: When both polarity quotients have diameter one less than their factors, the resulting quotient-product diameter is max(D(H), D(K)) − 1.
- Extensions and Applications: Generalized n-gons, ladder graphs, and joined-star graphs provide factor families for which the exact diameter is known after applying the corollary.
6. Structural Results Applied to Generalized Polygons
Applying the structural theorems to generalized polygons yields exact-diameter constructions and infinite graph families for diameters 2, 3, and 5 whose orders asymptotically approach the Moore bound.
- Generalized polygons: Generalized n-gons and their polarity quotients provide factor graphs for applying the paper’s Kronecker-product results.The constructions use incidence-graph representations of generalized polygons, including thin polygons with order (1, 1).
- Thin polygons: Reflection polarities on thin generalized n-gons yield quotient paths P_n with endpoint loops and diameter n − 1.Each thin generalized n-gon G_n(1, 1) admits n reflection polarities, and its quotient is P_n.
- Polarity quotients: For non-rotation polarities, the polarity quotient of a generalized n-gon has diameter one less than the incidence graph.This relation extends from thick polygons to the thin cases under the appropriate polarity.
- Product constructions: Products of generalized m-gons and n-gons produce isomorphic quotient graphs of exact diameter max(m, n) − 1.The two equivalent constructions are P(G_m ⊙ G_n) and P_m(G_m) ⊗ P_n(G_n).
- Large graph families: The resulting families have degrees (q + 1)(r + 1), and their orders asymptotically approach the Moore bound as q and r increase.This follows because the polygon polarity quotients themselves asymptotically approach the bound and the product construction preserves that behavior.
- Replication: Replication of absolute vertices increases degree by k while preserving diameter and adds k(q^(m/2) + 1)(r^(n/2) + 1) vertices.The replicated graph has degree (1 + q)(1 + r) + k and diameter max(m, n) − 1.
7. A Generalized Quadrangle Example, With New Largest Diam-3 Graphs
Generalized quadrangles, including the thin quadrangle G_4(1,1), yield diameter-3 graph families with new degree coverage and orders exceeding previous records at degrees 18, 19, and 20.
- 7.1. Polarities of Generalized Quadrangles: The quadrangle construction uses polarity quotients of G_4(q,q) factors, including q = 1 and q = 2^(2m+1).The product has degree (1 + q_1)(1 + q_2), diameter 3, and an order given by the construction’s vertex formula.
- 7.2. New Graphs: Using G_4(1,1) and G_4(q,q) gives degree 2(q + 1), order 4(q^3 + q^2 + q + 1), and an asymptotic Moore-bound ratio of 1/2.For q = 2^(2m+1), these degrees are not covered by the Delorme graphs.
- 7.2. New Graphs: Using q_1 = 2 and q_2 = q gives degree 3(q + 1), order 15(q^3 + q^2 + q + 1), and an asymptotic Moore-bound ratio of 15/27.These degrees also include values not covered by the Delorme graphs for q = 2^(2m+1).
- 7.2. New Graphs: For degree 27, the construction gives 8775 vertices; replication then gives 9100, 9425, and 9750 vertices at degrees 28, 29, and 30.The replicated increments use 325 absolute vertices.
- 7.3. Results: The product constructions provide more degree values as intervals grow, while covering degrees different from those supplied by other generalized-quadrangle constructions.Their degree coverage is sparser than the comparison family but enlarges the set of near-Moore-bound degrees.
- 7.3. Results: The constructions add larger diameter-3 entries to the Degree-Diameter Table for degrees 18, 19, and 20.These are the largest degrees appearing in that table.
8. Conclusions
The paper presents new large graph families approaching the Moore bound, while noting that few such families are known and that their broader significance remains uncertain. It also points to applications in low-latency network topologies.
- Graphs of diameters 2, 3 and 5 were constructed that approach the Moore bound on graph size.
- Some constructed graphs are larger than any previously known, to the authors’ knowledge.
- Few known graph families asymptotically approach the Moore bound, whose best-known competing bounds differ by only 1 or 2 in most cases.
- The broader interpretation is unresolved: these families may support the tightness of the Moore bound or instead be exceptions to a tighter undiscovered general bound.
- Large low-diameter graph topologies are relevant to high-performance networks because lower diameter gives better network latency.