About maximal number of edges in hypergraph-clique with chromatic number 3

arXiv1107.1869MaRDI QIDQ6226496FDOQ6226496

Authors: Danila Cherkashin 

Publication date: 10 July 2011

Abstract: Let $H=(V,E)$ be a hypergraph. By the chromatic number of a hypergraph $H=(V,E)$ we mean the minimum number $chi(H)$ of colors needed to paint all the vertices in $V$ so that any edge $einE$ contains at least two vertices of some different colors. Finally, a hypergraph is said to form a clique, if its edges are pairwise intersecting. In 1973 ErdH{o}s and Lov'asz noticed that if an $n$-uniform hypergraph $H=(V,E)$ forms a clique, then $chi(H)in2,3$. They untoduced following quantity. ${\displaystyle }$ M(n) = max {|E|: exists { m an} n-{ m uniform} { m clique} H = (V,E) { m with} chi(H) = 3}. ${\displaystyle }$ Obviously such definition has no sense in the case of $chi(H)=2$. Theorem 1 (P. Erdos, L. Lovasz} The inequalities hold ${\displaystyle }$ n!(e-1) le M(n) le n^n. ${\displaystyle }$ Almost nothing better has been done during the last 35 years. At the same time, another quantity $r(n)$ was introduced by Lovasz r(n) = max {|E|: ~ exists { m an} ~ n-{ m uniform} ~ { m clique} ~ H = (V,E) ~ { m s.t.} ~ au(H) = n}, ${\displaystyle }$ where $au(H)$ is the {it covering number} of $H$, i.e., ${\displaystyle }$ au(H) = min {|f|: ~ f subset V, ~ forall ~ e in E ~ f cap e eq emptyset}. ${\displaystyle }$ Clearly, for any $n$-uniform clique $H$, we have $au(H)len$, and if $chi(H)=3$, then $au(H)=n$. Thus, $M(n)ler(n)$. Lov'asz noticed that for $r(n)$ the same estimates as in Theorem 1 apply and conjectured that the lower estimate is best possible. In 1996 P. Frankl, K. Ota, and N. Tokushige disproved this conjecture and showed that $r(n)ge(fracn2{)}^{n-1}$. We discovered a new upper bound for the r(n) (so for M(n) too). Theorem 2. ${\displaystyle }$ M(n) leq r(n) le c n^{n-1/2} ln n. ${\displaystyle }$, where c is a constant.

This page was built for publication: About maximal number of edges in hypergraph-clique with chromatic number 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6226496)