The matching lower bound for 4-cycles is a good point of reference for understanding lower bounds for the \(\mathsf {CONGEST}\)  model that rely on reductions from 2-party communication complexity. It relies on the fact that there is a 4-cycle-free graph \(G\)  on \(n\)  nodes with \(\Theta (n^{3/2})\)  edges, due to Erdös [1]}, whose work implies that this is the Turán Number of 4-cycles [2]}. The setting is as follows. Each of two players, Alice and Bob, has an input string of \(k\)  bits, \(x=(x_1,\dots , x_k)\)  and \(y=(y_1,\dots , y_k)\) , respectively. By communicating with each other, the players need to compute the set disjointness function \(Disj(x,y)\) , whose value is 1 if and only if the input strings represent disjoint subsets of the set \(\lbrace 1,\dots ,k\rbrace \) , that is, if and only if there is no index \(1\le i \le k\)  such that \(x_i=y_i=1\) . The 2-party set disjointness problem is known to require exchanging \(\Omega (k)\)  bits, even by randomized protocols due to Kalyanasundaram and Schnitger [3]}, Razborov [4]}, and Bar-Yossef, Jayram, Kumar, and Sivakumar [5]}. The reduction to distributed detection of 4-cycles is as follows. Each of the two players takes a subgraph of the 4-cycle free graph \(G\)  according to their respective input. That is, the edges of \(G\)  are mapped to the set \(\lbrace 1,\dots ,k\rbrace \) , with a value of \(n\)  for which \(k=\Theta (n^{3/2})\) . Each player imagines a subgraph of \(G\)  that has an edge for any index in which their input is 1. The players then imagine that their two subgraphs are connect by a perfect matching: each node in Alice's subgraph is connected to the respective node in Bob's subgraph (the nodes of both subgraphs are the nodes of \(G\) ). Now, it is easy to see that the combined graph contains a 4-cycle if and only if the input strings \(x,y\)  are disjoint, as the only 4-cycles that can occur are those that have two edges from the perfect matching, and two edges that represent the same index in the bit strings of the players. Thus, if Alice and Bob can simulate a distributed algorithm for 4-cycle detection, they solve set disjointness. They simulate a given algorithm as follows. Any message that the algorithm sends between two nodes that are in the same subgraph (either that of Alice of that of Bob) can be internally simulated by the respective player. The only messages that need to be explicitly sent between the two players are those that are sent along the edges of the perfect matching. There are \(n\)  such edges, and so simulating a round of the detection algorithms costs \(O(n\log (n))\)  bits of communication between the two players. Since \(\Omega (k)=\Omega (n^{3/2})\)  is a lower bound on the total number of bits that need to be exchanged for solving set disjointness, we get that the distributed 4-cycle detection algorithm must consist of at least \(\Omega (k/n\log (n))=\Omega (n^{3/2}/n\log (n))=\tilde{\Omega }(n^{1/2})\)  rounds.
