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

Definitions

Let t(H, G) = ⁠# labeled copies of H in G/v(G)^v(H)⁠, known as the subgraph density (in particular, t(K₂, G) is the edge density of G). A sequence of graphs {G_n} is called quasi-random if, for all graphs H, the edge density t(K₂, G_n) approaches some p and t(H, G_n) approaches p^e(H) as n increases, where e(H) is the number of edges in H. 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 F is called forcing if for all graph sequences {G_n} where t(K₂, G_n) approaches p as n goes to infinity, {G_n} is quasi-random if t(F, G_n) approaches p^e(F). 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 {G_n} is quasi-random whenever t(F, G_n) approaches p^e(F) for all F∈F. 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.

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. 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 t(H, G_n) approaches p^e(H) for every forest H when {G_n} 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.