Bounds for graphs of given girth and generalized polygons
In this paper we present a bound for bipartite graphs with average bidegrees η and ξ satisfying the inequality η ≥ ξ α, α ≥ 1. This bound turns out to be the sharpest existing bound. Sizes of known families of finite generalized polygons are exactly on that bound. Finally, we present lower bound...
Gespeichert in:
| Datum: | 2002 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2002
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/154677 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-154677 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1546772019-06-16T01:30:37Z Bounds for graphs of given girth and generalized polygons Benkherouf, L. Ustimenko, V. In this paper we present a bound for bipartite graphs with average bidegrees η and ξ satisfying the inequality η ≥ ξ α, α ≥ 1. This bound turns out to be the sharpest existing bound. Sizes of known families of finite generalized polygons are exactly on that bound. Finally, we present lower bounds for the numbers of points and lines of biregular graphs (tactical configurations) in terms of their bidegrees. We prove that finite generalized polygons have smallest possible order among tactical configuration of given bidegrees and girth. We also present an upper bound on the size of graphs of girth g ≥ 2t + 1. This bound has the same magnitude as that of Erd¨os bound, which estimates the size of graphs without cycles C₂t. 2002 Article Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ. 1726-3255 2001 Mathematics Subject Classification 90B06, 05C80, 05D409, 05D99, 05E20 http://dspace.nbuv.gov.ua/handle/123456789/154677 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper we present a bound for bipartite
graphs with average bidegrees η and ξ satisfying the inequality η ≥ ξ
α, α ≥ 1. This bound turns out to be the sharpest existing bound.
Sizes of known families of finite generalized polygons are exactly
on that bound. Finally, we present lower bounds for the numbers
of points and lines of biregular graphs (tactical configurations) in
terms of their bidegrees. We prove that finite generalized polygons
have smallest possible order among tactical configuration of given
bidegrees and girth. We also present an upper bound on the size
of graphs of girth g ≥ 2t + 1. This bound has the same magnitude
as that of Erd¨os bound, which estimates the size of graphs without
cycles C₂t. |
| format |
Article |
| author |
Benkherouf, L. Ustimenko, V. |
| spellingShingle |
Benkherouf, L. Ustimenko, V. Bounds for graphs of given girth and generalized polygons Algebra and Discrete Mathematics |
| author_facet |
Benkherouf, L. Ustimenko, V. |
| author_sort |
Benkherouf, L. |
| title |
Bounds for graphs of given girth and generalized polygons |
| title_short |
Bounds for graphs of given girth and generalized polygons |
| title_full |
Bounds for graphs of given girth and generalized polygons |
| title_fullStr |
Bounds for graphs of given girth and generalized polygons |
| title_full_unstemmed |
Bounds for graphs of given girth and generalized polygons |
| title_sort |
bounds for graphs of given girth and generalized polygons |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2002 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/154677 |
| citation_txt |
Bounds for graphs of given girth and generalized polygons / L. Benkherouf, V. Ustimenko // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 1–18. — Бібліогр.: 26 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT benkheroufl boundsforgraphsofgivengirthandgeneralizedpolygons AT ustimenkov boundsforgraphsofgivengirthandgeneralizedpolygons |
| first_indexed |
2025-07-14T06:14:09Z |
| last_indexed |
2025-07-14T06:14:09Z |
| _version_ |
1837601809812684800 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2002). pp. 1–18
c© Journal ”Algebra and Discrete Mathematics”
Bounds for graphs of given girth and
generalized polygons
Lakdere Benkherouf and Vasyl Ustimenko
Communicated by V.V. Kirichenko
Dedicated to V. V. Kirichenko on the occasion of his 60th birthday
Abstract. In this paper we present a bound for bipartite
graphs with average bidegrees η and ξ satisfying the inequality η ≥
ξα, α ≥ 1. This bound turns out to be the sharpest existing bound.
Sizes of known families of finite generalized polygons are exactly
on that bound. Finally, we present lower bounds for the numbers
of points and lines of biregular graphs (tactical configurations) in
terms of their bidegrees. We prove that finite generalized polygons
have smallest possible order among tactical configuration of given
bidegrees and girth. We also present an upper bound on the size
of graphs of girth g ≥ 2t + 1. This bound has the same magnitude
as that of Erdös bound, which estimates the size of graphs without
cycles C2t.
1. Introduction
Let Γ be a simple graph (undirected, no multiple edges, no loops) and
let F be a family of graphs none of which is isomorphic to a subgraph of
Γ. In this case we say that Γ is F -free.
This paper is in final form and no version of it will be submitted for publication
elsewhere.
2001 Mathematics Subject Classification 90B06, 05C80, 05D409, 05D99,
05E20.
Key words and phrases: Extremal Graph Theory, Operations Research, Family
of Graphs of High Girth, Simple Groups of Lie Type..
2 On bipartite graphs
Let P be a certain graph theoretical property. By exP (v, F ) we de-
note the greatest number of edges of F -free graph on v-vertices, which
satisfies property P .
If property P is trivial, that is, valid for all simple graphs we shall
omit index P and write ex(v, F ).
Extremal graph theory contains several important results on ex(v, F ),
where F is a finite collection of cycles of different length (see [2], [24]).
The following unpublished result of Paul Erdös is often refereed to as
The Even Circuit Theorem (see [2], [24]).
Let Cn denote the cycle of length n. Then
ex(v,C2k) ≤ Cv1+1/k,
where C is positive independent constant. For a proof of this result
and its generalization: see [25], [26].
In [24] the upper bound
ex(v,C3, C4, . . . , C2k+1) ≤ (1/2)1+1/kv1+1/k + O(v)
was established for all integers k ≥ 1.
In this paper we will prove that
ex(v.C3, C4, . . . , C2k) ≤ 1/2v1+1/k + O(v),
and obtain the following bound
exP (m)(C3, C4, . . . C2t) ≤ 1/21+1/(m+1)tv1+1/(m+1)t + O(v) for even k,
and
exP (m)(C3, C4, . . . , C2t) ≤ v1+1/m(t+2)+t−1 + O(v) for all odd k,
where m > 1 is a real number and P (m) is a property: graph is bipartite
with average bidegrees η and ξ satisfying inequality η ≥ ξm.
Studies of exP (m)(v,C3, . . . , Ct) is motivated by some problems in
Operation Research, Theory of Communication Networks and Cryptog-
raphy. Among graphs satisfying P (m) are tactical configurations, that
is, biregular bipartite graphs.
In section 1 we shall establish some lower bounds for the numbers of
points and lines of tactical configurations. In section 2 we shall consider
tactical configurations of minimal order. This is a natural generalization
of the well known cages (see [3] and further references). Section 3 is
devoted to upper bounds for size of tactical configurations. In section 4
we shall develop an important technique for computing walks on bipartite
graphs with given average bidegrees. This method allow us to generalize
results of section 3 for more general case of graphs with the property
P (m). We shall establish ex(v,C3, . . . , C2k) and repeat the result of
Erdös and Simonovits on ex(v,C3, C4, . . . , C2k+1) in the last section.
L. Benkherouf, V. Ustimenko 3
2. Some inequalities for tactical configurations
A tactical configuration introduced by E. H. Moore [15] almost century
ago is a rank two incidence structure ∆ = ∆(l, p, a, b) consisting of l lines
and p points in which each line is incident to a points and each point is
incident to b lines. We denote the incidence graph of ∆ by Γ = Γ(∆),
though when no confusion arise we may abuse terminology and refer to Γ
as a tactical configuration. We call bipartite graphs the incidence graphs
of the incidence structures. If the structure is a tactical configuration,
then the incidence graphs are called biregular with bidegrees a, b.
We shall assume that the graph Γ(∆) has order v = l + p (number
of vertices), and size e = la = pb (number of edges). We also mean, as
usual, that the girth g of a graph is the length of its minimal cycle.
The following lemma gives a lower bound on the number of points in
a tactical configuration of girth ≥ 2k. It gives also a lower bound for the
number of lines.
Lemma 1. Let Γ = Γ(∆) with ∆(l, p, s + 1, r + 1) of girth ≥ 2k. Then
the following inequalities hold
1. If k = 2t + 1, then
(1 + r)
t
∑
i=0
(rs)i ≤ p (2.1)
(1 + s)
t
∑
i=0
(rs)i ≤ l (2.2)
2. If k = 2t, then
(1 + r)
t−1
∑
i=0
(rs)i + (rs)t ≤ p (2.3)
(1 + s)
t−1
∑
i=0
(rs)i + (rs)t ≤ l (2.4)
Proof. The approach we adopt in the proof has its root in the Theory
of Branching Process in Applied Probability, see for example Karlin and
Taylor [7]. The idea is to consider an arbitrary vertex v and count the
number of vertices at a given distance d, d ≤ [g/2], where g is the girth.
Let us assume that we start counting from a point v = p. The pass of
length d ≤ k between two chosen vertices is unique, because of absence
4 On bipartite graphs
of cycles of length 2d. Thus, we may use the idea of branching processes
to count the number of vertices at distance d from p.
If l2h+1 refers to the number of lines at distance 2h + 1 from p and
p2h+2 refers to the number of points at distance 2h + 2 from p, then
l1 = r + 1, p2 = (r + 1)s, l3 = (r + 1)sr, . . . . Finally, we get
l2h+1 = (s + 1)rhsh (2.5)
p2h+2 = (r + 1)rhsh+1 (2.6)
where h = 0, 1, . . . , t.
Summing (2.5) from h = 0 to t in case of odd t gives (2.2). Summing
(2.6) from h = 0 to t in case of even t gives (2.3). By interchanging points
and lines in (2.5) and (2.6)together with parameters r and s and using
the same a argument as above we obtain (2.1) and (2.4). This completes
the proof.
Remark 1. If t+1 = s+1 = k, then the order of the graph is v = 2p = 2l
and the inequalities in Lemma 1 are equivalent to the well known Tutte’s
inequality for arbitrary regular graph.
v ≥ 2(1 + (k − 1) + . . . (k − 1)(g−2/2))
3. Minimal configurations with prescribed girth and their
applications
The well known assignment problem in Operations Research is equivalent
to finding the tactical configuration of given bidegees r + 1 and s + 1 of
minimal order. It is an important special case of the Transport Problem
(see, for instance Taha [16]). There is a well known efficient algorithm
to solve this problem. In many cases this algorithm can be modified
to solve efficiently assignments problem with additional restrictions. In
our case this translate to the problem of finding a tactical configuration
with minimal number of vertices among graphs satisfying a the list of
restrictions.
let us consider the case when the precise list of restrictions is the ab-
sence of cycles of length 4, 6, . . . 2k−2. One can notice that the incidence
graph of tactical configuration does not have cycles of odd length and the
last requirement is equivalent to inequality g ≥ 2k. Unfortunately there
is no known modification of existing assignments problem algorithms or
other methods for the efficient solution of this problem.
L. Benkherouf, V. Ustimenko 5
Let v(r, s, g) refers to the minimal order of a tactical configuration
with bidegrees s + 1 and r + 1 and girth g ≥ 2k, that is, the solution of
the variant of assignment problem as above.
The problem of testing whether or not given tactical configuration
∆(r, s, l, p) of the girth g is a solution of the problem, that is, checking the
condition p + l = v(s, r, g) can be a very difficult one. The computation
of function v(r, s, g) is a hard problem of Applied Combinatorics.
We may assume, without loss of generality, that r ≥ s . It is clear
that if both inequalities (2.1) and (2.3) above turn out to be equalities,
then our test is trivial and ∆ is the solution of our variant of assign-
ment problem. In this special situation we will use term ”extra special
configuration”. In such a configuration we have the ”best possible so-
lution” of the problem. Of course , in the case of small bidegrees and
girth we may easily find examples where tactical configuration ∆ is not
an extraspecial, but p + l = v(r + 1, s + 1, g)
We will use term ”extraspecial” for graphs of extraspecial tactical
configurations and regular graphs (not necessarily bipartite) of Tutte’s
bound order.
It is important that the totality of extraspecial configurations is non
empty. Generalized m-gons were defined by J. Tits in 1959 (see [18], [19]
and the survey [17]) as a tactical configurations of bidegrees s + 1 and
t + 1 of girth 2m and diameter m. The pair (s, t) is known as order of
generalized m-gon.
The following result is well known (see [3])
Theorem 1. A finite generalized n-gon of order (s, t) has n ∈ {3, 4, 6,
8, 12} unless s = t = 1. If s > 1 and t > 1, then
1. n 6= 12
2. If n = 4, then s ≤ t2, t ≤ s2;
3. If n = 6, then st is a square and s ≤ t3, t ≤ s3;
4. If n = 8, then 2st is a square and s ≤ t2, t ≤ s2;
This is the original Feit-Higman theorem [6] combined with well
known inequalities.
The known examples of generalized n-gons of bidegrees ≥ 3 and
m ∈ {3, 4, 6, 8} are rank 2 incidence graphs of geometries of finite simple
groups of Lie type. The regular incidence graphs are m = 3 ( group
A2(q) ), m = 4 ( group B2(q) or C2(q) ), m = 6 ( group G2(q)). In all
cases s = r = q, where q is prime power.
6 On bipartite graphs
The biregular but not regular generalized n-gons have parameters
s = qα and t = qβ, where q is some prime power. The list is below:
1. n = 4
s = q, r = q2 and q is arbitrary prime power,
s = q2, r = q3 and q is arbitrary prime power
2. n = 6
s = q2, t = q3 and q = 32k+1, k > 1
3. n = 8
s = q, t = q2 and q = 22k+1.
Besides finite generalized polygons related to simple groups of Lie
type, which we consider above, there are important ”nonclassical exam-
ples”: nondezargezian projective plane, nonclassical generalized quadrag-
ons and hexagons (see [17] and further references).
Theorem 2. Finite generalized polygons are extraspecial configurations.
Proof. The order of regular generalized m-gons of degree q + 1 is 1 +
q + q2 + · · · + qm−1 and reaches the Tutte’s bound for graphs of girth
m − 2. The finite irregular tactical configurations which are generalized
polygons have to be of even diameter m = 2k . If their degrees are r + 1
and s + 1 then the numbers of points p and number of lines l can be
computed by the formulas
p = 1 + r + rs + r2s + r2s2 + ... + rksk + rk+1sk,
l = 1 + s + sr + s2r + s2r2 + ... + skrk+1 + sk+1rk+1,
where k have to be an element of {2, 3, 4, 6}. They are at bounds (2.1)
and (2.2) for points and lines.
Thus finite generalized m-gone is a perfect cage configuration.
Application in Operations Research need explicit constructions of
tactical configurations of given girth and bi-degrees of ”small size”, that
is, close to bounds (3.1)-(3.4). General constructions of that kind are
presented in [21].
L. Benkherouf, V. Ustimenko 7
3.1. Cages and v(r, s, g) for r = s
We shall next examine the function v(k, k, g) and regular extraspecial
configurations. A cage (see [3]) is a k = t + 1-regular graph of given
girth with the minimal number v(k, g) of vertices. As it follows from
definitions of functions v(r, s, g), which is the minimal order of tactical
configuration with bidegrees r + 1 and s + 1 of girth (see section 2) and
v(k, g)
v(t, t, g) ≥ v(t + 1, g)
Remark. We use same name for two functions but number of variables
shall allow to distinguish them.
If we are dealing with t-regular extraspecial configuration, then
v(t, t, g) is same as v(t, g) which achieves Tutte’s bound.
The cage whose number of vertices is equal to this bound and whose
girth is odd is called Moore graph. The only Moore’s graph of degree
2 are 2n + 1-gons. An m-gon is just a totality of vertices (points) and
edges (lines) of ordinary cycle of length m with the natural incidence. A
Moore graph of degree k ≥ 3 has diameter 2 and k ∈ {3, 7, 51}.
We are interested in the case of even girth because tactical configu-
rations are bipartite graphs and have no odd cycles. When the degree is
2, then we have a 2n-gone which is an example of extraspecial configu-
rations. In fact, the (2, g)-cage is the g-circuit, and v(g, 2) = g.
Let us list some well known families of cages of even girth.
(i) the (k, 4)-cage is the complete bipartite graph Kk,k and v(k, 4) =
2k.
If k = q + 1 for a prime power q, then
(ii) a (k, 6)-cage is the incidence graph of a projective plane PG(2, q),
and v(k, g) = 2(q2 + q + 1);
(iii) a (k, 8)-cage is the incidence graph of a generalized quadrangle
CQ(q, q), and v(k, g) = 2(q3 + q2 + q + 1);
(iv) a (k, 12)-cage is the incidence graph of a generalized hexagon
GH(q, q), and v(k, q) = 2(q + 1)(q4 + q2 + 1)
The (3, 8)-cage is the Tutte - Coxeter graph (v=30) [20].
One has v(7, 6) = 90 and the unique (7, 6) cage was independently
found in [8], [5]. Finally, there are 3 distinct (3, 10)- cages, all of them
are bipartite [9], and v(3, 10) = v(2, 2, 10) = 70.
8 On bipartite graphs
The problem of determining v(k, g) was posed in 1959 by F. Kartesi
who noticed that v(3, 5) = 10 was realized by the Petersen graph. Sachs
showed that v(k, g) is finite and Erdös and Sashs gave the upper bound.
This bound was improved in [10] for the best known general bound see
[14]. For the case of bipartite graphs similar problem had been considered
in [12]. A lower bound is given by Tutte’s formula.
Applications in Operations Research, Cryptography, Networking also
need constructions of regular graphs of a given gorth with the lowest
known order. There are some interesting examples of cubic graphs of
that kind (see [22] and further references).
4. Bounds for the size of tactical configurations
The minimization problem for the order of a graph with prescribed bide-
grees r, s and girth g is equivalent to the maximization of the size (num-
ber of edges) of a graph with parameters r, s and g. The maximal number
of edges of the graph of order v without cycles C2k is estimated by Erdös
Even Circuit Theorem.
Let ex(v, n) be, as usual, the greatest number of edges (size) in a
graph on v vertices, which contains no cycles C3, C4, . . ., Cn.
As it was mentioned in the introduction, from Erdös’ Even Circuit
Theorem and its modifications (see [2]) it follows that
ex(v, 2k) ≤ Cv1+1/k (4.1)
where C is a positive constant.
In the case of tactical configuration with the restriction on bidegrees
it is possible to get a stronger bounds than the one given by the Even
Cycle Theorem.
Let us consider some corollaries of the Lemma 1. Without loss of
generality we will assume r = am, s = a, where m ≥ 1
In case of k = 2t, we may omit all terms of the left hand side of (1.3)
and (1.4) except highest terms, amta < p, and atamt < l.
Adding last inequalities
we get a(m+1)t < v/2, or a < (v/2)1/((m+1)t) . We also have l(a+1) = e
or la = e − l. Thus e − l < l(v/2)1/((m+1)t) .
Put v instead of l to get e < v(v/2)(1/((m+1)t) + v, which leads to the
next theorem
Theorem 3.
e ≤ (1/2)(1/(m+1)t)v(1+1/(m+1)t) + v (4.2)
L. Benkherouf, V. Ustimenko 9
Remark 2. If m = 1 the magnitude of right hand side is same as that
of Erdös Even Circuit Theorem, but the constant is better. The constant
has monotonic dependence on m, and is always < 1. If m > 1, then
(2.4) is stronger than Erdos inequality in magnitude. Of course (2.4) is
applicable only to bipartite biregular graphs.
Let us consider the case k = 2t + 1. If we discard some of the
summands on the left hand side of (2.1) we get rtst + rt+1st < p. Set as
before r = am, and s = a to get amt+1(am + 1) < p. Also, l(p + 1) =
p(am + 1) = e gives amt+t(l/p)(a + 1)l < p or amt+t(a + 1)l < p2 =
l2(a + 1)2/(am + 1)2.
Simplifying last inequality we obtain
amt+t(am + 1)2/(a + 1) < l.
Note that the function f(a) = (am + 1)2/(a + 1) is increasing.
Thus f(a−1)amt+t < l or amt+t−1[(a−1)2+1] < l. The last inequality
then leads to (a − 1)mt+2m+t−1 < l or a − 1 < e(mt+2m+t−1)−1
. But we
know that l(a + 1) = e. So l(a − 1) = e − 2l, and multiplication of two
sides of the last inequality by l produces
e < ll+(m(t+2)+t−1)−1
+ 2l.
Order v = p + l is ≥ l, thus substitution of v instead of l gives us a
slightly weaker inequality.
Theorem 4.
e ≤ v1+1/(m(t+2)+t−1) + 2v (4.3)
Remark 3. If m = 1, then the above bound has the same magnitude as
that of Erdös bound in Even Circuit Theorem, but the constant is better
than in (3.1). In fact we can improve the constant by substitution l = v/2
into inequality 3 to get.
e ≤ (1/2)1+1/(2t+1)v1+1/(2t+1) + v (4.4)
If m > 1, then magnitude of (3.3) is better than that of Erdös bound.
Remark 4. Theorems 3 and 4 give slightly better bounds than the upper
bounds given in [21] (better constants but the same magnitude). This,
we shall generalize for graphs with average bidegrees in next section.
10 On bipartite graphs
5. Bipartite graphs with given average bidegrees
Here, we assume that we have a random tactical configuration ∆ =
∆(l, p, a(ω), b(ω)) consisting of l lines and p points laid out as a Branching
Process. We shall assume, without loss of generality, that level zero
consists of some line x0, say. This line is incident to m points with
probability p(m), where E(M) = η + 1, where M denotes the random
variable representing the outcomes m and η ≥ 1 and is known. Here, E
denotes the usual expectation operator.
Now, let Xn
l ,(Xn
p) be the number of lines (points, respectively) at
level n. We shall assume from level 1 onwards that each line is incident
to a(ω) points with probability p(a(ω)), where a(ω) takes the integer
values 0, ..., p, with E(a) = η. Similarly, we have each point is incident
to b(ω) lines with probability p(b(ω)), with E(b) = ξ,where ξ ≥ 1 and
known.
If the girth of our graph is > 2t, then there is at most one pass
between any two vertices at a distance ≤ t. Points of level k are precisely
at distance 2k +1 from the initial line. The line of level k are at distance
2k. Thus, computation ofXkl, 2k ≤ k and Xp
k can be done by branching
process.
We have
Xp
0 = M,
Xp
n =
Xl
n
∑
i=1
Zi
X l
n =
Xl
n−1
∑
j=1
Yj
where Z ′
is are i.i.d random variables, with mean η and variance σ2
Z ,
corresponding to a(ω). The variables Yj are i.i.d random variables corre-
sponding to b(ω), with mean ξ and variance σ2
Y . We shall be interested
in finding a closed form for the means and the variances of the random
variables Xp
n, X l
n defined above.
The next two lemmas provide an answer to our query.
Lemma 2. X l
0 = 1,
(i) E[Xp
n] = (η + 1)(ηξ)n, n = 1, ...
Proof. The proof is standard: see Karlin and Taylor [7] for similar ideas.
Note that
E[Xp
n] = E[E[Xp
n|X
l
n]].
L. Benkherouf, V. Ustimenko 11
Now, consider E[Xp
n|X l
n = x] = E[
x
∑
i=1
Zi] = xE[Z] = ηx,
because of the independence of Zi. Hence
E[Xp
n] = ηE[X l
n]. (5.1)
Now, we compute E[Xn
l]. Again E[X l
n] = E[E[X l
n|X
p
n−1]]. But,
E[X l
n|X
p
n−1 = x] = E[
x
∑
j=1
Yj] = ξx,
by the independence, whence
E[X l
n] = ξE[Xp
n−1]. (5.2)
by independence. Hence, combining (5.1) and (5.2) we get
E[Xp
n] = ηξE[Xp
n−1] = (ηξ)nE[Xp
0 ]
But E[Xp
0 ] = η + 1. Hence,
E[Xp
n] = (η + 1)(ηξ)n. (5.3)
To show part (ii) note that E[X l
n] = ξE[Xp
n−1] = (η + 1)ξ(ηξ)n−1, by
(5.3), as required.
The next lemma gives a bound on the variances of the random vari-
ables Xp
n and X l
n.
Lemma 3.
(i) V ar(Xp
n) ≤ Ṽ
{
(η + 1)(ξ + η2)(ξη)n−1 (ηξ)n−1
−1
(ηξ)−1 + (ηξ)2(n−1)
}
(ii) V ar(X l
n) ≤ Ṽ
{
ξ(η + 1)(ξ + η2)(ξη)n−2 (ηξ)n−1
−1
(ηξ)−1 + (ηξ)2(n−1)
}
,
where Ṽ = max{V ar(X), V ar(Z), V ar(Xp
0 ), V ar(X l
0)}.
Proof. We shall only prove (i). The proof of (ii) is similar. Note that
V ar(Xp
n) = E[(Xp
n)2] − (E[Xp
n])2. (5.4)
Let us compute E[(Xp
n)2]. We have E[(Xp
n)2] = E[E[(Xp
n)2|X l
n]], and
E[(Xp
n)2|X l
n = x] = E
[
(
x
∑
i=1
Zi)
2
]
= V ar
[
x
∑
i=1
Zi
]
+
(
E
[
x
∑
i=1
Zi
])2
= xV ar(Z) + (xη)2,
12 On bipartite graphs
by independence. Hence
E[(Xp
n)2] = V ar(Z)E[X l
n] + η2E[(X l
n)2]. (5.5)
Now, we are required to compute E[(X l
n)2]. The same argument used
above gives
E[(X l
n)2] = V ar(Y )E[Xp
n−1] + ξ2E[(Xp
n−1)
2]. (5.6)
Combining (5.4), (5.5), and (5.6) gives
V ar(Xp
n) = V ar(Z)E[X l
n]+
+η2
{
V ar(Y )E[Xp
n−1] + ξ2E[(Xp
n−1)
2]
}
− (E[Xp
n])2.
This can be shown to be equal to:
V ar(Z)E[X l
n] + η2V ar(Y )E[Xp
n−1] + (ηξ)2V ar(Xp
n−1).
Using the previous lemma the above is less than or equal to:
max{V ar(Y ), V ar(Z)}(η + 1)(ηξ)n−1(ξ + η2) + (ηξ)2V ar(Xp
n−1).
Now, we use induction to get
V ar(Xp
n) ≤ Ṽ
{
(η + 1)(ξ + η2)(ξη)n−1 (ηξ)n−1 − 1
(ηξ) − 1
+ (ηξ)2(n−1)
}
,
where Ṽ = max{V ar(X), V ar(Z), V ar(Xp
0 ), V ar(X l
0)}, as required.
The next lemma (which is a direct consequence of lemmas 3 and 4
and Chebeychev inequality: see [7]) gives confidence intervals for both
Xp
n and X l
n.
(i) The confidence interval for Xp
n is
(η + 1)(ηξ)n ± ksp,
for some nonnegative k > 0 and
sp = (Ṽ
{
(η + 1)(ξ + η2)(ξη)n−1 (ηξ)n−1 − 1
(ηξ) − 1
+ (ηξ)2(n−1)
}
)1/2.
(5.7)
L. Benkherouf, V. Ustimenko 13
(ii) The confidence interval for X l
n is
(η+)ξ(ηξ)n−1 ± k′sl,
for some nonnegative k > 0, and
sl = (Ṽ
{
ξ(η + 1)(ξ + η2)(ξη)n−2 (ηξ)n−1 − 1
(ηξ) − 1
+ (ηξ)2(n−1)
}
)1/2.
(5.8)
Remark 5. Note that (4.7) shows that the order of Xp
n is at most O((η+
1)(ηξ)n), while the order of X l
n is at most O((η + 1)ξ(ηξ)n−1).
6. On the size of general bipartite graphs
In this section we will consider upper bounds for the size of bipartite
graphs Gi of increasing order v = vi without cycles of girth g > 2k
satisfying inequality ηi ≥ ξm
i , where m ≥ 1 is some positive real number.
and superlinear size without cycles C2k.
We have a free choice which partition set is the point set. So we may
assume that ηi ≥ ξi (the average degree for points is greater than or
equal to average degree of lines). Thus our result for m = 1 estimates
size of general bipartite graphs of a given girth.
Theorem 5. Let Gi, i = 1, . . . be a family of bipartite graphs without
even cycles C4, . . . , C2k such that average degrees ηi and ξi of lines and
points satisfy the inequality: ηi ≥ ξi
m. Then, we have:
(i) e ≤ (1/2)(1/(m+1)t)pv(1/(m+1)t) + O(v)
(ii) e ≤ p1+1/(m(t+2)+t−1) + O(v)
hold for cases k = 2t and k = 2t + 1 respectively.
Proof. Let Gi, i = 1, . . . be a family of graphs satisfying the restrictions
on the bidegrees and the girths as above. It follows from [12], that the
size of the bipartite graphs of a given girth, with the restrictions on the
bidegrees as stated above, is superlinear function Cvα, α > 1 of order
v. Thus, we may assume that function ξi is unbounded. Else, we may
bound the number of edges of the graphs by a linear expression in v. In
fact, we shall conduct all computations up to O(v). We will also keep the
notations of the previous section: ηi and ξi will be the average degrees
for the lines and the points respectively. Without loss of generality we
may assume ηi ≥ ξi. i = 1, . . . .
Let us consider case k = 2t. In this case, there is not more then one
pass of length ≤ 2t between two given elements at distance 2t. Hence,
we may apply result (4.8) to get, if ξ is ”sufficiently large”
X l
t = (η + 1)ξ(ηξ)t−1 − C1η
(t−1/2)ξn−3/2 ≤ l.
14 On bipartite graphs
The expression one left hand side gives us the number of lines at
distance 2t from chosen line, where C1 is some constant. If we swap
points and lines together with their average degrees we get”
(ξ + 1)η(ηξ)t−1 − (ξη)t−1 ≤ p.
Addition of last two inequalities gives us
2(ηξ)t + [(η + ξ)(ηφ)t−1 − C1(ηξ)t−1(η/ξ)1/2 − (ηξ)t−1] ≤ (p + l) = v
when ξ is sufficiently large, expression in parenthesis is positive and we
are getting
2(ηξ)t < v.
For ξ = a and η ≥ am we may write
a < (v/2)1/(m+1)t
.
Analogously to similar case for biregular graphs we are getting pa ≤
p(v/2)1/(m+1)t
. The last inequality together with p(a + 1) = e gives us
the following bound for the size e
e < p(v/2)1/(m+1)t + O(v).
Let us consider the case k = 2t + 1. It follows from (4.8) that X l
t is at
least (η + 1)ηtξt − Cηtξt−3/2, where C is some positive constant. Thus
instead of the inequality X l
t + X l
t−1 ≤ l we can write:
ηt+1ξt + ηtξt + (ηtξt−1 + ηt−1ξt−1 − Cηtξt−3/2).
For sufficiently large ξ, the expression in brackets in the previous
formula will be negative and we get ηt+1ξt + ηtξt < l. Setting as before
η ≥ am, ξ = a. Thus amt+1(am + 1) < l. From pξ = lη, we get
e = p(a + 1) > l(am + 1) and (am + 1) ≤ p(a+ 1)/lamt+t(p/l)(a + 1)l < l
or
mt+t(a + 1)l < l2 = p2(a + 1)2/(am + 1)2a.
Simplifying the last inequality we obtain
amt+t(am + 1)2/(a + 1) < p.
We can notice that the function f(a) = (am + 1)2/(a + 1) is increasing.
Thus f(a − 1)amt+t < l or amt+t−1[(a − 1)2 + p] < l. From the last
inequality we get (a − 1)mt+2m+t−1 < l or a − 1 < l(mt+2m+t−1)−1
. We
L. Benkherouf, V. Ustimenko 15
know that p(a + 1) = e. So, p(a − 1) = e − 2l and multiplication of the
two sides of the last inequality by l gives e < pp(m(t+2)+t−1)−1
+ O(p) of
lines and the number of pints of Gi satisfy the inequality ηi ≥ ξi
m for
certain real number m > 1. Then, e ≤ (1/2)1+1/kv1+1/k + O(v) in the
case of k even and e ≤ v1+1/k + O(v) if k is odd.
Remark 6. The bounds in the theorem 5 are sharp up to constant when
we deal with families of generalized k + 1-gons. In particular for m > 1,
we have the following list: (m = 2, k = 3), (m = 3/2, k = 3, (m =
3/2, k = 5), (m = 2, k = 7).
7. On the size of general graphs of high girth
In this section, we shall be concerned with the size of graphs of large
girth as function of the order.
Theorem 6. Let F = {Gj}, j = 1, . . . be a family of bipartite graphs
without of cycles Ci, 3 ≤ i ≤ n, n ≥ 3, that is, a family of graphs of
girth g > n. Let e and v be the size and the order of graphs from F
respectively.
Then
(i)e ≤ (1/2)v1+1/k + O(v) for n = 2k
(ii) e ≤ (1/2)1+1/kv1+1/k + O(v) for n = 2k + 1
Proof. Let η be the average degree of graph Gi. Let us consider the case
n = 2t + 1. If the girth g ≥ 2k + 2, then there is at most 1 pass between
vertices at distance k, we can choose adjacent vertices v and u and count
the number of passes at distance ≤ t via branching process. Let Yl(u)
(Yl(w))be the totality of vertices x of length l, l ≤ k + 1 such that the
pass between u and v does not contain w (u respectively). It is clear,
that |Yl(u)| = |Yl(v)| = yl. We have |Yl(u)∩Ys(v)| = 0, because common
point for Yl(u) and Ys(w) corresponds to cycle of length l+s+1 ≤ 2k+1.
The induced subgraph of Gi with the union of all Yl(u) and Ys(v is a tree
which is a bipartite graph. Thus, we can estimate the number yl via
the technique of section 5. We need just to take in account that in our
case η = ξ and at the first step of branching process we have η instead of
η + 1. Thus yl ≥ ηl−1 − Cηl−2, l = 1, . . . , k + 1. After summation of the
above inequalities and multiplication by 2 we get that the number Ind
of all vertices for our tree is at least
2ηk + 2(1 + η + . . . ηt−1 − C1ηt−2).
If parameter i for Gi and related η are ”sufficiently large” then The
expression in brackets above will be positive. Thus ηk < Ind < (v/2),
16 On bipartite graphs
η < (v/2)1/k and (v/2)η(v/2)1+1/k . But (v/2)(η + 1) = e or (v/2)η =
e − v/2. Finally e < (1/2)1+1/kv1+1/k + O(v) and the statement (i) of
the theorem is proven.
Let us consider the case of n = 2k. There is at most one pass between
two given vertices at the distance l, l ≤ 2k otherwise we have a cycle
C2l−2. Thus we may choose a vertex v and count number Xl vertices
at distance l from v by branching process with η = ξ. As it follows
from results of section 4 sp (sl, respectively) is less then Cηk−2, where
k is a highest degree of η in the expression for Xn
p (respectively Xn
l ) for
appropriate n , where C is a certain constant. Thus
Xl ≥ (η + 1)ηk−1 − Cηk−2.
So from Xl + Xl−1 ≤ v we can obtain
ηk + [2ηk−1 + ηk−2 − C1ηk−2] ≤ v.
If η is sufficiently large then the expression in parenthesis is positive
and we can write simply ηk ≤ v. We can get η ≤ v1/k. Multiplication
by v of both sides of last inequality together with 2e = (η + 1)v gives us
e ≤ 1/2v1+1/k + O(v).
8. Conclusion
Let us reformulate main results in terms of ex notations.
We presented an upper bound on the ex(v,C3, . . . , C2n) and a bound
exP (m)(v,C3, . . . , Ct), where P (m) is a property of the bipartite graph
whose average bidegrees η and ξ satisfy the inequality η ≥ ξm, m ≥ 1.
We proved that the sizes of the tactical configurations of finite general-
ized polygons are exactly on that bound. In fact, we proved that finite
generalized polygons have minimal possible order among tactical config-
urations of the same bidegrees and girth.
Upper bounds for ex(v,C2n) are known to be sharp up to constant
in case of n ∈ {2, 3, 5}. The question on the sharpness of this bound for
other n is still open. We conjecture that our bound for the
exP (m)(v,C3, . . . C2m) is sharp if and only if (m,n) belongs to the fol-
lowing list: (2, 3), (3/2, 3), (3/2, 5), (2, 14).
References
[1] N.L. Biggs, Graphs with large girth, Ars Combinatoria, 25C (1988), 73–80.
[2] B. Bollobás, Extremal Graph Theory, Academic Press.
[3] A. E. Brouder, A. M. Cohen, A. Niemaier, Distance regular graphs, A Series of
Modern Surveys in Mathematics, band 18, Springer-Verlag, 495pp.
L. Benkherouf, V. Ustimenko 17
[4] V. Ustimenko, Graphs with special walks and Cryptography, Acta Applicandae
Mathematicae, Acta Applicandae Matematicae, 2002, vol. 74, issue 2, pp.117-153.
[5] R. Baker, An elliptic semiplane, J. Comb Theory (A), 25, 1988, 193-195.
[6] W. Feit, G. Higman, The nonexistence of certain generalized polygons, J. Algebra
1 (1964), 114-131.
[7] S. Karlin, H.M. Taylor, A first course in stochastic processes, Academic Press,
New-York. (1975).
[8] M. O’Keefe, P. Wong, The smallest graph of girth 6 and valency 7, J. Graph
Theory, 5 (1981),79-85.
[9] M. O’Keefe, P. Wong, The smallest graph of girth 10 and valency 3, J. Graph
Theory 5 (1980), 91-105.
[10] N. Sauer. Extermaleigenschaften regularer Graphen gegebener Taillenweite, 1, 2,
Osterreich. Acad. Wiss. Math. Natur. Kl. S. -B 2, 176 (1967), 9-25, 27-43.
[11] Carter, R.W., Simple Groups of Lie Type, Wiley, New York (1972).
[12] Füredi, Z., Lazebnik, F., Seress, Á., V. A. Ustimenko and A.J.Woldar, Graphs of
prescribed girth and bi-degree, J. Combin. Theory B 64 (2) (1995), 228–239.
[13] Lazebnik, F., Ustimenko, V.A. and A.J. Woldar, A new series of dense graphs of
high girth, Bull. AMS 32 (1) (1995), 73–79.
[14] Lazebnik, F., Ustimenko, V.A. and A.J. Woldar, New upper bounds on the order
of cages, Electronic J. Combin. 14 R13 (1997), 1–11.
[15] E. H. Moore, Tactical Memoranda, Amer. J. Math., v.18, 1886, p. 264-303.
[16] Taha, H, Operations Research: An Introduction, Prentice Hall, New-Jersey (1996)
[17] J. A. Thas, Generalized polygons, in F. Buekenhout (ed), Handbook on Incidence
Geometry, North-Holland, Amsterdam, 1995, Ch. 9.
[18] J. Tits, Sur la trialite et certains groupes qui s’en deduisent, Publ. Math. I.H.E.S.
2 (1995), 15-20.
[19] J. Tits Les groupes simples de Suzuki et de Ree, Seminare Bourbaki 13 (210)
(1960/1961), 1 - 18.
[20] W. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1945)
[21] V. Ustimenko, A. Woldar, Extremal properties of regular and affine generalized
m-gons as tactical configurations, European J. of Combinatorics, to appear.
[22] C. Parker and P. Rowley, Subgroup chain Graphs, J. of Algebraic Combinatorics.
[23] M. Simonovits, Extremal Graph Theory, Selected Topics in Graph Theory 2
(L.W.Beineke and R.J.Wilson,eds.), Academic Press, London, 1983, pp. 161-200.
[24] P. Erdös, M. Simonovits, Compactness results in extremal graph theory Combi-
natorica 2 (3) (1982), 275 - 288.
[25] J. A. Bondy, M. Simonovits, Cycles of even length in graphs, J. Combin. Theory,
Ser. B, 16 (1974), 87-105.
[26] R. J. Faudree, M. Simonovits, On a class of degenerate extremal graph problems,
Combinatorica, 3 (1), 1983, 83-93.
18 On bipartite graphs
Contact information
L. Benkherouf and
V. Ustimenko
Department of Mathematics and Statistics,
Sultan Qaboos University, P.O.Box 36, Al-
Khod 123, Oman
E-Mail: vasyl@squ.edu.om
Received by the editors: 21.10.2002.
|