Rational exponents in extremal graph theory
Copyright policy )Rational exponents in extremal graph theory
Given a family of graphs \mathcal{H} , the extremal number ex (n, \mathcal{H}) is the largest m for which there exists a graph with n vertices and m edges containing no graph from the family \mathcal{H} as a subgraph. We show that for every rational number r between 1 and 2, there is a family of graphs \mathcal{H}_r such that ex (n, \mathcal{H}_r) = \Theta(n^r) . This solves a longstanding problem in the area of extremal graph theory.
- University of Oxford United Kingdom
- Carnegie Mellon University United States
- THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD United Kingdom
- California Institute of Technology United States
bipartite graphs, Extremal graph theory, algebraic constructions, FOS: Mathematics, Mathematics - Combinatorics, 19999 Mathematical Sciences not elsewhere classified, Combinatorics (math.CO), 004, 510
bipartite graphs, Extremal graph theory, algebraic constructions, FOS: Mathematics, Mathematics - Combinatorics, 19999 Mathematical Sciences not elsewhere classified, Combinatorics (math.CO), 004, 510
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).25 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%
Citations provided by BIP!Popularity provided by BIP!