Back to Search
Start Over
The feasible region of induced graphs.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2023:Part 2, Vol. 158, p105-135. 31p. - Publication Year :
- 2023
-
Abstract
- The feasible region Ω ind (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 Ω ind (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) ∈ Ω ind (F) is the inducibility of F and Ω ind (K r) yields the Kruskal-Katona and clique density theorems. We begin a systematic study of Ω ind (F) by proving some general statements about the shape of Ω ind (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ás for the number of cliques in a graph with given edge density. We also consider the problems of determining Ω ind (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 Ω ind (C 4) is determined by the solution to the triangle density problem, which has been solved by Razborov. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BIPARTITE graphs
*QUANTUM graph theory
*INDEPENDENT sets
*COMPLETE graphs
*ALGEBRA
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 158
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 160368784
- Full Text :
- https://doi.org/10.1016/j.jctb.2022.09.003