A Partial Answer to Sidorenko’s Conjecture on a Correlation Inequality for Bipartite Graphs
Danyal Soybas, Onur Alp Ilhan
Department of Mathematics, Faculty of Education, Erciyes University, Kayseri, Turkey
Email address:
To cite this article:
Danyal Soybas, Onur Alp Ilhan. A Partial Answer to Sidorenko’s Conjecture on a Correlation Inequality for Bipartite Graphs.Mathematics Letters.Vol.1, No. 3, 2015, pp. 17-19. doi: 10.11648/j.ml.20150103.11
Abstract: Sidorenko conjectured an integral inequality for a product of functions h(x_{i}, y_{i}) where the diagram of the product is a bipartite graph G in [8]. We answered the conjecture positively when the function h is multiplicative or additive separable with respect to variables x and y.
Keywords: Sidorenko’s Conjecture, Bipartite Graph, Lebesgue Measure, Measurable Function
1. Introduction
Denote the Lebesgue measure on [0, 1] by µ. Let a fuction h(x, y) be bounded, nonnegative and measurable on [0, 1]^{2}. Let G be a bipartite graph where vertices u_{1}, u_{2},…,u_{n} form the first part and v_{1}, v_{1},…, v_{m} the second part. We denote by E the set of pairs (i, j) for which u_{i} and v_{j }are adjacent in G. So |E| is the number of edges. The following conjecture was discussed in works [2,3] published in Russian. The same arguments were explained in detail again in [8].
Conjecture 1 [2]. For any bipartite graph G and any function h
(1)
Two particular cases of Inequality 1 (G is a path, h is symmetric; G is a path of length 3, h is not necessarily symmetric) were proven in [4,5] and [6], respectively.
One might conjecture that the considered products of functions are always non-negative correlated. Unfortunately, this is not the case. For instance, it would require
However, a counterexample to the last inequality was found in [7].
Conjecture 2 [2]. Let the numbers of edges and vertices of a bipartite graph G satisfy the conditions |E| ≥ n; |E| ≥ m. Then, for any functions h, f_{1}, f_{2},…, f_{n}, g_{1}, g_{2},…, g_{m},
(2)
Inequality 2 is essentially stronger than inequality 1. For instance, inequality 2 implies [2]:
(3)
Conjecture 1 and 2 were proven in [2] for various classes of graphs.
2. Main Results
We start by mentioning a simple example as follows:
Let be a function given by h is trivially non-negative, bounded and Lebesgue measurable. Let G be a finite simple bipartite graph with {u_{1}, u_{2}} such that u_{1}_{ }to both v_{1}_{ }and v_{2 }and u_{2} to both v_{1}_{ }and v_{2}. Siderenko’s conjecture is positively confirmed because
Lemma 3 [1]. Suppose that 1 ≤ r < ∞ and is non-negative. Then. If r > 1, then equality holds if and only if f is (essentially) constant.
In order to make the understanding of Theorem 4 easier, we give a simpler format of it as an example. First let G be a simple bipartite graph from u_{1} to both v_{1} and v_{2} and the function be measurable on [0, 1]^{2}. Let h be written as h(x,y)=h(x).g(y)
I1=
By Lemma 3, we get
Now we can give Theorem 4 which is a generalization of above mentioned argument.
Theorem 4. For any bipartite graph G and any non-negative, bounded and Lebesgue measurable function h such that h(x,y)=f(x).g(y) we have
Proof: Let G be a finite simple bipartite graph with bipartition {u_{1},u_{2,},…u_{m}}
where d(u_{i}) is the degree of u_{i. }
By Lemma 3 we know that the inequality
satisfies for all natural number n.
By using Fubini’s Theorem we have
Hence the proof was completed.
Now under the same assumption of G given before Theorem 4, let the function be written as h(x,y)=f(x)+g(y) which is measurable on [0, 1]^{2}
Since the integrands at second and third order in above expression are the same, by Lemma 3 we have
Theorem 5. For any bipartite graph G and any function h such that h(x,y)=h(x)+g(y), we have
Proof:
By Lemma 3 we get
By Binom expansion we get
which completed the proof.
Following Theorem 6 which was given in [1] can be considered as an useful means to investigate whether our Theorem 4 and Theorem 5 can be generalized to any bounded, non-negative and Lebesgue measurable function h.
Theorem 6 [1]. Suppose than n is a positive integer , not both of p, q are zero, , and f and g non-negative. Then
If neither f nor g is the zero function then if n + p > 1, equality implies that f is constant, and if n + q >1, equality implies that g is constant.
Remark: We do not know whether Theorem 4 is valid for all non-negative, bounded and Lebesgue measurable functions h. If we can show that Theorem 4 is true for any function h such that
where f_{s}(x) and g_{s}(y) are polynomials. Then by using Theorem 4, Theorem 5 and Theorem 6, we can easily generalize it to all h by using well-known Weierstrass approximation theorem, because polynomials are uniformly dense in C([0, 1]).
Acknowledgements
We would like to thank to Prof. Dr. Peter Johnson for his valuable suggestions.
References