About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3

Details About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3 About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3

2011-10-08

arxiv.org/abs/1110.1756v1

Mathematics

Combinatorics

6 pages

Scientific paper

In 1973 P. Erd\H{o}s and L. Lov\'asz noticed that any hypergraph whose edges are pairwise intersecting has chromatic number 2 or 3. In the first case, such hypergraph may have any number of edges. However, Erd\H{o}s and Lov\'asz proved that in the second case, the number of edges is bounded from above. For example, if a hypergraph is $ n $-uniform, has pairwise intersecting edges, and has chromatic number 3, then the number of its edges does not exceed $ n^n $. Recently D.D. Cherkashin improved this bound (see \cite{Ch}). In this paper, we further improve it in the case when the number of vertices of an $n$-uniform hypergraph is bounded from above by $ n^m $ with some $ m = m(n) $.

Affiliated with

Also associated with

No associations

Rating

About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and About dependence of the number of edges and vertices in hypergraph clique with chromatic number 3 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497814