Loading...
Please wait, while we are loading the content...
Similar Documents
Extremal Subgraphs of Random Graphs L k l 6 Babai
| Content Provider | Semantic Scholar |
|---|---|
| Author | Spencer, Joel |
| Copyright Year | 2006 |
| Abstract | We shall prove that if L is a 3-chromatic (so called "forbidden") graph, and -R" is a random graph on n vertices, whose edges are chosen indepen-6" is a bipartite subgraph of R" of maximum size, -F" is an L-free subgraph of R" of maximum size, dently, with probability p, and then (in some sense) F" and 6" are very near to each other: almost surely they have almost the same number of edges, and one can delete O,( 1) edges from F" to obtain a bipartite graph. Moreover, with p = and L any odd cycle, F" is almost surely bipartite. Notation. Below we restrict our consideration to simple graphs: loops and multiple edges are excluded. We shall denote the number of edges of a graph G by e(G), the number of vertices by u(G), but superscripts will also denote the number of vertices; G", R", T"*d will always be graphs on n vertices. The set of vertices of a graph G is denoted by V(G) . The subgraph of a graph F spanned by a subset A will be denoted by GF(A), or simply by G(A). The chromatic number of a graph G will be denoted by x(G). The number of edges of a graph will be called "the size of the graph." If X and Yare disjoint vertex sets in a graph G, then ec(X, Y) denotes the number of edges joining X to Y, and dc(X, Y) denotes the edge-density between them: Journal of Graph Theory, Vol. 14, No. 5, 599-622 (1990) |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.renyi.hu/~miki/BabaiSimSpen90.pdf |
| Alternate Webpage(s) | http://www.renyi.hu/~miki/BabaiSimSpen90.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
