Forcing graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.