Elusive extremal graphs
Copyright policy )Elusive extremal graphs
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.
- Jagiellonian University Poland
- Lovasz Laszlo M United States
- University of Warwick
- University of Warwick United Kingdom
- Masaryk University Czech Republic
Extremal problems in graph theory, very large finite graphs, neighborhood sampling, property testing, subgraph sampling, Mathematics - Combinatorics, Density (toughness, etc.), uniqueness of optimal solutions, QA, Small world graphs, complex networks (graph-theoretic aspects), dense graphs, sparse graphs, Computer Science - Discrete Mathematics
Extremal problems in graph theory, very large finite graphs, neighborhood sampling, property testing, subgraph sampling, Mathematics - Combinatorics, Density (toughness, etc.), uniqueness of optimal solutions, QA, Small world graphs, complex networks (graph-theoretic aspects), dense graphs, sparse graphs, Computer Science - Discrete Mathematics
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).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!