Elusive extremal graphs

DOI10.1112/PLMS.12382MaRDI QIDQ3389178zbMATH OpenOpenAlexWikidataFDO

Authors A. Grzesik, László Miklós Lovász, Daniel Král'

Publication date 10 May 2021

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

sparse graphsproperty testingdense graphsuniqueness of optimal solutionsneighborhood samplingsubgraph samplingvery large finite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Density (toughness, etc.) (05C42)

Abstract: We study the uniqueness of optimal solutions to extremal graph theory problems. Lovasz conjectured that every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints so that the resulting set is satisfied by an asymptotically unique graph. This statement is often referred to as saying that `every extremal graph theory problem has a finitely forcible optimum'. We present a counterexample to the conjecture. Our techniques also extend to a more general setting involving other types of constraints.

Recommendations

• Extremal graph theory and finite forcibility
• Finitely forcible graph limits are universal
• Compactness and finite forcibility of graphons
• On a conjecture of Nagy on extremal densities
• Boundedness of optimal matrices in extremal multigraph and digraph problems

Cited in

(9)

• Inducibility and universality for trees
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• Extremal traceable graphs with non-traceable edges
• Acquisition-extremal graphs
• Extremal graphs having no stable cutset
• Finitely forcible graphons with an almost arbitrary structure
• scientific article; zbMATH DE number 4181393 (Why is no real title available?)
• EXTREME STEINER GRAPHS
• Forcing generalised quasirandom graphs efficiently

This page was built for publication: Elusive extremal graphs

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