Extremal subgraphs of random graphs
| Autor: | Konstantinos Panagiotou, Angelika Steger, Graham Brightwell |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Random graph
Discrete mathematics Applied Mathematics General Mathematics Maximum cut media_common.quotation_subject Image (category theory) Graph theory Infinity Computer Graphics and Computer-Aided Design Extremal graph theory Combinatorics Matrix (mathematics) Bipartite graph Software media_common Mathematics |
| Zdroj: | Random Structures & Algorithms. 41:147-178 |
| ISSN: | 1042-9832 |
| Popis: | We prove that there is a constant c > 0, such that whenever p ≥ n-c, with probability tending to 1 when n goes to infinity, every maximum triangle-free subgraph of the random graph Gn,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). 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 and M ≤ $(\matrix{ n \cr 2 \cr })$ **image** /2, is “nearly unique”. More precisely, given a maximum cut C of Gn,M, we can obtain all maximum cuts by moving at most \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*}\end{document} **image** vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 (Presented at the Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), 477-485.) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text