Forcing Graphs

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., and forcing graphs play an important role in the study of pseudorandomness in graph sequences.

Definitions

Let , known as the subgraph density (in particular, is the edge density of ). A sequence of graphs is called quasi-random if, for all graphs , the edge density approaches some and approaches as increases, where is the number of edges in . Intuitively, this means that a graph sequence with a given edge density has the number of graph homomorphisms that one would expect in a random graph sequence. A graph is called forcing if for all graph sequences where approaches as goes to infinity, is quasi-random if approaches . In other words, one can verify that a sequence of graphs is quasi-random by just checking the homomorphism density of a single graph.

There is a second definition of forcing graphs using the language of graphons. Formally, a graph is called forcing if every graphon such that is constant. Intuitively, it makes sense that these definitions are related. The constant graphon represents the Erdős–Rényi random graph , so one could expect it to have a close relationship with quasi-random graphs. In fact, these definitions are equivalent.

Examples

The first forcing graph to be considered is the 4-cycle , as it bears a close relationship with other conditions of quasi-randomness. It was shown in the same paper by Chung, Graham, and Wilson that every even cycle and complete bipartite graphs of the form with are forcing. Conlon, Fox, and Sudakov expanded this last result to include all bipartite graphs with two vertices in one part that are complete to the other part

Forcing families

Forcing families provide a natural generalization of forcing graphs. A family of graphs is forcing is quasi-random whenever approaches for all . Characterizing forcing families is much more challenging than characterizing forcing graphs, so there are few that are known. Known forcing families include:

* , where is a positive integer;
* , where and are positive integers with ;
* , where ; and
* , where and .

Forcing conjecture

The forcing conjecture was posed by Skokan and Thoma in 2004 and formalized by Conlon, Fox, and Sudakov in 2010. It provides a characterization for forcing graphs, formalized as follows:

One direction of this claim is well-known. Chung, Graham, and Wilson showed that if a graph has an odd cycle, it cannot be forcing, so if a graph is forcing, then it must be bipartite. Also, Conlon, Fox, and Sudakov argued that approaches for every forest when is a nearly regular (and not necessarily quasi-random) graph sequences. Thus, a forcing graph must be bipartite and have at least one cycle. The other direction is yet to be proven, but no forcing graph that does not have both of these properties has been found.

The forcing conjecture also implies Sidorenko's conjecture, a long-standing conjecture in the field. It is known that all forcing graphs are Sidorenko, so if the forcing conjecture is true, then all bipartite graphs with at least one cycle would be Sidorenko. Since trees are Sidorenko, all bipartite graphs would be Sidorenko.

References

{{reflist

Graph families