Left-cut-percolation and induced-Sidorenko bigraphs

Abstract

A Sidorenko bigraph is one whose density in a bigraphon $W$ is minimized precisely when $W$ is constant. Several techniques of the literature to prove the Sidorenko property consist of decomposing (typically in a tree decomposition) the bigraph into smaller building blocks with stronger properties. One prominent such technique is that of $N$-decompositions of Conlon--Lee, which uses weakly Hölder (or weakly norming) bigraphs as building blocks. In turn, to obtain weakly Hölder bigraphs, it is typical to use the chain of implications reflection bigraph $⟹$ cut-percolating bigraph $⟹$ weakly Hölder bigraph. In an earlier result by the author with Razborov, we provided a generalization of $N$-decompositions, called reflective tree decompositions, that uses much weaker building blocks, called induced-Sidorenko bigraphs, to also obtain Sidorenko bigraphs. In this paper, we show that "left-sided" versions of the concepts of reflection bigraph and cut-percolating bigraph yield a similar chain of implications: left-reflection bigraph $⟹$ left-cut-percolating bigraph $⟹$ induced-Sidorenko bigraph. We also show that under mild hypotheses, the "left-sided" analogue of the weakly Hölder property (which is also obtained via a similar chain of implications) can be used to improve bounds on another result of Conlon--Lee that roughly says that bigraphs with enough vertices on the right side of each realized degree have the Sidorenko property.

42 pages, 5 figures