On the rational Turan exponents conjecture

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 37
  • Download : 0
The extremal number ex(n, F) of a graph F is the maximum number of edges in an n -vertex graph not containing F as a subgraph. A real number r is an element of [1, 2] is realisable if there exists a graph F with ex(n, F) = Theta(n(r)). Several decades ago, Erd6s and Simonovits conjectured that every rational number in [1, 2] is realisable. Despite decades of effort, the only known realisable numbers are 0, 1, 7/5 , 2, and the numbers of the form 1 + 1/m, 2 - 1/m, 2 - 2/m for integers m >= 1. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erd6s and Simonovits. First, we show that 2 - a/b is realisable for any integers a, b >= 1 with b > a and b equivalent to +/- 1 (mod a). This includes all previously known ones, and gives infinitely many limit points 2 - 1/m in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. (C) 2020 Elsevier Inc. All rights reserved.
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2021-05
Language
English
Article Type
Article
Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.148, pp.149 - 172

ISSN
0095-8956
DOI
10.1016/j.jctb.2020.12.003
URI
http://hdl.handle.net/10203/282279
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0