Unavoidable order-size pairs in hypergraphs -- positive forcing density

DOI10.5070/C63362798MaRDI QIDQ6204681zbMATH OpenOpenAlexFDO

Authors Maria Axenovich, József Balogh, Felix Christian Clemen, Lea Weber

Publication date 2 April 2024

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.06626

zbMATH Keywords

forcing densityinduced hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: ErdH{o}s, F"uredi, Rothschild and S'os initiated a study of classes of graphs that forbid every induced subgraph on a given number $m$ of vertices and number $f$ of edges. Extending their notation to $r$-graphs, we write $(n,e)o_r(m,f)$ if every $r$-graph $G$ on $n$ vertices with $e$ edges has an induced subgraph on $m$ vertices and $f$ edges. The emph{forcing density} of a pair $(m,f)$ is ${\displaystyle }$ sigma_r(m,f) =left. limsuplimits_{n o infty} frac{|{e : (n,e) o_r (m,f)}|}{�inom{n}{r}} ight. .${\displaystyle }$ In the graph setting it is known that there are infinitely many pairs $(m,f)$ with positive forcing density. Weber asked if there is a pair of positive forcing density for $rgeq3$ apart from the trivial ones $(m,0)$ and $$. Answering her question, we show that $(6,10)$ is such a pair for $r=3$ and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.

Recommendations

• Absolutely avoidable order-size pairs in hypergraphs
• More non-bipartite forcing pairs
• Forcing quasirandomness with triangles
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Induced subgraphs of given sizes

Cites work

• Absolutely avoidable order-size pairs for induced subgraphs
• An exact result for 3-graphs
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• Induced subgraphs of given sizes
• On extremal problems of graphs and generalized graphs
• Partition relations for cardinal numbers
• Supersaturated graphs and hypergraphs
• Sur une propriété des nombres tétraédraux
• Systems of sets possessing the T-property
• Unavoidable patterns

Cited in

(5)

• Absolutely avoidable order-size pairs for induced subgraphs
• Absolutely avoidable order-size pairs in hypergraphs
• More non-bipartite forcing pairs
• Avoiding intersections of given size in finite affine spaces \(\operatorname{AG}(n,2)\)
• The feasibility problem: the family \(\mathcal{F}(G)\) of all induced \(G\)-free graphs.

This page was built for publication: Unavoidable order-size pairs in hypergraphs -- positive forcing density

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