|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Combinatorial theorems in sparse random sets | | D. Conlon
; W.T. Gowers
; | | Date: |
18 Nov 2010 | | Abstract: | We develop a new technique that allows us to show in a unified way that many
well-known combinatorial theorems, including Tur’an’s theorem, Szemer’edi’s
theorem and Ramsey’s theorem, hold almost surely inside sparse random sets. For
instance, we extend Tur’an’s theorem to the random setting by showing that for
every epsilon > 0 and every positive integer t >= 3 there exists a constant C
such that, if G is a random graph on n vertices where each edge is chosen
independently with probability at least C n^{-2/(t+1)}, then, with probability
tending to 1 as n tends to infinity, every subgraph of G with at least (1 -
frac{1}{t-1} + epsilon) e(G) edges contains a copy of K_t. This is sharp up to
the constant C. We also show how to prove sparse analogues of structural
results, giving two main applications, a stability version of the random
Tur’an theorem stated above and a sparse hypergraph removal lemma. Many
similar results have recently been obtained independently in a different way by
Schacht and by Friedgut, R"odl and Schacht. | | Source: | arXiv, 1011.4310 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER