2021/08/14 by Leonardo N. Coregliano, Coregliano, Leonardo N., Alexander Razborov +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Primary: 05C35 #Secondary: 28A35
paper · pdf · doi:10.48550/arxiv.2108.06599
openalex publication_date 2021/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sidorenko's Conjecture says that the minimum density of a bigraph G in a bigraphon W of a given edge density is attained when W is a constant function. A consequence of a result by B. Szegedy is that it is enough to show Sidorenko's Conjecture under the further assumption that W is biregular. In this paper, we retrieve this result with a more elementary proof. With this biregularity result and some ideas of its proof, we also obtain simple proofs of several other results related to Sidorenko's Conjecture. Furthermore, we also show that bigraphs that have a special type of tree decomposition, called reflective tree decomposition, satisfy Sidorenko's conjecture. This both unifies and generalizes the notions of strong tree decompositions and N-decompositions from the literature.