✦ LIBER ✦

Extremal subgraphs of random graphs

✍ Scribed by László Babai; Miklós Simonovits; Joel Spencer

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 1015 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140511

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We shall prove that if L is a 3‐chromatic (so called “forbidden”) graph, and —R^n^ is a random graph on n vertices, whose edges are chosen independently, with probability p, and —B^n^ is a bipartite subgraph of R^n^ of maximum size, —F^n^ is an L‐free subgraph of R^n^ of maximum size, then (in some sense) F^n^ and B^n^ are very near to each other: almost surely they have almost the same number of edges, and one can delete O~p~(1) edges from F^n^ to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, F^n^ is almost surely bipartite.

📜 SIMILAR VOLUMES

Extremal subgraphs for two graphs

✍ F.R.K Chung; P Erdös; J Spencer 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 564 KB

Pancyclic subgraphs of random graphs

✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f

Extremal graphs with bounded densities o

Extremal graphs with bounded densities of small subgraphs

✍ Griggs, Jerrold R.; Simonovits, Mikl�os; Thomas, George Rubin 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 1 views

Let Ex(n, k, µ) denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most µ edges. Here we summarize some known results of the problem of determining Ex(n, k, µ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new

Extremal bipartite subgraphs of cubic tr

Extremal bipartite subgraphs of cubic triangle-free graphs

✍ Glenn Hopkins; William Staton 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB

## Abstract A cubic triangle‐free graph has a bipartite subgraph with at least 4/5 of the original edges. Examples show that this is a best possible result.

Random Subgraphs of Cayley Graphs overp-

Random Subgraphs of Cayley Graphs overp-Groups

✍ C.M. Reidys 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 146 KB

The subject of this paper is the size of the largest component in random subgraphs of Cayley graphs, X n , taken over a class of p-groups, G n . G n consists of p-groups, G n , with the following properties: , where K is some positive constant. We consider Cayley graphs X n = (G n , S n ), where S

Long cycles in subgraphs of (pseudo)rand

Long cycles in subgraphs of (pseudo)random directed graphs

✍ Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant __c__ = __c__(γ) such that the following holds. Let __G__ = (__V, E__) be a (pseudo)random directed graph on __n__ vertice