The Setting
For finite simple graphs and , a homomorphism from to is a map , injective or not, that sends every edge of to an edge of , and is the number of homomorphisms from to .✦ The homomorphism density of in and the edge density of are the real numbers (1)
The item concerns one bipartite graph with 35 vertices and 66 edges.
The counterexample statement is the assertion that for some positive integer there is a simple graph on the vertex set with at least one edge and .✦
The Graph
The faces are the following twenty-two three-element subsets of the point set : (2)✦
The incidence graph is the bipartite graph whose vertices are the thirteen points and the twenty-two faces, a point being adjacent to a face exactly when .✦
A corner of is a pair of a face index and a slot .✦ The point of a corner of is the entry in slot of the list of the points of in increasing order.✦ The 66 corners are the 66 edges of , the corner joining to .
Kernels on Finite Probability Spaces
A probability law on a finite set is a function whose values sum to .✦ The expectation of a function under is the number .✦ The product of probability laws on , indexed by a finite set , is the probability law on that gives the weight ; when every is and , it is written .✦
For probability laws on a finite set and on a finite set and a function , the kernel mean of is the number ✦, and the bipartite moment of is the number (3)✦ with indexed by the points and by the faces, one factor for each corner.
A symmetric counter kernel is a triple of a nonempty finite set , a probability law on and a function with for all , such that (4)✦
The Claim
Theorem 1. Let be the incidence graph of the faces (2).
For some positive integer and some simple graph on with at least one edge, as in the counterexample statement, (5)✦
The counterexample statement holds: (6)✦
Every symmetric counter kernel gives the counterexample statement: (7)✦
What Is Checked
Claims (5) and (6) are stated over the incidence graph of the faces (2) and over simple graphs on , with the homomorphism density and the edge density (1). Claim (7) is stated over symmetric counter kernels (4), whose kernel mean and bipartite moment (3) are expectations under a probability law on a finite set and under its products.
The library proves that the product of probability laws on a finite set is again a probability law, its weights being nonnegative and summing to , and that adjacency in is symmetric and irreflexive.