Large holes in quasi-random graphs (Q1010779)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Large holes in quasi-random graphs |
scientific article; zbMATH DE number 5540965
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Large holes in quasi-random graphs |
scientific article; zbMATH DE number 5540965 |
Statements
Large holes in quasi-random graphs (English)
0 references
7 April 2009
0 references
Summary: Quasi-random graphs have the property that the densities of almost all pairs of large subsets of vertices are similar, and therefore we cannot expect too large empty or complete bipartite induced subgraphs in these graphs. In this paper we answer the question what is the largest possible size of such subgraphs. As an application, a degree condition that guarantees the connection by short paths in quasi-random pairs is stated.
0 references
quasi random graphs
0 references
density of large subsets
0 references
largest size empty subgraphs
0 references
largest size of complete bipartite induced subgraphs
0 references
0.8199079632759094
0 references
0.7984283566474915
0 references
0.7982757687568665
0 references
0.7861578464508057
0 references
0.780145525932312
0 references
