The Library
Two conjectures in Ramsey-Turan theory
Tools
Tools
Tools
Kim, Jaehoon, Kim, Younjin and Liu, Hong (2019) Two conjectures in Ramsey-Turan theory. SIAM Journal on Discrete Mathematics, 33 (1). pp. 564-586. doi:10.1137/18M1186708 ISSN 0895-4801.
|
PDF
WRAP-two-conjectures-theory-Liu-2018.pdf - Accepted Version - Requires a PDF viewer. Download (690Kb) | Preview |
Official URL: https://doi.org/10.1137/18M1186708
Abstract
Given graphs H 1 ,...,H k , a graph G is ( H 1 ,...,H k )-free if there is a k -edge-colouring φ : E ( G ) → [ k ] with no monochromatic copy of H i with edges of colour i for each i ∈ [ k ]. Fix a function f ( n ), the Ramsey-Tur ́an function RT( n,H 1 ,...,H k ,f ( n )) is the maximum number of edges in an n -vertex ( H 1 ,...,H k )-free graph with independence number at most f ( n ). We determine RT( n,K 3 ,K s ,δn ) for s ∈ { 3 , 4 , 5 } and sufficiently small δ , confirming a conjecture of Erd ̋os and S ́os from 1979. It is known that RT( n,K 8 ,f ( n )) has a phase transition at f ( n ) = Θ( √ n log n ). However, the value of RT( n,K 8 ,o ( √ n log n )) was not known. We determined this value by proving RT( n,K 8 ,o ( √ n log n )) = n 2 4 + o ( n 2 ), answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings.
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph coloring, Ramsey numbers | ||||||||||||
| Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||
| ISSN: | 0895-4801 | ||||||||||||
| Official Date: | 28 March 2019 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 33 | ||||||||||||
| Number: | 1 | ||||||||||||
| Page Range: | pp. 564-586 | ||||||||||||
| DOI: | 10.1137/18M1186708 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Reuse Statement (publisher, data, author rights): | “First Published in SIAM Journal on Discrete Mathematics in [volume and number, or year], published by the Society for Industrial and Applied Mathematics (SIAM)” and the copyright notice as stated in the article itself “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.” | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| Date of first compliant deposit: | 12 December 2018 | ||||||||||||
| Date of first compliant Open Access: | 12 December 2018 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
