An approximate version of Sidorenko's conjecture (Q616156): Difference between revisions

A conjecture of Erdős-Simonovits and Sidorenko states that, if \(H\) is a bipartite graph, then the random graph with edge density \(p\) has in expectation asymptotically the minimum number of copies of \(H\) over all graphs of the same order and edge density. In this paper the authors prove that this conjecture holds for every bipartite graph which has a vertex completely connected to the other part. The proof uses a new probabilistic technique called dependent random choice method. As a corollary they obtain an approximate version of the conjecture for all graphs. The authors also answer a question of \textit{F.R.K. Chung}, \textit{R.L. Graham} and \textit{R.M. Wilson} [``Quasi-random graphs'', Combinatorica 9, No.\,4, 345--362 (1989; Zbl 0715.05057)] by proving a theorem for a large class of bipartite graphs, namely for every bipartite graph which has two vertices in one part completely connected to the other part, which has at least two vertices. In the third section of the paper some remarks about related problems are given.