2-colorings of uniform hypergraphs
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.
- A note on random greedy coloring of uniform hypergraphs
- Color-critical graphs and hypergraphs with few edges: a survey
- scientific article; zbMATH DE number 3188524 (Why is no real title available?)
- Improved bounds and algorithms for hypergraph 2-coloring
- On a combinatorial problem. II
- On a property of families of sets
- On 2-coloring certain k-uniform hypergraphs
- New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)
- Equitable colorings of hypergraphs with \(r\) colors
- On some generalizations of the property B problem of an \(n\)-uniform hypergraph
- On the construction of non-2-colorable uniform hypergraphs
- On the vertex number of almost bipartite hypergraphs
- On balanced colorings of hypergraphs
This page was built for publication: 2-colorings of uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q509176)
