A note on codegree problems for hypergraphs
The codegree, \(\text{codeg}(\{u,v\})\), of distinct vertices \(u\), \(v\) of a triple system (= 3-uniform hypergraph) \(\mathcal G\) is defined to be \(|\{e\in{\mathcal G}\mid u, v\in e\}|\); codeg\(({\mathcal G})\) is defined to be \(\min_{u\neq v}\) \({\text{codeg}}(\{u,v\})\). The authors consider a question of S. Abbasi, Problem 1.2: When \(n\equiv 0\pmod 4\), does every triple system \(\mathcal G\) on \(n\) vertices satisfying \({\text{ codeg}}({\mathcal G})\geq\frac n2\), admit a covering by vertex-disjoint copies of \(K_4^{(3)}\)? They prove Theorem 2.1: For every \(\varepsilon>0\) there exists an infinite family \(\{{\mathcal G}_i\}_{i\in I}\) of triple systems so that each \({\mathcal G}\in\{{\mathcal G}_i\}_{i\in I}\) has the property that \(\text{codeg} ({\mathcal G})\geq (\frac 35-\varepsilon)|V({\mathcal G})|\), and that every collection of vertex-disjoint copies of \(K_4^{(3)}\) within \(\mathcal G\) leaves at least \(\varepsilon|V({\mathcal G})|\) vertices uncovered. They follow this with Conjecture 3.1: Let \(\mathcal G\) be a triple system on \(n\) vertices. If \({\text{codeg}}({\mathcal G})\geq\frac{n}2\), then \(\mathcal G\) contains a \(K_4^{(3)}\). Modifying an example due to the second author and \textit{V. Rödl} [Regularity properties for triple systems, in preparation], they prove probabilistically that the constant \(\frac 12\) in the lower bound for \({\text{codeg}}({\mathcal G})\) in Conjecture 3.1 cannot be improved: There exists a triple system \({\mathcal G}\) on \(n\) vertices which satisfies \(\text{codeg}({\mathcal G})=\frac n2-o(n)\), but which contains no \(K_4^{(3)}\).
- Perfect matchings and K₄^3-tilings in hypergraphs of large codegree
- On codes from hypergraphs.
- Subgraphs with large minimum \(\ell\)-degree in hypergraphs where almost all \(\ell\)-degrees are large
- Codegree problems for projective geometries
- On the co-degree threshold for the Fano plane
- The co-degree density of the Fano plane
- Co-degree density of hypergraphs
- Codegree thresholds for covering 3-uniform hypergraphs
- The codegree threshold for 3-graphs with independent neighborhoods
- On the codegree density of complete 3-graphs and related problems
- Extremal problems on the hypercube and the codegree Turán density of complete r-graphs
- Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
- Covering and tiling hypergraphs with tight cycles
- Shadows of 3-uniform hypergraphs under a minimum degree condition
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- A geometric theory for hypergraph matching
- The codegree Turán density of tight cycles minus one edge
- Positive co-degree densities and jumps
- The codegree Turán density of 3-uniform tight cycles
- Positive co-degree density of hypergraphs
- Positive co-degree Turán number for C₅ and C₅^-
- Hypergraphs with arbitrarily small codegree Turán density
- A jump in the codegree Turán densities of long tight cycles
- The codegree Turán density of tight cycles
- On an extremal hypergraph problem related to combinatorial batch codes
- Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
- Packing k-partite k-uniform hypergraphs
This page was built for publication: A note on codegree problems for hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2732632)
