Finitely forcible graphons with an almost arbitrary structure

DOI10.19086/DA.12058MaRDI QIDQ5126772zbMATH OpenOpenAlexFDO

Authors László Miklós Lovász, Jonathan A. Noel, Jakub Sosnovec, Daniel Král'

Publication date 20 October 2020

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

convergent sequences of large graphsextremal graph theorygraph limits

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75)

Abstract: Graphons are analytic objects representing convergent sequences of large graphs. A graphon is said to be finitely forcible if it is determined by finitely many subgraph densities, i.e., if the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Such graphons appear in various scenarios, particularly in extremal combinatorics. Lovasz and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Kral and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every $varepsilon>0$ that any graphon spans a $1-varepsilon$ proportion of a finitely forcible graphon.

Recommendations

• Finitely forcible graphons
• Compactness and finite forcibility of graphons
• Infinite-dimensional finitely forcible graphon
• Finitely forcible graph limits are universal
• Weak regularity and finitely forcible graph limits

Cites work

• A new bound for the 2/3 conjecture
• A new lower bound based on Gromov's method of selecting heavily covered points
• A Solution to the 2/3 Conjecture
• Asymptotic structure of graphs with the minimum number of triangles
• Bounds for graph regularity and removal lemmas
• Compactness and finite forcibility of graphons
• Elusive extremal graphs
• Finitely forcible graph limits are universal
• Finitely forcible graphons
• Flag algebras
• Generalized quasirandom graphs
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• Hypergraphs do jump
• Infinite-dimensional finitely forcible graphon
• Large networks and graph limits
• Limits of dense graph sequences
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Moments of two-variable functions and the uniqueness of graph limits
• Non-three-colourable common graphs exist
• On 3-hypergraphs with forbidden 4-vertex configurations
• On the maximum number of five-cycles in a triangle-free graph
• On the Minimal Density of Triangles in Graphs
• On the number of pentagons in triangle-free graphs
• Quasi-random graphs
• Quick approximation to matrices and applications
• Testing properties of graphs and functions
• Threshold graph limits and random threshold graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Very large graphs
• Weak regularity and finitely forcible graph limits

Cited in

(10)

• Finitely forcible graph limits are universal
• Cut distance identifying graphon parameters over weak* limits
• Finitely forcible graphons
• Compactness and finite forcibility of graphons
• On a question of Vera T. Sós about size forcing of graphons
• Weak regularity and finitely forcible graph limits
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons and permutons
• Infinite-dimensional finitely forcible graphon
• Forcing generalised quasirandom graphs efficiently

This page was built for publication: Finitely forcible graphons with an almost arbitrary structure

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