# Inducibility of the Net Graph

Adam Blumenthal Department of Mathematics and Computer Science, Westminster
College, E-mail<EMAIL_ADDRESS>. Michael Phillips Department of
Mathematical and Statistical Sciences, University of Colorado Denver, E-mail:
<EMAIL_ADDRESS>.

###### Abstract

A graph $F$ is called a fractalizer if for all $n$ the only graphs which
maximize the number of induced copies of $F$ on $n$ vertices are the balanced
iterated blow ups of $F$. While the net graph is not a fractalizer, we show
that the net is nearly a fractalizer. Let $N(n)$ be the maximum number of
induced copies of the net graph among all graphs on $n$ vertices. For
sufficiently large $n$ we show that, $N(n)=x_{1}\cdot x_{2}\cdot x_{3}\cdot
x_{4}\cdot x_{5}\cdot
x_{6}+N(x_{1})+N(x_{2})+N(x_{3})+N(x_{4})+N(x_{5})+N(x_{6})$ where $\sigma
x_{i}=n$ and all $x_{i}$ are as equal as possible. Furthermore, we show that
the unique graph which maximizes $N(6^{k})$ is the balanced iterated blow up
of the net for $k$ sufficiently large. We expand on the standard flag algebra
and stability techniques through more careful counting and numerical
optimization techniques.

##  1 Introduction

In 1975, Pippenger and Golumbic [15] proposed the _inducibility problem_ :
determine the maximum possible density of induced copies of a $k$-vertex graph
$H$ that can be contained in an $n$-vertex graph. Here, we take the density to
be the number of copies of $H$ divided by $\binom{n}{k}$, the number of
$k$-vertex induced subgraphs of the host graph. For a $k$-vertex graph $H$ and
$n$-vertex graph $G$, we denote by $I(H,G)$ the number of induced copies of
$H$ in $G$, and by $i(H,G):=I(H,G)/\binom{n}{k}$ the density of $H$ in $G$. If
$G$ is an $n$-vertex graph which maximizes $I(H,G)$ over all $n$-vertex
graphs, then we say that $G$ is extremal and introduce the notations
$I(H,n)=I(H,G)$ and $i(H,n)=i(H,G)$. Finally, we define the inducibility of
$H$ as
$\displaystyle\lim_{n\to\infty}\frac{I(H,n)}{\binom{n}{k}}=\lim_{n\to\infty}i(H,n)$.

Pippenger and Golumbic [15] proved for all $k$-vertex graphs $H$ that
$i(H)\geq\frac{k!}{k^{k}-k}=(1+o(1))\frac{k!}{k^{k}}$ by construction.
Although they use different verbiage, the authors use an _iterated, balanced
blow-up_ of a graph $H$ as their construction for the lower-bound on $i(H)$. A
_blow-up_ of a graph $H=(V(H)=\\{v_{1},\dots,v_{k}\\},E(H))$ by replacing each
vertex $v_{i}$ with a graph $H_{i}$ so that for any distinct $i,j\in[k]$, a
pair of vertices $x\in H_{i}$ and $y\in H_{j}$ are adjacent if and only if
$v_{i}v_{j}\in E(H)$. We say that a blow-up is _balanced_ (or nearly balanced)
if $\left||H_{i}|-|H_{j}|\right|\leq 1$ for all $i,j\in[k]$, and call a blow-
up _iterated_ if each $H_{i}$ is itself a blow-up of $H$, each part in each
$H_{i}$ is a blow-up, etc.

Until Razborov [16] introduced the flag algebra method in 2007, little
progress had been made toward the resolution of the inducibility problem.
Since then, the problem has been closed for several small graphs [2, 9, 6].
Fox, Huang and Lee [8], and separately Yuster [19] resolved this problem for
almost all graphs by considering $G_{n,p}$ for arbitrary fixed $p$ as
$n\to\infty$. Here, $G_{n,p}$ is a vector of $\binom{n}{2}$ Bernoulli($p$)
random variables, each determining the presence or absence of an edge in an
$n$-vertex graph. In order to fully express their result, we also need the
following definition.

A graph $F$ is a fractalizer if, for each $n$, all graphs on $n$ vertices
which maximize the number of induced copies of $F$ are balanced iterated blow-
ups of $F$. The result by Fox, Huang and Lee states that $G_{n,p}$ is a
fractalizer (or fractalizes) with high probability. However, other than
$K_{n}$ and $\overline{K_{n}}$, no small or explicit, large graphs are known
to be fractalizers. One issue is with the strength of the definition. It has
been shown by Lidický, Mattes, and Pfender [13] that $C_{5}$ is _almost_ a
fractalizer:

  * •

for $n$ sufficiently large, all extremal constructions are balanced $C_{5}$
blow-ups,

  * •

balanced iterated blow-ups are extremal for all $n$, but

  * •

there is a structure on 8 vertices (the Möbius ladder) which has the same
number of induced copies of $C_{5}$ as its balanced blow-up.

In this paper, we determine the inducibility of the net graph (as seen in
Figure 1), as well as the unique $n$-vertex graphs which maximize the density
of induced net graphs, or _nets_ , when $n$ is a power of 6. Our work is
heavily influenced by [2] wherein the Balough, Hu, Lidický, and Pfender
resolve one case of another 1975 question of Pippenger and Golumbic [15]
regarding the inducibility of cycle graphs. In this paper, we build on their
methods to include careful analysis of particular subgraph densities to
determine for sufficiently large $n$ the graph which maximizes the density of
the net graph.

We show that the net graph satisfies a weaker condition (see [13] for more
discussion regarding this topic): the balanced iterated blow-up of the net
uniquely maximizes the density of the net graph when $n$ is a power of 6, and
for $n$ large enough, the graphs which maximize the density of the net are
balanced, iterated blow-ups of the net. We note that the graph obtained by
adding a pendant to each vertex in a $K_{4}$ has the same number of induced
copies of the net graph as a balanced iterated blow-up of the net on 8
vertices, so the net cannot be a fractalizer. As it stands, there are still no
known nontrivial fractalizers.

Inducibility has natural extensions to directed graphs as well. Falgas-Ravry
and Vaughan [7] considered inducibility of small outstars, with an extension
to all outstars by Huang in [12] before being further generalized to other
types of stars by Hu, Ma, Norin, and Wu [11]. Orientations of short paths and
the $C_{4}$ are explored in [4] and [10], respectively. The inducibility of
directed graphs on at most 4 vertices was explored in [17], and the
corresponding tournaments were completely resolved in [3]. Other recent work
includes closing bipartite graphs on 5 vertices in [14] and an exploration of
inducibility for $d$-ary trees in [5].

Figure 1: The net graph and the iterated blow-up of the net graph on 36
vertices.

Additionally, we would like to provide the reader with a better sense of how
one would approach problems like those presented in this paper. We believe
that many steps of this process can (and should) be stream-lined, either by
explicitly providing more generalized results or proposing stages which can be
automated. To that end, we state and prove an important property of vertices
in extremal constructions of inducibility problems: every vertex in an
extremal construction should be in roughly the same number of induced copies
of the target structure.

######  Lemma 1.1.

Let $H$ be a $k$-vertex graph, and let $G$ be an $n$-vertex graph which
satisfies $I(H,G)=I(H,n)$. Every $v\in V(G)$ is contained in at least
$(L+o(1))\binom{n}{k-1}$ copies of $H$ where $L$ is any lower-bound on $i(H)$.

###### Proof.

Let $L$ be any lower-bound for the inducibility of the $k$-vertex graph $H$.
If we denote by $H^{u}$ the number of nets containing a vertex $u$ in an
extremal graph $G$, then $\sum_{u\in V(G)}H^{u}\geq
k\cdot(L+o(1))\binom{n}{k}$, implying that the average $\overline{H^{u}}$ of
$H_{u}$ over $V(G)$ is at least $(L+o(1))\binom{n}{k-1}$.

Let $u,v\in V(G)$ be given arbitrarily, and denote by $H^{uv}$ the number of
nets containing both of $u$ and $v$. Trivially, we have that
$H^{uv}\leq\binom{n-2}{k-2}$. Construct $G^{\prime}$ from $G$ by deleting $v$
and duplicating $u$ as $u^{\prime}$. As $G$ is extremal, we have the following
sequence of inequalities:

$0\geq I(H,G^{\prime})-I(H,G)\geq H^{u}-H^{v}-H^{uv}\geq
H^{u}-H^{v}-\binom{n-2}{k-2}.$

Therefore, we have for every pair $u,v\in V(G)$ that
$|H^{u}-H^{v}|\leq\binom{n-2}{k-2}$. As some vertex must be in at least
$\overline{H^{u}}$ induced copies of $H$, it follows that $H^{u}$ is at least

$\displaystyle\overline{H^{u}}-\binom{n-2}{k-2}$
$\displaystyle\geq(L+o(1))\binom{n}{k-1}-\binom{n-2}{k-2}$
$\displaystyle=(L+o(1))\binom{n}{k-1}-o(n^{k-1})$
$\displaystyle=(L+o(1))\binom{n}{k-1}$

for every $u\in V(G)$, as desired. ∎

The main result of this paper is Theorem 1, which follows from Theorem 2
(below) using a standard argument that is largely reproducible for other
graphs.

######  Theorem 1.

For $k\geq 1$, the unique graph on $6^{k}$ vertices which maximizes the number
of induced copies of the net graph is a balanced, iterated blow-up of the net.

In order to prove Theorem 1, we first prove Theorem 2, which is sufficient for
determining the unique limit object maximizing the density of induced copies
of the net graph. A proof sketch for Theorem 2 follows in Section 2, and the
proof of Theorem 2 fills most of Section 3 with the final arguments to
conclude Theorem 1 at the very end.

######  Theorem 2.

There exists $n_{0}$ such that for every $n\geq n_{0}$

$N(n)=x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}\cdot x_{5}\cdot x_{6}+\sum_{1\leq
i\leq 6}N(x_{i})$

where $\sum x_{i}=n$ and $|x_{i}-x_{j}|\in\\{0,1\\}$ for all $i,j\in[6]$.
Moreover, if $G$ maximizes the density of nets among $n$-vertex graphs, then
$G$ is a balanced blow-up of the net.

##  2 Proof Sketch for Theorem 2

We begin the proof of Theorem 2 by showing that the extremal construction is
in some sense very close to a balanced blow-up of the net; we would need only
to delete less than $0.2\%$ of the vertices and add/remove at most $0.001\%$
of the edges in an extremal graph for it to become a blow-up of the net with
part sizes _almost_ balanced (Claim 3.1). Once this has been accomplished, we
argue that actually no edges should be added or removed (Claim 3.2), and then
further that no vertices need to be deleted (Claims 3.3 through 3.5), implying
that the extremal construction is precisely a blow-up of the net. Once we have
this result, we argue that the parts are all asymptotically the same size
using basic analytic techniques, then that they differ by at most one vertex
(Claim 3.6), concluding the proof of Theorem 2.

We show that extremal constructions are similar to nearly-balanced blow-ups of
the net by investigating the density of two classes of 8-vertex graphs. The
first is $N_{22}$, any 8-vertex graph obtained by cloning any two distinct
vertices in the net, and the second is $N_{3}$, any 8-vertex graph obtained by
cloning any one vertex twice in the net. For examples of $N_{3}$ graphs, see
Figure 2 where the dotted lines between vertices in the same part indicate
that the edges are allowed but not necessarily present, as is standard
procedure when drawing flags.

Figure 2: The two classes of $N_{3}$ graphs, with dotted lines to indicate
potential edges.

Beginning our investigation of the extremal constructions by focusing on
$N_{22}$ subgraphs will allow us to show (1) that much of the top-layer
structure is present, and (2) the sizes of part sets are relatively balanced.
We also investigate $N_{3}$ subgraphs to improve our bounds related to
balanced part sizes at a small sacrifice to adherence to top-layer structure.

Now, we observe that in a balanced iterated blow-up of the net,
$N_{22}(Z)-5\cdot N_{3}(Z)$ is computationally indistinguishable from 0 for
any net $Z$, and so $N_{22}(Z)-a\cdot N_{3}(Z)$ should be a very small
positive number when $5-a$ is a small positive number. (We will discuss the
choice of $a$ later.) Further, in a balanced iterated blow-up of the net, no
more than $1/36+o(1)$ of the 8-vertex supergraphs of a net contained in a part
are in either $N_{22}$ or $N_{3}$, so a net $Z$ which maximizes
$N_{22}(Z)-a\cdot N_{3}(Z)$ should be a top-layer net. We use just one such
net to classify the rest of the vertices in the graph into seven sets, six of
which will function as approximations to the blow-up sets and one containing
fewer than $0.2\%$ of the vertices which we cannot guarantee behave nicely.

We use flag algebra computations to bound $N_{22}-a\cdot N_{3}$, then apply an
averaging argument to achieve a lower bound on the maximum of
$N_{22}(Z)-a\cdot N_{3}(Z)$ over all nets $Z$. This bound is then included in
quadratic programs designed to produce bounds on the number of vertices that
we would need to delete, the number of edges that would need to be switched,
and the relative sizes of the parts we find, and we solve these quadratic
programs using Lagrange multipliers. Different choices for $a$ result in
different sets of bounds, and we choose the set of bounds we need based on the
arguments described next.

At this point, we will have argued that the extremal construction must be
similar to a balanced blow-up of the net; some of the edges in the graph may
disagree with the blow-up structure, the parts can vary in size to a small
degree, and a very small set of vertices may simply not fit in any of the
parts. To argue that no edges among the six primary parts disagree with the
blow-up structure, we show that any pair of vertices violating the top-layer
structure actually destroy more potential nets than they create. As such, we
know that at least 99.8% of the graph respects the top-layer structure. We
then argue that the remaining 0.2% of the vertices either cannot be placed in
one of the six primary parts without creating conflict with at least 3% of the
vertices or else would unbalance the six parts too much. The bulk of the
enumeration in the proof of Theorem 2 is found in these two arguments and is
therefore a decent place to start when approaching the inducibility problem
with a new graph.

We also know that all vertices must be in the same number of copies of the
desired structure (Lemma 1.1), ignoring lower order terms. That means, in our
problem, every vertex in an extremal construction is in
$(24/1555+o(1))\cdot\binom{n}{5}\approx 0.0001286\cdot n^{5}$ nets. We then
find an upper bound on the number of nets which contain one of the 0.2% of
vertices which create conflict with 3% of the graph, and observe that this
upper bound is less than $0.0001275\cdot n^{5}$. In other words, all vertices
in the graph are in $0.001286\cdot n^{5}$ nets, but vertices which misbehave
are in at most $0.0001275\cdot n^{5}$ nets and hence do not exist in our
extremal construction. This allows us to conclude that our extremal
construction is a blow-up of the net graph, and we use two more arguments to
show first that the parts are asymptotically balanced and finally that they
differ by at most 1 vertex.

##  3 Proof of Theorem 2

######  Proposition 3.0.

There exists some $a\in(4.9,5)$ and $n_{0}\in\mathbb{N}$ such that every
extremal graph $G$ on at least $n_{0}$ vertices satisfies:

$\displaystyle i(N,G)$ $\displaystyle<.017202164$ $\displaystyle 4\cdot
d(N_{22},G)-3a\cdot d(N_{3},G)$ $\displaystyle\geq
0.00071788399+o(1)>0.00071788398.$

###### Proof.

This result follows from an application of the plain flag algebra method. We
ran Flagmatic ([18]) on 8 vertices which verified the first inequality for
sufficiently large $n$. For the second inequality, we minimized the difference
$4d(N_{22},G)-3a\cdot d(N_{3},G)$, for several choices of $a\in(4.9,5)$,
subject to the constraint that $i(N)>24/1555$, the limiting density of the net
in our conjectured extremal constructions. Our particular choice of $a$ which
we carry forward into future calculations will be described in more detail
later, but we note here that we will use $a=4.99$. Values for $a$ closer to 5
and further from 5 gave collections of bounds that were less cooperative with
future arguments, specifically Claim 3.2. ∎

Let $G$ be an extremal graph on $n$-vertices with $n$ large enough to satisfy
the conditions of Proposition 3.0. Denote the set of all induced net in $G$ by
$\mathcal{Z}$, let $a\in\mathbb{R}$ be taken from Proposition 3 (it will be
specified later), and let $Z$ be an induced net maximizing $(N_{22}(Z)-a\cdot
N_{3}(Z))\binom{n-2}{4}$.

Below we obtain a lower bound on this linear combination in terms of flag
algebra bounds by noting that it must be at least as large as the average
value over all nets:

$\displaystyle\left(d(N_{22}(Z))-a\cdot d(N_{3}(Z))\right)\binom{n-6}{2}$
$\displaystyle\geq\frac{1}{|N|}\sum_{Y\in
N}(d(N_{22}(Y))-ad(N_{3}(Y)))\binom{n-6}{2}$
$\displaystyle=\frac{4d(N_{22})-3ad(N_{3})\binom{n}{8}}{d(N)\binom{n}{6}}$
$\displaystyle=\left(\frac{\frac{4}{28}d(N_{22})-\frac{3a}{28}d(N_{3})}{d(N)}\right)\binom{n-6}{2}.$

Substituting the bounds from Proposition 3.0 gives that

$d(N_{22}(Z))-a\cdot d(N_{3}(Z))>\frac{0.00071788398}{28\cdot
0.17202164}=0.00014904353852556826.$

Label the vertices in $Z$ as $z_{1},\dots,z_{6}$, and define sets of vertices
$Z_{i}$ for $i\in[6]$ such that

$Z_{i}:=\\{v\in V(G):G[(Z\backslash z_{i})\cup v]\equiv N\\}.$

Effectively this creates sets of vertices $Z_{i}$ which look like $z_{i}$ to
the other vertices in $Z$. For the sake of simplicity, let us label the
vertices of $Z$ so that $E(Z)=\\{z_{i}z_{j}:j=i+3\text{ or }i,j\geq 4\\}$.

A funky pair $(x,y)$ is any pair of vertices $x\in Z_{i}$ and $y\in Z_{j}$ for
$i\not=j$ where either $xy\in E(G)$ and $z_{i}z_{j}\not\in E(Z)$ or else
$xy\not\in E(G)$ and $z_{i}z_{j}\in E(Z)$. In other words, a pair of vertices
$x,y$ in distinct $Z_{i},Z_{j}$ respectively is called funky if their
adjacency status is inconsistent with that of $z_{i}$ and $z_{j}$. More
specifically, we refer to the funky pair $x,y$ as a funky edge if $xy\in E(G)$
or as a funky non-edge if $xy\not\in E(G)$. We denote by $E_{f}$ the set of
all funky pairs in $G$. It follows from the above inequality that

$\sum_{i=1}^{3}|Z_{i}||Z_{i+3}|+\sum_{4\leq i<j\leq
6}|Z_{i}||Z_{j}|-|E_{f}|-a\sum_{i\in[6]}|Z_{i}|^{2}/2>0.000149043538\cdot\binom{n-6}{2}.$

We then pick $X_{i}\subseteq Z_{i}$ and
$X_{0}=V(G)\backslash\left(\displaystyle\cup_{i=1}^{6}X_{i}\right)$ so as to
maximize the left-hand side of (4.1), below, where we also define
$x_{i}:=\frac{1}{n}|X_{i}|$ for $i=0,\dots,6$ and $f$ as the density of funky
pairs with neither end in $X_{0}$, normalized by a factor $\binom{n}{2}^{-1}$.
This gives the following useful bound to be used as a constraint in the proof
of Claim 3.1:

$\displaystyle 2\sum_{1\leq i<j\leq
6}x_{i}x_{j}-2f-a\sum_{i=1}^{6}x_{i}^{2}>0.000149043538.$ (1)

In the following claim, we specify a specific real number $a$, which gives
corresponding bounds. Note that different choices for $a$ will result in
different inequalities below and that the choice of $a$ is primarily made in
such a way to allow arguments _later in the proof_ to go through.
Specifically, we chose $a=4.99$ so that arguments in Claim 3.2 produce the
desired contradictions.

######  Claim 3.1.

For $a=4.99$, we have for all $i\in[6]$ that

$\displaystyle 0.165791592261\leq x_{i}$ $\displaystyle\leq 0.167541741072,$
$\displaystyle x_{0}$ $\displaystyle\leq 0.00165262197319,$ $\displaystyle f$
$\displaystyle\leq 0.0000027521.$

###### Proof.

These bounds are achieved via a straight-forward application of quadratic
programming and Lagrange multipliers; see Appendix A for details. The
structure of this proof follows closely to that of Claim 4 in [2]. ∎

Define $x_{\text{min}}:=0.165791592261$ and $x_{\text{max}}:=0.167541741072$.
We can show that the funky degree of any $x\in V(G)\backslash X_{0}$ satisfies
$d_{f}(x)\leq 1-(1+a)\cdot x^{\prime}\approx 0.0069084$: if we move $v$ from
$X_{1}$ to $X_{0}$, then the left hand side of 1 will decrease by

$\frac{1}{n}(2(x_{2}+\cdots+x_{6})-2d_{f}(v)-2\cdot a\cdot x_{1}+o(1)).$

This quantity must be positive as $X_{0},X_{1},\dots,X_{6}$ were chosen to
maximize the left hand side of 1. This together with the bounds on $x_{i}$
from Claim 3.1 implies that

$d_{f}(v)\leq x_{2}+\cdots+x_{6}-d_{f}(v)-a\cdot x_{1}+o(1)\leq 1-(1+a)\cdot
x^{\prime}+o(1).$

Given that the funky degree of vertices in $V(G)\backslash X_{0}$ is bounded
above by $0.0069084$, we now show that all funky pairs in $G$ must involve a
vertex in $X_{0}$. This is the first place in which our strategy diverges from
that of Balogh, Hu, Lidický, and Pfender in [2]. The $C_{5}$ problem involves
a great deal of symmetry as $C_{5}$ is both vertex-transitive and self-
complementary. The net graph has neither of these properties, although we will
certainly take advantage of the symmetries that the net graph _does_ have.
Instead, we will iteratively show that certain types of funky pairs which
avoid $X_{0}$ do not exist, and then use these observations to reduce the
number of possible nets in which the more troublesome funky pairs may reside.

In the proof of the following claim, we will use some unorthodox terminology,
which we now introduce. We refer to $X_{1},\dots,X_{6}$ as _blobs_ , and we
specify $X_{1}$, $X_{2}$, and $X_{3}$ as _outer blobs_ as a reference to the
vertices $z_{1}$, $z_{2}$, and $z_{3}$ in $Z$, and we specify $X_{4}$,
$X_{5}$, and $X_{6}$ as _inner blobs_ for an equivalent reason. We define the
_blob distance_ of two vertices $x\in X_{i}$ and $y\in X_{j}$ for $i,j\in[6]$
as the distance of $z_{i}$ and $z_{j}$ in $Z$, we say that two or more
vertices are _coblobular_ if their blob distance is 0. We say that a subgraph
of $G$ is _blob-induced_ or _respects the blob-structure_ if the subgraph
contains no funky edges, usually with no pair of coblobular vertices.

######  Claim 3.2.

There are no funky pairs in $X_{1}\cup\cdots\cup X_{6}$.

###### Proof.

We prove this claim by contradiction. Let $u,v\in(X_{1}\cup\cdots\cup X_{6})$
be a funky pair in $G$, and let $G^{\prime}$ be obtained from $G$ by changing
the status of the edge $uv$. We will show that the bounds in Claim 4 imply
that $G^{\prime}$ must contain more nets than the extremal construction $G$.

Using the bounds in Claim 3.1, we can find at least $0.00069\cdot n^{4}$ nets
containing the pair $u,v$ in $G^{\prime}.$ Without loss of generality, the
funky pair $u,v$ are of one of the following four types: (1) $u\in X_{4}$,
$v\in X_{5}$, (2) $u\in X_{1}$, $v\in X_{4}$, (3) $u\in X_{1}$, $v\in X_{5}$,
or (4) $u\in X_{1}$, $v\in X_{2}$. We will show that if $u,v$ are a funky pair
of one of these types, in this order, then $G$ has fewer than $0.00069\cdot
n^{4}$ nets which contain the pair $u,v$.

First, we note that there are at most $x_{0}/6\cdot n^{4}$ nets using at least
one vertex in $X_{0}$. Second, we count the number of nets in $G$ containing
$u,v$ and at least two other vertices $u^{\prime},v^{\prime}$ in funky pairs
by observing that there are at most $f/2\cdot n^{4}$ nets wherein
$(u^{\prime},v^{\prime})$ is funky and at most $(d_{f}(u)+d_{f}(v))/2\cdot
n^{4}$ where $u^{\prime}$ and $v^{\prime}$ are each funky to at least one of
$u$ or $v$.

Third, we want to bound the number of nets wherein $(u,v)$ is the only funky
pair. Let $N$ be a net in $G$ with $u,v\in V(N)$ and note that $N$ contains a
$P_{4}$ which itself has no funky pairs. As $P_{4}$ is prime, we note that
this $P_{4}$ is either blob-induced or coblobular.

Suppose towards contradiction that this $P_{4}$ is blob-induced and assume
without loss of generality that it lies in $X_{1}$, $X_{4}$, $X_{6}$, and
$X_{3}$. If $u,v$ are not in this $P_{4}$, then they must be blob-distance at
least 2 from each other, forcing at least one of them to have at least one
additional funky partner within the $P_{4}$, a contradiction. Otherwise, there
exists a second non-funky $P_{4}$ in $N$ which must then be blob-induced; any
placement of this non-funky $P_{4}$ contradicts the assumption that $(u,v)$ is
the only funky pair in $N$.

Therefore, the original $P_{4}$ is coblobular, which implies first that the
third triangle vertex must be coblobular with the $P_{4}$. Since the net has
_some_ funky pair, it follows that $u,v$ must be a funky pendant-edge in $N$;
as such, we have at most $(x_{\text{max}}n)^{4}/12$ nets in $G$ where $u,v$ is
the only funky pair.

The nets in $G$ that have yet to be counted are those containing precisely one
other vertex $w$ which is funky to $u$, $v$, or both; there are at most
$c\cdot(d_{f}n)\cdot(x_{\text{max}}n)^{3}$ for some constant $c$. In order to
arrive at our desired contradiction, we would need $c$ to satisfy

$(x_{\text{max}})^{4}/12+c\cdot
d_{f}\cdot(x_{\text{max}})^{3}+x_{0}/6+d^{2}_{f}+f/2<0.00069,$

which is the case when $c<9.522$.

_Sub-claim 5.1_ There are no funky pairs in $X_{4}\cup X_{5}\cup X_{6}$.

###### Proof.

Let us first enumerate the nets containing $u$, $v$, and a vertex $w$ which is
funky with both $u$ and $v$, and suppose without loss of generality that $u\in
X_{4}$ and $v\in X_{5}$.

There are no nets in which $w$ is in $X_{1}\cup X_{2}$ by the following
contradiction argument. Suppose $N$ is just such a net and $w\in X_{1}$
without loss of generality; this implies that a mutual non-neighbor $x\in
V(N)$ of $v$ and $w$ must be located in $X_{3}$, and the existence of a $v-x$
path in $N$ implies the existence of $y\in V(N)\cap X_{6}$. Clearly $y$ is a
triangle vertex in $N$ but its neighborhood in $N$ forms an independent set, a
contradiction.

There are no nets in which $w$ is in $X_{6}$ by the following contradiction
argument. Suppose $N$ is just such a net and observe that $X_{6}\cap V(N)$ is
empty as $N$ contains no $C_{4}$s. We can then see that $w$ is a triangle
vertex, one of $u$ or $v$ is a triangle vertex, but the third triangle vertex
cannot be adjacent to the other two without additional funky pairs.

Now we count the nets with $w\in X_{6}$. We know that at most one of $u$, $v$,
$w$ is a triangle vertex, and so the remaining two vertices $t_{1},t_{2}$ must
be blob-distance at most one from each of $u$, $v$, and $w$; hence $t_{1}$ and
$t_{2}$ are in different interior blobs as nets do not contain $C_{4}$s. The
last vertex is then a pendant of the triangle vertex in $\\{u,v,w\\}$, and so
must be blob-distance at least 2 from both $t_{1}$ and $t_{2}$. There are 3
distinct configurations for $t_{1}$ and $t_{2}$, which specifies precisely the
location of the last pendant, implying that there are at most
$3d_{f}(x_{\text{max}})^{3}n^{4}$ such nets.

Lastly, we count the nets wherein $w$ is funky only with $u$ and apply
symmetry to acquire the number of nets wherein $w$ is funky only with $v$. As
$uv\not\in E(G)$, we have that within any such net, $v$ is contained in a non-
funky $P_{4}$. If this $P_{4}$ is completely contained in $X_{5}$, then $u$ is
a triangle vertex, $v$ is a pendant, and $w$ is also a pendant in this non-
funky $P_{4}$. The pendant of $u$ can either be in $X_{1}$ or $X_{5}$,
implying that there are
$\left(\frac{1}{2}+\frac{1}{6}\right)d_{f}x_{\text{max}}^{3}n^{4}$ such nets.
Otherwise, $v$ is a triangle vertex, $p_{v}\in X_{2}$, and $u$ is a pendant
vertex. Either the $P_{4}$ intersects $X_{4}$ or $X_{6}$, the latter implying
that $w\in X_{6}$, $p_{2}\in X_{3}$, and $t_{u}\in X_{4}$ (giving
$d_{f}x_{\text{max}}^{3}n^{4}$ nets), and the former implying that $w\in
X_{1}$, $t_{w}\in X_{4}$, and $t_{u}\in X_{6}$ (giving
$d_{f}x_{\text{max}}^{3}n^{4}$ nets). So, we have
$\frac{8}{3}d_{f}x_{\text{max}}^{3}n^{4}$ nets wherein $w$ is funky only with
$u$, and thus
$(3+\frac{16}{3})d_{f}x_{\text{max}}^{3}n^{4}<9.522d_{f}x_{\text{max}}^{3}n^{4}$.
This gives the desired contradiction, proving Sub-claim 5.1. ∎

_Sub-claim 5.2_ There are no funky non-edges in $X_{1}\cup\cdots\cup X_{6}$.

###### Proof.

First note that Sub-claim 5.1 implies that the only possible funky non-edges
exist between an outer blob and its adjacent inner blob, so we will suppose
towards contradiction and without loss of generality that $u\in X_{1}$ and
$v\in X_{4}$.

Let us first determine how many nets containing $u$, $v$, and $w$ wherein $w$
is funky to both $u$ and $v$. By Sub-claim 1, we know that $w\not\in X_{5}\cup
X_{6}$. Therefore, $w\in X_{2}\cup X_{3}$. No vertex in any such net can be
adjacent to both $u$ and $w$, so $u=p_{w}$ and $v$ is a triangle-vertex. If
$w\in X_{2}$, then we need a third triangle vertex $x$ in $X_{5}$, and then
$p_{x}\in X_{3}$. A symmetric argument works for $w\in X_{3}$, so we have
$2d_{f}(x^{\prime\prime})^{3}n^{4}$ nets of this form.

Now let us count the number of nets containing $u$, $v$, and $w$ wherein $w$
is funky only to $v$, and note by Sub-claim 1 that none exist where $w\in
X_{5}\cup X_{6}.$ Furthermore, we know that any such net contains a non-funky
$P_{4}$ which excludes $v$ but includes $u$. If this $P_{4}$ is contained in
$O1$, then $w\in X_{1}$, both $u$ and $w$ are pendants, $v$ is a triangle
vertex, and its pendant can be anywhere in $X_{1}\cup X_{5}\cup X_{6}$, giving
a count of $(\frac{1}{6}+2\cdot\frac{1}{2})d_{f}x_{\text{max}}^{3}n^{4}$ nets.
Otherwise, the $P_{4}$ is blob-induced and $u$ is a pendant of a vertex
$t_{u}\not=v$ in $X_{4}$. By symmetry, we assume that the $P_{4}$ intersects
$X_{2}$, and note that $v$ must be adjacent to the vertex $y\in X_{5}$ from
the $P_{4}$. Since $p_{y}\in X_{2}$, it follows that $v$ is a triangle vertex
and $w=p_{v}\in X_{3}$, giving a count of $d_{f}x_{\text{max}}^{3}n^{4}$ nets.
Hence we have $\frac{19}{6}d_{f}x_{\text{max}}^{3}n^{4}$ nets wherein $w$ is
funky only $v$.

Finally, we count the number of nets containing $u$, $v$, and $w$ wherein $w$
is funky only to $u$. Observe that any such net contains a non-funky $P_{4}$
containing $v$. If this $P_{4}$ is entirely within $X_{4}$, then $u$ is a
triangle vertex, $v$ and $w$ are the pendants in this $P_{4}$, and $p_{u}$
must also be contained in $X_{4}$ due to adjacency restrictions, giving a
count of $\frac{1}{6}d_{f}x_{\text{max}}^{3}n^{4}$ nets. Otherwise, the
$P_{4}$ is blob-induced, $v$ is a triangle vertex, $p_{v}\not=u$ is contained
in $X_{1}$, $u$ is a pendant, the triangle is blob-induced, and $w=t_{u}$ is
not the triangle vertex in the aforementioned $P_{4}$, giving a count of
$2d_{f}x_{\text{max}}^{3}n^{4}$ nets by symmetry. This results in
$\frac{13}{6}d_{f}x_{\text{max}}^{3}n^{4}$ nets wherein $w$ is funky only to
$u$.

Therefore, there are at most
$(\frac{13}{6}+\frac{19}{6}+2)d_{f}x_{\text{max}}^{3}n^{4}$ nets containing
the funky pair $u\in X_{1}$ and $v\in X_{4}$. Since
$\frac{13}{6}+\frac{19}{6}+2<9.522$, we have our contradiction. This implies
not only that no funky pair exists in $X_{1}\cup X_{4}$, but further that no
funky non-edge exists in $X_{1}\cup\cdots\cup X_{6}$, proving Sub-claim 5.2. ∎

_Sub-claim 5.3_ There are no funky pairs in $X_{1}\cup X_{5}$.

###### Proof.

Without loss of generality, suppose $u\in X_{1}$ and $v\in X_{5}$. We will
begin by counting the nets wherein $w$ is funky to both $u$ and $v$, noting
that $w$ is therefore contained in $X_{3}$. So we know that the triangle in
any such net is necessarily formed by $u$, $v$, and $w$; the pendants of both
$u$ and $w$ must be in $X_{1}$ and $X_{3}$, respectively, while $p_{v}$ may be
anywhere in $X_{5}\cup X_{2}$, giving $2d_{f}x_{\text{max}}^{3}n^{4}$ nets.

We now count the number of nets wherein $w$ is funky only to $u$. By Sub-claim
5.2, we have that $w\not\in X_{4}$. We get $d_{f}x_{\text{max}}^{3}n^{4}$ nets
when $w\in X_{6}$ and no nets when $w\in X_{2}$. When $w\in X_{5}$, the only
possible location for a third neighbor of $u$ is in $X_{1}$, implying both $v$
and $w$ are triangle vertices; their pendants cannot be blob-adjacent, so
$p_{v},p_{w}\in X_{5}$ giving $\frac{1}{2}d_{f}x_{\text{max}}^{3}n^{4}$ nets.
The only remaining case is when $w\in X_{3}:$ as nets do not contain $C_{4}$s,
$X_{6}$ is empty, $w$ would have to be the pendant of $u$, we would need a
triangle vertex $t\in X_{4}$, $p_{t}\in X_{1}$, and $p_{v}\in X_{2}$, giving a
count of $d_{f}x_{\text{max}}^{3}n^{4}$ nets. This implies that there are at
most $\frac{5}{2}d_{f}x_{\text{max}}^{3}n^{4}$ nets wherein $w$ is funky only
to $u$.

Finally, we count the number of nets wherein $w$ is funky only to $v$. Sub-
claim 5.2 implies that $w\in X_{1}\cup X_{3}$, so we first count those where
$w\in X_{1}$. In this case, no nets intersect $X_{4}$ since nets do not
contain $C_{4}$s, and hence the non-funky $P_{4}$ which does not contain $v$
must be entirely within $X_{1}$. As $v$ cannot have three neighbors in
$X_{1}$, we have that $p_{v}$ is anywhere in $X_{2}\cup X_{5}\cup X_{6}$,
giving a count of $3\cdot\frac{1}{2}d_{f}x_{\text{max}}^{3}n^{4}$ nets. Next,
we see that if $w\in X_{3}$, then either $u$ or $w$ is a triangle vertex, but
not both. In either case, their pendant would have to share their blob, which
then contradicts the existence of a third triangle vertex. So we have at most
$\frac{3}{2}d_{f}x_{\text{max}}^{3}n^{4}$ nets wherein $w$ is funky only to
$u$.

As $2+\frac{5}{2}+\frac{3}{2}<9.522$, we have our desired contradiction,
proving Sub-claim 5.3. ∎

Taking the above three sub-claims together, we have that all funky pairs in
$X1\cup\cdots\cup X_{6}$ must be between outer blobs. To finish the proof of
Claim 3.2, we suppose toward the familiar contradiction, without loss of
generality, that $u\in X_{1}$ and $v\in X_{2}$. We will count the number of
nets containing $u$, $v$, and $w$, wherein $w$ is funky to at least one of $u$
and $v$.

We begin by counting the nets wherein $w$ is funky to both $u$ and $v$, noting
that our sub-claims imply that $w\in X_{3}$. In this case, there can be at
most one vertex in an interior blob, giving a count of
$4d_{f}x_{\text{max}}^{3}n^{4}$ nets.

We will then use symmetry to only count the nets wherein $w$ is funky only to
$u$. We know that the third neighbor $x$ of $u$ in any such net is contained
in $X_{1}\cup X_{4}$, implying that $w$ must be a neighbor of $v$. Therefore,
we have that $w\in X_{2}$ with $v$, $p_{v}$ and $p_{w}$, giving at most
$2d_{f}x_{\text{max}}^{3}n^{4}$ nets in this case.

Doubling our most recent case to account for the nets wherein $w$ is funky
only to $v$, we have that there are at most $8d_{f}x_{\text{max}}^{3}n^{3}$
nets containing $u$, $v$, and some $w$ which is funky to one or both of $u$
and $v$, giving our desired contradiction and completing the proof that there
are no funky pairs in $X_{1}\cup\cdots\cup X_{6}$. ∎

We now intend to show that in an extremal example, the trash is empty (i.e.
$x_{0}=0$). We will do this by considering the ramifications of moving a
vertex $x\in X_{0}$ to a blob, specifically as they relate to $d_{f}(x)$.
Claim 3.3 gives a lower bound on the potential funky degree of trash vertices,
while Claim 3.4 shows that every vertex in an extremal example must be in
roughly the same number of nets. Claim 3.5 then argues that trash vertices, by
virtue of having high funky degree, cannot be in the correct number of nets.
This will imply that $X_{0}$ contains only vertices which can be placed in a
blob without creating any funky pairs.

######  Claim 3.3.

If a vertex $x\in X_{0}$ is moved to $X_{i}$, then either $d_{f}(x)=0$ or else

$d_{f}(x)\geq\left\\{\begin{matrix}0.0433316&i\in[3]\\\
0.0322447&i\not\in[3].\end{matrix}\right.$

###### Proof.

Prior to moving $x$ into a blob, there were no funky pairs; as such, after
moving $x$, all funky pairs must include $x$. Suppose that $d_{f}(x)>0$ and
let $w$ be a funky partner of $x$. For the purposes of case analysis, there
are six orientations for the funky pair $(x,w)$. For the sake of brevity, we
will only show the arguments for one of the cases here, and the others can be
found in the Appendix B.

To achieve a lower-bound on $d_{f}(x)$, we will take an approach similar to
the proof of Claim 3.2. As all funky pairs include $x$, we know that every net
containing the funky pair $(x,w)$ contains at least one non-funky $P_{4}$.
Further, we need only find the placement of the $d_{f}(x)n$ funky partners of
$x$ which maximizes the number of nets containing $(x,w)$. Regardless of the
location of $x$ and $w$, we can get a trivial upper bound on the number of
nets containing both $x$ and another vertex in the trash as
$\frac{n^{3}}{6}(x_{0}n)$.

The case we will investigate is when $x\in X_{1}$ and $w\in X_{2}$, and we
begin by determining all possible configurations of nets containing the edge
$xw$. First, let us determine those configurations wherein all of the other 4
vertices are coblobular:

  * (a)

a non-funky $P_{4}$ is contained in $X_{1}$,

  * (b)

four vertices lie in $X_{2}$ and $x=p_{w}$,

  * (c)

four vertices lie in $X_{2}$ and $w=p_{x}$,

  * (d)

four vertices lie in $X_{2}$ and $wx\in\Delta$, or

  * (e)

four vertices lie in one of $X_{3}$, $X_{4}$ or $X_{6}$.

Note that four vertices cannot lie in $X_{5}$ as $w$ can neither be funky to
any other vertex in the graph nor have degree 5. Together, constructions (a)
and (b) contribute at most $2(x_{\text{max}}n)^{4}/24$ nets. Notice, however,
that constructions (c)-(e) all require the choice of 2 additional funky
partners of $x$; we could take a trivial upper bound of
$5\cdot\frac{(d_{f}(x)n)^{2}}{2}\cdot\frac{(x_{\text{max}}n)^{2}}{2}$ but the
entire funky neighborhood of $x$ cannot be in 4 places at once. We will
leverage this observation shortly.

If there is a non-funky blob-induced $P_{4}$ in the net, then it must neither
contain $w$ nor intersect $X_{5}$. Therefore, any such net must have its non-
funky blob-induced $P_{4}$ in $X_{1}$, $X_{4}$, $X_{6}$, and $X_{3}$. In this
case, $x=t_{w}$ and contributes at most $(x_{\text{max}}n)^{3}$ for each funky
neighbor in $X_{6}$. The only remaining case is that the non-funky $P_{4}$
contains $w$ and lies in $X_{2}$, implying that $xw\in\Delta$ and $p_{x}$ is
in $X_{1}\cup X_{4}\cup X_{6}\cup X_{3}$.

So, there are at most $(x_{\text{max}}n)^{4}/12$ nets containing $xw$ and no
other funky partners of $x$. We now take advantage of the observation that the
funky neighbors of $x$ cannot be in more than one place at a time. Define
$d_{i}(x)$ to be the density of funky partners in $X_{i}$. First, we determine
an upper bound on the nets containing $xw$ and one other funky partner of $x$:

$\displaystyle(d_{6}(x)n)\cdot(x_{\text{max}}n)^{3}+(d_{2}(x)n)\cdot\frac{(x_{\text{max}}n)^{2}}{2}\cdot(x_{\text{max}}n)$
$\displaystyle=x_{\text{max}}^{3}n^{4}\left(d_{6}(x)+\frac{1}{2}d_{2}(x)\right)$
$\displaystyle\leq d_{f}(x)x_{\text{max}}^{3}n^{4},$

which is achieved if all funky partners of $x$ lie in $X_{6}$. Next, we
determine an upper bound on the nets containing $xw$ and two other funky
partners of $x$:

$\displaystyle
n^{4}\frac{x_{\text{max}}^{2}}{2}\left(\frac{(d_{2}(x)^{2}+d_{3}(x)^{2}+d_{4}(x)^{2}+d_{6}(x)^{2})}{2}+d_{2}(x)(d_{3}(x)+d_{6}(x))\right).$

We observe that any maximum of this expression will occur when $d_{4}(x)=0$.
Further, if $d_{i}(x)>0$ for each $i\in\\{2,3,6\\}$, then there exist pairs of
funky partners $(v_{3},v_{6})\in X_{3}\times X_{6}$ which do not contribute to
the net count; as such, a maximum of our expression occurs when $d_{6}(x)=0$
as well. Therefore, we have that the number of nets containing $xw$ and two
other funky partners of $x$ is bounded above by

$\displaystyle
n^{4}\frac{x_{\text{max}}^{2}}{2}\left(\frac{(d_{2}(x)^{2}+d_{3}(x)^{2})}{2}+d_{2}(x)d_{3}(x)\right)$
$\displaystyle=n^{4}\frac{x_{\text{max}}^{2}}{2}\cdot\frac{1}{2}(d_{2}(x)+d_{3}(x))^{2}$
$\displaystyle\leq
n^{4}\frac{x_{\text{max}}^{2}}{2}\cdot\frac{1}{2}(d_{f}(x))^{2}$
$\displaystyle=\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}n^{4}.$

Therefore, it follows that when $x\in X_{1}$ and $w\in X_{2}$, the number of
nets containing $xw$ is bounded above by

$n^{4}\left(\frac{x_{\text{max}}^{4}}{12}+d_{f}(x)x_{\text{max}}^{3}+\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{x_{0}}{6}\right).$

If we delete the edge $xw$, we have at least
$x_{\text{min}}^{3}(x_{\text{min}}-d_{f}(x))n^{4}$ nets. As $G$ is extremal,
it follows that

$x_{\text{min}}^{3}(x_{\text{min}}-d_{f}(x))\leq\frac{x_{\text{max}}^{4}}{12}+d_{f}(x)x_{\text{max}}^{3}+\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{x_{0}}{6},$

which implies that $d_{f}(x)\geq 0.0433316$. Following similar arguments,
detailed in Appendix B, we arrive at the bounds found in Table 1, concluding
the proof of Claim 3.3.

Table 1: Number of copies of nets containing $x,w$ in given config class. $x$ | $w$ | Upper Bounds for Nets | Lower Bound for $d_{f}(x)$
---|---|---|---
$X_{1}$ | $X_{2}$ | $\frac{1}{6}x_{0}+\frac{1}{12}x_{\text{max}}^{4}+d_{f}(x)x_{\text{max}}^{3}+\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}$ | 0.0433316
$X_{1}$ | $X_{4}$ | $\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}$ | 0.0610118
$X_{1}$ | $X_{5}$ | $\frac{1}{6}x_{0}+\frac{1}{12}x_{\text{max}}^{4}+d_{f}(x)x_{\text{max}}^{3}+\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}$ | 0.0433316
$X_{4}$ | $X_{1}$ | $\frac{1}{6}x_{0}+\frac{13}{6}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{8}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}$ | 0.0322447
$X_{4}$ | $X_{2}$ | $\frac{1}{6}x_{0}+\frac{1}{12}x_{\text{max}}^{4}+\frac{3}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}$ | 0.0349529
$X_{4}$ | $X_{5}$ | $\frac{1}{6}x_{0}+d_{f}(x)x_{\text{max}}^{3}+\frac{1}{8}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}$ | 0.0504913

∎

The following claim follows directly from Lemma 1.1 and is placed here
primarily to remind the reader ahead of Claim 3.5 in roughly how many nets any
given vertex in $G$ must reside.

######  Claim 3.4.

Every vertex of the extremal graph $G$ is contained in at least
$(24/1555+o(1))\binom{n}{5}\approx 0.00012861736n^{5}$ induced net graphs.

The following claim will then imply that our extremal example $G$ is a (not
necessarily balanced or iterated) blow-up of the net graph.

######  Claim 3.5.

For each $v\in X_{0}$, there is some $i\in[6]$ so that $v$ can be moved to
$X_{i}$ without creating any funky pairs.

###### Proof.

Assume there exists some $x\in X_{0}$ so that $d_{f}(x)>0$ if $x$ were to be
placed in any of the 6 main blobs. We will show that $x$ is in far fewer than
$(24/1555+o(1))\binom{n}{5}$ nets, a contradiction.

Let $a_{i}n$ be the number of neighbors of $x$ in $X_{i}$ and $b_{i}n$ be the
number of neighbors of $x$ in $X_{i}$ for each $i\in\\{0,1,\dots,6\\}$.
Normalizing by $n^{4}$, we will let $A$ be the number of nets containing $x$
and vertices from 5 different blobs, $B$ be the number of nets containing $x$
and 5 coblobular vertices, and $C$ be all other nets not involving trash
vertices.

We have that

$\displaystyle A$ $\displaystyle\leq
b_{2}b_{3}a_{4}b_{5}b_{6}+b_{1}b_{3}b_{4}a_{5}b_{6}+b_{1}b_{2}b_{4}b_{5}a_{6}+a_{1}b_{2}b_{3}a_{5}a_{6}+b_{1}a_{2}b_{3}a_{4}a_{6}+b_{1}b_{2}a_{3}a_{4}a_{5},$
$\displaystyle B$
$\displaystyle\leq\sum_{i=1}^{6}\left(\frac{a_{i}^{3}b_{i}^{2}}{3!2!}+\frac{a_{i}b_{i}^{4}}{1!4!}\right)\text{,
and }$ $\displaystyle C$
$\displaystyle\leq\frac{1}{2!2!}\sum_{i=1}^{3}a_{i}^{2}b_{i}^{2}\left(-a_{i}-a_{i+3}+\sum_{1\leq
j\leq
6}a_{j}\right)+\frac{1}{2!2!}\sum_{i=4}^{6}a_{i}^{2}b_{i}^{2}(a_{1}+a_{2}+a_{3}-a_{i-3}).$

A convenient way to convince yourself that these counts are correct is to
observe that every net must contain either a non-funky bull or a non-funky
$P_{4}+K_{1}$, and note that these structures are either blob-induced or
component-wise coblobular and respect the blob-structure. We will say that $D$
is the number of nets containing $x$ and at least one other trash vertex.

The goal of this claim, then, is to show that the following program is bounded
away from $(24/1555)/5!=1/7775\approx 0.000128617363$:

$(P)\left\\{\begin{matrix}[l]\text{maximize}&A+B+C+D\\\ \text{subject
to}&\sum_{i=0}^{6}(a_{i}+b_{i})=1\\\ &(x^{\prime})\leq
a_{i}+b_{i}\leq(x^{\prime\prime})\text{ for }i\in[6],\\\ &a_{0}+b_{0}\leq
x_{0},\\\ &a_{2}+a_{3}+b_{4}+a_{5}+a_{6}\geq 0.0433316,\\\
&a_{1}+a_{3}+a_{4}+b_{5}+a_{5}\geq 0.0433316,\\\
&a_{1}+a_{2}+a_{4}+a_{5}+b_{6}\geq 0.0433316,\\\
&b_{1}+a_{2}+a_{3}+b_{5}+b_{6}\geq 0.0322447,\\\
&a_{1}+b_{2}+a_{3}+b_{4}+b_{6}\geq 0.0322447,\\\
&a_{1}+a_{2}+b_{3}+b_{4}+b_{5}\geq 0.0322447,\\\ &a_{i},b_{i}\geq 0\text{ for
}i\in\\{0,1,\dots,6\\}.\end{matrix}\right.$

However, we do not have a form for $D$ as we will be optimizing over all
possible ways to place trash vertices into the blobs and assume that the trash
vertices always contribute to nets a vertex from its blob contributes to nets.
So we relax the above problem the following:

$(P^{\prime})\left\\{\begin{matrix}[l]\text{maximize}&f=A+B+C\\\ \text{subject
to}&\sum_{i=1}^{6}(a_{i}+b_{i})=1\\\ &(x^{\prime})\leq
a_{i}+b_{i}\leq(x^{\prime\prime}+x_{0})\text{ for }i\in[6],\\\
&a_{2}+a_{3}+b_{4}+a_{5}+a_{6}\geq 0.0433316,\\\
&a_{1}+a_{3}+a_{4}+b_{5}+a_{5}\geq 0.0433316,\\\
&a_{1}+a_{2}+a_{4}+a_{5}+b_{6}\geq 0.0433316,\\\
&b_{1}+a_{2}+a_{3}+b_{5}+b_{6}\geq 0.0322447,\\\
&a_{1}+b_{2}+a_{3}+b_{4}+b_{6}\geq 0.0322447,\\\
&a_{1}+a_{2}+b_{3}+b_{4}+b_{5}\geq 0.0322447,\\\ &a_{i},b_{i}\geq 0\text{ for
}i\in\\{0,1,\dots,6\\}.\end{matrix}\right.$

We will discretize the space of possible solutions to $(P^{\prime})$,
determine the value of the objective function at the center of each cell, and
use a bound on the gradient to show that the function is bounded above by
$0.0001275$ in each cell. If the global bound on the gradient is not
sufficient in bounding the optimization function, we generate a bound on the
gradient within the cell, and if necessary, refine the discretization within
the cell. For every $a_{i}$ and $b_{i}$, we check $s+1=51$ equally spaced
values between 0 and $x^{\prime\prime}+x_{0}$, inclusive. By this, we have a
grid of $s^{12}$ boxes where every feasible solution of $(P^{\prime})$, and
hence of $(P)$, is in one of the boxes.

To determine a global bound on the gradient, we find the partial derivatives
of $f$:

$\displaystyle\frac{\partial f}{\partial a_{1}}$
$\displaystyle=b_{2}b_{3}a_{5}a_{6}+\frac{1}{24}b_{1}^{4}+\frac{1}{4}a_{1}^{2}b_{1}^{2}+\frac{1}{2}(a_{1}b_{1}^{2})(a_{2}+a_{3}+a_{5}+a_{6})+\frac{1}{4}(a_{2}^{2}b_{2}^{2}+a_{3}^{2}b_{3}^{2}+a_{5}^{2}b_{5}^{2}+a_{6}^{2}b_{6}^{2})$
$\displaystyle\frac{\partial f}{\partial a_{4}}$
$\displaystyle=b_{2}b_{3}b_{5}b_{6}+b_{1}a_{2}b_{3}a_{6}+b_{1}b_{2}a_{3}a_{5}+\frac{1}{24}b_{4}^{4}+\frac{1}{4}a_{4}^{2}b_{4}^{2}+\frac{1}{4}(a_{2}^{2}b_{2}^{2}+a_{3}^{2}b_{3}^{2})+\frac{1}{2}(a_{4}b_{4}^{2})(a_{2}+a_{3})$
$\displaystyle\frac{\partial f}{\partial b_{1}}$
$\displaystyle=b_{3}b_{4}a_{5}b_{6}+b_{2}b_{4}b_{5}a_{6}+a_{2}b_{3}a_{4}a_{6}+b_{2}a_{3}a_{4}a_{5}+\frac{1}{6}a_{1}^{3}b_{1}+\frac{1}{6}a_{1}b_{1}^{3}+\frac{1}{2}a_{1}^{2}b_{1}(a_{2}+a_{3}+a_{5}+a_{6})$
$\displaystyle\frac{\partial f}{\partial b_{4}}$
$\displaystyle=b_{1}b_{3}a_{5}b_{6}+b_{1}b_{2}b_{5}a_{6}+\frac{1}{6}a_{4}^{3}b_{4}+\frac{1}{6}a_{4}b_{4}^{3}+\frac{1}{2}a_{4}^{2}b_{4}(a_{2}+a_{3}).$

We were able to bound each of these partials by
$\frac{4}{3}(x^{\prime\prime}+x_{0})^{4}$. To do so, one should observe the
portion of the partial contributed by $A$ can be bounded above by
$(x^{\prime\prime}+x_{0})^{4}$ in each case, and therefore the rest of the
partial can be bounded by $(1/3)(x^{\prime\prime}+x_{0})^{3}$ by taking
advantage of obvious symmetries. One should note that the partial taken with
respect to $b_{1}$ is the closest to meeting our bound, while the others are
closer to $\frac{7}{6}(x^{\prime\prime}+x_{0})^{3}$.

As each 12-dimensional cell has side-length $1/s$, the objective function can
exceed the value at its center by at most
$12\cdot\frac{1/2}{2}\cdot\frac{4}{3}(x^{\prime\prime}+x_{0})^{4}$. The local
bounds on the gradient are obtained in our algorithm are achieved by
substituting $(a_{i}+(1/t)/2)$ and $(b_{i}+(1/t)/2)$ into each partial, where
$t$ is the side-length of the current cell which may or may not be refined,
and we simply take the steepest direction of ascent as our bound to replace
$\frac{4}{3}(x^{\prime\prime}+x_{0})^{4}$.

Using $s=50$, we successfully bounded the objective function below
$0.0001275$; a handful of cells required refinement, but not one cell required
more than 6 refinements. The C++ code can be found at
https://sites.google.com/view/ablumenthal/.

As the number of nets containing $x$ is bounded away from the average, we have
contradicted the existence of a trash vertex which cannot be placed in any
blob without creating funky pairs, completing the proof of Claim 8. ∎

Since every trash vertex can be placed into one of the six blobs without
creating any funky pairs with vertices originally in $X_{1}\cup\cdots\cup
X_{6}$. Therefore, we simply add each trash vertex into its corresponding
blob; at worst, we may have funky pairs involving trash vertices in different
blobs, but we simply apply Claim 3.2 noting that our bounds on $d_{f}(x)$ and
$f$ are even more strict.

Therefore, we have established the top-layer structure of $G$ where each part
is roughly one-sixth of the graph. As such, an induced net in $G$ can only be
found by picking a single vertex from each of the 6 blobs or by picking all 6
within the same blob, implying that

$N(n)=(x_{1}\cdots x_{6})n^{6}+N(x_{1}n)+\cdots+N(x_{6}n).$

By averaging over all subgraphs of $G$ of order $n-1$, we have that
$N(n)\leq\frac{n}{n-6}N(n-1)$ for all $n$, so

$\ell:=\lim_{n\to\infty}\frac{N(n)}{\binom{n}{6}}$

exists and so satisfies

$\ell+o(1)=6!(x_{1}\cdots x_{6})+\ell\cdot(x_{1}^{6}+\cdots x_{6}^{6}),$

which implies that that $x_{i}=\frac{1}{6}+o(1)$ and $\ell=\frac{24}{1555}$,
giving the constraints on the $x_{i}$’s. In order to complete the proof of
Theorem 2, we need only show that $|X_{i}|-|X_{j}|\leq 1$ for all $i,j\in[6]$.

######  Claim 3.6.

For $n$ large enough, we have $|X_{i}|-|X_{j}|\leq 1$ for all $i,j\in[6]$.

###### Proof.

Let $i,j\in[6]$ satisfy $|X_{i}|-|X_{j}|\geq 2$, noting that $i\not=j$. Let
$v\in X_{i}$ be chosen to minimize $N^{u}$ over vertices in $X_{i}$ and $w\in
X_{j}$ be chosen to maximize $N^{w}$ over vertices in $X_{j}$. As $G$ is
extremal, $N^{v}+N^{v,w}-N^{w}\geq 0$; otherwise, we can increase the number
of nets by replacing $v$ with a copy of $w$.

Let $y_{i}:=|X_{i}|=x_{i}n$ and $y_{j}:=|X_{j}|=x_{j}n$. By the monotonicity
of $\frac{N(n)}{n^{6}}$, we have

$\frac{24}{1555}+o(1)\geq\frac{N(y_{j})}{\binom{y_{j}}{6}}\geq\frac{N(y_{i})}{\binom{y_{i}}{6}}\geq\frac{24}{1555}+o(1).$

Therefore, as $y_{i}-y_{j}\geq 2$ and $x_{k}=\frac{1}{6}+o(1)$ for all
$k\in[6]$,

$\displaystyle N^{v}+N^{vw}-N^{w}$
$\displaystyle\leq\frac{N(y_{i})}{y_{i}}+\frac{y_{1}\cdots
y_{6}}{y_{i}}+\frac{y_{1}\cdots
y_{6}}{y_{i}y_{j}}-\frac{N(y_{j})}{y_{j}}-\frac{y_{1}\cdots y_{6}}{y_{j}}$
$\displaystyle=\frac{y_{j}N(y_{i})-y_{i}N(y_{j})}{y_{i}y_{j}}+(y_{j}-y_{i}+1)\cdot\frac{y_{1}\cdots
y_{6}}{y_{i}y_{j}}$
$\displaystyle\leq\left(\frac{24}{1555}+o(1)\right)\left(\frac{1}{y_{i}}\binom{y_{i}}{6}-\frac{1}{y_{j}}\binom{y_{j}}{6}\right)+(-2+1)\cdot\frac{y_{1}\cdots
y_{6}}{y_{i}y_{j}}$ $\displaystyle\leq\left(\frac{24}{1555\cdot
6!}+o(1)\right)\left(y_{i}^{5}-y_{j}^{5}\right)-\frac{y_{1}\cdots
y_{6}}{y_{i}y_{j}}$ $\displaystyle=\left(\frac{24}{1555\cdot
6!}+o(1)\right)(y_{i}-y_{j})(y_{i}^{4}+y_{i}^{3}y_{j}+y_{i}^{2}y_{j}^{2}+y_{i}y_{j}^{3}+y_{j}^{4})-\frac{y_{1}\cdots
y_{6}}{y_{i}y_{j}}$ $\displaystyle\leq\left(\frac{24}{1555\cdot
6!}+o(1)\right)\cdot 2\cdot
4n^{4}\left(\frac{1}{6}+o(1)\right)^{4}-n^{4}\left(\frac{1}{6}+o(1)\right)^{4}$
$\displaystyle=n^{4}\left(\frac{1}{6}+o(1)\right)^{4}\cdot\left(\left(\frac{24\cdot
8}{1555\cdot 6!}+o(1)\right)-1\right)<0,$

a contradiction, proving our claim. ∎

With this claim, the proof of Theorem 2 is complete. We now turn our attention
back to Theorem 1: for $k\geq 1$, the unique graph on $6^{k}$ vertices which
maximizes the number of induced copies of the net graph is a balanced,
iterated blow-up of the net. We will note that the following argument is
largely recyclable to other graphs, given a proof of corresponding “Theorem
2.” In other words, if one can show that large extremal constructions for a
given graph $G$ are (nearly) balanced blow-ups of $G$, then the following
argument can be recycled to show that the $|G|^{k}$-size extremal
constructions are unique, and the structure iterates.

###### Proof.

Let $G$ be a minimum counter-example. If $G$ has the outer structure of the
net, then the subgraphs inside the blobs are balanced, iterated blow-ups,
implying that $G$ would be a balanced, iterated blow-up of the net; as such,
$G$ does not have the outer structure of the net. Specifically, $G$ has
$6^{k}>n_{0}$ vertices, where $n_{0}$ comes from Theorem 2, and $G$ has at
least as many nets as the balanced, iterated blow-up $N_{6^{k}}$.

Take any extremal $H$ on $6^{\ell}\geq n_{0}$ vertices, and replace every
vertex in $G$ with a copy of $H$ to construct $G_{1}$, which has at least
$6^{k}\cdot N(H)+N(G)\cdot(6^{\ell})^{6}$ nets. Replace every vertex in
$N_{6^{k}}$ to make $G_{2}$ and note that it has $6^{k}\cdot
N(H)+N(N_{6^{k}})\cdot(6^{\ell})^{6},$ which is extremal by Theorem 2. This
implies that $G_{1}$ is also extremal, so by Theorem 2 we get that $G_{1}$ is
a balanced blow-up of the net with blobs $X_{1},\dots,X_{6}$. Two vertices in
$G_{1}$ are in the same set $X_{i}$ if and only if their adjacency pattern
agrees on more than half of the remaining vertices. But this implies that
every copy $H^{\prime}$ of $H$ in $G_{1}$ inserted into the blow-up of $G$ has
the property that $V(H^{\prime})$ are coblobular, inducing a net-structure on
$G$, a contradiction. ∎

The only remaining components of the net inducibility problem involve
determining all small graphs which maximize the density of induced net graphs.
We know that for $n=8$, there is a graph which contains the same number of
induced net graphs as a balanced, iterated blow-up of the net graph,
indicating that the net graph is not a fractalizer. Therefore, we will not
continue to pursue the net inducibility problem beyond these results.

##  4 Conclusion

We note also that Claim 3.2 could be automated with a computer algebra system.
We have a particular interest in this observation since we suspect that
asymmetric graphs may be a fruitful direction of study to find a nontrivial
fractalizer, but many simplifying techniques used in the literature are not
applicable to them. A graph is said to be asymmetric if its automorphism group
is trivial. This class of graphs is interesting since many counterexamples to
being a fractalizer take advantage of graph automorphisms. For example, it can
be shown that any graph with twins is not a fractalizer. The smallest
nontrivial assymmetric graphs are on 7 vertices, which is still potentially
tractable with flag algebras, and we expect that this will be where the
smallest nontrivial fractalizer will be found. Nevertheless, we will not be so
bold as to officially conjecture such a thing, and so we instead provide the
following weaker conjecture:

######  Conjecture 3.

There exists an asymmetric fractalizer on at most $9$ vertices.

We make the above conjecture because (a) we believe it to be true, but also
(b) we would certainly like to be proven wrong if possible.

## References

  * [1] SageMath, the Sage Mathematics Software System (Version 6.3), 2020.  https://www.sagemath.org.
  * [2] J. Balogh, P. Hu, B. Lidický, and F. Pfender.  Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle.  preprint, 2018.
  * [3] D. Burke, B. Lidický, F. Pfender, and M. Phillips.  Inducibility of 4-vertex tournaments.  Manuscript.
  * [4] I. Choi, B. Lidický, and F. Pfender.  Inducibility of directed paths.  Discrete Mathematics, 343, 2020.
  * [5] E. Czabarka, A. A. V. Dossou-Olory, L. A. Székely, and S. Wagner.  Inducibility of $d$-ary trees.  Discrete Math., 343(2):111671, 15, 2020.
  * [6] C. Even-Zohar and N. Linial.  A note on the inducibility of 4-vertex graphs.  Graphs and Combinatorics, 31(5):1367–1380, 2014.
  * [7] V. Falgas-Ravry and E. R. Vaughan.  Turán $H$-densities for 3-graphs.  Electron. J. Combin., 19(3):Paper 40, 26, 2012.
  * [8] J. Fox, H. Huang, and C. Lee.  A solution to the inducibility problem for almost all graphs.  preprint, 2017.
  * [9] J. Hirst.  The inducibility of graphs on four vertices.  Journal of Graph Theory, 75, 2013.
  * [10] P. Hu, B. Lidický, F. Pfender, and J. Volec.  Maximum density of induced oriented $c_{4}$ is achieved by iterated blow-ups.  Manuscript.
  * [11] P. Hu, J. Ma, S. Norin, and H. Wu.  The inducibility of oriented stars, 2020.
  * [12] H. Huang.  On the maximum induced density of directed stars and related problems.  SIAM J. Discrete Math., 28(1):92–98, 2014.
  * [13] B. Lidický, C. Mattes, and F. Pfender.  $C_{5}$ is almost a fractalizer.  preprint, 2020.
  * [14] H. Liu, O. Pikhurko, M. Sharifzadeh, and K. Staden.  Stability from graph symmetrisation arguments with applications to inducibility, 2020.
  * [15] N. Pippenger and M. Golumbic.  The inducibility of graphs.  Journal of Combinatorial Theory (B), 19:189–203, 1975.
  * [16] A. Razborov.  Flag algebras.  J. Symbolic Logic, 72:1239–1282, 2007.
  * [17] Łukasz Bożyk, A. Grzesik, and B. Kielak.  On the inducibility of oriented graphs on four vertices, 2020.
  * [18] E. R. Vaughan.  Flagmatic 2.0.  2012\.
  * [19] R. Yuster.  On the exact maximum induced density of almost all graphs and their inducibility.  Journal of Combinatorial Theory, Series B, 136:81–109, 2019.

##  5 Appendix A

This appendix includes the proof of Claim 3.1. It was placed here so as to not
distract from the more interesting arguments and because the arguments herein
are easily reproducible for other graphs.

###### Proof.

To obtain the bounds in Claim 3.1, we solve four quadratic programs as in the
proof of Claim 4 of [2]. The objectives are to minimize $x_{1}$, maximize
$x_{1}$, maximize $x_{0}$, and maximize $f$, respectively. The constraints are
$\displaystyle\sum_{i=0}^{6}x_{i}=1$ and

$2\sum_{1\leq i<j\leq 6}x_{i}x_{j}-2\cdot
f-a\sum_{i=1}^{6}x_{i}^{2}>0.000149043538$

in all four cases. By symmetry, bounds for $x_{1}$ apply also for
$x_{2},\dots,x_{6}$. Recall that we chose $a=4.99$.

Consider the first program described above:

$(P)\left\\{\begin{matrix}\text{minimize}&&x_{1}\\\ \text{subject
to}&&\sum_{i=0}^{6}x_{i}=1\\\ &&2\sum_{1\leq i<j\leq 6}x_{i}x_{j}-2\cdot
f-a\sum_{i=1}^{6}x_{i}^{2}>0.000149043538\\\ &&x_{i}\geq 0\text{ for
}i\in\\{0,1,\dots,6\\}.\end{matrix}\right.$

If $(P)$ has a feasible solution $(S)$, then there exists a feasible solution
$S^{\prime}$ of $(P)$ where

$\displaystyle S^{\prime}(x_{1})=S(x_{1}),\text{ }S^{\prime}(f)=0,\text{
}S^{\prime}(x_{0})=S(x_{0}),$ $\displaystyle
S^{\prime}(x_{2})=\cdots=S^{\prime}(x_{6})=\frac{1}{5}(1-S(x_{1})-S(x_{0})).$

Since $x_{2},\dots,x_{6}$ appear only in constraints, we only need to check if
the second constraint is satisfied. The left hand side of this constraint can
be rewritten as

$\displaystyle 2x_{1}\sum_{2\leq i<j\leq 6}x_{i}+2\sum_{2\leq i<j\leq
6}x_{i}x_{j}-a\sum_{1\leq i<j\leq 6}x_{i}^{2}-2f$
$\displaystyle=2x_{1}\sum_{2\leq i<j\leq 6}x_{i}-\sum_{2\leq i<j\leq
6}(x_{i}-x_{j})^{2}-(a-4)\sum_{1\leq i<j\leq 6}x_{i}^{2}-ax_{1}^{2}-2f.$

Note that the sum of squared differences in the last line is minimized if
$x_{i}=x_{j}$ for all $i,j\in\\{2,\dots,6\\}$. The term
$x_{2}^{2}+\cdots+x_{6}^{2}$, subject to $x_{2}+\cdots+x_{6}$ being a
constant, is also minimized if $x_{i}=x_{j}$ for all $i,j\in\\{2,\dots,6\\}$.
Since $f\geq 0$, the term $2f$ is minimized when $f=0$. Hence, the second
constraint in the program is satisfied by $S^{\prime}$ and we can add the
constraints $x_{2}=\cdots=x_{6}$ and $f=0$ to bound $x_{1}$. The resulting
program $(P^{\prime})$ is

$(P^{\prime})\left\\{\begin{matrix}\text{minimize}&&x_{1}\\\ \text{subject
to}&&x_{0}+x_{1}+5y=1\\\ &&10x_{1}y-(4-a)\cdot
5y^{2}-ax_{1}^{2}>0.000149043538\\\ &&x_{0},x_{1},y\geq 0.\end{matrix}\right.$

We solve $(P^{\prime})$ using Lagrange multipliers with the work delegated to
Sage [1]. Finding an upper bound on $x_{1}$ is done by changing the objective
to maximization.

Similarly, we can set $x_{1}=\cdots=x_{6}=\frac{1}{6}$ to get an upper bound
on $f$. We can set $f=0$ and $x_{1}=\cdots=x_{6}=(1-x_{0})/6$ to get an upper
bound on $x_{0}$. We omit the details as the arguments are similar to above.
Sage scripts for solving the all such programs are provided at
https://sites.google.com/view/ablumenthal/. ∎

##  6 Appendix B

This appendix contains the remaining 5 cases needed to acquire the bounds
listed in Table 1 for Claim 3.3. In each of theses cases, a vertex $x\in
X_{0}$ is moved to a blob and we determine an upper bound on the number of
nets containing $x$ and some funky partner $w$. The cases explored involve the
locations of both $x$ and $w$, and the upper bound on the number of nets
containing this pair vertices is used to provide a lower bound on the
normalized funky degree of $x$. As follows are the five remaining cases with
some notes about recommended techniques that could be used in future work when
studying the inducibility of graphs on $n\geq 6$ vertices.

######  Case 1.

If $x\in X_{1}$ and $w\in X_{4}$, then there are at most

$\left(\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$, and so $d_{f}(x)\geq 0.0610118$.

###### Proof.

As $xw\not\in E(G)$, we know that $w$ is contained in a non-funky $P_{4}$ in
any net containing both $x$ and $w$. We first count nets with a non-funky
$P_{4}$ contained in $X_{4}$. If $x$ is a triangle vertex, then $w$ is a
pendant in the non-funky $P_{4}$ containing $w$. Further, $p_{x}\in X_{2}\cup
X_{3}\cup X_{4}$. This gives at most
$n^{4}\cdot\left(\frac{d_{f}(x)x_{\text{max}}^{3}}{3!}+\frac{d_{f}(x)x_{\text{max}}^{2}}{2}\right)$
nets of this type. Otherwise, $x$ is a pendant, so $t_{x}\in X_{4}$, giving at
most $n^{4}\cdot\frac{d_{f}(x)^{3}x_{\text{max}}}{6}$ nets of this type.

Next, we count the number of nets containing $x$ and $w$ with a blob-induced
$P_{4}$. As $w\in X_{4}$, we know that $w$ is a triangle vertex and hence $x$
is a pendant. Every net containing $x$ and $w$ must then have a blob-induced
bull, giving at most $n^{4}\cdot\frac{1}{3}d_{f}(x)x_{\text{max}}^{3}$ nets of
this type. We thus have a normalized count of

$\left(\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$, and so $d_{f}(x)\geq 0.0610118$. ∎

######  Case 2.

If $x\in X_{1}$ and $w\in X_{5}$, then there are at most

$\left(\frac{1}{6}x_{0}+\frac{1}{12}x_{\text{max}}^{4}+d_{f}(x)x_{\text{max}}^{3}+\frac{1}{4}d_{f}(x)^{2}x_{\text{max}}^{2}\right)n^{4}$

nets containing $x$ and $w$, and so $d_{f}(x)\geq 0.0433316$.

###### Proof.

We begin by noting that $xw\in E(G)$, and we now outline all of the
configurations of nets containing both $x$ and $w$.

Suppose that $x=p_{w}$. Then any net containing $x$ and $w$ also contains a
non-funky $P_{4}$ which avoids both $x$ and $w$. As such, either this non-
funky $P_{4}$ is contained in $X_{5}$ or else is blob-induced in $X_{1}$,
$X_{4}$, $X_{6}$, and $X_{3}$. Note that the former case involves no
additional funky partners of $x$ and the latter involves precisely one
additional funky partner of $x$ located in $X_{1}$.

Suppose instead that $x=t_{w}$. Once more, any net containing $x$ and $w$ also
contains a non-funky $P_{4}$ which avoids both of these vertices and must
hence be contained entirely in $X_{1}$ or in $X_{3}$. Note that the former
case involves no additional funky partners of $x$ and the latter involves 2
additional funky partners of $x$ located in either $X_{1}$ or $X_{3}$.

Finally, suppose that $x$ and $w$ are both triangle vertices. Note that the
third triangle vertex $(t_{3})$ must be contained in an inner blob. There is
precisely one construction when $t_{3}\in X_{4}$, and it involves precisely
one additional funky partner of $x$, its pendant, located in $X_{3}$. There is
precisely one construction when $t_{3}\in X_{6}$, and it involves precisely
one funky partner of $x$, in this case $t_{3}$, located in $X_{6}$. There are
two possible configurations when $t_{3}\in X_{5}$. If $p_{x}\in X_{1}$, then
we get 1 configuration, and it involves precisely one additional funky partner
of $x$, $t_{3}$, in $X_{4}$. Otherwise, $p_{x}\in X_{3}\cup X_{5}$ with 2
potential configuration, both involving an additional funky partner of $x$ in
$X_{5}$ so the non-funky $P_{4}$ which does not contain $x$ is completely
contained in $X_{5}$. The two configurations differ on whether $p_{x}$ is in
$X_{5}$ or $X_{6}$, but this pendant is necessarily an additional funky
partner of $x$.

We now bound the number of nets by partitioning the nets over the number of
additional funky partners of $x$ and bounding each of these values. There are
two configurations where 0 additional funky partners are needed, giving
$2\cdot\binom{x_{\text{max}}n}{4}$ nets. We now notice that there are
precisely four possible configurations involving exactly 1 additional funky
partner of $x$, and each of these configurations involve the funky partner in
a different blob. This implies that each funky partner of $x$ is in at most
$x_{\text{max}}^{3}$ nets with $x$ and $w$, giving at most
$d_{f}(x)x_{\text{max}}^{3}$ nets containing $x$, $w$ and one more funky
partner of $x$.

Finally, we consider how the funky partners of $x$ are distributed among the
six blobs more carefully while bounding the number of nets which use two
additional funky partners of $x$. One of the configurations involves 2
additional funky partners of $x$ in $X_{5}$, another involves 2 additional
funky partners of $x$ in $X_{3}$, and the last involves an additional funky
partner of $x$ in $X_{3}$ and another in $X_{5}$. Therefore, the number of
nets containing $x$, $w$, and two more funky partners of $x$ is maximized when
all funky partners of $x$ are in $X_{3}\cup X_{5}$, and all pairs of such
funky partners can contribute to the count. Therefore, we obtain a reasonable
upper-bound of at most $\frac{n^{4}}{4}d_{f}(x)^{2}x_{\text{max}}^{2}$.

This gives the claimed enumeration and implies in the usual way that
$d_{f}(x)\geq 0.0433316$. We note that in several cases, we were drastically
over-counting by presuming that all choices of 4 vertices in one part would
induce the desired structure, namely a $P_{4}$. This is certainly absurd as
the inducibility of the $P_{4}$ has been shown to be at most 0.204513 in [18].
Future work on the inducibility of graphs of 6 or more vertices may very well
involve this sort of approach, but the improvement of the bounds here does not
warrant the added complexity of argument. ∎

######  Case 3.

If $x\in X_{4}$ and $w\in X_{1}$, then there are at most

$\left(\frac{13}{6}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{8}d_{f}(x)x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$, and so $d_{f}(x)\geq 0.0322447$.

###### Proof.

In this case, as $xw\not\in E(G)$, we know that $w$ is necessarily in a non-
funky $P_{4}$. We now partition the configurations based on whether or not a
non-funky $P_{4}$ containing $w$ is blob-induced or entirely contained in
$X_{1}$.

There are four cases in which a non-funky $P_{4}$ containing $w$ is blob-
induced:

  * •

$x$ is a triangle vertex and the $P_{4}$ that doesn’t contain $x$ intersects
$X_{1}$, $X_{4}$, $X_{5}$, and $X_{2}$, with the remaining vertex $(p_{x})$ in
$X_{3}$,

  * •

$x$ is a triangle vertex and the $P_{4}$ that doesn’t contain $x$ intersects
$X_{1}$, $X_{4}$, $X_{6}$, and $X_{3}$, with the remaining vertex $(p_{x})$ in
$X_{2}$,

  * •

$x$ is a pendant vertex and there is a blob-induced bull intersecting all
blobs but $X_{2}$, or

  * •

$x$ is a pendant vertex and there is a blob-induced bull intersecting all
blobs but $X_{3}$.

Interestingly enough, each of the four cases involves precisely 1 additional
funky partner of $x$, and the inclusion of this funky partner in $X_{3}$,
$X_{2}$, $X_{6}$ or $X_{5}$ (corresponding accordingly to the four cases
respectively) completely determines the remaining structure. Again, each funky
partner of $x$ contributes at most $x_{\text{max}}^{3}$ nets containing $x$
and $w$, so we have at most $n^{4}d_{f}(x)x_{\text{max}}^{3}$ nets in our
count thus far.

Now consider all nets containing $x$ and $w$ wherein the non-funky $P_{4}$
containing $w$ is entirely within $X_{1}$. If $x$ is a pendant vertex, then in
fact five vertices must be chosen from $X_{1}$, three of which will be
additional funky partners of $x$. This gives at most
$\binom{d_{f}(x)n}{3}x_{\text{max}}n$ nets. Otherwise, $x$ is a triangle
vertex and $w$ is a pendant vertex, so we further partition based on whether
$p_{x}$ is a funky partner of $x$.

If $p_{x}$ is a funky partner of $x$, then $p_{x}\in X_{2}\cup X_{3}$. In this
case, we need to select a funky partner of $x$ in $X_{1}$ and another in
$X_{2}\cup X_{3}$, as well as two other vertices in $X_{1}$. We get the
largest count in this case when all funky partners of $x$ are in $X_{1}\cup
X_{2}\cup X_{3}$, and we only induce a net if we choose one funky partner in
$X_{1}$ and one funky partner in $X_{2}\cup X_{3}$. Therefore, there are at
most $\frac{1}{2}\binom{d_{f}(x)n}{2}$ ways to pick two funky partners of $x$
which could possible lead to valid configurations. This gives an upper bound
of $\frac{1}{2}\binom{d_{f}(x)n}{2}\binom{x_{\text{max}}n}{2}$ nets in this
case.

If $p_{x}$ is not a funky partner of $x$, then $p_{x}\in X_{1}\cup X_{5}\cup
X_{6}$. In this case, we get the most nets when all funky neighbors of $x$ are
in $X_{1}$. We necessarily pick 2 vertices in $X_{1}$, but we pick 3 whenever
$p_{x}$ is in $X_{1}$. Therefore, we have at most
$d_{f}(x)n\cdot\binom{x_{\text{max}}n}{3}+2x_{\text{max}}n\cdot
d_{f}(x)n\cdot\binom{x_{\text{max}}n}{2}$ nets here.

We thus have an upper bound of

$\left(\frac{13}{6}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{8}d_{f}(x)x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$ in this case, implying in the usual way that
$d_{f}(x)\geq 0.0322447,$ as desired. ∎

######  Case 4.

If $x\in X_{4}$ and $w\in X_{2}$, then there are at most

$\left(\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$, and so $d_{f}(x)\geq 0.0349529$.

###### Proof.

In this case, we observe that $xw\in E(G)$. We again determine all
configurations, then partition the potentially induced nets over the number of
additional funky partners of $x$ in the configuration.

First, suppose $xw$ is a triangle-edge. Note that $t_{3}$ must be placed blob-
distance at most 1 from $w$, and that $p_{w}$ cannot be blob-distance 1 from
either $t_{3}$ or its pendant. The implication of this is that $t_{3}\in
X_{2}$, as are $p_{w}$ and the pendant of $t_{3}$. We garner 3 configurations
when $p_{x}\in X_{1}\cup X_{4}\cup X_{6}$ is not a funky partner of $x$,
giving three configurations in which $x$ has precisely 1 funky partner
$(t_{3})$ in $X_{2}$. Alternatively, we garner 2 configurations when $p_{x}\in
X_{2}\cup X_{3}$ is a funky partner of $x$, giving a configuration with two
funky partners chosen in $X_{2}$ or a pair of funky partners chosen in $X_{2}$
and $X_{3}$.

Next, we consider the brief case where $x=p_{w}$. In this case, $w$ is a
triangle vertex in an outer blob and all such configurations involve a non-
funky bull subgraph. As these bull subgraphs are non-funky and contain a
triangle vertex in an outer-blob, all five vertices must be coblobular,
leading to precisely 1 configuration and no additional funky partners.

Finally, we consider the case where $x=t_{w}$, and we consider the placement
of the non-funky $P_{4}$ which does not contain $x$. Observe that if the
$P_{4}$ is coblobular in $X_{4}$, then we have one valid configuration with no
additional funky vertices. If the $P_{4}$ is coblobular in any of $X_{1}$,
$X_{2}$, $X_{3}$ or $X_{6}$, each of these choices corresponds to a valid
configuration with 2 additional funky vertices. The final option is that the
$P_{4}$ is blob-induced in $X_{1}$, $X_{4}$, $X_{6}$ and $X_{3}$, resulting in
precisely 1 configuration and 1 additional funky vertex in $X_{1}$.

We now bound the number of configurations by partitioning over the number of
additional funky vertices. Note that there are two configurations with 0
additional funky partner, giving an upper bound of
$2\binom{x_{\text{max}}n}{4}$. For those configurations containing only 1
additional funky partner, we note that the funky partner must be in $X_{1}$ or
$X_{2}$. Every funky partner in $X_{2}$ contributes at most
$3x_{\text{max}}n\cdot\binom{x_{\text{max}}n}{2}$ nets as $p_{x}$ could be
chosen in 3 different blobs, whereas every funky partner in $X_{1}$ can
contribute at most $(x_{\text{max}}n)^{3}$ nets. As such, the worst-case
scenario is when all funky neighbors of $x$ are in $X_{2}$, and each
contributes the maximum possible number of nets, giving at most
$\frac{3}{2}d_{f}(x)x_{\text{max}}^{3}n^{4}$ nets containing $x$, $w$, and
precisely 1 additional funky partner of $x$.

Lastly, we carefully consider the configurations in which 2 additional funky
partners are used. These configurations involve two funky partners chosen in
$X_{2}$ (and two non-funky partners chosen in $X_{2}$), two funky partners
chosen so that one is in $X_{2}$ and the other is on $X_{3}$ (and two non-
funky partners chosen in $X_{2}$), or two funky partners chosen in one of
$X_{1}$, $X_{2}$, $X_{3}$ or $X_{6}$ (and two non-funky partners chosen from
the same set). The important observation here is gleaned from the
parentheticals: every choice of two funky partners of $x$ produces at most
$\binom{x_{\text{max}}n}{2}$ nets, implying that there are at most
$\binom{x_{\text{max}}n}{2}\binom{d_{f}(x)n}{2}$ nets containing $x$, $w$, and
two additional funky neighbors of $x$. This is potentially achievable when all
funky partners of $x$ are located in $X_{2}\cup X_{3}$ when we disregard the
likelihood of inducing the necessary structures in the blobs.

Our final count gives at most

$\left(\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$, implying that $d_{f}(x)\geq 0.0349529$ in the
usual way. ∎

######  Case 5.

If $x\in X_{4}$ and $w\in X_{5}$, then there are at most

$\left(\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$, and so $d_{f}(x)\geq 0.0504913$.

###### Proof.

Note that $xw\not\in E(G)$. First, we consider the configurations which
contain $w$ as a triangle vertex. Note that in each of these configurations,
$x$ will be a pendant of some other triangle vertex. Further, if a non-funky
$P_{4}$ containing $w$ is blob-induced, then in fact the configuration
contains a blob-induced bull. The two possible configurations are when the
bull does not intersect $X_{3}$ and when the bull does not intersection
$X_{1}$. The former case involves 1 additional funky partner of $x$ located in
$X_{1}$, and the latter involves 1 additional funky partner in $X_{6}$.

Otherwise, the non-funky $P_{4}$ containing $w$ is entirely within $X_{5}$.
When $x$ is a triangle vertex in such a configuration, there is 1 additional
funky partner of $x$ selected in $X_{5}$, the pendant vertex that is neither
$p_{x}$ nor $w$. We can then pick $p_{x}$ as a non-funky partner in $X_{1}\cup
X_{5}$ or as a funky partner in $X_{3}$. When $x$ is a pendant vertex, five
vertices must be chosen in $X_{5}$, 3 of which must be additional funky
partners of $x$.

Note that every configuration in this case involves at least 1 additional
funky partner of $x$. For those configurations involving precisely 1
additional funky partner of $x$, we observe that each choice of funky partner
of $x$ can lead to at most 1 valid configuration:

  * •

if the funky partner is in $X_{1}$, then the configuration must involve a
blob-induced bull which does not intersect $X_{3}$,

  * •

if the funky partner is in $X_{6}$, then the configuration must involve a
blob-induced bull which does not intersect $X_{1}$, and

  * •

if the funky partner is in $X_{5}$, then $x$ is a triangle vertex, the non-
funky $P_{4}$ is contained entirely in $X_{5}$, and $p_{x}\in X_{1}$.

Hence, there are at most $d_{f}(x)x_{\text{max}}^{3}n^{4}$ nets containing
$x$, $w$, and exactly one additional funky partner of $x$. There is only one
configuration which involves exactly 2 additional funky partners, and the
configuration requires a funky partner in each of $X_{3}$ and $X_{5}$. For
every pair $(w^{\prime},w^{\prime\prime})$ of funky partners of $x$ where
$w^{\prime}\in X_{3}$ and $w^{\prime\prime}\in X_{5}$ can produce at most
$\binom{x_{\text{max}}^{2}n}{2}$ nets, and there are at most
$\frac{1}{2}\binom{d_{f}(x)n}{2}$ such pairs, giving at most
$\frac{1}{8}d_{f}(x)^{2}x_{\text{max}}^{2}n^{4}$ nets containing $x$, $w$, and
two additional funky partners of $x$.

Finally, there is one configuration involving precisely 3 additional funky
partners of $x$ and no configurations with 4 additional funky partners, which
gives at most $\binom{d_{f}(x)n}{3}x_{\text{max}}n$ nets containing $x$, $w$,
and at least 3 additional funky partners of $x$ for at most

$\left(\frac{1}{6}x_{0}+\frac{1}{2}d_{f}(x)x_{\text{max}}^{3}+\frac{1}{2}d_{f}(x)^{2}x_{\text{max}}^{2}+\frac{1}{6}d_{f}(x)^{3}x_{\text{max}}\right)n^{4}$

nets containing $x$ and $w$. We then have in the usual way that $d_{f}(x)\geq
0.0504913$ in this case. ∎