2023/09/22 by Dmitriy Gorovoy, Gorovoy, Dmitriy, Andrzej Grzesik +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2309.12866
openalex publication_date 2023/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1991 Gy\H ori, Pach, and Simonovits proved that for any bipartite graph H containing a matching avoiding at most 1 vertex, the maximum number of copies of H in any large enough triangle-free graph is achieved in a balanced complete bipartite graph. In this paper we improve their result by showing that if H is a bipartite graph containing a matching of size x and at most (1)/(2)√(x-1) unmatched vertices, then the maximum number of copies of H in any large enough triangle-free graph is achieved in a complete bipartite graph. We also prove that such a statement cannot hold if the number of unmatched vertices is Ω(x).