Abstract
In this paper, we deal with a generalization $\Gamma(\Omega,q)$ of the bipartite graphs $D(k,q)$ proposed by Lazebnik and Ustimenko, where $\Omega$ is a set of binary sequences that are adopted to index the entries of the vertices. A few sufficient conditions on $\Omega$ for $\Gamma(\Omega,q)$ to admit a variety of automorphisms are proposed. A sufficient condition for $\Gamma(\Omega,q)$ to be edge-transitive is proposed further. A lower bound of the number of the connected components of $\Gamma(\Omega,q)$ is given by showing some invariants for the components. For $\Gamma(\Omega,q)$, paths and cycles which contain vertices of some specified form are investigated in details. Some lower bounds for the girth of $\Gamma(\Omega,q)$ are then shown. In particular, one can give very simple conditions on the index set $\Omega$ so as to assure the generalized graphs $\Gamma(\Omega,q)$ to be a family of graphs with large girth.
Introduction
In extremal graph theory, the search for "sparse but sturdy" graphs—those with relatively few edges but no small cycles—is a fundamental pursuit. These structures, known as graphs with large girth, are essential for designing high-performance error-correcting codes (such as LDPC codes), cryptographic protocols, and efficient communication networks.
A landmark in this field is the bipartite graph $D(k,q)$, introduced by Lazebnik and Ustimenko. While $D(k,q)$ is celebrated for being $q$-regular, edge-transitive, and possessing a large girth, its specific algebraic construction is somewhat rigid. This paper introduces $\Gamma(\Omega, q)$, a sophisticated generalization that extends the classical $D(k,q)$ and Wenger graphs $G_n(q)$ into a more flexible framework using sets of binary sequences ($\Omega$) to index vertex entries.
The Algebraic Framework of $\Gamma(\Omega, q)$
The authors employ an algebraic construction where vertices are represented as vectors over a finite field $\mathbb{F}_q$. The core innovation is the use of a set of binary sequences, denoted as $\Omega$, to index the coordinates of these vectors.
Adjacency via Equations
In this bipartite construction, two vertices (one from the "left" partition and one from the "right") are connected if their coordinates satisfy a specific system of linear and non-linear equations. This method allows the global properties of the graph—such as symmetry and girth—to be directly dictated by the combinatorial structure of the sequence set $\Omega$.
One critical condition identified is that $\Omega$ be "prefix-closed" (Condition C1). If a sequence is in $\Omega$, its prefix must also be in $\Omega$. This hierarchical structure allows the defining equations to be solved iteratively, which is the key to proving the graph's fundamental properties.
Symmetry and Edge-Transitivity
To evaluate the symmetry of $\Gamma(\Omega, q)$, the authors construct explicit automorphisms—bijective maps that preserve adjacency. The paper identifies specific combinatorial conditions on $\Omega$ that guarantee the graph is edge-transitive.
Specifically, if $\Omega$ contains all subsequences generated by certain bit-deletion rules (referred to as $H_0$ and $H_1$), the graph attains a high degree of symmetry. This demonstrates that edge-transitivity does not require the rigid structure of the original $D(k,q)$, but can be achieved through a variety of sequence sets that satisfy these bit-wise deletion properties.
Connectivity and Invariants
Analysis shows that $\Gamma(\Omega, q)$ is often a disconnected graph. To understand its structure, the authors identify algebraic invariants—expressions that remain constant across all vertices within a single connected component.
By utilizing these invariants, the paper establishes a lower bound for the number of separate connected components: at least $q^{|\Omega^*| - h(\Omega, q)}$, where $h$ is a value derived from the equivalence classes of the sequences. This provides a clear mathematical bound on how the graph is partitioned.
Girth Bounds and Extremal Properties
The girth (the length of the shortest cycle) is a primary metric of interest. By tracing the coordinates of vertices along a path, the authors derive lower bounds for the girth based on the properties of the sequences in $\Omega$.
They prove that for specific choices of $\Omega$, the girth $g$ is at least $2(|\alpha| + 3)$, where $|\alpha|$ is the length of a sequence in the set. For instance, the authors provide a concrete example (Example 4) of a graph within this family that possesses a girth of at least 14. This confirms that the $\Gamma(\Omega, q)$ framework can successfully produce the large-girth graphs required for advanced technical applications.
Conclusion
This research successfully unifies and generalizes several important families of bipartite graphs. By linking the combinatorial structure of binary sequences to the topological properties of graphs, the authors provide a powerful new method for constructing symmetric, large-girth graphs. While determining the exact girth for the most general cases remains an open challenge, the provided lower bounds and the edge-transitivity theorems offer a robust foundation for future work in coding theory and algebraic graph theory.
Summary updated