Loading...
Please wait, while we are loading the content...
Similar Documents
Extremal subgraphs of random graphs: an extended version
| Content Provider | Semantic Scholar |
|---|---|
| Author | Brightwell, Graham Panagiotou, Konstantinos Steger, Angelika |
| Copyright Year | 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$. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv.org/pdf/0908.3778v1.pdf |
| Alternate Webpage(s) | http://proxy9747.my-addr.org/myaddrproxy.php/https/arxiv.org/pdf/0908.3778v1.pdf |
| Alternate Webpage(s) | https://arxiv.org/pdf/0908.3778v1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
