|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Extremal Subgraphs of Random Graphs: an Extended Version | | Graham Brightwell
; Konstantinos Panagiotou
; Angelika Steger
; | | Date: |
26 Aug 2009 | | Abstract: | We prove that there is a constant $c >0$, such that whenever $p ge n^{-c}$,
with probability tending to 1 when $n$ goes to infinity, every maximum
triangle-free subgraph of the random graph $G_{n,p}$ is bipartite. This answers
a question of Babai, Simonovits and Spencer (Journal of Graph Theory, 1990).
The proof is based on a tool of independent interest: we show, for instance,
that the maximum cut of almost all graphs with $M$ edges, where $M >> n$, is
’’nearly unique’’. More precisely, given a maximum cut $C$ of $G_{n,M}$, we can
obtain all maximum cuts by moving at most $O(sqrt{n^3/M})$ vertices between
the parts of $C$. | | Source: | arXiv, 0908.3778 | | 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