TWO CONJECTURES IN RAMSEY-TURAN THEORY

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 101
  • Download : 0
Given graphs H-1, ... , H-k, a graph G is (H-1, ... , H-k)-free if there is a k-edge-coloring phi: E(G) -> [k] with no monochromatic copy of H-i with edges of color i for each i is an element of [k]. Fix a function f(n); then the Ramsey Turan 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, delta n) for s is an element of {3, 4, 5} and sufficiently small (5, confirming a conjecture of Erdos and SOs [Stud. Sci. Math. Hung., 14 (1979), pp. 27-36]. It is known that RT(n, K-8, f (n)) has a phase transition at f (n) = Theta(root n log n). However, the value of RT(n, K-8, o(root n log n)) was not known. We determined this value by proving RT(n, Kg, n, K-8, o(root n log n)) = n(2)/4 + o(n(2)), answering a question of Balogh, Hu, and Simonovits [J. Combin. Theory Ser. B, 114 (2015), pp. 148-169]. The proofs utilize, among others, dependent random choice and results from graph packings.
Publisher
SIAM PUBLICATIONS
Issue Date
2019-03
Language
English
Article Type
Article
Citation

SIAM JOURNAL ON DISCRETE MATHEMATICS, v.33, no.1, pp.564 - 586

ISSN
0895-4801
DOI
10.1137/18M1186708
URI
http://hdl.handle.net/10203/268272
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