Book chapter
On the chromatic number of a random 3-uniform hypergraph
P. 190-203.
We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.
The paper deals with the max-cut problem for random hypergraphs. We consider a binomial model of a random k-uniform hypergraph H(n, k, p) for some fixed k≥3k≥3, growing n and p=p(n)p=p(n). For given natural number q, the max-q-cut for a hypergraph is the maximal possible number of edges that can be properly colored with q colors under the same coloring. Generalizing the known results for graphs we show that in the sparse case (when p=cn/(nk)p=cn/(nk) for some fixed c>0c>0 not depending on n) there exists a limit constant γ(c,k,q)γ(c,k,q) such that
max-q-cut(H(n,k,p))n⟶Pγ(c,k,q)max-q-cut(H(n,k,p))n⟶Pγ(c,k,q)
as n→+∞n→+∞. We also prove some estimates for γ(c,k,q)γ(c,k,q) of the form Ak,q⋅c+Bk,q⋅c√+o(c√)Ak,q⋅c+Bk,q⋅c+o(c).
The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n-uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with not large maximum edge degree is r-colorable. As an application of our proof technique we establish a new lower bound for Van der Waerden number W(n,r), the minimum N such that in any r-coloring of the set {1,...,N} there exists a monochromatic arithmetic progression of length n.
The work deals with combinatorial problems concerning colorings of non-uniform hypergraphs. Let $H=(V,E)$ be a hypergraph with minimum edge-cardinality $n$. We show that if $H$ is a simple hypergraph (i.e. every two distinct edges have at most one common vertex) and $$ \sum_{e\in E}r^{1-|e|}\leqslant c\sqrt{n}, $$ for some absolute constant $c>0$, then $H$ is $r$-colorable. We also obtain a stronger result for triangle-free simple hypergraphs by proving that if $H$ is a simple triangle-free hypergraph and $$ \sum_{e\in E}r^{1-|e|}\leqslant c\cdot n, $$ for some absolute constant $c>0$, then $H$ is $r$-colorable.
The paper deals with the classical extremal problem concerning colorings of hypergraphs. The problem is to find the value m(n,r), equal to the minimum number of edges in a n-uniform hypergraph with chromatic number greater than r. We obtain new upper and lower bounds for m(n,r) in the case when the parameter r is very large in comparison with n.