The Setting
Let be the incidence graph of 13 points and 22 triples of them, a bipartite graph with 35 vertices and 66 edges. A finite simple graph whose homomorphism density lies below , the 66th power of its edge density, is a counterexample to Sidorenko’s conjecture for . Suppose a symmetric kernel with values in on a finite probability space fails the same inequality, its -density lying below the 66th power of its mean. The question is whether finite graphs then fail it too, and from how many vertices on.
The Graph
The points are , and the faces are the following three-element sets of points, in this order: (1)✦ The incidence graph is the simple graph on the 35 vertices formed by the 13 points and the 22 faces in which a point and a face are adjacent exactly when they are incident, .
A corner is a pair of a face and a slot .✦ The three points of each face are listed in increasing order in the slots , and the point of the corner is the point of in slot .✦ There are 66 corners, one for each edge of .
Densities
The homomorphism count of a simple graph in a simple graph , both on finite vertex sets, is the number of maps , injective or not, that send adjacent vertices to adjacent vertices.✦ The homomorphism density of in is (2)✦ and the edge density of is (3)✦
Finite Probability Laws
A finite probability law on a finite set is an assignment of a weight to each point of such that the weights sum to .✦ The expectation of a real function on under is (4)✦
The point mass at a point of is the law on with weight at and elsewhere.✦ For , the mixture of two laws and on is the law with weights ✦; the biased coin with bias is the law on that mixes and in this way.✦ On a nonempty finite set , the uniform law gives every element the weight .✦
The product law of finite probability laws on , one for each index of a finite set , is the law on maps with weights (5)✦ when every is it is written , or for . The compound law of a law on and laws on a finite set , one for each , is the law on with weights .✦
The Random Graph of a Kernel
Let and be finite probability laws on finite sets and , and let be a real function on . The kernel mean of is (6)✦ and its bipartite moment, the homomorphism density of in with points drawn by and faces by , is (7)✦ the product running over the 66 corners.
A symmetric counter kernel is a nonempty finite set with a finite probability law and a function with such that, with on both sides, the kernel mean is positive and the bipartite moment is smaller than .✦
Fix such a kernel and a nonempty finite set . An edge pattern on is an assignment of a bit to each unordered pair of elements of , and the graph of an edge pattern is the simple graph on in which distinct vertices and are adjacent exactly when .✦ For a labelling , the edge coin law at is the product, over the unordered pairs , of the biased coins with bias .✦ The host law is the compound law of and the edge coin laws.✦ The -random graph on is for an edge pattern drawn by .
The noninjective indicator of a map from the 35 vertices of to is when is not injective and when it is.✦
The Claim
Theorem 1. Let be a symmetric counter kernel with kernel mean and bipartite moment .
For every integer with there is a simple graph on the vertex set with at least one edge and (8)✦
For every nonempty finite set , the -random graph on has expected -density (9)✦ and expected edge density (10)✦
For every nonempty finite set , when a map from the vertices of to takes independent values, each uniform on , its noninjective indicator has expectation (11)✦
Let now and be any real numbers, and an integer with . Then (12)✦
In the paper, the result reads: if is a symmetric -valued kernel on a finite probability space with , and , then for any integer there is a finite simple graph on vertices with .
What Is Checked
The claim is stated over the incidence graph of the 13 points and 22 faces, the homomorphism density and the edge density of finite simple graphs, a symmetric counter kernel with its kernel mean and bipartite moment , the host law on edge patterns of a nonempty finite set with their graphs , and the product of uniform laws on the maps from the vertices of to .
Of these constructions, the library proves that the point mass, the mixture, the biased coin, the product law, the compound law and the uniform law each have nonnegative weights summing to .