Elusive extremal graphs

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 19 Aug 2020Embargo end date: 01 Jul 2018 United States, Poland English Publisher:WileyJournal:Proceedings of the London Mathematical Society, volume 121, pages 1,685-1,736 (issn: 0024-6115, eissn: 1460-244X,

Copyright policy )Funded by:NSF | PostDoctoral Research Fel..., UKRI | Analytic methods for larg..., EC | LaDIST

Authors: Grzesik, Andrzej; Král, Daniel; Lovász, László Miklós;

doi: 10.1112/plms.12382 , 10.48550/arxiv.1807.01141

arXiv: 1807.01141

handle: 1721.1/140576.2

Elusive extremal graphs

- Summary
- Subjects
- Metrics

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.

Countries

United States, Poland

Related Organizations

View all View all

Keywords

FOS: Computer and information sciences, Extremal problems in graph theory, Discrete Mathematics (cs.DM), very large finite graphs, neighborhood sampling, property testing, subgraph sampling, FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), uniqueness of optimal solutions, Combinatorics (math.CO), QA, Small world graphs, complex networks (graph-theoretic aspects), dense graphs, sparse graphs, Computer Science - Discrete Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	4
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%