Forcing graph

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

Definitions

A sequence of graphs {G_n} is called quasi-random if, for all graphs H, t(K₂, G_n)→p and t(H, G_n)→p^e(H) for some p as n→∞, where t is the homomorphism density (in particular, t(K₂ ,G_n) is the edge density of G_n) and e(H) is the number of edges in H. A graph F is called forcing if for all graph sequences {G_n} with t(K₂, G_n)→p, t(F, G_n)→p^e(F) implies that {G_n} is quasi-random. 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 W such that t(F, W) = t(K₂, W)^e(F) is constant. Intuitively, it makes sense that these definitions are related. The constant graphon W(x, y)=p represents the Erdős–Rényi random graph G(n,p), 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 C₄, 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 C_2t and complete bipartite graphs of the form K_2,t with t ≥ 2 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 F is forcing if t(F, G_n)→ p^e(F) for all F∈F implies that {G_n} is quasi-random. Characterizing forcing families is much more challenging than characterizing forcing graphs, so there are few that are known. Known forcing families include:

• {K₂, C_2t}, where t is a positive integer;
• {C_2s, C_2t}, where s and t are positive integers with s ≠ t;
• {K₂, K_2,t}, where t ≥ 2; and
• {K_2,s, K_2,t}, where s ≠ t and s, t ≥ 2.

These results are attributed to Chung, Graham, and Wilson.

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:

A graph is forcing if and only if it is bipartite and contains a cycle.

One direction of this claim is well-known. If a graph is forcing, then it must be bipartite and contain a 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.