The feasible region of induced graphs

DOI10.1016/J.JCTB.2022.09.003MaRDI QIDQ2101166zbMATH OpenOpenAlexFDO

Authors Xizhi Liu, Dhruv Mubayi, Christian Reiher

Publication date 28 November 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

feasible regionsinducibility of graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial aspects of representation theory (05E10)

Abstract: The feasible region $Omeg{a}_{mind}(F)$ of a graph $F$ is the collection of points $(x,y)$ in the unit square such that there exists a sequence of graphs whose edge densities approach $x$ and whose induced $F$-densities approach $y$. A complete description of $Omeg{a}_{mind}(F)$ is not known for any $F$ with at least four vertices that is not a clique or an independent set. The feasible region provides a lot of combinatorial information about $F$. For example, the supremum of $y$ over all $(x,y)inOmeg{a}_{mind}(F)$ is the inducibility of $F$ and $Omeg{a}_{mind}(K_r)$ yields the Kruskal-Katona and clique density theorems. We begin a systematic study of $Omeg{a}_{mind}(F)$ by proving some general statements about the shape of $Omeg{a}_{mind}(F)$ and giving results for some specific graphs $F$. Many of our theorems apply to the more general setting of quantum graphs. For example, we prove a bound for quantum graphs that generalizes an old result of Bollob'as for the number of cliques in a graph with given edge density. We also consider the problems of determining $Omeg{a}_{mind}(F)$ when $F=K_r^{-}$, $F$ is a star, or $F$ is a complete bipartite graph. In the case of $K_r^{-}$ our results sharpen those predicted by the edge-statistics conjecture of Alon et. al. while also extending a theorem of Hirst for $K_4^{-}$ that was proved using computer aided techniques and flag algebras. The case of the 4-cycle seems particularly interesting and we conjecture that $Omeg{a}_{mind}(C_4)$ is determined by the solution to the triangle density problem, which has been solved by Razborov.

Recommendations

• The feasible region of hypergraphs
• scientific article; zbMATH DE number 2197902
• Induced saturation of graphs
• scientific article; zbMATH DE number 6712567
• Feasibility conditions on the parameters of a strongly regular graph
• The inducibility of complete bipartite graphs
• Graphs with bounded induced distance
• scientific article; zbMATH DE number 1262797
• On graphs induced by non-empty subsets
• The inducibility of blow-up graphs

Cites work

• A completion of the proof of the Edge-statistics Conjecture
• A Disproof of a Conjecture of Erdős in Ramsey Theory
• A note on the inducibility of 4-vertex graphs
• A Remark on the Number of Complete and Empty Subgraphs
• Anticoncentration for subgraph statistics
• Edge-statistics on large graphs
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 969189 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Maximum star densities
• On complete subgraphs of different orders
• On Sets of Acquaintances and Strangers at any Party
• On the 3-local profiles of graphs
• On the boundary of the region defined by homomorphism densities
• On the local profiles of trees
• On the Minimal Density of Triangles in Graphs
• Stability from graph symmetrisation arguments with applications to inducibility
• The clique density theorem
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• The exact minimum number of triangles in graphs with given order and size
• The feasible region of hypergraphs
• The inducibility of complete bipartite graphs
• The inducibility of graphs
• The inducibility of graphs on four vertices
• The number of cliques in graphs of given order and size
• Undecidability of linear inequalities in graph homomorphism densities

Cited in

(11)

• On the boundary of the region defined by homomorphism densities
• The feasible region of hypergraphs
• scientific article; zbMATH DE number 6712567 (Why is no real title available?)
• Stability from graph symmetrisation arguments with applications to inducibility
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• The feasibility problem: the family \(\mathcal{F}(G)\) of all induced \(G\)-free graphs.
• Ordered and colored subgraph density problems
• Inducibility in H-free graphs and inducibility of Turán graphs
• The edge-statistics conjecture for hypergraphs
• The binomial random graph is a bad inducer
• Some exact inducibility-type results for graphs via flag algebras

This page was built for publication: The feasible region of induced graphs

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