Bigraph percolation problems

Abstract

A bigraph $G$ is weakly norming if the $e(G)$th root of the density of $G$ in $|W|$ is a norm in the space of bounded measurable functions $W:\Omega \times \Lambda \to \mathbb{R}$. The only known technique, due to Conlon--Lee, to show that a bigraph $G$ is weakly norming is to present a cut-percolation sequence of $G$. In this paper, we identify a key obstacle for cut-percolation, which we call fold-stability and we show that existence of a cut-percolating of a bigraph $G$ is equivalent to non-existence of non-monochromatic fold-stable colorings of the edges of $G$.

arXiv comment41 pages. (This version fixes a crucial typo in the definition of a fold (2.6.2): $L$ must be a union of connected components of $G-\mathrm{Fix}(f)$ (not of $G$).)