Sidorenko Conjecture: How OpenAI’s 35-Vertex Graph Challenges the Random-Graph Bound
Randomness was supposed to set the floor. For every bipartite pattern, the Sidorenko conjecture predicts that a graph with a given edge density contains at least the pattern density supplied by a uniformly random model. OpenAI’s manuscript claims that a carefully arranged graph can slip beneath that floor. The proposed Sidorenko conjecture counterexample has 35 … Read more