The degree and codegree threshold for linear triangle covering in 3-graphs

2022/12/07 by Yuxuan Tang, Yue Ma, Tang, Yuxuan +3
Computer Science · Engineering · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2212.03718

openalex publication_date 2022/12/07 · openalex created_date 2022/12/21 · openalex updated_date 2026/07/28

Abstract

Given two k-uniform hypergraphs F and G, we say that G has an F-covering if every vertex in G is contained in a copy of F. For 1≤ i ≤ k-1, let c_i(n,F) be the least integer such that every n-vertex k-uniform hypergraph G with δ_i(G)> c_i(n,F) has an F-covering. The covering problem has been systematically studied by Falgas-Ravry and Zhao [Codegree thresholds for covering 3-uniform hypergraphs, SIAM J. Discrete Math., 2016]. Last year, Falgas-Ravry, Markström, and Zhao [Triangle-degrees in graphs and tetrahedron coverings in 3-graphs, Combinatorics, Probability and Computing, 2021] asymptotically determined c₁(n, F) when F is the generalized triangle. In this note, we give the exact value of c₂(n, F) and asymptotically determine c₁(n, F) when F is the linear triangle C₆³, where C₆³ is the 3-uniform hypergraph with vertex set \v₁,v₂,v₃,v₄,v₅,v₆\ and edge set \v₁v₂v₃,v₃v₄v₅,v₅v₆v₁\.

Related

• The degree and codegree threshold for generalized triangle and some trees covering
• The degree threshold for covering with all the connected 3-graphs with 3 edges
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Codegree thresholds for covering 3-uniform hypergraphs
• Exact minimum codegree thresholds for K₄^--covering and K₅^--covering