A $K_{3,5}$-free graph has at most four common neighbors for every triple of vertices. A copy of $K_{4,4}$ saturates this restriction on every triple in either of its parts. In fact, a triple can lie in a part of at most one such copy, which gives a cubic upper bound on the total number of copies. Attaining this bound requires many complete bipartite subgraphs to coexist without allowing even one triple a fifth common neighbor.

For finite simple graphs $H$ and $F$, write $\mathrm{ex}(n,H,F)$ for the maximum number of unlabeled, not necessarily induced copies of $H$ in an $n$-vertex $F$-free graph. The problem above is the smallest instance of the question of Pohoata, Tidor, and Yu [2, Question 4.1]: for every fixed , is

They proved the corresponding statement for $s=2$. We establish the case $(s,t)=(3,4)$.

The missing parameter is the size of the forbidden common neighborhood. The general lower bound of Gerbner and Patkós [1, Theorem 1.6(iii)] gives $\mathrm{\Omega }(n^{3/2-o(1)})$ copies at our parameters. Janzer, Longbrake, and Yepremyan [3, Theorem 1.1] obtained the cubic order for $\mathrm{ex}(n,K_{a,b},K_{3,t})$, for fixed and sufficiently large $t$. Hou, Hu, and Wang [4, Theorem 1.2] made the sufficient threshold explicit:

For $a=b=4$, this guarantees many $K_{4,4}$’s while excluding $K_{3,7}$; it does not exclude $K_{3,5}$. Wang, Yang, and Zhou [5, Theorem 1.1] reached $t=b+1$ for $b\ge 5$ and $4\le a\le b$, leaving $b=4$ outside their range. Thus Theorem 1, together with their theorem, answers (1) for every $s=3$ and $t\ge 4$.

The finite-geometric approach explains both the cubic scale and the obstruction at this last parameter. A cap in $\mathrm{PG}(5,q)$ is a set of points with no three collinear, so every triple spans a plane. In a point–hyperplane incidence graph, its common neighbors are then described by a plane section of the point set. Four-point sections can produce $K_{4,4}$’s, whereas larger sections can produce forbidden common neighborhoods. A set with $q^3$ points and a positive proportion of the $\mathrm{\Theta }(q^9)$ planes meeting it in four points has the appropriate scale for a cubic construction.

We use the point set of Wang, Yang, and Zhou [5, Section 3], specializing its defining polynomial $f$ to degree four. On a typical plane, the section is given by the roots of $f+A^2-\alpha B^2-C$, where $\alpha$ is a fixed nonsquare and $A,B,C$ have degree at most two. When $\mathrm{deg}f\ge 5$, the other terms cannot cancel its leading coefficient. At degree four, the entire section polynomial can vanish. This happens for $q^3(q+1)$ planes for every monic quartic, so choosing $f$ randomly cannot eliminate these sections. Moreover, every point belongs to $q(q+1)$ of these identity planes. A subset meeting each of them in at most four points therefore has size at most $4q^2$. Point deletion would lose the $q^3$ scale on which the construction depends. The simultaneous-splitting argument in [5, Section 4] also requires a shift of degree strictly less than $\mathrm{deg}f$, whereas the shift can have degree four here.

We retain all points and modify the incidence graph. First choose $f$ so that there are $\mathrm{\Omega }(q^9)$ four-point sections, then use the random projective pairing of Janzer, Longbrake, and Yepremyan [3, Section 4] to obtain $\mathrm{\Omega }(q^9)$ designated copies in expectation. The exceptional plane sections define complete bipartite blocks containing every possible forbidden common neighborhood. Deleting all their edges is too expensive for the available counting argument: the expected number of edge–block incidences is $O(q^5)$, and an edge can belong to $O(q^4)$ designated copies. The resulting $O(q^9)$ loss has the same order as the entire supply of copies.

Instead, we first delete the blocks whose two sides come from exceptional planes. Their expected edge count is only $O(q)$, so their deletion costs $O(q^5)$ copies. We then delete edges belonging to more than $L$ exceptional blocks, at an expected cost of $O(q^9/L)$ copies. Choosing $L$ as a sufficiently large absolute constant leaves $\mathrm{\Omega }(q^9)$ copies for a suitable projective pairing. Each remaining block has one side of size at most four, and each remaining edge is subject to at most $L$ blocks.

The last step uses the cap property a second time. A designated copy meets the side of size at most four in any remaining block in at most two vertices. Three points would determine the controlled-side plane and force the opposite rich plane to be exceptional. For each vertex on the other side, we independently retain two neighbors in this side. This prevents every triple there from having a common neighbor through the block. At the same time, each choice has a positive constant probability of retaining all edges of a fixed designated copy that it affects. There are at most $16L$ affecting choices per copy, so its survival probability stays bounded away from zero as $q$ grows. This is why controlling block overlap before pruning preserves the cubic order. The geometry is established in Section 2, and the two alteration stages are proved in Sections 3 and 4.

For completeness, we give the upper-bound count used above. Write $N(H,G)$ for the number of copies of $H$ in $G$. For a vertex set $X$, let ${\mathrm{\Gamma }}_G(X):={\bigcap }_{x\in X}{N}_G(x)$ be its common neighborhood.

It remains to prove the lower bound. Throughout the construction, all implied constants are absolute, and limits in $q$ are taken through odd prime powers.

The choice of the quartic must produce many four-point sections, but it cannot avoid long sections. We first classify the latter and count their incidences for an arbitrary quartic. Only then do we choose its coefficients to obtain the four-point sections used for the copies.

Let $q>4$ be an odd prime power, and let ${\mathbb{F}}_q$ be the field with $q$ elements. The projective space $\mathrm{PG}(5,q)$ consists of the one-dimensional subspaces of ${\mathbb{F}}_q^6$; a projective plane corresponds to a three-dimensional vector subspace. Subspace dimensions below are projective unless explicitly described as affine. A cap is a set with no three collinear points.

Fix a nonsquare $\alpha \in {\mathbb{F}}_q$ and a monic quartic

In homogeneous coordinates $[w:x:y:z:u:v]$, set

Thus $|S|=q^3$. This is the quartic specialization of the point set in [5, Section 3]; we give all the section arguments needed here.

Every triple now determines a unique plane. To understand how many other points that plane can contain, consider the affine projection

For a projective plane $\mathrm{\Pi }$ not contained in $w=0$, let $H=\mathrm{\Pi }\cap \{w=1\}$. If $dim\rho (H)=2$, the restriction of $\rho$ to $H$ is an affine isomorphism, so $H$ has a unique representation

where $A,B,C$ are affine functions of $(x,u)$. We call $\mathrm{\Pi }$ a graph plane. Upon substituting $u=t^2$, write

The points of $S\cap \mathrm{\Pi }$ correspond bijectively to the roots in ${\mathbb{F}}_q$ of

a polynomial of degree at most four.

Let $\mathcal{I}$ be the family of graph planes satisfying $P_{\mathrm{\Pi }}\equiv 0$, called identity planes. For each $c\in {\mathbb{F}}_q$, put

and let $\mathcal{F}$ be the family of all projective planes contained in at least one $F_c$. Define the exceptional family and its section sizes by

Membership in $\mathcal{D}$ does not require a section to have more than four points; in particular, some exceptional planes miss $S$.

The exceptional family is defined by the form of the plane rather than a threshold on its section size. This makes its incidences exactly countable and ensures that every section larger than four is included.

The incidence count above holds for every monic quartic. We now choose one with $\mathrm{\Omega }(q^9)$ four-point sections. At this stage only the section on one plane matters; the later random pairing will match it with a section on the other side of the graph. Thus a direct average over the four lower coefficients of $f$ suffices.

Fix such a quartic $f$, and define

For $A\in \mathcal{B}$, let ${\mathrm{\Pi }}_A$ be its associated plane, called its rich plane. This plane is unique: any three points of $A$ are noncollinear by Lemma 3 and therefore span ${\mathrm{\Pi }}_A$. Distinct rich planes give distinct four-sets, so

Fix the cap and the family $\mathcal{B}$ from Section 2. We seek a projective pairing with many designated copies after two deletions: first remove blocks with two exceptional sides, then remove edges lying in too many blocks. To make these requirements hold for the same pairing, we will compare the copy count and deletion costs pointwise before taking expectations.

We use the point–hyperplane incidence framework of [3, Section 4]. Fix a nondegenerate symmetric bilinear form $⟨\cdot ,\cdot ⟩$ on ${\mathbb{F}}_q^6$. For a projective subspace $U$, let $U^{⟂}$ be the projectivization of the orthogonal complement of its corresponding vector subspace. This operation reverses containment, maps planes to planes, and satisfies

Choose $T$ uniformly from $\mathrm{PGL}(6,q)$, the group of invertible linear transformations of ${\mathbb{F}}_q^6$ modulo nonzero scalar multiples. The transformation $T$ need not preserve the form.

On two disjoint copies $S_L,S_R$ of $S$, define a bipartite graph $G_T^0$ by

The orthogonality test is independent of the nonzero vector representatives of the projective points and of the linear representative of $T$.

For $A,C\in \mathcal{B}$, call $(A,C)$ a designated pair when

Then $T({\mathrm{\Pi }}_C)={\mathrm{\Pi }}_A^{⟂}$, so every point of $A$ is orthogonal to every point of $T(C)$. Hence $A_L$ and $C_R$ form a $K_{4,4}$, which we call a designated copy. Distinct designated pairs give distinct copies, since their vertex sets in the fixed bipartition differ.

For integers $0\le k\le m$, write

for the number of $k$-dimensional vector subspaces of ${\mathbb{F}}_q^m$, with the empty product equal to one. The formula follows by counting ordered linearly independent $k$-tuples and dividing by the number of ordered bases of ${\mathbb{F}}_q^k$. In particular, the number of projective planes in $\mathrm{PG}(5,q)$ is

The group $\mathrm{PGL}(6,q)$ acts transitively on planes: a linear isomorphism between their vector subspaces extends to an isomorphism of ${\mathbb{F}}_q^6$. Thus, for each fixed $A,C\in \mathcal{B}$,

If $K_0(T)$ is the number of designated copies, then

This gives the required number of copies on average, but $G_T^0$ need not be $K_{3,5}$-free. We next isolate the blocks in which the common-neighborhood condition can fail. The estimates of their sizes will be combined with (18), rather than imposing separate high-probability events.

A triple can have more than four common neighbors in $G_T^0$ only when the corresponding plane section is exceptional. For $E\in \mathcal{D}$, define two complete bipartite subgraphs:

Here a product of two labeled vertex sets denotes the complete bipartite graph between them. Both graphs lie in $G_T^0$, by (15). We call them exceptional blocks and keep them indexed by $(I,E)$ or $(\mathrm{II},E)$, even when their edge sets coincide.

In type I, call the left side the controlled side and the right side the exceptional side; in type II, reverse these roles. Thus the exceptional side always comes from $S\cap E$. A block is mutual if its controlled-side plane is also in $\mathcal{D}$: this means $T{(E)}^{⟂}\in \mathcal{D}$ in type I and $T^{-1}(E^{⟂})\in \mathcal{D}$ in type II. By Proposition 4, the controlled side of every nonmutual block has size at most four.

A uniformly random projective plane contains a fixed point of $\mathrm{PG}(5,q)$ with probability

Indeed, count point–plane incidences and use transitivity on points. Its expected intersection size with $S$ is therefore $q^3/(q^3+1)$.

Let $Z(T)$ be the sum of the edge counts of all exceptional blocks, including their indexing multiplicity. For each fixed $E$, both controlled-side planes in (19) and (20) are uniformly distributed over all projective planes. Hence

Let $U(T)$ be the corresponding sum over mutual blocks only. For fixed $E,F\in \mathcal{D}$, each event $T{(E)}^{⟂}=F$ or $T^{-1}(E^{⟂})=F$ has probability $1/N_2$, and the block then has $a_E{a}_F$ edges. Therefore

Here we used (8) and (17). To turn these edge estimates into bounds on lost copies, we need a uniform bound on the number of designated copies containing one edge.

Deleting all exceptional-block edges would now give only an $O(q^9)$ bound on the expected loss, which does not guarantee that any fixed proportion of the $\mathrm{\Omega }(q^9)$ copies remains. The smaller estimate $\mathbb{E}U(T)=O(q)$ allows mutual blocks to be removed outright. For the other blocks, we use their total incidence count to discard only edges with large load.

We now make the two preliminary deletions. First delete every edge lying in a mutual block, obtaining $G_T^1$. For each $e\in E(G_T^1)$, define its load

All blocks in this definition retain their original vertex sets and edge sets from $G_T^0$; deletion does not redefine them. For a positive integer $L$, delete every edge with ${\lambda }_e>L$, obtaining $G_T^{\mathrm{pre}}$. Since

at most $Z(T)/L$ edges are deleted in this second step. Every edge of $G_T^{\mathrm{pre}}$ lies in at most $L$ indexed nonmutual blocks.

Let $K_{\mathrm{pre}}(T)$ count designated copies whose edges all survive in $G_T^{\mathrm{pre}}$. For every $T$, the number of removed edges is at most $U(T)+Z(T)/L$. Charging each destroyed copy to one of its deleted edges gives

Taking expectations in this pointwise inequality and using (18), (22), and (23), we obtain absolute constants $c_1,C_1,C_2>0$ such that

for all sufficiently large $q$. Fix an integer $L\ge 4C_2/c_1$, and then take $q$ sufficiently large that $C_1{q}^5\le c_1{q}^9/4$. Some $T$ consequently satisfies

Fix this transformation $T$ for the remainder of the proof. The pointwise comparison (24) is what permits the copy count and both deletion costs to be handled together.

Fix the transformation from (25). It remains to remove forbidden common neighborhoods inside the nonmutual blocks. Each block has at most four vertices on its controlled side, and we will retain at most two of them as neighbors of each vertex on its exceptional side. Such a restriction could destroy a designated copy with probability one if that copy needed three controlled-side vertices. The following geometric fact rules out this obstruction.

We can therefore choose two-subsets without making the survival of any designated copy impossible. For an indexed nonmutual block $B$, let $X_B$ and $Y_B$ denote its original labeled controlled and exceptional sides. Whenever $3\le |X_B|\le 4$, choose, for every $y\in Y_B$, a uniformly random set

All choices are independent over indexed pairs $(B,y)$. Retain an edge $e$ of $G_T^{\mathrm{pre}}$ precisely when, for every block $B$ containing it with $|X_B|\ge 3$, writing $e=xy$ with $x\in X_B$ and $y\in Y_B$ gives $x\in R_{B,y}$. Blocks with $|X_B|\le 2$ impose no restriction. The selections use the original sets $X_B$, even when some incident edges were deleted earlier. Let $G$ be the resulting random subgraph.

The pruning is thus effective for every outcome of the random choices. Its effect on designated copies is different: they require at most two neighbors from any one choice, and the load bound limits the number of choices that affect them. The following estimate quantifies both facts.