The Erdös-Faber-Lovász Conjecture for Gap-Restricted Hypergraphs ()
1. Introduction
Let
be a hypergraph with vertex set
and edge set
. For each edge
, e is a subset of
. Let
denote the number of vertices in edge
, and call it edge cardinality of e. An edge
with
is called a k-edge in hypergraph H. For an edge
with
, we call edge e a k+-edge. If
holds for each edge
, then H is called loopless hypergraph. We call a vertex
incident with an edge
if
. A pair of distinct edges
is intersecting if
. An edge coloring of H is a function
such that any pair of intersecting edges
satisfies that
. The chromatic index
of hypergraph H is the minimum number of colors of all edge colorings of H, i.e., the minimum value of w. We call a hypergraph H linear if
holds for any pair of distinct edges
. For loopless linear hypergraphs, there is a famous conjecture proposed by Erdös, Faber and Lovász in 1972.
Conjecture 1. [1] (The Erdös-Faber-Lovász Conjecture) For any loopless linear hypergraph H with n vertices,
.
A hypergraph H is called intersecting hypergraph if H satisfies that, any pair of distinct edges are intersecting. We call a hypergraph H r-uniform if
holds for each edge
. If Conjecture 1 is true, it is known that there are three classes of loopless linear hypergraphs, finite projective planes, degenerate planes and complete graphs with odd vertices, which are extremal hypergraphs of Conjecture 1.
An m-ordered finite projective plane H with n vertices and n edges, where
, is a hypergraph satisfying:
1) H is
-uniform and each vertex
incident with
edges.
2) For any two distinct vertices, there is exactly one edge containing both vertices.
3) For any two distinct edges, there is exactly one vertex incident with both edges.
4) There are four vertices so that no edge can contain more than two of these vertices.
It is known that for each prime power
,
-ordered finite projective plane exist. A Fano plane in Figure 1 is a finite projective plane with order 2.
We briefly explain why it is an extremal hypergraph of Conjecture 1. For a finite projective plane H with order m and
vertices, since H is an intersecting hypergraph, each edge in H has a different color in any edge coloring of H. Also by
, we have
.
The hypergraph in Figure 2 is also intersecting linear hypergraph, which is called degenerate plane. A degenerate plane D with n vertices is formed by
2-edges which have a common vertex v and a
-edge which is formed by all vertices in
. Since degenerate plane D is an intersecting hypergraph with n edges, there is
. In Figure 3, it is a complete graph with odd vertices. A complete graph Kn with odd integer n is a graph formed by n vertices and any pair of vertices is connected by a 2-edge. It is well known that
for any odd n.
In 1988, Chang and Lawer [2] showed that
is true for
every loopless linear hypergraph H with n vertices. In 1992, based on Seymour’s result [3] which related to the size of matchings in loopless linear hypergraphs, Kahn and Seymour [4] proved that the fractional chromatic index of any loopless linear hypergraph H is no more than the number of vertices in H. In the same year, Kahn [5] also gave an asymptotic bound of chromatic indices,
, for loopless linear hypergraphs according to Conjecture 1. In 2008, Sánchez-Arroyo [6] verified that Conjecture 1 is true for any linear hypergraph H with n vertices which satisfy that
for any edge
. Romero and Alonso-Pecina [7] showed that the conjecture is true for loopless linear hypergraphs with at most 12 vertices in 2014. In 2019, Faber and Harris [8] showed that
is true for any linear hypergraph H with n vertices and medium-size edges. In 2020, Bretto, Faisant and Hennecart [9] confirmed that, for weakly trianguled hypergraphs, Conjecture 1 is true.
In 2021, Alesandroni [10] gave a result on EFL Conjecture in dual version. For any hypergraph
, the dual of H is a hypergraph
with
,
such that
if and only if
. A vertex coloring of H is a function
that maps from
to a color set C such that no edge contains homochromatic vertices. Clearly, H has an edge coloring with w colors if and only if
has a vertex coloring with w colors. Since we are only talking about edge coloring of hypergraphs in this paper, in order to show more clearly how the result of Alesandroni relates to Conjecture 1, here we present the form of the result in the edge coloring version.
Theorem 2. [10] Let H be a loopless linear hypergraph with n vertices. For every
, if there are at most k2 k-edges in H, then
.
When hypergraph H does not contain k-edge (
), Theorem 2 implies a result as follows.
Corollary 3. For any loopless linear hypergraph H with n vertices, if
holds for each
, then
.
In 2023, Kang et al. [11] verified Conjecture 1 on linear hypergraphs whose vertices number is sufficiently large. Recently, Wang and Zhang [12] generalized a result of Bretto, Faisant and Hennecart in [9] .
In this paper, we first show that Conjecture 1 holds for a class of odd-edge hypergraphs and a class of even-edge hypergraphs (Theorem 4, Definition 2.1). Then we extend Theorem 4 to a more general class of loopless linear hypergraphs (Theorem 5). Based on Corollary 3, we further verify that Conjecture 1 holds for gap-restricted hypergraphs, and this result is better than Theorem 5. Finally, we give a corollary and some relevant discussion on some guesses of possible counterexamples of Conjecture 1.
2. Main Results
In this section, we give some results on Conjecture 1 according to the edge cardinality in loopless linear hypergraphs. First, we present a simple result for odd-edge (even-edge) hypergraphs.
Definition 2.1. (Odd-edge (Even-edge) hypergraphs) A loopless linear hypergraph H is called odd-edge (even-edge) if
is odd (even) for any edge e in H.
For any pair of distinct vertices
in hypergraph H, we call u and v adjacent if there exists an edge
satisfying that
. Let
be the number of k-edges which intersect with e and
be the number of k+-edges which intersect with e in H. Let
be the rank of hypergraph H and
be the anti-rank of hypergraph H. We use
to denote the number of k-edges which are incident with vertex v and
to denote the number of k+-edges which are incident with vertex v in H. Now, we give a result based on the restriction of
for each integer
and each k-edge e.
Theorem 4. Let H be an odd-edge (even-edge) hypergraph with n vertices. If
holds for every integer
and every k-edge
, then
.
Proof. We give an edge coloring of H with at most n colors to prove the theorem. Consider that coloring an edge with large cardinality is more likely to be affected by other colored edges than coloring an edge with small cardinality. We will color all edges in H according to a non-increasing order of edge cardinality. For any integer
, let
be a k-edge. We use
to denote the number of colors which appear on intersecting edges of e.
When we are ready to color edge e, since the edge coloring is performed in a non-increasing order, the colored edges are either
-edges or k-edges.
Recall that
. We discuss two cases according to the magnitude between
and
.
Case 1.
.
For each vertex
, since hypergraph H is linear and
, the number of vertices which are adjacent to v is no more than
. Note that, for each vertex
which is adjacent to v, u is either contained by edge e or by an intersecting edge of e. By
, there are
vertices adjacent to v in edge e. Then the number of adjacent vertices of v which are contained by intersecting edges of e is no more than
. For each k-edge which is incident with v, there are
vertices adjacent to v in the k-edge. By the definition of
, there are
vertices adjacent to v in all k-edges which are incident with v except edge e. Recall that, for each
-edge incident with vertex v, the
-edge has at least k vertices which are adjacent to v. So, for each vertex
, there is
(1)
Note that
. By (1), we have
Also by
, there is
(2)
Recalling that the colored edges are either
-edges or k-edges, by (2), we have
(3)
By
and
, there is
. Also by (3), we have
Case 2.
.
By
, there is
. Recall that H
is an odd-edge (even-edge) hypergraph. For each integer
, if there exists a k-edge in
, then H must have no
-edge. It means that, before we color k-edge e, the colored edges are either
-edges or k-edges. Then we count the number of
-edges which intersect with e in H to estimate of
. As discussed above, for each vertex
, the number of its adjacent vertices contained in intersecting edges of e is at most
. And similarly, the number of adjacent vertices of v which are contributed by intersecting k-edges of e is
. Recall that, for each
-edge incident with vertex v, the
-edge contains at least
vertices adjacent
to v. Then
is true for each vertex
. By
and
, the number of
-edges which intersect with e satisfies that
Then we have
Recalling that
, there is
As discussed above, in either of the cases,
holds for each integer
and each k-edge
, which means that there exists an available color to color every edge
. Then we have an edge coloring of H with at most n colors.
For general hypergraphs, we have the following extension. Note that, for each odd-edge (even-edge) hypergraph H,
holds for any pair of distinct edges
with
. Inspired by the gap
in odd-edge (even-edge) hypergraphs, we can describe a more general class of linear hypergraphs by the following definition. Call
is the edge gap of hypergraph H. Restricting
by edge gap of hypergraph, we have the following result.
Theorem 5. Let H be a loopless linear hypergraph. If
holds for every integer
and every k-edge
, then
.
Proof. We give an edge coloring of H with at most n colors in a non-increasing order of edge cardinality. For any integer
, if H has no k-edges, then there is no further discussion. If H has k-edges, let
be a k-edge. We also use
to denote the number of colors appearing on intersecting edges of e. We discuss two cases according to the magnitude between n and
.
Case 1.
.
Noting that
in this case,
is strictly monotonically decreasing with respect to
. By
, there is
. Therefore, we have
. As
discussed above, when we are ready to color edge e, the colored edges are either
-edges or k-edges. And similarly, for each vertex
, we have
. Recalling that
and
, there is
(4)
Since the value of
is no more than the number of colored edges which are intersecting with e, by inequation (4) and
, we have
Case 2.
.
Noting that
in this case,
is monotonically increasing with respect to
. Then there is
. So,
.
By the definition of the edge gap
, if there exist some k-edges in
, then H must have no
-edges for any
when
. By the order of coloring edges, before we color k-edge e, the colored edges are either
-edges or k-edges. As discussed above, we first count the number of
-edges which intersect with e. And similarly, for each vertex
, the number of its adjacent vertices contained in intersecting
-edges of e is at most
. Note that each
-edge incident with vertex v has at least
vertices
which are adjacent to v. Then we have
for each vertex
. Since
and
, the number of
-edges intersect with e satisfies that
Also by
and
, there is
Then we have
for every integer
and every k-edge
, which means that there exists an available color to color each edge
when we color the edge with n colors in an order of descending edge cardinality. So H has an edge coloring with at most n colors.
Clearly, Theorem 5 implies the following result.
Corollary 6. Let H be a loopless linear hypergraph with n vertices. If
holds for every integer
and every k-edge
, then
.
Based on the fact that any pair of intersecting edges have at most one common vertex in linear hypergraphs, it is easy to see that the maximum possible number of k-edges in H decreases as k increases. On the other hand, if there is an edge e with large cardinality in linear hypergraph H, then there is no other edge of H that contains any pair of vertices in edge e. That is to say, if a linear hypergraph H has been with a large enough
, then H would satisfy the condition in Theorem 5.
Here is a detailed description. Note that, for each integer
,
holds for each vertex v in any linear hypergraph with n vertices.
Let H be a loopless linear hypergraph with n vertices and
be a k-edge, where
. Then there is
. It is easy to see that, if
holds for every integer
, then
is true for every k-edge
. By Theorem 5, there is
. Note that, when
is large enough,
is true for every
integer
. So,
holds for every loopless linear hypergraph H whose
is large enough.
By Corollary 3,
holds for each loopless linear hypergraph H with n vertices and
. For a hypergraph H and an edge set
, the subgraph induced by
of H is a hypergraph with vertex set
and edge set
. Therefore, by Corollary 3, we can get an edge coloring of the subgraph induced by all
-edges in H with at most n colors, which means that we do not need to consider the coloring of
-edges in H when color H with n colors. So, the edge gap between any pair of
-edges in H does not affect whether
or not. Therefore, we can obtain a more general result by relaxing the constraint conditions in the definition of
. For a loopless linear hypergraph H with n vertices, call
the partial edge gap of H.
Note that we count the gap between k-edges (
) and
-edges in the process of the calculation of partial edge gap
of hypergraph H.
Definition 2.2. (Gap-restricted hypergraphs) A loopless linear hypergraph H with n vertices is called gap-restricted if
holds for every integer
and every k-edge
.
Based on the partial edge gap, we give a result for gap-restricted hypergraphs.
Theorem 7. Let H be a gap-restricted hypergraph with n vertices. There is
.
Proof. By Corollary 3, we have an edge coloring of the subgraph of H which is induced by all
-edges with at most n colors, which means that we can color all
-edges in H with no more than n colors. Now, we will color remaining edges which are not colored in H in a non-increasing order of edge cardinality. For any integer
, if H has no k-edges, then there is no further discussion. If H has k-edges, let e be a k-edge in
. We also use
to denote the number of colors which appear on intersecting edges of e.
When
, i.e.
,
is strictly monotonically decreasing with respect to
. Recalling that
, there is
. Since H is a gap-restricted hypergraph, there is
. By inequation (4) in the proof of Theorem 5 (Case 1), we have
. Note that
. Then there is
When
, i.e.
,
is monotonically increasing with respect to
. Recalling that
, there is
. Therefore, we have
.
By the definition of
and
, if
, then H has no
-edges for any
. When we are ready to color k-edge e (
), since the edge coloring is performed in a non-increasing order, the colored edges are either
-edges or k-edges. As discussed above, for each vertex
, the number of adjacent vertices of v contained by intersecting
-edges of e is at most
. Note that each
-edge which is incident with vertex v contains at least
vertices which are adjacent to v. So,
is true for each vertex
. Considering that
and
, we have
By
and
, there is
There is an available color to color each edge
when we color H with n colors in an order of descending edge cardinality. Then we can get an edge coloring of H with at most n colors.
3. Concluding Remarks
If a loopless linear hypergraph H with n vertices has at most k2 k-edges for every
, then
is true for every
integer
and every k-edge
. So, any hypergraph which satisfies the condition in Theorem 2 is a gap-restricted hypergraph. It is not vice versa. For example, for any integers
, we construct a linear hypergraph H as follows. It is formed by h k-stars (a linear k-uniform hypergraph with k2 k-edges which have exactly one common vertex) and h 2-edges such that the h common vertices of k-stars form an h cycle. Clearly, H satisfies the condition in Theorem 7 but does not satisfy the condition in Theorem 2.
Based on the proof of Theorem 7, if there exists a non-increasing sequence of all edges in H such that, for every integer
and every k-edge
, the number of intersecting k-edges of e is no more than
before e in the sequence, then
.