On forbidding graphs as traces of hypergraphs

2023/10/09 by Dániel Gerbner, Gerbner, Dániel, Picollelli, Michael E. · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.2310.05601

openalex publication_date 2023/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We say that a hypergraph H contains a graph H as a trace if there exists some set S⊂ V(H) such that H|_S=\h∩ S: h∈ E(H)\ contains a subhypergraph isomorphic to H. We study the largest number of hyperedges in 3-uniform hypergraphs avoiding some graph F as trace. In particular, we improve a bound given by Luo and Spiro in the case F=C₄, and obtain exact bounds for large n when F is a book graph.

Cited by

• Recent advances in arrow relations and traces of sets

Related

• Forbidding K_2,t traces in triple systems
• A note on the Turán number for the traces of hypergraphs
• On 3-uniform hypergraphs without a cycle of a given length
• 3-uniform hypergraphs without a cycle of length five
• A simple upper bound for trace function of a hypergraph with applications