2025/01/31 by Xizhi Liu, Liu, Xizhi · 4 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2501.19229
openalex publication_date 2025/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-graph is a triangle if there exists a positive integer i ≤ \lceil r/2 \rceil such that it is isomorphic to the following r-graph with three edges: \\1, …, r\,~\1, …, i, r+1, …, 2r-i\,~\i+1, …, r, r+1, 2r-i+1, …,2r-1\\. We prove an Andrásfai--Erdős--Sós-type stability theorem for triangle-free r-graphs. In particular, it implies that for large n, the unique extremal triangle-free construction on n vertices is the balanced complete r-partite r-graph. The latter result answers a question by Mubayi and Pikhurko~\cite[Problem~20]MPS11 on weakly triangle-free r-graphs for large n in a stronger form. The proof combines the recently introduced entropic technique of Chao--Yu~\citeCY24 with the framework developed in~\citeLMR23unif,HLZ24.