3-uniform hypergraphs and linear cycles

DOI10.1016/J.ENDM.2017.06.064MaRDI QIDQ1689945zbMATH OpenOpenAlexFDO

Authors Beka Ergemlidze, Abhishek Methuku, Ervin Győri

Publication date 18 January 2018

Full work available at URL https://arxiv.org/abs/1609.03934, http://real.mtak.hu/71046/1/1609.03934v2.pdf

zbMATH Keywords

independence numberloose cyclelinear cycle

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Hypergraphs (05C65)

Abstract: Gy'arf'as, GyH{o}ri and Simonovits proved that if a $3$-uniform hypergraph with $n$ vertices has no linear cycles, then its independence number $alphagefrac2n5$. The hypergraph consisting of vertex disjoint copies of a complete hypergraph $K_5^3$ on five vertices, shows that equality can hold. They asked whether this bound can be improved if we exclude $K_5^3$ as a subhypergraph and whether such a hypergraph is $2$-colorable. In this paper we answer these questions affirmatively. Namely, we prove that if a $3$-uniform linear-cycle-free hypergraph doesn't contain $K_5^3$ as a subhypergraph, then it is $2$-colorable. This result clearly implies that its independence number $alphagelceilfracn2ceil$. We show that this bound is sharp. Gy'arf'as, GyH{o}ri and Simonovits also proved that a linear-cycle-free $3$-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free $3$-uniform hypergraph has a vertex of degree at most $n-2$ when $nge10$.

Recommendations

• 3-uniform hypergraphs and linear cycles
• On 3-uniform hypergraphs without linear cycles
• A note on the linear cycle cover conjecture of Gyárfás and Sárközy
• On 3-uniform hypergraphs without a cycle of a given length
• 3-uniform hypergraphs without a cycle of length five

Cites work

• A homological approach to two problems on finite sets
• Exact solution of some Turán-type problems
• On 3-uniform hypergraphs without linear cycles

Cited in

(10)

• 3-uniform hypergraphs without a cycle of length five
• On 3-uniform hypergraphs without linear cycles
• On the size of 3-uniform linear hypergraphs
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• On the feedback number of 3-uniform hypergraphs
• On 3-uniform hypergraphs without a cycle of a given length
• A note on the linear cycle cover conjecture of Gyárfás and Sárközy
• The lifting of graphs to 3-uniform hypergraphs and some applications to hypergraph Ramsey theory
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• 3-uniform hypergraphs and linear cycles

This page was built for publication: 3-uniform hypergraphs and linear cycles

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