\section{Introduction}
Let $H=(A,B;E)$ be a connected bipartite graph with at least one
edge. We distinguish its two vertex parts and call it a
\emph{bigraph} (Definition~\ref{def:bigraph}). For a bounded
measurable function, or \emph{kernel}, $W:[0,1]^2\to\RR$, its
homomorphism density is
\[
 t_H(W)=\int_{[0,1]^A\times[0,1]^B}
       \prod_{uv\in E}W(x_u,y_v)\,dx\,dy.
\]
When $W$ represents the adjacency matrix of a finite graph,
this integral is the proportion of vertex maps that preserve
edges \cite{Lovasz}. The graph $H$ is \emph{weakly norming} if
$\|W\|_{r(H)}:=t_H(|W|)^{1/|E|}$ is a norm on kernels
(Definition~\ref{def:weak-norming}).

Even cycles, complete bipartite graphs, and hypercubes are weakly
norming \cite{Hatami}. Every weakly norming graph is also
edge-transitive: its symmetries can move any edge to any other
\cite{Sidorenko}. A full classification remains open.
Graph norms have close ties to quasirandomness
\cite{Thomason87,CGW}, Schatten--von Neumann norms
\cite{Hatami,Lovasz}, graphon theory \cite{Lovasz,DGRR},
and Sidorenko's inequality \cite{Sidorenko93,Hatami}.

Conlon and Lee \cite{CL} introduced a broad class of weakly norming
graphs, the \emph{reflection bigraphs}. Their construction included
all examples known at the time, and it remains open whether it
captures every weakly norming graph. Roughly, take a finite group
generated by Euclidean reflections and two points in one closed
region between its reflecting hyperplanes. The two vertex parts
are distinguished copies of the points' image sets, with an edge
for each pair of images obtained from the same group element;
see Figure~\ref{fig:reflection-chambers} and
Definition~\ref{def:reflection}.

Their proof proceeds through a combinatorial property called
\emph{cut-percolation}. A \emph{fold} uses a part-preserving symmetry
that is its own inverse and exchanges two sides separated by its
fixed vertices. It keeps the marked edges on one side and copies
that pattern to the other (Definition~\ref{def:fold}). A graph is
cut-percolating if a sequence of folds spreads one marked edge to
all edges;
Figure~\ref{fig:c6-percolation} illustrates this on the six-cycle.
Conlon and Lee proved that reflection bigraphs cut-percolate and
that cut-percolating bigraphs are weakly norming \cite{CL}.
Write $\Fold(H)$ for the group generated by the fold symmetries.

Conlon and Lee suggested that cut-percolating bigraphs should in
turn be reflection bigraphs \cite[Section~6]{CL}. Our main result
proves this prediction (Theorem~\ref{thm:classification}).
Figure~\ref{fig:implications} puts the result in context: reflection
bigraphs now have several equivalent structural characterizations,
while weakly norming graphs have equivalent analytic
characterizations from earlier work \cite{Hatami,DGRR,LS}.
Showing that these two classes coincide would give a powerful structural
characterization of weakly norming graphs.

We also obtain further characterizations and recognition results for
cut-percolating bigraphs, which we describe below.

\begin{figure}[htbp]
\centering
\input{figures/c6-percolation-drawing}
\caption{Three folds spread one marked edge over $C_6$.
At each step, keep the pattern in the shaded half and copy it
across the dashed line. The number of marked edges grows from
one to two, then four, then six. Filled and empty vertices
distinguish the two vertex parts.}
\label{fig:c6-percolation}
\end{figure}

\begin{figure}[!b]
\centering
\input{figures/implications-drawing}
\caption{Relations for a finite connected simple bigraph $H$ with an
edge. Weak H\"older bounds copy counts with different edge kernels
by their monochromatic counts \eqref{eq:holder}; step Sidorenko
means that averaging a graphon over partition classes cannot
increase its copy count (Definition~\ref{def:step-sidorenko}).
The new implication, Lemma~\ref{lem:transitive-reflection},
closes the right-hand cycle. The dashed arrow remains conjectural.
The green arrow holds for incidence bigraphs of simple two-designs
and their uniform twin blowups.}
\label{fig:implications}
\end{figure}

\Needspace{6\baselineskip}
\subsection{Our results}
\paragraph{Classification.}
Our main theorem gives four equivalent descriptions of the graphs
obtained by the Conlon--Lee method (Figure~\ref{fig:implications}).
Edge-transitivity of $\Fold(H)$ means that a sequence of fold
symmetries can move any edge to any other. If the copying process
could only add red edges, this would suffice to make every edge red:
we could reach each edge in turn without losing earlier marks.
In the actual folding game, however, a fold copies both red and
uncolored edges. A red edge becomes uncolored when its counterpart
on the retained side is uncolored. Thus, the implication from
edge-transitivity to cut-percolation is nontrivial.

Transitivity of $\Fold(H)$ on each vertex part is a weaker
condition: any vertex can be moved to any other in the same part,
without requiring the same for edges. We show that even this
condition forces a reflection representation
(Lemma~\ref{lem:transitive-reflection}).

\Needspace{10\baselineskip}
\begin{theorem}[Classification]\label{thm:classification}
Let $H=(A,B;E)$ be a finite connected simple bigraph with at least
one edge. The following conditions are equivalent:
\begin{enumerate}
\item $\Fold(H)$ is transitive on each of $A$ and $B$;
\item $\Fold(H)$ is transitive on $E$;
\item $H$ is a reflection bigraph for a finite Coxeter system;
\item $H$ is cut-percolating.
\end{enumerate}
\end{theorem}

Thus transitivity on the two vertex parts already forces
percolation and a reflection representation. In particular,
\textup{(ii)}$\Rightarrow$\textup{(iv)} settles
Coregliano's explicit Conjecture~1.1 \cite{Coregliano}.
The equivalence with \textup{(iii)} confirms the stronger
reflection prediction stated immediately after Conjecture~6.1
in \cite[Section~6]{CL}. Together with their theorem that
reflection bigraphs are weakly norming, it also settles that
conjecture; see Remark~\ref{rem:broader-cut-group} for the
authors' clarification.

\paragraph{Recognition.}
The classification raises an algorithmic question: given a graph,
can we decide efficiently whether it cut-percolates? We reduce
this problem to graph isomorphism, using polynomially many queries
on graphs of polynomial size and polynomial work between them. This is a
\emph{polynomial-time Turing reduction}
(Section~\ref{sec:recognition-model}).

\Needspace{5\baselineskip}
\begin{theorem}[Recognition]\label{thm:recognition}
On finite connected simple bigraphs with at least one edge,
recognizing cut-percolation is polynomial-time Turing reducible
to graph isomorphism. For an input with $n$ vertices, it can
therefore be decided in time $n^{(\log n)^{O(1)}}$, and in
polynomial time at any fixed maximum degree.
\end{theorem}

The running-time bounds use the graph-isomorphism algorithms of
Babai \cite{Babai} and Luks \cite{Luks}. Section~\ref{sec:recognition}
also gives short, efficiently checkable certificates and an
alternative proof independent of the classification.

\paragraph{Incidence designs.}
For incidence bigraphs of simple two-designs, we can also settle
the remaining implication from weak norming to cut-percolation.
Recall that a two-design consists of equal-sized subsets, called
\emph{blocks}, with every point pair in the same number of blocks;
simple means that no block is repeated (Definition~\ref{def:design}).

\Needspace{7\baselineskip}
\begin{theorem}[Simple two-designs]\label{thm:designs}
Let $F$ be the incidence bigraph of a simple two-design on $v$
points, with block size $2\le k<v$ and every point pair in at
least one block. Then $F$ is cut-percolating if and only if every
$k$-element subset of the points is a block. Within this family,
cut-percolation, being a reflection bigraph, and weak norming
are equivalent. The same classification holds after uniformly
duplicating vertices independently in the two parts.
\end{theorem}

These \emph{complete designs} were already known to give weakly
norming reflection bigraphs \cite{CL}. Our contribution is to
exclude all other designs, even after vertex duplication.
The proof in Appendix~\ref{app:designs} is analytic and independent
of the structural classification.

\paragraph{The one-sided criterion fails.}
Coregliano \cite[Section~7]{CoreLeft} suggested a one-sided analogue:
if the fold group is transitive on the left part, can folds spread
one marked left vertex to the whole left part
(Definition~\ref{def:left-percolation})? We give a counterexample,
showing why transitivity on both parts matters in
Theorem~\ref{thm:classification}.

\begin{theorem}[One-sided counterexample]\label{thm:one-sided}
There is a connected bigraph on $256$ vertices, each of degree
four, whose fold group is transitive on the left part, but no
fold sequence spreads one marked left vertex to the whole left
part. This bigraph is not weakly norming.
\end{theorem}

Section~\ref{sec:one-sided} gives the construction and determines
all its folds. The obstruction to weak norming is in
Appendix~\ref{app:local-obstruction}.

\paragraph{Concrete consequences.}
Two vertices in the same part are \emph{twins} if they have the
same neighbors (Definition~\ref{def:twins}). For a connected
cut-percolating graph without twins, the full group $\Fold(H)$
itself is a finite reflection group (Theorem~\ref{thm:intrinsic}).
In general, identifying twin vertices gives this intrinsic
reflection structure (Corollary~\ref{cor:all-twins}).
For fixed degrees $a,b$ on the two parts, there are only finitely
many connected cut-percolating bigraphs exactly when at least
one of $a,b$ is odd (Theorem~\ref{thm:degree-finiteness}).
At every odd prime degree $p\ge5$, exactly four such bigraphs
occur (Theorem~\ref{thm:prime-degree}).
We also classify those with no cycle of length less than eight
(Theorem~\ref{thm:large-girth}). Among them, only the edge--triangle
incidence bigraph of the regular $24$-cell has minimum degree
at least three. It has $192$ vertices; its two parts index the
edges and triangular faces of that four-dimensional polytope,
with adjacency by containment. Appendix~\ref{app:consequences}
derives these lists from the finite Coxeter diagrams.

\subsection{Further context and previous work}\label{sec:previous-work}
The homomorphism density introduced above extends to independent
probability spaces for the two vertex parts and to a different
kernel on each edge (Section~\ref{sec:analytic-formulations}).
This extension explains the role of H\"older and Cauchy--Schwarz
in the theory.

\paragraph{Analytic characterizations.}
Hatami's generalized H\"older inequality \cite[Theorem 2.8]{Hatami},
stated in \eqref{eq:holder} and also
called \emph{decorated H\"older}, allows a different kernel on each
edge. Writing $m=|E|$, it implies the Sidorenko inequality
\[
 t_H(W)\ge\left(\int_{[0,1]^2}W\right)^m
 \qquad(W\ge0).
\]
Sidorenko's conjecture asks for this bound for every bipartite $H$
\cite{Sidorenko93}. Progress beyond weakly norming graphs includes
graphs with a vertex adjacent to every vertex of the other part
\cite{CFS} and graphs built by suitable gluings of trees \cite{CKLL}.

In the usual formulation with \emph{graphons}, symmetric measurable
functions $[0,1]^2\to[0,1]$ \cite{Lovasz}
(Section~\ref{sec:analytic-formulations}),
Kr\'al', Martins, Pach, and Wrochna \cite{KMPW} introduced the
step Sidorenko property from Figure~\ref{fig:implications}.
Weak norming immediately implies it: the averaging operation
cannot increase a relabeling-invariant norm, by convexity;
see the explanation after Definition~\ref{def:step-sidorenko}.
Dole\v{z}al, Greb\'{i}k, Hladk\'{y}, Rocha, and
Rozho\v{n} \cite[Theorem 3.25]{DGRR} proved the converse for
connected graphs.
Lee and Sch\"ulke \cite[Theorem 1.5(i)]{LS} characterized weak
norming by convexity of $W\mapsto t_H(W)$ on nonnegative graphons:
the value at a weighted average of kernels is at most the same
weighted average of their values. They used Hessians, matrices of second partial derivatives
along finite-dimensional kernel perturbations, to exclude several
edge-transitive candidates; the same test underlies
Lemma~\ref{lem:cross-covariance}.

These characterizations are analytic tests for the property,
rather than a description of the graphs that have it.
The remaining structural question is whether every connected
weakly norming bigraph is cut-percolating. We leave this open.
By Theorem~\ref{thm:classification}, it is equivalent to asking
whether weak norming forces transitivity of the fold group.

\paragraph{Symmetry and percolation.}
Hatami \cite{Hatami} proved basic restrictions on weakly norming
graphs, including \emph{biregularity}: all vertices in each part
have the same degree, possibly different between parts
(Definition~\ref{def:bigraph}). Sidorenko \cite{Sidorenko}
proved that a connected weakly norming graph must be
edge-transitive under its full automorphism group, the group of
all part-preserving graph symmetries (Section~\ref{sec:graph-notation}).
That group can be larger than the fold group.
For instance, the Heawood graph has an edge-transitive
automorphism group but is not weakly norming. It is the incidence
graph of the Fano plane, the design on seven points whose seven
three-point blocks contain each point pair exactly once. The criteria of \cite{KMPW} exclude it;
Example~\ref{ex:fano-profile} gives an explicit witness.

For reflection bigraphs, Baek, Conlon, and Lee
\cite[Section 3.1]{BCL} gave an algebraic proof of percolation
on the Coxeter coset spaces of
Definition~\ref{def:reflection}. They used a stronger percolation
property to bound the number of edges in graphs containing no
copy of certain incidence graphs. These arguments start with a reflection representation;
our classification recovers one from the fold group.

Coregliano \cite{Coregliano} proved that a connected bigraph
cut-percolates exactly when every \emph{fold-stable} edge
coloring is monochromatic. Here a coloring may change under
a fold provided the resulting colored bigraph is isomorphic
to the original one (Definition~\ref{def:fold-stable}).
Monochromatic means that all edges have one color.
Our classification supplies a simpler
obstruction: when percolation fails, a nonempty proper union
of fold-group orbits in one vertex part gives a nonconstant
two-color \emph{star coloring}, with all edges at each vertex of
one part sharing a color, fixed pointwise by every oriented
fold. See Corollary~\ref{cor:star-obstruction}.

\paragraph{Incidence designs.}
Our analytic argument builds on the positivity tests for weighted
homomorphism counts of Kr\'al', Martins, Pach, and Wrochna
\cite[Theorem 3]{KMPW}. If a design's incidence bigraph is weakly
norming, these tests force swaps of points to preserve the blocks.
We show that there must be enough
such swaps to make every subset of the prescribed size a block.
The argument also handles uniform vertex duplication. Together
with the known reflection construction \cite{CL}, this proves
Theorem~\ref{thm:designs} independently of the structural classification.

\Needspace{8\baselineskip}
\subsection{Proof ideas and organization}
The proof of the classification has two steps.

\paragraph{Finding a reflection quotient.}
The graph's \emph{Laplacian} is the matrix in~\eqref{eq:laplacian}
comparing each vertex value with the values at its neighbors.
Place the vertices in its \emph{Fiedler eigenspace}, the eigenspace
for the smallest positive eigenvalue, by projecting their coordinate
vectors onto it, as in~\eqref{eq:spectral-map}. A fold is \emph{atomic}
if it exchanges just two components outside its fixed vertices
(Definition~\ref{def:atomic}). Its
\emph{odd functions}, which change sign under the involution, are
controlled by the \emph{Dirichlet Laplacian} on one component:
the Laplacian restricted to functions zero outside that component.
Its lowest eigenvector is strictly positive and unique up to scale.
Consequently, the atom acts on the Fiedler eigenspace either
trivially or as an orthogonal reflection. The reflecting
hyperplane, or \emph{mirror}, contains exactly the images of its
fixed vertices. Identifying vertices with the same image gives the
\emph{spectral quotient}, which is a reflection bigraph.
Section~\ref{sec:spectral-setup} defines the spectral objects;
Definition~\ref{def:spectral-quotient} defines the quotient.

\paragraph{Recovering the fibers.}
The vertices above one quotient vertex form its \emph{vertex
fiber}; the edges above one quotient edge form its \emph{edge
fiber} (Definition~\ref{def:spectral-quotient}).
Fold all image points into one fundamental chamber by a sequence
of atomic folds. This sequence gives a bijection from each original vertex
fiber to one of two fibers above a chosen \emph{base edge}, and
from each whole edge fiber to the base edge fiber, using compatible
endpoint bijections.
The original graph is therefore exactly a part-respecting
tensor product $H=R\otimes F$: its vertices have two coordinates,
and adjacency holds in both coordinates
(Definition~\ref{def:tensor}). Here $R$ is the reflection quotient,
and the \emph{residual factor} $F$ is the graph inside the base
edge fiber (Theorem~\ref{thm:tensor}). It inherits fold-group
transitivity and has fewer edges. Induction gives the
classification.

\paragraph{Recognizing cut-percolation.}
The Laplacian eigenvectors identify a polynomial list of possible
component pairs exchanged by atomic folds
(Lemma~\ref{lem:support-list}). Graph-isomorphism queries then
determine which vertex moves these folds allow. By the classification,
it suffices to check whether these moves connect each vertex part
(Section~\ref{sec:vertex-recognition}).

\paragraph{Excluding incomplete designs.}
We record, for each point, the labels assigned to its neighboring
blocks after deleting one chosen block
(Definition~\ref{def:profiles}). Decorated H\"older imposes a
positivity condition on these records (Lemma~\ref{lem:profile-psd}).
For a design, this forces enough swaps of points to generate all
point permutations, so every possible block must be present.
Deleting all copies of the chosen block extends the argument to
uniform vertex duplication.

\paragraph{Separating the one-sided notions.}
The counterexample encodes its left vertices by bit strings.
Some bits can be copied freely. Among vertices agreeing on these
bits, differences in the remaining three bits survive every fold
sequence. This prevents percolation,
although the fold symmetries together can move any left vertex
to any other. The key work is to determine all folds, ruling out
further symmetries that could erase the protected differences
(Section~\ref{sec:one-sided}).

Section~\ref{sec:prelim} introduces folds, reflection bigraphs,
and their connection to graph norms.
Section~\ref{sec:structure} proves the classification, and
Section~\ref{sec:recognition} gives the recognition algorithm
and an independent alternative. Section~\ref{sec:one-sided}
constructs the one-sided counterexample.
Appendix~\ref{app:designs} contains the design classification
and its analytic inequality, and settles Problem~2 of Amarra,
Devillers, and Praeger \cite{ADP} (Corollary~\ref{cor:adp-aut}).
Appendix~\ref{app:consequences}
describes the intrinsic fold group and derives the consequences
for degrees and short cycles. Appendix~\ref{app:local-obstruction}
proves the analytic obstruction for the one-sided counterexample.