On The Study Of A Class Of Algebraic Bipartite Graphs

Graphs with large girth and a high degree of symmetry have been applied to variant problems in extremal graph theory, finite geometry, coding theory, cryp-tography, communication networks and quantum computations. For integer k≥ 2 and prime power q, by using the root systems of some Lie groups Lazebnik and Ustimenko proposed in 1995 a q-regular algebraic bipartite graph D(k,q), which is edge-transitive and of girth at least k+4. Since then, the graphs D(k, q) at-tracted considerable attention and research efforts. This class of bipartite graphs can provide the best-known bounds for many problems from extremal graph theory, construction methods of great potentiality for LDPC codes with excellent perfor-mance, and a good base for designing cryptograph systems with low complexity of computation. In this thesis, we studied the properties of D(k,q) further. We showed a closed-form expression for some paths of D(k,q), proved that the best-known conjecture for the girth of D(k, q) is true for a few new cases, proposed a new generalization for D(k, q), and discussed the properties of the generalized graphs further, such as the number of connected components, paths and their closed-form expressions, automorphisms, symmetry and girth of these graphs.At first, we proposed for the bipartite graph D(k,q) an equivalent construc-tion ∧k,q, showed some properties of linear transformations σ, τ and δ which are defined over Fq∞, and studied the uniqueness of expression for polynomials of these linear transformations over Fq. Then, by using of these linear transformation-s we rewritten the adjacent relations of ∧k,q, and obtained a recurrence relation for the vertices on paths of ∧k,q, Furthermore, by using of homogeneous polyno-mials ρs(ω1,ω2,…,ωn), we gave a closed-form expression for the vertices on the paths led by the all-zero vector with the colors(the first entries of the vectors) of the vertices. Particularly, when in each one of the two vertex sets the difference of the colors of any two consecutive vertices on such a path is constant, we computed the entries of every vertex on the path, and thus we proved that the following conjecture on the girth of D(k, q)Conjecture A:D(k,q) has girth k+5 for all odd k and all q> 4. is true when (k+5)/2 is a power of the characteristic of the finite field IF/9. To study Conjecture A further, we proposed a generalization in finite field for the binomial coefficients Ck,8=(k+s)!/k!s!:where b is an element in IF*q of order h, s mod h is the smallest nonnegative integer such that h divides s - s mod h. We obtained a series of identity relations for the generalized binomial coefficients θb(k,s). Furthermore, for any path in ∧k,q, led by the all-zero vector, when in each one of the two vertex sets the differences of the colors of consecutive vertices on this path form a geometric progression, we computed the entries of every vertex on the path, and thus we proved that Conjecture A is true when (k+5)/2 is the product of a power of the characteristic of IFq, and a factor of q-1. This is the best-known result on the study for Conjecture A at present.By indexing the entries of the vertex vectors with binary sequences from a set Ω with the exception of the colors, we proposed a new class of bipartite graphs Γ(Ω,q):the vertex sets L(Ω) and R(Ω) are two copies of the set of sequences over IFq of length |Ω|+1, [l] ∈L(Q) and 〈r〉 ∈ R(Ω) are adjacent in Γ(Ω, q) if and only if lα0+rα0= r*lα, if α0∈Ω, lβ1+rβ1=l*rβ, if β1 ∈Ω,where * is a symbol not in Ω,l* and r* express the colors of the vertices, and define *0=*1= η as the null sequence. Γ(Ω,q) is a generalization of the bipar-tite graph D(k,q). At first we showed some invariants over each of the connected components of Γ(Ω,q):if binary sequence a and its reversal sequence a are two distinct sequences in Ω, then there is an invariant α(·, a) over each of the connected components of Γ(Ω,q). Furthermore, these invariants can assume any values freely on different components. Thus, we obtained a lower bound for the number of the connected components of Γ(Ω,q). Then, we showed some automorphisms of Γ(Ω,q) and some sufficient conditions for the bipartite graph Γ(Ω,q) to be symmetry un-der variant senses. Particularly, we showed a condition for the graph Γ(Ω,q) to be edge-transitive:If for any binary sequence a in Ω, any sequence obtained from a by deleting a bit either from the first position, or from the last position, or from two consecutive zeros, or from two consecutive ones, is still in Ω, then the bipartite graph Γ(Ω,q) is edge-transitive. We discussed the paths in Γ(Ω,q) that are led by a vertex whose entries are zero excepting the color, obtained a closed-form expression for the vertices on such a path with the colors of the vertices. Furthermore, by using of these expressions we proved the nonexistence of some special cycles. Finally, we obtained some lower bounds for the girth of Γ(Ω,q). Particularly, excepting the concrete number of the connected components, the best-known research results on D(k,q) can be deduced from our discussion on Γ(Ω,q) in this thesis.