\section{An algebraic six-block lower construction}
\label{sec:lower-exact}
For a symmetric matrix $L\in\{1,2,3,4\}^{s\times s}$ and a positive
mass vector $a\in\mathbb R^s$ with $\sum_i a_i=1$, partition the
vertex set into blocks of asymptotic proportions $a_i$ and give every
pair between blocks $i,j$ label $L_{ij}$. Diagonal entries specify
labels inside a block. These are finite-part labelings in the graph-limit formulation
of~\cite{CP}; see~\cite{Lovasz} for general background on graph limits.
In this section all vertices are matched, so
our construction gives a lower bound on $\gamma'(4)$ and hence on
$\gamma(4)$.

\subsection{Reducing the matching problem to a quadratic optimization}
For $i<j$, let $x_{ij}$ be the number of matching edges between the
blocks divided by the total number $N$ of vertices. Let $x_{ii}$ be
the proportion of vertices in block $i$ matched internally. Thus
\begin{equation}\label{eq:lower-flow-polytope}
 x_{ii}+\sum_{j\ne i}x_{ij}=a_i,\qquad x_{ij}\ge0.
\end{equation}
The convention on $x_{ii}$ is essential: an internal matching edge
accounts for two vertices. Write $\mathcal P(a)$ for this polytope.
For an edge type $e=ij$, let $V(e)=\{i,j\}$, with a singleton when
$i=j$, and let $L_e=L_{ij}$. Define the symmetric matrix
\[
 H_{ef}=\sum_{u\in V(e)}\sum_{v\in V(f)}
 \mathbf 1\{L_e\le L_{uv},\ L_f\le L_{uv}\}.
\]
The asymptotic proportion of noncritical pairs is
\begin{equation}\label{eq:lower-noncritical}
 Q(x)=x^THx.
\end{equation}
Indeed an endpoint born on an edge of label $b$ is noncritical to an
endpoint born at $c$ precisely when its ambient edge label is at least
both $b$ and $c$. Counting ordered pairs gives the displayed formula;
diagonals and matching edges contribute only $O(N)$ finite error.
Consequently the construction's minimum critical density is
$1-\max_{x\in\mathcal P(a)}Q(x)$.

A useful reduction removes every cross type $ij$ with
$L_{ij}\ge\max(L_{ii},L_{jj})$: replace its mass by the same amount
of internal vertex mass in each endpoint block. This preserves
\eqref{eq:lower-flow-polytope} and weakly decreases the birth label
at every affected endpoint. It therefore cannot decrease $Q$.
It is enough to maximize over the reduced flow polytope.

The maximum of a quadratic need not occur at a polytope vertex.
We will use a sufficient condition that controls the whole polytope.
If $v_1,\ldots,v_m$
are all reduced flow vertices and
\begin{equation}\label{eq:lower-gram-certificate}
 v_i^THv_j\le T\quad(1\le i,j\le m),
\end{equation}
then every convex combination $x=\sum_i\theta_i v_i$ satisfies
$Q(x)=\sum_{i,j}\theta_i\theta_jv_i^THv_j\le T$.
Thus it is enough to check the mixed bilinear values as well as the
values at the vertices. We refer to
\eqref{eq:lower-gram-certificate} as the bilinear certificate.

\subsection{The value and masses}
Let $\tau$ be the unique root in
$(0.359275945611134729,0.359275945611134730)$ of
\[
 P(t)=34006t^6-148176t^5+211627t^4-226450t^3
       +422009t^2-423516t+105476.
\]
Set $D(t)=694t^3-1512t^2+469t+285$ and
\[
 \alpha_L=
 \frac{-49\tau^4+3367\tau^3-7130\tau^2+2072\tau+1484}{12D(\tau)}.
\]
Then
\[
 \alpha_L=0.419772820486240077721086607635089744919175\ldots.
\]
Use blocks $A,B,C,D,E,F$ with label matrix
\[
 L=\begin{pmatrix}
1&2&1&1&1&1\\
2&4&3&4&4&1\\
1&3&1&2&2&1\\
1&4&2&3&3&1\\
1&4&2&3&4&1\\
1&1&1&1&1&1
\end{pmatrix}
\]
and masses $a^*=n(\tau)/(6D(\tau))$, where
\[
 n(t)=\begin{pmatrix}
-77t^3+312t^2-389t+226\\
1469t^3-2981t^2+675t+637\\
(t-1)(1337t^2-1993t-452)\\
222t^3-440t^2+154t+32\\
835t^3-1995t^2+886t+250\\
378t^3-638t^2-53t+113
\end{pmatrix}.
\]
The masses are approximately
\[
 (.0705314504,.3229020494,.3659074690,
 .0234231357,.2005210862,.0167148093).
\]

\begin{theorem}\label{thm:lower-exact}
The minimum asymptotic critical density of this construction is exactly
$\alpha_L$. In particular $\gamma(4)\ge\gamma'(4)\ge\alpha_L$.
\end{theorem}

\begin{proof}
We first exhibit three matching flows that attain the proposed value.
Write the six masses as $(p,b,z,d,e,f)$. The flows, numbered 1, 2,
and 3, have the following coordinates; all coordinates omitted from
the table are zero:
\[
\begin{array}{c|ccc}
 &1&2&3\\\hline
AB&p&0&p\\
AE&0&p&0\\
BC&b-p-f&0&z-d-e\\
BF&f&f&f\\
CD&0&d&d\\
CE&p-b+z+f&e-p&e\\
DE&d&0&0\\
BB&0&b-f&b-p-z+d+e-f\\
CC&0&p+z-d-e&0\\
EE&b-p-z-d+e-f&0&0
\end{array}
\]
The six nonzero coordinates in each flow are strictly positive at $a^*$.
Let $C_1,C_2,C_3$ be their noncritical quadratic matrices, obtained
by substituting this table in \eqref{eq:lower-noncritical}.
We call these flows \emph{active} because they attain the maximum
noncritical density at the chosen masses.
Put $K(t)=111t^3-220t^2+77t+16$ and
\[
 \lambda_1=\frac{(\tau-1)(7\tau^3-6\tau^2-32\tau-14)}{2K(\tau)},
 \quad\lambda_2=\tau,\quad\lambda_3=1-\lambda_1-\lambda_2.
\]
These weights are positive. Exact arithmetic modulo $P$ verifies
\[
 (a^*)^TC_k a^*=1-\alpha_L=:T\quad(k=1,2,3),
 \qquad \left(\sum_k\lambda_kC_k\right)a^*=T\mathbf1.
\]
Thus the active flows attain noncritical density $T$.

For the reverse inequality, the remaining cross types after the
reduction above are
\[
 AB,\ AD,\ AE,\ BC,\ BF,\ CD,\ CE,\ DE,\ DF,\ EF,
\]
together with the six internal types. Let $B$ be their $6\times16$
endpoint-incidence matrix: $B_{i,e}=1$ if type $e$ has an endpoint in
block $i$, and $0$ otherwise, with a single 1 for an internal type.
The reduced polytope is $Bx=a^*$, $x\ge0$. It is bounded, and $B$
has rank six. Its vertices can therefore be enumerated by choosing
six columns $J$, solving $B_Jx_J=a^*$ when $B_J$ is nonsingular,
and setting every other coordinate to zero.

Here are the exact checks used in that enumeration. Let $\bar a$ be
the rational vector
\[
 \begin{split}
 (&0.070531450396389,\ 0.322902049431553,\
   0.365907468971544,\\
  &0.023423135669300,\ 0.200521086237747,\
   0.016714809293466).
 \end{split}
\]
The exact algebraic vector $a^*$ lies in the coordinate box
$|a_i-\bar a_i|\le10^{-13}$. Among the column choices, 2880 are
nonsingular. Of these, exactly 240 have every coordinate of
$B_J^{-1}a$ strictly positive throughout the box; each of the others
has a coordinate strictly negative throughout the box. Thus this
procedure gives every vertex, with the same feasible column choices
throughout the box.
Of the $240\cdot241/2=28920$ unordered bilinear pairs in
\eqref{eq:lower-gram-certificate}, 28915 are strictly below $T$;
the five remaining pairs are identically equal to one of the three
active quadratic forms. The strict pairs have certified margin greater
than $0.000548643283$. These assertions are checked using rational
interval arithmetic, not floating-point tolerances. It follows that
all matching flows have noncritical density at most $T$.

The computational part of this proof consists of these finite
rational sign and polynomial-identity checks. The accompanying
\path{lower-certificate/verify_algebraic.py} checks normalization,
positivity, the three active equalities, and the stationarity identity
in $\mathbb Q[t]/(P)$, and isolates the specified root by Sturm
sequences. It then invokes \path{verify_flow_bound.py}, which
reconstructs $B$, $H$, every nonsingular column choice, and every
bilinear pair from the displayed label matrix and flow maps. The
interval box and the rational input data are included in
\path{lower-certificate/stationarity-input.json}. No optimization
routine is needed to verify the assertions.

Finally, approximate $a^*$ by rational mass vectors and take finite
blow-ups with even total order. Any sequence of their matching flows
has a convergent subsequence, and its limit belongs to
$\mathcal P(a^*)$. Continuity of $Q$ therefore preserves the lower
bound on critical density in the limit. Conversely, the displayed
active flows can be approximated by finite matchings, with only
$o(N)$ endpoints adjusted for integrality and parity. Their critical
counts change by $o(N^2)$. This proves both the finite realization
of the lower bound and the asserted asymptotic equality.
\end{proof}

The number $\alpha_L$ has degree six over $\mathbb Q$. Its primitive
integer minimal polynomial is
\begin{align*}
&5754135102948532776960X^6-13507216477071755171328X^5\\
&\quad+13208173323262094551248X^4-6886878440990980289832X^3\\
&\quad+2019436570431176007853X^2-315750351353916573206X
+20566231563858477973.
\end{align*}
Both this polynomial and $P$ are irreducible modulo 41. The designated
roots of $P$ and the displayed minimal polynomial lie in the isolating
interval stated for $\tau$ and, respectively,
\[
 (0.41977282048624007772,0.41977282048624007773).
\]
The polynomial relation and irreducibility checks are included in
the symbolic certificate.


\subsection{Deriving the algebraic parameters}
The degree-six equation follows by eliminating the stationarity
equations of the three active quadratic forms. Write $q=d+e$.
Among the three active noncritical forms only the first depends on
the split between $d$ and $e$ with $q$ fixed, and its stationary split
is
\[
 d=(b+q-p-z-f)/4.
\]
After substituting this expression, let $\widetilde C_1,
\widetilde C_2,\widetilde C_3$ be the quadratic matrices in
$(p,b,z,q,f)$. For weights $u,v,1-u-v$, put
$H(u,v)=u\widetilde C_1+v\widetilde C_2+(1-u-v)\widetilde C_3$.
Near the certified solution this matrix is positive definite, and
minimizing its quadratic on the mass hyperplane gives
\[
 T(u,v)=\frac1{\mathbf1^TH(u,v)^{-1}\mathbf1}
       =\frac{N(u,v)}{4S(u,v)},
\]
where
\begin{align*}
N={}&u^2(-20v^3+420v^2-224v-128)\\
 &+u(7v^4+559v^3-842v^2+164v+112)\\
 &+4v^4+156v^3-248v^2+52v+36,\\
S={}&u^2(156v^2-84v-56)
 +u(234v^3-344v^2+61v+49)\\
 &+v^4+65v^3-102v^2+20v+16.
\end{align*}
At the stationary solution $T=1-\alpha_L$ and $T_u=T_v=0$.
The polynomial $F=N-4(1-\alpha_L)S$ is quadratic in $u$, and its
discriminant factors as
\begin{align*}
\operatorname{disc}_u F={}&(v-1)
 (104\alpha_Lv^2-56\alpha_Lv-28\alpha_L+v^3-38v^2+20v+12)\\
 &\times\bigl(8328\alpha_Lv^3-18144\alpha_Lv^2
 +5628\alpha_Lv+3420\alpha_L\\
 &\hspace{22mm}+49v^4-3367v^3+7130v^2-2072v-1484\bigr).
\end{align*}
The first two factors do not vanish in the isolating box. The last
factor and its $v$ derivative vanish. Solving the last factor for
$\alpha_L$ yields its stated rational formula with $v=\tau$, and
\[
 \frac{d}{dt}
 \left(\frac{-49t^4+3367t^3-7130t^2+2072t+1484}{12D(t)}\right)
 =-\frac{P(t)}{12D(t)^2}.
\]
The double-root formula for $u$ gives $\lambda_1$, and the linear
stationarity equations give the cubic numerators of the masses.
Eliminating $t$ gives the degree-six polynomial for $\alpha_L$.
The checker
\path{lower-certificate/verify_elimination_independent.py}
reconstructs $N/(4S)$ from determinants of the active quadratic forms
and checks the entire displayed discriminant identity with exact
polynomial arithmetic.