Forcing graph
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory, a forcing graph is one whose density determines whether a graph sequence is quasi-random. The term was first coined by Chung, Graham, and Wilson in 1989. Forcing graphs play an important role in the study of pseudorandomness in graph sequences. The forcing conjecture states that the forcing graphs are exactly the cyclic bipartite graphs. It has been described as "one of the major open problems in extremal combinatorics".
In graph theory, a forcing graph is one whose density determines whether a graph sequence is quasi-random. The term was first coined by Chung, Graham, and Wilson in 1989. Forcing graphs play an important role in the study of pseudorandomness in graph sequences. The forcing conjecture states that the forcing graphs are exactly the cyclic bipartite graphs. It has been described as "one of the major open problems in extremal combinatorics".
Text derived from https://en.wikipedia.org/w/index.php?oldid=1351707136 under CC BY-SA 4.0; modifications have been made.