Elusive extremal graphs

DOI10.1112/PLMS.12382zbMATH Open1462.05194arXiv1807.01141OpenAlexW2811492944WikidataQ105319188 ScholiaQ105319188MaRDI QIDQ3389178FDOQ3389178

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)

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.

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

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

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)

Cited In (9)

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

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)