DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kang, Dong Yeap | ko |
dc.contributor.author | Kim, Jaehoon | ko |
dc.contributor.author | Liu, Hong | ko |
dc.date.accessioned | 2021-04-05T02:30:19Z | - |
dc.date.available | 2021-04-05T02:30:19Z | - |
dc.date.created | 2021-04-05 | - |
dc.date.created | 2021-04-05 | - |
dc.date.created | 2021-04-05 | - |
dc.date.issued | 2021-05 | - |
dc.identifier.citation | JOURNAL OF COMBINATORIAL THEORY SERIES B, v.148, no.1, pp.149 - 172 | - |
dc.identifier.issn | 0095-8956 | - |
dc.identifier.uri | http://hdl.handle.net/10203/282279 | - |
dc.description.abstract | 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. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.title | On the rational Turan exponents conjecture | - |
dc.type | Article | - |
dc.identifier.wosid | 000624939200006 | - |
dc.identifier.scopusid | 2-s2.0-85099234280 | - |
dc.type.rims | ART | - |
dc.citation.volume | 148 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 149 | - |
dc.citation.endingpage | 172 | - |
dc.citation.publicationname | JOURNAL OF COMBINATORIAL THEORY SERIES B | - |
dc.identifier.doi | 10.1016/j.jctb.2020.12.003 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.contributor.nonIdAuthor | Kang, Dong Yeap | - |
dc.contributor.nonIdAuthor | Liu, Hong | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Turan numbers | - |
dc.subject.keywordAuthor | Extremal number | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.