2-colorings of uniform hypergraphs (Q509176): Difference between revisions

One of the most popular and classical extremal problems in hypergraph theory is the property of the existence \(2\)-coloring of its vertex set such that no hyper-edge of the hypergraph concerned is monochromatic. Certain bounds for the least number \(m(n)\) of edges of an \(n\)-uniform hypergraph with this property have been determined in the recent literature. A hypergraph \(H\) is said to have the property \(B_k\) if its vertex set can be \(2\)-colored so that every edge has at least \(k\) vertices of each color. Let \(m_k(n)\) denote the least number of edges of an \(n\)-uniform hypergraph without property \(B_k\). A hypergraph \(H\) is said to satisfy the property \(B_{k,\varepsilon}\) if there exists a spanning subgraph \(H^\prime=(V,E^\prime)\) with the property \(B_k\) for which \(E^\prime|\geq (1-\varepsilon)|E|\). The least number of edges in a n-uniform hypergraph without property \(B_{k,\varepsilon}\) is denoted by \(m_{k,\varepsilon}(n)\). Note that for \(\varepsilon= 0\), we have \(m_{k,\varepsilon}(n)=m_k(n)\). In this paper, authors discuss an interesting theorem which provides a lower bound for the quantity \(m_{k,\varepsilon}(n)\). This results states that if \(\varepsilon\geq 14\), \(k\geq 2\) and \(2k^2(n-k)\leq (n-2k)^2\), then \(m_{k,\varepsilon}(n)\geq 0.0361\cdot\varepsilon\cdot\sqrt{n}\cdot\frac{2^{2n-2}}{{\binom{n-1}{k-1}}^2}\). This is the only result proved in this note. The arguments in the proof of this result are computational and logical in nature and are mathematically valid. The content of the paper seems to generate further findings in this area of research.