Submitted on February 8, 2023. Revised on May 25, 2023. Accepted on June 9,
2023. Published online in June 2023. Editor in charge: Mr Editor.

Author One et al., 2023

# Analysis on the Influence of Synchronization Error on Fixed-filter Active
Noise Control

Guo Yu111Author One affiliation, Brazil<EMAIL_ADDRESS>
###### Abstract

Abstract The efficacy of active noise control technology in mitigating urban
noise, particularly in relation to low-frequency components, has been well-
established. In the realm of traditional academic research, adaptive
algorithms, such as the filtered reference least mean square method, are
extensively employed to achieve real-time noise reduction in many
applications. Nevertheless, the utilization of this technology in commercial
goods is often hindered by its significant computing complexity and inherent
instability. In this particular scenario, the adoption of the fixed-filter
strategy emerges as a viable alternative for addressing these challenges,
albeit with a potential trade-off in terms of noise reduction efficacy. This
work aims to conduct a theoretical investigation into the synchronization
error of the digital Active Noise Control (ANC) system.

Keywords: Fixed-filter, Active noise control, Multichannel active noise
control

1 Brazilian Review of Finance (Online), Rio de Janeiro, Vol. XX, No. Y, August
2023, pp. x–xx ISSN 1679-0731, ISSN online 1984-5146 ©2023 Sociedade
Brasileira de Finanças, under a Creative Commons Attribution 3.0 license
Brazilian Review of Finance (Online) XX(Y), 2023

##  1 Problem statement

Active Noise Control (ANC), also known as active noise cancellation or active
noise reduction, is a technology and technique used to reduce or eliminate
unwanted ambient noise by generating sound waves that are precisely phase-
inverted to the incoming noise [1, 2, 3, 4]. The goal of ANC is to create a
quieter and more comfortable environment for individuals in various settings,
such as homes [5, 6, 7, 8, 9, 10, 11, 12, 13], offices, vehicles, and even
headphones [14, 15, 16, 17, 18, 19, 20, 21]. ANC works on the principle of
superposition of sound waves. When two sound waves with equal amplitude but
opposite phases (180-degree phase difference) are combined, they interfere
destructively, effectively canceling each other out. This means that if you
can create a sound wave that is exactly out of phase with the unwanted noise,
they will cancel each other, resulting in reduced or eliminated noise. ANC
systems are often adaptive, meaning they continuously monitor the incoming
noise and adjust the anti-noise signal in real-time. This adaptation allows
the system to respond to changes in the noise environment, making it effective
in various conditions. Nevertheless, the utilization of adaptive algorithms,
such as those based on the least mean squares (LMS) methodology, often raises
stability concerns. Additionally, the sluggish convergence rate associated
with these algorithms can significantly impact their effectiveness in
effectively handling dynamic noise [22, 23, 24, 25].

In the practical applications, such as in commercial ANC headphones, the
processor initially performs offline estimation of the secondary paths.
Subsequently, the control filters are trained using an adaptive filter
technique. Once the optimal control filters have been obtained, the processor
will cease training and proceed to utilize these filters for the purpose of
filtering the reference signal [26, 27, 28]. By implementing the
aforementioned technique, the ANC system is able to provide effective noise
suppression while solving the system stability issue caused by the adaptive
active control algorithms [29, 30, 31, 32, 33, 34, 35]. The active control
technique referred to as the fixed-filter approach has been extensively
employed in commercial applications and has garnered significant attention in
academic research [36, 37, 38, 39, 40].

The rationale behind the effectiveness of the aforementioned strategy is
readily apparent. The coefficients of optimal filters remain unchanged when
the physical environment and primary noise remain fixed. In a practical
context, the majority of ANC applications fulfill these two criteria. It can
be argued that in a given physical environment, many distinct ANC systems with
identical Analog-to-Digital Converter (ADC), Digital-to-Analog Converter
(DAC), and sampling rates will possess identical optimal control filter
coefficients to effectively address a shared primary noise source. By
extrapolating this assumption, it is possible to utilize a high-cost yet high-
performance processor for training the best control filter. Subsequently, the
obtained coefficients can be implemented on a less expensive but lower-
performance processor to effectively mitigate the primary noise in the
identical physical setting. The less expensive processor just requires the
completion of fixed filters, specifically the Finite Impulse Response (FIR)
with the ideal control filter’s coefficients. This approach eliminates the
requirement for adaptive filters, resulting in a substantial reduction in
computational workload.

Figure 1: The single-channel feedforward ANC system [41].

Nevertheless, the empirical findings of the experiment diverge from this
premise. Regardless of the type of primary noise employed or the specific
physical environment, it is evident that the noise reduction achieved by a
fixed filter is consistently inferior than that of the comparable adaptive
Active Noise Control (ANC) filter. This is due to the oversight of the fact
that two digital hardware configurations, even if they are identical systems
that are powered on at different times, must possess distinct system clocks.
The disparity can be attributed to two distinct components: variations in
frequency and disparities in the early phase of the system clock. The
utilization of several system clocks will result in distinct sample clocks for
the analog-to-digital converter (ADC), thereby significantly impacting the
performance of the fixed filter. In the subsequent study, we designate the
sample clock of the adaptive ANC filter system, which obtains the optimal
control filters, as the reference clock. We refer to the disparity in initial
phase and frequency between the sampling clocks of the fixed filter and
adaptive ANC filter as the initial phase error and frequency error,
respectively.

##  2 The influence of frequency error on fixed filter

To simplify the analysis, we assume the primary noise is a plane wave that
transmits along the x-axis in a free field, and the ANC system is a single-
channel feedforward structure. The reference microphone is at location A, the
original point of the x-axis. The error microphone is located at the B of the
axis, whose distance is l. The pressure of the primary noise is

$p(t,x)=p_{a}e^{j(\omega_{0}t-kx)},$ (1)

In this context, $\omega_{0}$ represents the frequency of the primary noise,
$p_{a}$ denotes the amplitude of the plane wave, and $k$ is defined as
$\frac{\omega_{0}}{c_{0}}$, where $c_{0}$ represents the speed of sound in the
air. The pressure of the primary noise at the reference microphone’s location
is denoted as $p_{a}e^{j(\omega_{0}t)}$, whereas at the error microphone’s
location, it is represented as $p_{a}e^{j(\omega_{0}t-kl)}$, which is referred
to as the disturbance noise.

Figure 2: Block diagram of the ANC system on processor

When the processor gains the optimal control filter, it stops the adaptive
process, and the block diagram of the ANC system on it can be expressed as
Figure 2. The sample period of the Analog-Digital convertor is $T_{s}$, so the
reference signal should be

$\begin{array}[]{l}{x(t)=p(t,0)|_{t=nT_{s}}=p(t,0)\sum_{n=-\infty}^{\infty}\delta(t-nT_{s})}\\\
{\mathrm{\;\;\;\;\;\;\;}=p_{a}\sum_{n=-\infty}^{\infty}e^{j\omega_{0}t}\delta(t-nT_{s})}\end{array}.$
(2)

Its Fourier transform is given by

$X(\omega)=\frac{2\pi
p_{a}}{T_{s}}\sum_{j=-\infty}^{+\infty}\delta(\omega-\omega_{0}-j\frac{2\pi}{T_{s}})$
(3)

The impulse response of the optimal control filter can be expressed as

$g^{o}(t)=\sum_{n=0}^{N-1}w_{n}\delta(t-nT_{s}).$ (4)

The length of the optimal control filter is set to $N$, and its frequency
response is obtained from

$G^{o}(\omega)=\sum_{n=0}^{N-1}w_{n}e^{-j\omega nT_{s}}.$ (5)

To reconstruct the digital signal to the analog signal, we build a
reconstruction filter whose frequency response is obtained from

$H(\omega)=\left\\{\begin{array}[]{c}{T_{s}\mathrm{\;\;\;}0\leq\omega<\frac{\pi}{T_{s}}}\\\
{0\mathrm{\;\;\;}\text{others}}\end{array}\right.$ (6)

As mentioned in the previous assumption, the sound transmits in a free field
and doesn’t have any transmission attenuation. Therefore, the secondary path
only brings some delays to the primary noise. The transfer function of the
secondary path can be described as

$S(\omega)=e^{-j\omega t_{s}}.$ (7)

The anti-noise at the location of the error microphone should be

$c(t,l)=p(t,0)*g(t)*h(t)*s(t){\rm=}p_{a}\sum_{n=0}^{N-1}w_{n}e^{j\omega_{0}(t-nT_{s}{\rm-}t_{s})}.$
(8)

The anti-noise wave can completely cancel the disturbance noise at the
location of the error microphone. So,

$p(t,l)+c(t,l)=0.$ (9)

By substituting (8) to (9), we can derive

$p(t,l)=-p_{a}\sum_{n=0}^{N-1}w_{n}e^{j\omega_{0}(t-nT_{s}{\rm-}t_{s})}.$ (10)

Figure 3: Reference sampling clock vs error sampling clock

When we reload the coefficients of the control filter into new digital
hardware, the system clocks of these systems probably have a slight difference
in frequency, even if they use the frequency sources with the same rate
frequency output. The different system clocks must trigger them to own
different sampling clocks. As Figure 3 shows, A denotes the reference sampling
clock of the digital system shown in Figure 2, and B represents the error
sampling clock of another system with the same control filter and hardware as
the previous one but a different system clock. $\mathrm{\nabla}t$ is the
difference between the reference and error sampling clock. The primary noise
sampled by the error sampling clock will bring in some error. Then, the new
reference signal can be written as

$\begin{split}x^{\prime}(t)&=p(t,0)|_{t=n(T_{s}+\nabla
t)}=x_{a}(t)\sum_{n=-\infty}^{\infty}\delta(t-nT_{s}-n\nabla t)\\\
&=p_{a}\sum_{n=-\infty}^{\infty}e^{j\omega_{0}t}\delta(t-nT_{s}-n\nabla
t).\end{split}$ (11)

Its Fourier transform is given by

$X^{{}^{\prime}}(\omega)=\frac{2\pi p_{a}}{T_{s}+\nabla
t}\sum_{j=-\infty}^{+\infty}\delta(\omega-\omega_{0}-j\frac{2\pi}{T_{s}+\nabla
t}).$ (12)

Due to the optimal control filter using the same error sampling clock, its
impulse response will also change to be

$g^{o}{}^{{}^{\prime}}(n)=\sum_{n=0}^{N-1}w_{n}\delta(t-nT_{s}-n\nabla t),$
(13)

whose frequency response is given by

$G^{o}{}^{{}^{\prime}}(\omega)=\sum_{n=0}^{N-1}w_{n}e^{-j\omega
n(T_{s}{\rm+}\nabla t)}.$ (14)

To reconstruct the digital signal to its analog signal, we build the
reconstruction filter as

$H^{\prime}(\omega)=\left\\{\begin{array}[]{c}{T_{s}+\nabla
t\mathrm{\;\;\;\;\;\;}0\leq\omega<\frac{\pi}{T_{s}+\nabla t}}\\\
{0\mathrm{\;\;\;\;\;\;\;\;\;\;\;\;\;\;}\text{others}}\end{array}\right.$ (15)

Hence, the new anti-noise is obtained from

$c^{\prime}(t,l)=x^{\prime}(t)*g^{o}{}^{{}^{\prime}}(t)*h(t)*s(t)=p_{a}\sum_{n=0}^{N-1}w_{n}e^{j\omega_{0}[t-n(T_{s}+\nabla
t){\rm-}t_{s}]},$ (16)

and the pressure on the error microphone is stated to be

$e(t)=p(t,l)+c^{\prime}(t,l)=w_{1}p_{a}e^{j\omega_{0}(t-T_{s})}(e^{j\omega_{0}\nabla
t}-1).$ (17)

The magnitude of the error signal is represented as

$||e(t)||_{2}=2w_{1}^{2}p_{a}^{2}[1-\cos(\omega_{0}\nabla t)].$ (18)

Based on the Nyquist principle

$\left\\{\begin{array}[]{c}{\frac{1}{T_{s}}>\frac{\omega_{0}}{\pi}}\\\
{\frac{1}{T_{s}+\nabla t}>\frac{\omega_{0}}{\pi}}\end{array}\right.$ (19)

we can figure out $-\pi<{\omega}_{0}\mathrm{\nabla}t<\pi$. From the equation
(18) and (19), we can know when $\mathrm{\nabla}\mathrm{t}$ equals to 0, the
anti-noise can counterbalance to the effect of disturbance noise. But
$\mathrm{|}\mathrm{\nabla}\mathrm{t|}$ increase, the pressure of residual
sound at the error microphone will also increase.

##  3 The influence of initial phase error

With the advancement of new technologies, numerous frequency sources with high
output frequency accuracy have emerged. These sources are extensively utilized
in high-precision digital systems. An exemplary illustration is the atomic
oscillator. A collective of atomic oscillators has the ability to generate a
frequency that is the same across all members. The underlying premise is
straightforward: Given the uniformity of atoms inside a given element, their
absorption or emission of energy should result in similar frequencies. Hence,
in the event that both digital systems employ the same atomic oscillator, they
have the potential to obtain an equivalent frequency.

Figure 4: Reference sampling clock and error sampling clock with different
initial phase

Nevertheless, it is essential to acknowledge that a digital system may exhibit
varying initial phases of system clocks depending on the moment it is powered.
The occurrence of an initial phase error in the initial phase will also result
in a comparable initial phase error in the sampling clock. The phenomena are
illustrated in Figure 4. The depicted image shows the reference sampling
clock, denoted by A, and the error sampling clock, represented by B. The A and
B sampling clocks exhibit identical frequencies but with distinct beginning
phases. The symbol $\mathrm{\nabla}\theta$ represents the initial phase
difference, referred to as the initial phase error.

###  3.1 Narrow Band Primary Noise

In general situations, $\mathrm{\nabla}\theta$ the same sampling clock causes
triggered at different times. In our application, $\mathrm{\nabla}\theta$
comes from the different beginnings of adaptive filter sampling clock and
fixed filter sampling clock. Based on experience, this initial phase error
should belong to a uniform disturbance. Its probability density function is

$P(\nabla\theta)=\left\\{\begin{array}[]{c}{\frac{1}{2\pi}\mathrm{\;\;\;}\nabla\theta\in\left[0,2\pi\right]}\\\
{0\mathrm{\;\;\;}\nabla\theta\notin\left[0,2\pi\right]}\end{array}\right.$
(20)

Because of the affection of this initial phase error, the sampled reference
signal will also change to

$\begin{split}x^{\prime\prime}(t)&=p(t,0)|_{t=nT_{s}+\frac{\nabla\theta}{2\pi}T_{s}}=x_{a}(t)\sum_{n=-\infty}^{\infty}\delta(t-nT_{s}-\frac{\nabla\theta}{2\pi}T_{s})\\\
&=p_{a}\sum_{n=-\infty}^{\infty}e^{j\omega_{0}t}\delta(t-nT_{s}-\frac{\nabla\theta}{2\pi}T_{s}).\end{split}$
(21)

From the above equation, we can figure out that the initial phase error brings
a constant delay for sampling impulses. The equation (21) can also be written
as

$x^{\prime\prime}(t)=p_{a}\sum_{n=-\infty}^{\infty}e^{j\omega_{0}(t+\frac{\nabla\theta}{2\pi}T_{s})}\delta(t-nT_{s}).$
(22)

In this equation, the initial phase error just makes the analog reference
signal have a time shift. Therefore, the implementation of anti-noise
technology should be considered to be

$c^{\prime\prime}(t,l)=x^{\prime\prime}(t)*g(t)*h(t)*s(t)=p_{a}\sum_{n=0}^{N-1}w_{n}e^{j\omega_{0}(t-nT_{s}+\frac{\nabla\theta}{2\pi}T_{s}{\rm-}t_{s})}.$
(23)

Therefore, the error (we call it residual error) brought by the initial phase
error at noise reduction can be expressed as

$e(\nabla\theta)=E\\{[p(t,l)+c^{\prime\prime}(t,l)]^{2}\\}-E\\{[p(t,l)+c(t,l)]^{2}\\}.$
(24)

The equation can rewritten as

$e(\nabla\theta)=E\\{p(t,l)^{2}\\}E\\{2-2\cos\frac{\omega_{0}}{\omega_{s}}\nabla\theta\\}$
(25)

This equation shows if the initial error is 0, the primary noise can be
completely canceled at the location of the error microphone. Due to
$\mathrm{\nabla}\theta$ is a uniform distributed random variable, the equation
(25) can be furtherly derived as

$e(\nabla\theta)=2E\\{p(t,l)^{2}\\}(1-\frac{\sin\frac{\omega_{0}\pi}{\omega_{s}}}{\frac{\omega_{0}\pi}{\omega_{s}}}).$
(26)

In the equation (26), ${\omega}_{s}$ is the sampling frequency. The curve of
equation (26) is plotted in Figure 5.

Figure 5: Residual Error vs the frequency of the reference signal

From Figure 5, we can figure out that the residual error will increase with
the reference signal frequency compared. In other words, the initial phase
error has more considerable influence on tonal noise with higher frequency
than low frequency.

###  3.2 Broad band primary noise

To analyze the initial phase noise on a single-channel ANC system when it
works on broadband noise, we set the primary noise as a chirp signal (Linear
Frequency Modulation) as

$p^{\prime}(t,x)=p_{a}e^{j[\pi mt^{2}-k(t)x]},$ (27)
$k(t)=\sqrt{\frac{4m^{2}t^{2}+2m}{c_{0}^{2}}},$ (28) $m=\frac{B}{T_{L}}.$ (29)

In the equation, B and $T_{L}$ are the bandwidth and period of the LFM signal,
respectively. Hence, the sound pressure of primary noise at the reference
microphone is given by

$p^{\prime}(t,0)=p_{a}e^{j\pi mt^{2}}.$ (30)

The reference signal sampled by the error sampling clock should be

$x^{\prime\prime\prime}(t)=p_{a}\sum_{n=-\infty}^{\infty}e^{j\pi
m(t+\frac{\nabla\theta}{2\pi}T_{s})^{2}}\delta(t-nT_{s}).$ (31)

Furthermore, we assume the optimal control filter just brings in the delay to
the input signal and changes the amplitude to negative. Therefore, the anti-
noise should be

$c^{\prime\prime\prime}(t,l)=x(t)*g^{o}(t)*h(t)*s(t)=-p_{a}e^{j\pi
m(t+\frac{\nabla\theta}{2\pi}T_{s}-t_{c}-t_{s})^{2}}.$ (32)

The disturbance noise at the error microphone should be

$p_{d}(t,l)=p_{a}e^{j\pi m(t-t_{c}-t_{s})^{2}}.$ (33)

The square of residual error at the location of the error microphone is
derived as

$e^{2}(t)=2p_{a}^{2}\\{1-\cos[2\pi
m(t-t_{c}-t_{s})\frac{\nabla\theta}{2\pi}T_{s}+\pi
m(\frac{\nabla\theta}{2\pi}T_{s})^{2}]\\}$ (34)

From the equation, we can know the $\mathrm{\nabla}\theta$ will also cause the
worst noise reduction. When the $\mathrm{\nabla}\theta$ is the zeros, the
primary noise can be completely canceled. If we substitute the equation (29)
to (34), we can get

$e^{2}(t)=2p_{a}^{2}\\{1-\cos\\{\frac{B}{T_{L}}\times[2\pi(t-t_{c}-t_{s})\frac{\nabla\theta}{2\pi}T_{s}+\pi(\frac{\nabla\theta}{2\pi}T_{s})^{2}]\\}\\}.$
(35)

When the $T_{L}$ is big enough, the $e^{2}(t)$ is close to 0. From the above
two analyses, we know the initial phase error has little affection for the
reference signal over a long period.

###  3.3 Narrow band primary noise in the Multi-channel ANC system

Figure 6: Block diagram of the multichannel ANC system

The block diagram of the multichannel ANC [42, 43, 44, 45, 46, 47, 48], which
works with the optimal control filter, is shown in Figure 6. The primary noise
is a sine tone whose frequency is ${\omega}_{0}$. The sampled reference signal
vector can be described as

$\bm{\mathrm{X}}(\omega)=[X_{0}(\omega),X_{1}(\omega),\ldots,X_{j}(\omega)]^{T}.$
(36)

When the sampling clock brings in the initial phase error, the sampled
reference signal vector is given by

$\bm{\mathrm{X}}^{{}^{\prime}}(\omega)=e^{j\omega_{0}\frac{\nabla\theta}{2\pi}T}[X_{0}(\omega),X_{1}(\omega),\ldots,X_{j}(\omega)]^{T}.$
(37)

The signal picked up by the error microphone is represented as

$\bm{\mathrm{e}}(t)=\bm{\mathrm{d}}(t)-e^{j\omega_{0}\frac{\nabla\theta}{2\pi}T}Fourier^{-1}\\{\bm{\mathrm{S}}(\omega)\bm{\mathrm{H}}(\omega)\bm{\mathrm{G}}(\omega)\bm{\mathrm{X}}(\omega)\\}$
(38)

We assume the anti-noise can completely cancel the primary noise without the
influence of the error sampling clock. Hence,

$\bm{\mathrm{d}}(t)-Fourier^{-1}\\{\bm{\mathrm{S}}(\omega)\bm{\mathrm{H}}(\omega)\bm{\mathrm{G}}(\omega)\bm{\mathrm{X}}(\omega)\\}=\bm{\mathrm{0}}.$
(39)

By substituting the equation (39) into (38), we can get

$\bm{\mathrm{e}}(t)=\bm{\mathrm{d}}(t)(1-e^{j\omega_{0}\frac{\nabla\theta}{2\pi}T}).$
(40)

The exception of the squared equation of (40) is obtained from

$E\\{e^{2}(t)\\}=E\\{d^{2}(t)\\}(1-\frac{\sin\frac{\omega_{0}\pi}{\omega_{s}}}{\frac{\omega_{0}\pi}{\omega_{s}}}).$
(41)

The outcome is comparable to that of single-channel active noise control (ANC)
when the frequency of the reference noise is low, as the initial phase error
has a diminished impact on the effectiveness of noise reduction.

## References

  * [1] D. Shi, B. Lam, W.-S. Gan, and J. Cheer, “Active noise control in the new century: The role and prospect of signal processing,” arXiv preprint arXiv:2306.01425, 2023.
  * [2] C. N. Hansen, Understanding active noise cancellation.  CRC Press, 2002.
  * [3] S. J. Elliott and P. A. Nelson, “Active noise control,” IEEE signal processing magazine, vol. 10, no. 4, pp. 12–35, 1993.
  * [4] S. M. Kuo and D. R. Morgan, “Active noise control: a tutorial review,” Proceedings of the IEEE, vol. 87, no. 6, pp. 943–973, 1999.
  * [5] B. Lam, D. Shi, V. Belyi, S. Wen, W.-S. Gan, K. Li, and I. Lee, “Active control of low-frequency noise through a single top-hung window in a full-sized room,” Applied Sciences, vol. 10, no. 19, p. 6817, 2020.
  * [6] B. Lam, D. Shi, W.-S. Gan, S. J. Elliott, and M. Nishimura, “Active control of broadband sound through the open aperture of a full-sized domestic window,” Scientific reports, vol. 10, no. 1, pp. 1–7, 2020.
  * [7] D. Shi, B. Lam, J. Ji, X. Shen, C. K. Lai, and W.-S. Gan, “Computation-efficient solution for fully-connected active noise control window: Analysis and implementation of multichannel adjoint least mean square algorithm,” Mechanical Systems and Signal Processing, vol. 199, p. 110444, 2023.
  * [8] R. Hasegawa, D.-Y. Shi, Y. Kajikawa, and W.-S. Gan, “Multi-channel anc window with virtual sensing technique,” IEICE Technical Report; IEICE Tech. Rep., vol. 118, no. 496, pp. 69–74, 2019.
  * [9] J. He, B. Lam, D. Shi, and W. S. Gan, “Exploiting the underdetermined system in multichannel active noise control for open windows,” Applied Sciences, vol. 9, no. 3, p. 390, 2019.
  * [10] R. Hasegawa, D. Shi, Y. Kajikawa, and W.-S. Gan, “Window active noise control system with virtual sensing technique,” in INTER-NOISE and NOISE-CON Congress and Conference Proceedings, vol. 258, pp. 6004–6012, Institute of Noise Control Engineering, 2018.
  * [11] B. Lam, C. Shi, D. Shi, and W.-S. Gan, “Active control of sound through full-sized open windows,” Building and Environment, vol. 141, pp. 16–27, 2018.
  * [12] C. Shi, N. Jiang, H. Li, D. Shi, and W.-S. Gan, “On algorithms and implementations of a 4-channel active noise canceling window,” in 2017 International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS), pp. 217–221, IEEE, 2017.
  * [13] B. Lam, K. C. Q. Lim, K. Ooi, Z.-T. Ong, D. Shi, and W.-S. Gan, “Anti-noise window: Subjective perception of active noise reduction and effect of informational masking,” Sustainable Cities and Society, vol. 97, p. 104763, 2023.
  * [14] X. Shen, D. Shi, S. Peksi, and W.-S. Gan, “Implementations of wireless active noise control in the headrest,” in INTER-NOISE and NOISE-CON Congress and Conference Proceedings, vol. 265, pp. 3445–3455, Institute of Noise Control Engineering, 2023.
  * [15] X. Shen, W.-S. Gan, and D. Shi, “Multi-channel wireless hybrid active noise control with fixed-adaptive control selection,” Journal of Sound and Vibration, vol. 541, p. 117300, 2022.
  * [16] X. Shen, D. Shi, S. Peksi, and W.-S. Gan, “A multi-channel wireless active noise control headphone with coherence-based weight determination algorithm,” Journal of Signal Processing Systems, vol. 94, no. 8, pp. 811–819, 2022.
  * [17] X. Shen, D. Shi, and W.-S. Gan, “A hybrid approach to combine wireless and earcup microphones for anc headphones with error separation module,” in ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8702–8706, IEEE, 2022.
  * [18] X. Shen, D. Shi, W.-S. Gan, and S. Peksi, “Adaptive-gain algorithm on the fixed filters applied for active noise control headphone,” Mechanical Systems and Signal Processing, vol. 169, p. 108641, 2022.
  * [19] X. Shen, D. Shi, W.-S. Gan, and S. Peksi, “Implementation of coherence-based-selection multi-channel wireless active noise control in headphone,” in INTER-NOISE and NOISE-CON Congress and Conference Proceedings, vol. 263, pp. 1945–1953, Institute of Noise Control Engineering, 2021.
  * [20] X. Shen, D. Shi, and W.-S. Gan, “A wireless reference active noise control headphone using coherence based selection technique,” in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7983–7987, IEEE, 2021.
  * [21] X. Shen, W.-S. Gan, and D. Shi, “Alternative switching hybrid anc,” Applied Acoustics, vol. 173, p. 107712, 2021.
  * [22] S. Wen, W.-S. Gan, and D. Shi, “Convergence behavior analysis of fxlms algorithm with different leaky term,” in INTER-NOISE and NOISE-CON Congress and Conference Proceedings, vol. 261, pp. 728–739, Institute of Noise Control Engineering, 2020.
  * [23] B. Lam, W.-S. Gan, D. Shi, M. Nishimura, and S. Elliott, “Ten questions concerning active noise control in the built environment,” Building and Environment, vol. 200, p. 107928, 2021.
  * [24] D. Shi, W.-S. Gan, B. Lam, and K. Ooi, “Fast adaptive active noise control based on modified model-agnostic meta-learning algorithm,” IEEE Signal Processing Letters, vol. 28, pp. 593–597, 2021.
  * [25] D. Shi, W.-S. Gan, B. Lam, S. Wen, and X. Shen, “Active noise control based on the momentum multichannel normalized filtered-x least mean square algorithm,” in INTER-NOISE and NOISE-CON Congress and Conference Proceedings, vol. 261, pp. 709–719, Institute of Noise Control Engineering, 2020.
  * [26] D. Shi, W.-S. Gan, B. Lam, and S. Wen, “Feedforward selective fixed-filter active noise control: Algorithm and implementation,” IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 28, pp. 1479–1492, 2020.
  * [27] D. Y. Shi, B. Lam, and W.-S. Gan, “A novel selective active noise control algorithm to overcome practical implementation issue,” in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1130–1134, IEEE, 2018.
  * [28] S. Wen, W.-S. Gan, and D. Shi, “Using empirical wavelet transform to speed up selective filtered active noise control system,” The Journal of the Acoustical Society of America, vol. 147, no. 5, pp. 3490–3501, 2020.
  * [29] D. Shi, C. Shi, and W.-S. Gan, “Effect of the audio amplifier’s distortion on feedforward active noise control,” in 2017 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pp. 469–473, IEEE, 2017.
  * [30] D. Shi, W.-S. Gan, B. Lam, S. Wen, and X. Shen, “Optimal output-constrained active noise control based on inverse adaptive modeling leak factor estimate,” IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 29, pp. 1256–1269, 2021.
  * [31] D. Shi, W.-S. Gan, B. Lam, and C. Shi, “Two-gradient direction fxlms: An adaptive active noise control algorithm with output constraint,” Mechanical Systems and Signal Processing, vol. 116, pp. 651–667, 2019.
  * [32] D. Shi, B. Lam, W.-S. Gan, and S. Wen, “Optimal leak factor selection for the output-constrained leaky filtered-input least mean square algorithm,” IEEE Signal Processing Letters, vol. 26, no. 5, pp. 670–674, 2019.
  * [33] D. Shi, W.-S. Gan, B. Lam, and X. Shen, “Optimal penalty factor for the mov-fxlms algorithm in active noise control system,” IEEE Signal Processing Letters, vol. 29, pp. 85–89, 2021.
  * [34] D. Shi, W.-S. Gan, B. Lam, and X. Shen, “A frequency-domain output-constrained active noise control algorithm based on an intuitive circulant convolutional penalty factor,” IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 31, pp. 1318–1332, 2023.
  * [35] C. K. Lai, D. Shi, B. Lam, and W.-S. Gan, “Mov-modified-fxlms algorithm with variable penalty factor in a practical power output constrained active control system,” IEEE Signal Processing Letters, 2023.
  * [36] D. Shi, B. Lam, K. Ooi, X. Shen, and W.-S. Gan, “Selective fixed-filter active noise control based on convolutional neural network,” Signal Processing, vol. 190, p. 108317, 2022.
  * [37] Z. Luo, D. Shi, X. Shen, J. Ji, and W.-S. Gan, “Deep generative fixed-filter active noise control,” in ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1–5, IEEE, 2023.
  * [38] D. Shi, W.-S. Gan, B. Lam, Z. Luo, and X. Shen, “Transferable latent of cnn-based selective fixed-filter active noise control,” IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2023.
  * [39] Z. Luo, D. Shi, W.-S. Gan, Q. Huang, and L. Zhang, “Performance evaluation of selective fixed-filter active noise control based on different convolutional neural networks,” in INTER-NOISE and NOISE-CON Congress and Conference Proceedings, vol. 265, pp. 1615–1622, Institute of Noise Control Engineering, 2023.
  * [40] Z. Luo, D. Shi, and W.-S. Gan, “A hybrid sfanc-fxnlms algorithm for active noise control based on deep learning,” IEEE Signal Processing Letters, vol. 29, pp. 1102–1106, 2022.
  * [41] D. Shi, “Algorithms and implementations to overcome practical issues in active noise control systems,” 2020.
  * [42] D. Shi, B. Lam, X. Shen, and W.-S. Gan, “Multichannel two-gradient direction filtered reference least mean square algorithm for output-constrained multichannel active noise control,” Signal Processing, vol. 207, p. 108938, 2023.
  * [43] Z. Luo, D. Shi, J. Ji, and W.-s. Gan, “Implementation of multi-channel active noise control based on back-propagation mechanism,” arXiv preprint arXiv:2208.08086, 2022.
  * [44] D. Shi, B. Lam, W.-S. Gan, and S. Wen, “Block coordinate descent based algorithm for computational complexity reduction in multichannel active noise control system,” Mechanical Systems and Signal Processing, vol. 151, p. 107346, 2021.
  * [45] D. Shi, B. Lam, S. Wen, and W.-S. Gan, “Multichannel active noise control with spatial derivative constraints to enlarge the quiet zone,” in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8419–8423, IEEE, 2020.
  * [46] D. Shi, W.-S. Gan, J. He, and B. Lam, “Practical implementation of multichannel filtered-x least mean square algorithm based on the multiple-parallel-branch with folding architecture for large-scale active noise control,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 28, no. 4, pp. 940–953, 2019.
  * [47] C. Shi, H. Li, D. Shi, B. Lam, and W.-S. Gan, “Understanding multiple-input multiple-output active noise control from a perspective of sampling and reconstruction,” in 2017 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pp. 124–129, IEEE, 2017.
  * [48] D. Shi, J. He, C. Shi, T. Murao, and W.-S. Gan, “Multiple parallel branch with folding architecture for multichannel filtered-x least mean square algorithm,” in 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1188–1192, IEEE, 2017.


# Inducibility in the hypercube

John Goldwasser† †West Virginia University<EMAIL_ADDRESS>and  Ryan
Hansen†<EMAIL_ADDRESS>
###### Abstract.

Let $Q_{d}$ be the hypercube of dimension $d$ and let $H$ and $K$ be subsets
of the vertex set $V(Q_{d})$, called configurations in $Q_{d}$. We say that
$K$ is an _exact copy_ of $H$ if there is an automorphism of $Q_{d}$ which
sends $H$ onto $K$. Let $n\geq d$ be an integer, let $H$ be a configuration in
$Q_{d}$ and let $S$ be a configuration in $Q_{n}$. We let
$\operatorname{\mathit{\lambda}}(H,d,n)$ be the maximum, over all
configurations $S$ in $Q_{n}$, of the fraction of sub-$d$-cubes $R$ of $Q_{n}$
in which $S\cap R$ is an exact copy of $H$, and we define the $d$-cube density
$\lambda(H,d)$ of $H$ to be the limit as $n$ goes to infinity of
$\operatorname{\mathit{\lambda}}(H,d,n)$. We determine $\lambda(H,d)$ for
several configurations in $Q_{3}$ and $Q_{4}$ as well as for an infinite
family of configurations. There are strong connections with the inducibility
of graphs.

##  1\. Introduction

The $n$-cube, which we denote by $Q_{n}$, is the graph whose vertex set
$V_{n}=V(Q_{n})$ is the set of all binary $n$-tuples, with two vertices
adjacent if and only if they differ in precisely one coordinate (so Hamming
distance 1). Let $[n]=\left\\{1,2,\ldots,n\right\\}$. We sometimes denote a
vertex $(x_{1},x_{2},\ldots,x_{n})$ of $Q_{n}$ by the subset $S$ of $[n]$ such
that $i\in S$ if and only if $x_{i}=1$. So if $n=4$, then $\emptyset$ denotes
$(0000)$, and $\left\\{1,3\right\\}$ or 13, denotes $(1010)$ and
$\left\\{\left\\{1\right\\},\left\\{1,3\right\\}\right\\}$ (or
$\left\\{1,13\right\\}$) denotes $\left\\{(1000),(1010)\right\\}$. The weight
of a vertex is the number of 1s. For each positive integer $d$ less than or
equal to $n$, $Q_{n}$ has $\binom{n}{d}2^{n-d}$ subgraphs which are isomorphic
to $Q_{d}$ ($d$ coordinates can vary, while $n-d$ coordinates are fixed). We
sometimes refer to each of the $d$ coordinates that can vary as a _flip bit_.
A single flip bit determines an edge while a set of $d$ flip bits, with the
other $n-d$ coordinates fixed, determines a particular sub-$d$-cube.

Let $H$ and $K$ be subsets of $V_{d}$ (we call $H$ and $K$ configurations in
$Q_{d}$). We say $K$ is an _exact copy_ of $H$ if there is an automorphism of
$Q_{d}$ which sends $H$ onto $K$. For example, $\left\\{\emptyset,12\right\\}$
is an exact copy of $\left\\{2,123\right\\}$ in $Q_{3}$, but
$\left\\{2,13\right\\}$ is not (the vertices are distance 3 apart). So if $K$
is an exact copy of $H$ then they induce isomorphic subgraphs of $Q_{d}$, but
the converse may not hold.

Let $d$ and $n$ be positive integers with $d\leq n$, let $H$ be a
configuration in $Q_{d}$ and let $S$ be a configuration in $Q_{n}$. We let
$G(H,d,n,S)$ denote the number of sub-$d$-cubes $R$ of $Q_{n}$ in which $S\cap
R$ is an exact copy of $H$ and define $g(H,d,n,S)$ by

$g(H,d,n,s)=\frac{G(H,d,n,S)}{\binom{n}{d}2^{n-d}}$

So $g(H,d,n,S)$ is the fraction of all sub-$d$-cubes whose intersection with
$S$ is an exact copy of $H$. We define
$\operatorname{\mathit{\lambda}}(H,d,n)$ to be the maximum of $g(H,d,n,S)$
over all configurations $S$ in $Q_{n}$. Note that $\lambda(H,d,n)$ is the
average of $2n$ densities $g(H,d,n-1,S_{j})$, each of them the fraction of
sub-$d$-cubes $R$ in a sub-$(n-1)$-cube of $Q_{n}$ in which $R\cap S_{j}$ is
an exact copy of $H$, where $S_{j}$ is the intersection of a maximizing
configuration in $Q_{n}$ with one of the $2n$ sub-$(n-1)$-cubes. Hence
$\operatorname{\mathit{\lambda}}(H,d,n)$ is the average of $2n$ densities,
each of them less than or equal to $\operatorname{\mathit{\lambda}}(H,d,n-1)$,
which means $\operatorname{\mathit{\lambda}}(H,d,n)$ is a nonincreasing
function of $n$, so we can define the $d$-cube density $\lambda(H,d)$ of $H$
by

$\operatorname{\mathit{\lambda}}(H,d)=\lim_{n\to\infty}\operatorname{\mathit{\lambda}}(H,d,n).$

So $\lambda(H,d)$ is the limit as $n$ goes to infinity of the maximum
fraction, over all $S\subseteq V_{n}$, of “good” sub-$d$-cubes – those whose
intersection with $S$ is an exact copy of $H$.

In [14] we initiated the investigation of $d$-cube-density. There have been
many papers on Turán and Ramsey type problems in the hypercube. There has been
extensive research on the minimum fraction of edges in $Q_{n}$ one can take
with no cycle of various lengths [8, 10, 13, 23] and a few papers on vertex
Turán problems in $Q_{n}$ [21, 19, 20]. There has also been extensive work on
which monochromatic cycles must appear in any edge coloring of a large
hypercube with a fixed number of colors [3, 4, 8, 9] and a few resultls on
which vertex structures must appear [16]. In [2] and [15], results were
obtained on _polychromatic colorings_ of $Q_{n}$. These are edge colorings
with $p$ colors such that every sub-$d$-cube contains every color.

We wanted to investigate a different extremal probelm in the hypercube: the
maximum density of a certain kind of sub-structure. Instead of using graph
isomorphism to determine if two substructures are the same, it seemed to
capture the essence of the $n$-cube better if the small structures were
“rigid” within a sub-$d$-cube, and that is what motivated our definitions of
exact copy of a configuration and $d$-cube density. While $d$-cube density is
not the same thing as graph inducibility, there are similarities between the
two notions and, in fact, we use several results on inducibility (see Section
4) in our proofs.

In [14] we used a kind of _blow–up_ to show that
$\lambda(H,d)\geq\frac{d!}{d^{d}}$ for every configuration $H$ in $Q_{d}$. We
defined a perfect $2d$-cycle $C_{2d}$ in $Q_{d}$ to be a cycle with $d$ pairs
of vertices each Hamming distance $d$ apart. We showed that
$\lambda(C_{8},4)=\frac{4!}{4^{4}}$, achieving the smallest possible value for
any configuration in $Q_{4}$. We also showed $\lambda(P_{4},3)=\frac{3}{8}$
where $P_{4}$ is the induced path in $Q_{3}$ with 4 vertices.

Finding $d$-cube density seems to be very difficult even for most small
configurations. In this paper we find the $d$-cube density for three
configurations in $Q_{3}$, two configurations in $Q_{4}$, and for an infinite
family of configurations, $d-1$ of them in $Q_{d}$ for each $d\geq 2$. We find
a construction to produce a lower bound and then find a matching upper bound
by using known results on the inducibility of small graphs to show the local
density cannot be larger. For all configurations in $Q_{2}$ and $Q_{3}$ for
which we could not determine the $d$-cube density, we give a construction to
produce a lower bound and give an upper bound computed by Rahil Baber [5]
using flag algebras.

In Section 2 we define local $d$-cube density, the notion we use to find the
upper bounds. In Section 3 we consider the possible configurations in $Q_{2}$.
In Section 4 we summarize the results on inducibility of graphs which we will
need. In Section 5 we discuss _layered_ configurations in $Q_{d}$, those that
are defined in terms of the weights of the $d$-vectors. In Section 6 we find
$d$-cube density for a nontrivial infinite family of configurations. In
Section 7 we consider $d$-cube density for configurations in $Q_{3}$, and in
Section 8 we determine the $d$-cube density for two configurations in $Q_{4}$.
In Section 9 we discuss some open problems and state some conjectures.

##  2\. Local $d$-cube density

Let $H$ be a configuration in $Q_{d}$ and $S$ be a a configuration in $Q_{n}$.
For each vertex $v\in S$, we let $\operatorname{\mathit{G}_{v({\rm
in})}}(H,d,n,S)$ be the number of sub-$d$-cubes $R$ of $Q_{n}$ containing $v$
in which $S\cap R$ is an exact copy of $H$ and
$\operatorname{\mathit{g}_{v({\rm
in})}}(H,d,n,S)=\frac{\operatorname{\mathit{G}_{v({\rm
in})}}(H,d,n,S)}{\binom{n}{d}}$. So $\operatorname{\mathit{g}_{v({\rm
in})}}(H,d,n,S)$ is the fraction of sub-$d$-cubes containing $v$ which have an
exact copy of $H$. We define $\operatorname{\mathit{\lambda}_{\rm
local(in)}}(H,d,n)$ to be the maximum of $\operatorname{\mathit{g}_{v({\rm
in})}}(H,d,n,S)$ over all $v$ and $S$ where $v\in S\subseteq V_{n}$. As with
$\operatorname{\mathit{\lambda}}(H,d,n)$, a simple averaging argument shows
that $\operatorname{\mathit{\lambda}_{\rm local(in)}}(H,d,n)$ is a
nonincreasing function of $n$, so we define
$\operatorname{\mathit{\lambda}_{\rm local(in)}}(H,d)$ by

$\operatorname{\mathit{\lambda}_{\rm
local(in)}}(H,d)=\lim_{n\to\infty}\operatorname{\mathit{\lambda}_{\rm
local(in)}}(H,d,n)$

For each $v\not\in S$, we perform a similar procedure to define
$\operatorname{\mathit{G}_{v({\rm out})}}(H,d,n,S)$,
$\operatorname{\mathit{g}_{v({\rm out})}}(H,d,n,S)$, and
$\operatorname{\mathit{\lambda}_{\rm local(out)}}(H,d)$. So
$\operatorname{\mathit{\lambda}_{\rm local(in)}}(H,d)$ and
$\operatorname{\mathit{\lambda}_{\rm local(out)}}(H,d)$ are the maximum local
densities of sub-$d$-cubes with an exact copy of $H$ among all sub-$d$-cubes
containing $v$ in $S$ and out of $S$ respectively. Finally, we define
$\operatorname{\mathit{\lambda}_{\rm local}}(H,d)$ to be
$\max\\{\operatorname{\mathit{\lambda}_{\rm
local(in)}}(H,d),\operatorname{\mathit{\lambda}_{\rm local(out)}}(H,d)\\}$.
Since the global density cannot be more than the maximum local density, we
must have $\lambda(H,d)\leq\operatorname{\mathit{\lambda}_{\rm local}}(H,d)$.

We refer to the following type of construction as a _partition-modular
construction_. These are constructions generated by choosing a partition of
$[n]=A_{1}\cup A_{2}\cup\cdots\cup A_{i}$ and taking as $S$ the set of
vertices such that their binary $n$-tuples satisfy a chosen set of congruences
for the weight of the coordinates within the parts. Sometimes we denote this
as a list of $i$-tuples along with a list of their moduli for convenience. For
example, the partition $A_{1}\cup A_{2}$ taking 01 mod $(2,2)$ would indicate
the partition $[n]=A_{1}\cup A_{2}$ with $S$ being all vertices with weight 0
mod 2 in $A_{1}$ and weight 1 mod 2 in $A_{2}$. The fractional sizes of the
$A_{i}$ which maximize the number of $Q_{d}$s having the configuration may
also be indicated.

Note that the sets in the partition may be of any sizes, however, when $i=1$
we call such a configuration _layered_ since it is equivalent to choosing all
vertices of particular weights modulo $a$ (i.e. entire “levels” of $Q_{n}$).

##  3\. Configurations in $Q_{2}$

It is obvious that $\lambda(H,d)=\lambda\left(\overline{H},d\right)$ where
$\overline{H}$ is the complement of the configuration $H$ in $Q_{d}$, so we
may restrict our consideration to only one configuration in each of the
complementary pairs.

Sketches of all of the configurations in $Q_{2}$, subject to the above
restriction, are given in Figure 1. In the figure, red vertices are in the
configuration and open blue are not. The edges have been added for emphasis,
but configurations are sets of vertices.

$Z_{1}$$Z_{2}$$Z_{3}$$Z_{4}$ Figure 1. Configurations in $Q_{2}$.

###  3.1. Lower Bounds by Construction

Clearly $\lambda(Z_{1},2)=1$, since we would simply take $S=\emptyset$. To
show $\lambda(Z_{4})=1$, we take $S$ to be the layered configuration $0\mod 2$
in $Q_{n}$ (all vertices with even weight).

We can find a lower bound for $Z_{2}$ by considering the layered configuration
in $Q_{n}$ given by $0\mod 3$. This gives $\frac{2}{3}\leq\lambda(Z_{2},2)$
since any sub-2-cube with the smallest weight of a vertex congruent to 1 or 2
mod 3 has an exact copy of $Z_{2}$. For an upper bound we have Baber’s flag
algebra computation $.685714$. We remark that this is close to
$\frac{24}{35}$, though this may reflect the flag algebra construction rather
than the actual value.

A construction for $Z_{3}$ is given by considering $[n]=A\cup B$ and then
taking $S$ to be the set of all vertices given by binary $n$-tuples with
weight $0\mod 2$ in $A$. This gives a “good” $Q_{2}$ for each $Q_{2}$ with one
flip bit in each of $A$ and $B$. If we take $\left\lvert
A\right\rvert=\lfloor\frac{n}{2}\rfloor$ and $\left\lvert
B\right\rvert=\left\lceil\frac{n}{2}\right\rceil$, this results in
$\lfloor\frac{n}{2}\rfloor\left\lceil\frac{n}{2}\right\rceil\approx\frac{n^{2}}{4}$
many “good” $Q_{2}$s, which shows $\frac{1}{2}\leq\lambda(Z_{3},2)$.

Table 1 summarizes the best results obtained in $Q_{2}$.

Configuration | Construction | Lower Bound | Upper Bound
---|---|---|---
$Z_{1}$ | $\emptyset$ | 1 | 1
$Z_{2}$ | Layered: $0$ mod $3$ | $2/3$ | $.685714286$
$Z_{3}$ |  $A\cup B$ taking $0$ mod $2$ in $A$ | $1/2$ |  $1/2$ (Theorem 3.1)
$Z_{4}$ | Layered: $0$ mod $2$ | 1 | 1
Table 1. Summary of the best results for configurations in $Q_{2}$.

###  3.2. Upper Bounds

In order to show that $\lambda(Z_{3},2)=\frac{1}{2}$, we use an argument that
will be applied, in a slightly more general form, to an infinite family of
configurations in Section 6.

######  Theorem 3.1.

$\lambda(Z_{3},2)=\frac{1}{2}$.

###### Proof.

We showed $\lambda(Z_{3},2)\geq\frac{1}{2}$ in Section 3.1. Let $v$ be a
vertex in $S$ and let $S_{v}=S\cap N(v)$, where $N(v)$ is the neighborhood of
$v$ in $Q_{n}$. A $Q_{2}$ containing $v$ can be “good” only if one of the two
vertices adjacent to $v$ is in $S_{v}$ and one is not. Hence

$\operatorname{\mathit{g}_{v({\rm in})}}(Z_{3},2,n,S)\leq\frac{\left\lvert
S_{v}\right\rvert\left(n-\left\lvert
S_{v}\right\rvert\right)}{\binom{n}{2}}\leq\frac{\left\lceil\frac{n}{2}\right\rceil\lfloor\frac{n}{2}\rfloor}{\binom{n}{2}}$

and

$\operatorname{\mathit{\lambda}_{\rm
local(in)}}(Z_{3},2)\leq\lim_{n\to\infty}\frac{\left\lceil\frac{n}{2}\right\rceil\lfloor\frac{n}{2}\rfloor}{\binom{n}{2}}=\frac{1}{2}.$

Since $Z_{3}$ is self-complementary in $Q_{2}$,
$\frac{1}{2}\leq\lambda(Z_{3},2)\leq\operatorname{\mathit{\lambda}_{\rm
local(out)}}(Z_{3},2)\allowbreak=\operatorname{\mathit{\lambda}_{\rm
local(in)}}(Z_{3},2)\allowbreak=\operatorname{\mathit{\lambda}_{\rm
local}}(Z_{3},2)\leq\frac{1}{2}$. ∎

##  4\. Inducibility

There are strong connections between $d$-cube density and _inducibility_ of a
graph. Given graphs $G$ and $H$, with $\left\lvert V(G)\right\rvert=n$ and
$\left\lvert V(H)\right\rvert=k$, the _density_ of $H$ in $G$, denoted
$\operatorname{d}_{H}(G)$, is defined by

$\operatorname{d}_{H}(G)=\frac{\textrm{\\# induced copies of $H$ in
$G$}}{\binom{n}{k}}$

Pippinger and Golumbic [22] defined the inducibility $i(H)$ of $H$ by

$i(H)=\lim_{n\to\infty}\max_{\left\lvert
V(G)\right\rvert=n}\operatorname{d}_{H}(G)$

Clearly $i(H)=i(\overline{H})$ where $\overline{H}$ is the complement of $H$.
We summarize a few inducibility results, some of which we will use to prove
upper bounds for $d$-cube density.

  1. (1)

$i(K_{1,2})=\frac{3}{4}$. The optimizing graph $G$ is
$K_{\frac{n}{2},\frac{n}{2}}$. That it cannot be larger than $\frac{3}{4}$
follows immediately from a theorem of Goodman [17] that says that in any
2-coloring of the edges of $K_{n}$, at least $\frac{1}{4}$ (asymptotically) of
the $K_{3}$s are monochromatic.

  2. (2)

$i(K_{2,2})=\frac{3}{8}$. In [6], Bollobás et. al. showed that the graph on
$n$ vertices which has the most induced copies of $K_{r,r}$, for any $r\geq
2$, is
$K_{\left\lceil\frac{n}{2}\right\rceil,\left\lfloor\frac{n}{2}\right\rceil}$.

  3. (3)

Since $2K_{2}$ is the complement of $K_{2,2}$, $i(2K_{2})=\frac{3}{8}$. In
[14], Goldwasser and Hansen showed that the bipartite graph on $n$ vertices
with the most induced copies of $2K_{2}$ is two disjoint copies of
$K_{\frac{n}{4},\frac{n}{4}}$ (with the obvious modification if $n$ is not
divisible by 4). This graph has $\frac{3}{32}$ of its subgraphs induced by 4
vertices isomorphic to $2K_{2}$. They needed this result to show that
$\operatorname{\mathit{\lambda}}(C_{8},4)=\frac{3}{32}$ where $C_{8}$ is the
“perfect” 8-cycle.

  4. (4)

$i(K_{1,3})=\frac{1}{2}$. In [7], Brown and Siderenko showed that the graph on
$n$ vertices which has the most induced copies of $K_{r,s}$, for any $r,s$
(except $r=s=1$), is complete bipartite. The optimizing graph for $K_{1,3}$ is
asymptotically, but not exactly, equibipartite; the sizes of the parts are
roughly $\frac{n}{2}\pm\frac{\sqrt{3n}}{2}$.

  5. (5)

In [18], Hirst used flag algebras to show that
$i(K_{1,1,2})=\frac{72}{125}=.576$ and $i(K_{\rm{PAW}})=\frac{3}{8}$ where
$K_{1,1,2}$ is $K_{4}$ minus an edge and $K_{\rm{PAW}}$ is $K_{3}$ plus a
pendant edge, leaving the path $P_{4}$ as the only graph on 4 vertices whose
exact inducibility has yet to be determined.

  6. (6)

In [11], Even-Zohar and Linial improve earlier best bounds [12, 24] for
$i(P_{4})$ and find the inducibility of some graphs on 5 vertices.

##  5\. Layered Configurations

Recall that we say a configuration $H$ in $Q_{d}$ is _layered_ if it is an
exact copy of a configuration $K$ in $Q_{d}$ such that $v\in K$ if and only if
$\operatorname{wt}(v)\in W_{H}$ for some subset $W_{H}$ of $[0,d]$. For
example, $H=\\{1001,\allowbreak 1110,\allowbreak 0010,\allowbreak
0100,\allowbreak 0111\\}$ is layered because there is an automorphism of
$Q_{4}$ (interchange 0 and 1 in the 2nd and 3rd coordinates) which maps $H$
onto $K=\\{1111,\allowbreak 1000,\allowbreak 0100,\allowbreak 0010,\allowbreak
0001\\}$and $K=\\{v\in Q_{4}:\operatorname{wt}(v)=1\textrm{ or }4\\}$. We call
$K$ a _canonical layered configuration_.

If $W_{H}$ is the set of weights for a canonical layered configuration $H$ in
$Q_{d}$, and if $j+2\in W_{H}$ if and only if $j\in W_{H}$ for all
$j\in[0,d-2]$, then $H$ is either all vertices, none of the vertices, all even
weight vertices, or all odd weight vertices in $Q_{d}$. We call these four
types of configurations trivial. Each trivial configuration has $d$-cube
density equal to 1 (using the obvious layered configuration $S$ in $Q_{n}$).
The configurations $W_{1},W_{3},W_{7},W_{8},W_{12}$ and $W_{14}$ (and their
complements) are layered configurations in $Q_{3}$, with $W_{1}$ and $W_{14}$
trivial (See Figure 2 and Table 2).

One can get a good lower bound construction for any layered configuration in
$Q_{d}$ by using an appropriate layered configuration $S$ in $Q_{n}$. For
example, if we represent the configuration $W_{8}$ by $H=\\{110,101,011\\}$,
we define $S$ by $S=\\{v\in V_{n}:\operatorname{wt}(v)\equiv 2\mod 3\\}$. Any
sub-3-cube of $Q_{n}$ whose smallest weight vertex has weight congruent to 0
or 1 mod 3 is “good”, showing that $\lambda(W_{8},3)\geq\frac{2}{3}$. Baber’s
flag algebra upper bound is $.66666666675$ so undoubtedly
$\lambda(W_{8},3)=\frac{2}{3}$, but we have not proved it.

######  Theorem 5.1.

If $H$ is a configuration in $Q_{d}$, then
$\operatorname{\mathit{\lambda}_{\rm local}}(H,d)=1$ if and only if $H$ is
layered.

To prove Theorem 5.1 we will need the following lemma which can be proved
using a “tower” of applications of Ramsey’s theorem.

######  Lemma 5.2.

[16] For all positive integers $k$ and $d$, there exists a positive integer
$N=N(k,d)$ such that for all $n\geq N$, if $c$ is any vertex coloring of
$Q_{n}$ with $k$ colors, for each $v\in V_{n}$, there exists a sub-$d$-cube
$D$ containing $v$ such that the coloring induced by $c$ on $D$ is layered
with “bottom” vertex $v$ (so $v$ plays the role of $\emptyset$ is a canonical
layered coloring).

###### Proof of Theorem 5.1.

Suppose $H$ is layered with weight set $W_{H}\subseteq[0,d]$. For each $n\geq
d$, if $S$ is any layered configuration in $Q_{n}$ with weight set $W_{S}$
such that $W_{H}\subseteq W_{S}$, then every sub-$d$-cube containing
$\emptyset$ has an exact copy of $H$, so $\operatorname{\mathit{\lambda}_{\rm
local}}(H,d)=1$.

Conversely, suppose $\operatorname{\mathit{\lambda}_{\rm local}}(H,d)=1$. We
can view a configuration $S$ in $Q_{n}$ as a $2$-coloring of $V_{n}$ – red if
in $S$, blue if not in $S$. Hence, by Lemma 5.2, there exists an integer $N$
such that for all $n\geq N$ and all $v\in V_{n}$, if $S$ is any configuration
in $Q_{n}$ then there exists a sub-$d$-cube $D$ containing $v$ such that
$D\cap S$ is a layered configuration in $D$. Since
$\operatorname{\mathit{\lambda}_{\rm local}}(H,d,n)$ is a nonincreasing
function of $n$, and since every vertex $v$ is contained in a sub-$d$-cube
which has an exact copy of a layered configuration, if $H$ is not layered then
$\operatorname{\mathit{\lambda}_{\rm local}}(H,d)<1$. ∎

Since $\operatorname{\mathit{\lambda}_{\rm local}}(H,d)=1$ for every layered
configuration $H$ in $Q_{d}$, our usual procedure of using
$\operatorname{\mathit{\lambda}_{\rm local}}(H,d)$ to get an upper bound for
$d$-cube density cannot work and that is why we have not been able to obtain
upper bounds by hand for any nontrivial layered configuration in $Q_{d}$ for
any $d$. As with $W_{8}$, Baber’s flag algebra upper bounds for
$\operatorname{\mathit{\lambda}}(W_{7},3)$ and
$\operatorname{\mathit{\lambda}}(W_{12},3)$ are within $10^{-9}$ of our lower
bounds ($\frac{1}{3}\leq\operatorname{\mathit{\lambda}}(W_{7},3)$ and
$\frac{1}{2}\leq\operatorname{\mathit{\lambda}}(W_{12},3)$). The flag algebra
upper bound for $\operatorname{\mathit{\lambda}}(W_{3},3)$ (one vertex in
$Q_{3}$) is $.610043$, not so close to our lower bound of $\frac{1}{2}$.

######  Conjecture 5.3.

$\operatorname{\mathit{\lambda}}(W_{7},3)=\frac{1}{3},\operatorname{\mathit{\lambda}}(W_{8},3)=\frac{2}{3},\operatorname{\mathit{\lambda}}(W_{12},3)=\frac{1}{2}$.

##  6\. An Infinite Family

Theorem 3.1 can be generalized to apply to an infinite family of
configurations containing $Z_{3}$, $W_{6}$, and $W_{13}$. Let $d$ and $i$ be
positive integers with $1\leq i<d$. We define the configuration $H(d,i)$ in
$Q_{d}$ by

$\displaystyle H(d,i)$ $\displaystyle=\left\\{(v_{1},v_{2},\ldots,v_{d})\in
V_{d}\ \middle|\ \sum_{j=1}^{i}v_{j}\textrm{ is even}\right\\}.$

######  Theorem 6.1.

$\lambda(H(d,i),d)=\binom{d}{i}\frac{i^{i}(d-i)^{d-i}}{d^{d}}$.

###### Proof.

Each vertex in $H(d,i)$ has precisely $d-i$ neighbors in $H(d,i)$ (change any
one of the last $d-i$ coordinates). Since $H(d,i)$ is self-complementary in
$Q_{d}$ $\left(\sum_{j=1}^{i}v_{j}\textrm{ is odd}\right)$,
$\operatorname{\mathit{\lambda}_{\rm
local}}(H(d,i),d)=\operatorname{\mathit{\lambda}_{\rm
local(in)}}(H(d,i),d)=\operatorname{\mathit{\lambda}_{\rm
local(out)}}(H(d,i),d)$.

If $n\geq d$ and $v\in S\subseteq V_{n}$ and $R$ is a sub-$d$-cube of $Q_{n}$
containing $v$, then $R$ can be good only if precisely $d-i$ neighbors of $v$
in $R$ are in $S$. If $x$ is the fraction of neighbors of $v$ in $Q_{n}$ which
are in $S$, then the fraction of sub-$d$-cubes of $Q_{n}$ containing $v$ which
have precisely $d-i$ neighbors in $S$ is $f(x)=\binom{d}{i}x^{d-i}(1-x)^{i}$.
By simple calculus, $f(x)$ is maximized on $[0,1]$ when $x=\frac{d-i}{d}$, so
$\operatorname{\mathit{\lambda}_{\rm
local(in)}}(H(d,i))\leq\binom{d}{i}\frac{(d-i)^{d-i}i^{i}}{d^{d}}$.

To show this upper bound is a lower bound as well, let
$S=${$(x_{1},x_{2},\ldots,x_{n}):\allowbreak\sum_{j=1}^{m}v_{j}$ is even,
where $m=\lfloor\frac{in}{d}\rfloor$}. Then any sub-$d$-cube of $Q_{n}$ with
precisely $i$ flip bits in $[1,m]$ is good, and this is a fraction

$\binom{d}{i}\frac{m^{i}(n-m)^{d-i}}{n^{d}}=\binom{d}{i}\left(\frac{\lfloor\frac{in}{d}\rfloor}{n}\right)^{i}\left(\frac{\left\lceil\frac{(d-i)n}{d}\right\rceil}{n}\right)^{d-i}$

of all sub-$d$-cubes, and the limit as $n$ goes to infinity is
$\binom{d}{i}\frac{i^{i}(d-i)^{d-i}}{d^{d}}$. ∎

Note that the configuration $W_{6}$ in $Q_{3}$ is $H(3,1)$, $W_{13}$ is
$H(3,2)$, and $Z_{3}$ in $Q_{2}$ is $H(2,1)$. Further note that
$\lim_{d\to\infty}\lambda(H(d,i),d)=\frac{i^{i}}{i!e^{i}}$. In particular,
when $i=1$, $\lim_{d\to\infty}(H(d,1),d)=\frac{1}{e}$. ($H(d,1)$ is a copy of
$Q_{d-1}$ in $Q_{d}$)

##  7\. Configurations in $Q_{3}$

The configurations in $Q_{3}$ are illustrated in Figure 2 and listed in Table
2. Recalling that $\lambda(H)=\lambda\left(\overline{H}\right)$ where
$\overline{H}$ is the complement of $H$ in $Q_{d}$, the table lists just one
configuration in each complementary pair.

$W_{1}$$W_{2}$$W_{3}$$W_{4}$$W_{5}$$W_{6}$$W_{7}$$W_{8}$$W_{9}$$W_{10}$$W_{11}$$W_{12}$$W_{13}$$W_{14}$ Figure 2. Configurations in $Q_{3}$. Configuration | Construction | Lower Bound | Upper Bound
---|---|---|---
$W_{1}$ | $\emptyset$ | 1 | 1
$W_{2}$ |  $A\cup B$ taking 00 mod 2 | $3/4$ |  | $3/4$
---
(Theorem 7.2)
$W_{3}$ | Layered: 0 mod 4 | $1/2$ | $.610043$
$W_{4}$ |  $A\cup B$ taking $0*$ mod 3 | $(2/3)^{3}\approx 0.2963$ | .$3047619$
$W_{5}$ |  |  $A\cup B$ taking
---
01,10,11 mod $(3,3)$
1/3 | .$333398$
$W_{6}$ |  $A\cup B$ taking $0*$ mod 2 | $4/9$ |  $4/9$ (Theorem 6.1)
$W_{7}$ | Layered: 0 mod 3 | $1/3$ | $.33333333366$
$W_{8}$ | Layered: 0 mod 3 | $2/3$ | $.66666666673$
$W_{9}$ |  |  $A\cup B$ taking
---
00,10,21, 31 mod $(4,2)$
$4/9$ | $.44444444453$
$W_{10}$ |  Blow-up of the configuration given in Figure 4 |  $\frac{5}{12}$ (Proposition 7.4) | $.4166666671$
$W_{11}$ | Perfect 8-cycle blow-up | $3/8$ |  $3/8$ (We proved this in [14])
$W_{12}$ | Layered: 0 and 1 mod 4 | $1/2$ | $.50000000004$
$W_{13}$ |  $A\cup B$ taking $0*$ mod 2 | $4/9$ |  $4/9$ (Theorem 6.1)
$W_{14}$ | Layered: 0 mod 2 | 1 | 1
Table 2. Summary of the best results for configurations in $Q_{3}$.

Six of these configurations are layered: the two trivial ones ($W_{1}$ and
$W_{14}$) and four others ($W_{3},W_{7},W_{8}$, and $W_{12}$). Letting $S$ be
the layered configuration 0 mod 3 in $Q_{n}$ shows that
$\lambda(W_{7},3)\geq\frac{1}{3}$ and $\lambda(W_{8},3)\geq\frac{2}{3}$. The
layered configuration 0 or 1 mod 4 shows that
$\lambda(W_{12},3)\geq\frac{1}{2}$. Baber’s flag algebra upper bound is within
$10^{-9}$ of the lower bound for each of these. For $W_{3}$ – one vertex in
$Q_{3}$ – the layered configuration 0 mod 4 in $Q_{n}$ shows that
$\lambda(W_{3},3)\geq\frac{1}{2}$, while the flag algebra upper bound is
.610043.

The configurations $W_{6}$ and $W_{13}$ are $H(3,1)$ and $H(3,2)$ respectively
in the infinite family of Section 6, so
$\lambda(W_{6},3)=\lambda(W_{13},3)=\frac{4}{9}$.

We showed $\lambda(W_{11},3)=\frac{3}{8}$ in [14] ($W_{11}$ is the induced
path with 4 vertices). The proof of Theorem 7.2 shows that
$\lambda(W_{2},3)=\frac{3}{4}$.

For $W_{4}$, with $[n]=A\cup B$ where $\left\lvert
A\right\rvert=\lfloor\frac{2n}{3}\rfloor$ and
$B=\left\lceil\frac{n}{3}\right\rceil$ we take $S$ to be the set of all
vertices $v=(x_{1},x_{2},\ldots,x_{n})$ where $\sum_{i\in A}x_{i}$ is
divisible by 3. Suppose a $Q_{3}$ has precisely two flip bits whose coordinate
numbers are in $A$. If the sum of all the other coordinates in $A$ is $m$,
then the $Q_{3}$ will have configuration $W_{4}$ if and only if $m$ is
congruent to 0 or 1 mod 3. For example, if $m\equiv 0$ mod 3 then a vertex in
the $Q_{3}$ will be in $S$ if and only if the two coordinates in $A$ are equal
to 0, while if $m\equiv 1$ mod 3 then a vertex in the $Q_{3}$ will be in $S$
if and only if the two coordinates in $A$ are equal to 1 (if $m\equiv 2$ mod 3
then the configuration will be $W_{13}$). In the limit as $n$ goes to
infinity, $\frac{4}{9}$ of the sub-3-cubes will have precisely two flip bits
in $A$, so
$\lambda(W_{4},3)\geq\frac{4}{9}\cdot\frac{2}{3}=\frac{8}{27}\approx.2963$.
Baber’s flag algebra upper bound is $.304762$.

For $W_{9}$, we partition $[n]$ into sets $A$ and $B$ with $\left\lvert
A\right\rvert=\lfloor\frac{2n}{3}\rfloor$ and
$B=\left\lceil\frac{n}{3}\right\rceil$ and let $S$ be the set of all vertices
$v=(x_{1},x_{2},\ldots,x_{n})$ such that both $\sum_{i\in A}x_{i}\equiv 0$ or
1 mod 4 and $\sum_{j\in B}x_{j}\equiv 0$ mod 2 or both $\sum_{i\in
A}x_{i}\equiv 2$ or 3 mod 4 and $\sum_{j\in B}x_{j}\equiv 1$ mod 2. Every
sub-3-cube $R$ which has two flip bits with coordinate numbers in $A$ and one
in $B$ will have an exact copy of $W_{9}$. For example, if $R$ is such that
the sum of the non flip bit coordinates in $A$ is 1 mod 4 and the sum of the
non flip bit coordinates in $B$ is 1 mod 2 then the coordinates in the flip
bits for $R$ of the vertices in $S$ with the coordinate in $B$ listed third
are 001, 100, 010, 110, so $R$ has an exact copy of $W_{9}$. In the limit as
$n$ goes to infinity, $\frac{4}{9}$ of the sub-3-cubes will have precisely two
flip bits with coordinate numbers in $A$, so
$\lambda(W_{9},3)\geq\frac{4}{9}$.

For $W_{5}$, we partition $[n]$ into a set $A$ of size
$\left\lceil\frac{n}{2}\right\rceil$ and $B$ of size
$\lfloor\frac{n}{2}\rfloor$ and let $S$ be all vectors
$v=(x_{1},x_{2},\ldots,x_{n})$ such that $\sum_{i\in A}x_{i}$ and $\sum_{j\in
B}x_{j}$ are both congruent to either 0 or 1 mod 3. If a $Q_{3}$ has two flip
bits with coordinate numbers in $A$ and one with coordinate number in $B$, we
let $y$ be the sum of the non flip bit coordinates in $A$ and $z$ be the sum
of the non flip bit coordinates in $B$. This $Q_{3}$ will be “good” if $(y,z)$
is congruent to $(0,1)$, $(0,2)$, $(2,1)$, or $(2,2)$ mod 3. For example, if
$(y,z)$ is congruent to $(0,2)$, then the coordinate in the flip bits for the
$Q_{3}$ of the vertices in $S$ with the coordinate in $B$ listed third are
001, 011, and 101 which is an exact copy of $W_{5}$. Since 4 of the 9 ordered
pairs $(y,z)$ where $y,z\in\\{0,1,2\\}$, produce “good” $Q_{3}$’s, in the
limit as $n$ goes to infinity, $\frac{4}{9}$ of the $Q_{3}$’s which have two
flip bits in $A$ and one in $B$ will have exact copies of $W_{5}$. By
symmetry, $\frac{4}{9}$ of the $Q_{3}$’s which have one flip bit in $A$ and
two in $B$ will have exact copies of $W_{5}$, so
$\lambda(W_{5},3)\geq\frac{3}{8}\cdot\frac{4}{9}+\frac{3}{8}\cdot\frac{4}{9}=\frac{1}{3}$.
Baber’s flag algebra upper bound is .333398.

In the remainder of this section, we will consider the two remaining
configurations in $Q_{3}$: $W_{2}$ and $W_{10}$.

The following Lemma is used in the proof that $\lambda(W_{2},3)=\frac{3}{4}$.

######  Lemma 7.1.

Let $G$ be a graph with $n$ vertices where $n$ is even. If $\left\lvert
E(G)\right\rvert=e$, then $G$ has at most
$\min\left\\{n\binom{\frac{n}{2}}{2},\frac{e}{2}(n-2)\right\\}$ induced copies
of $K_{1,2}$.

###### Proof.

That it has at most $n\binom{\frac{n}{2}}{2}$ was proved in [22]. The
optimizing graph is $K_{\frac{n}{2},\frac{n}{2}}$.

Each edge of $G$ can be in at most $n-2$ induced $K_{1,2}$s and summing over
all edges $uv$ counts each $K_{1,2}$ twice. ∎

Without restriction on the parity of $n$, the bound in Lemma 7.1 is
$\min\left\\{\lfloor\frac{n^{2}}{4}\rfloor\frac{n-2}{2},\frac{e}{2}(n-2)\right\\}$.

######  Theorem 7.2.

$\displaystyle\lambda(W_{2},3)=\frac{3}{4}$.

###### Proof.

We partition $[n]$ into sets $A$ and $B$ of sizes
$\left\lceil\frac{n}{2}\right\rceil$ and $\lfloor\frac{n}{2}\rfloor$
respectively. We define a configuration $S$ in $Q_{n}$ by
$v=(x_{1},x_{2},\ldots,x_{n})\in S$ if and only if $\sum_{i\in A}x_{i}$ and
$\sum_{j\in B}x_{j}$ are both even. If $D$ is any sub-3-cube of $Q_{n}$ with
one or two flip bits in coordinates with numbers in $A$ (and two or one in
$B$) then $D$ has an exact copy of $W_{2}$. For example, if two flip bits have
coordinate numbers in $A$ and one in $B$, and if the sum of the non flip bit
coordinates in $A$ is even and of the non flip bit coordinates in $B$ is odd,
then the vertices of $D$ whose flip bit coordinates (with the flip bit in $B$
listed third) are 001 and 111 are in $S$, so $D$ has an exact copy of $W_{2}$.

In the limit as $n$ goes to infinity, $\frac{3}{4}$ of the sub-3-cubes have
one or two flip bits with coordinate numbers in $A$, so
$\lambda(W_{2},3)\geq\frac{3}{4}$.

For the upper bound, suppose $\emptyset\in S$, and let $\mathscr{M}$ be the
set of good $Q_{3}$s containing $\emptyset$. Construct a graph $G_{s}$ with
$V(G_{s})=[n]$ and $E(G_{s})=\\{uv:\emptyset,uv$ are the vertices in $S$ for
some $M\in\mathscr{M}\\}$. If $u,v,x$ are flip bits for some $M$ in
$\mathscr{M}$, and if $uv$ is in $M$, then neither $ux$ nor $vx$ can be in
$E(G_{s})$, so $\left\lvert\mathscr{M}\right\rvert$ is less than or equal to
the number of induced copies of the graph with three vertices and a single
edge in a graph with $n$ vertices. Equivalently, this is less than or equal to
the number of induced copies of $K_{1,2}$ in a graph on $n$ vertices. This
means $\operatorname{\mathit{\lambda}_{\rm local(in)}}(W_{2})\leq
i(K_{1,2})=\frac{3}{4}$.

Now suppose $\emptyset\not\in S$. Let $A=\\{i\in[n]:i\in S\\}$,
$B=[n]\setminus A$, $\left\lvert A\right\rvert=a$, and $\left\lvert
B\right\rvert=b$. Let $\mathscr{M}$ be the set of all good $Q_{3}$s containing
$\emptyset$. If $M\in\mathscr{M}$, then the two vertices of $M$ in $S$ have
the structure of Type I, II, or III as shown in Figure 3, when $i$ and $j$ are
vertices adjacent to $\emptyset$ which are in $S$, while $u,v,x,y$ are
vertices adjacent to $\emptyset$ which are not in $S$. For example, in the
Type II configuration the vertices $i$ and $ixy$ are in $S$ while
$\emptyset,x,y,ix,iy,xy$ are not in $S$.

Type I$j$$i$

Type II$i$$ixy$

Type III$uv$$vx$

Figure 3. The three possible structures of vertices in $S$ for
$M\in\mathscr{M}$ where $\emptyset\not\in S$.

Define a graph $G_{s}$ by $V(G_{s})=B$ and $E(G_{s})=\\{uv:uv$ and $vx$ are
the vertices in $S$ of some Type III $M\in\mathscr{M}$ for some $x$ with flip
bits $u,v,x\\}$. For such an $M$, $ux$ cannot be in $S$ so the number of Type
III $Q_{3}$s in $\mathscr{M}$ is at most the number of induced copies of
$K_{1,2}$ in $G_{s}$.

If $L$ is a Type I $Q_{3}$ in $\mathscr{M}$ with flip bits $i,j,x$ and with
$i,j$ the vertices of $L$ in $S$, then $i,j\in A$ and $x\in B$. So the number
of Type Is in $\mathscr{M}$ is at most $b\binom{a}{2}$. If $L$ is a Type II
$Q_{3}$ in $\mathscr{M}$ where $i,ixy$ are the vertices of $L$ in $S$, then
$i\in A$ and $x,y\in B$, but $xy\not\in E(G_{s})$. So, if $e=\left\lvert
E(G_{s})\right\rvert$, then the number of Type II $Q_{3}$s in $\mathscr{M}$ is
at most $a\left[\binom{b}{2}-e\right]$. By Lemma 7.1, we have that the number
of Type III $Q_{3}$s in $\mathscr{M}$ is at most
$\min\left\\{b\binom{\frac{b}{2}}{2},\frac{e}{2}(b-2)\right\\}$.

One good candidate to maximize $\left\lvert\mathscr{M}\right\rvert$ is for
$\mathscr{M}$ to have no Type IIIs (i.e. $\left\lvert
E(G_{s})\right\rvert=0$), and for $S$ to include all vertices $j$ in $A$ and
all vertices $ixy$ where $i\in A$ and $x,y\in B$. That would give
$\left\lvert\mathscr{M}\right\rvert=b\binom{a}{2}+a\binom{b}{2}$. Another good
candidate would be to have $G_{s}$ be $K_{\frac{b}{2},\frac{b}{2}}$, so as to
maximize the number of Type IIIs. This would mean that
$\left\lvert\mathscr{M}\right\rvert=b\binom{a}{2}+a\left[\binom{b}{2}-\frac{b^{2}}{4}\right]+b\binom{\frac{b}{2}}{2}=b\binom{a}{2}+(2a+b)\binom{\frac{b}{2}}{2}$.

If $\left\lvert E\right\rvert=e$, then we have

($\star$) $\left\lvert\mathscr{M}\right\rvert\leq
b\binom{a}{2}+a\left[\binom{b}{2}-e\right]+\min\left\\{b\binom{\frac{b}{2}}{2},\frac{e}{2}(b-2)\right\\}.$

Where the three summands on the right-hand side are the maximum number of
“good” $Q_{3}$s of Type I, II, and III, and we have used Lemma 7.1. If
$e\geq\frac{b^{2}}{4}$ then
$\min\\{b\binom{\frac{b}{2}}{2},\frac{e}{2}(b-2)\\}=b\binom{\frac{b}{2}}{2}$,
so the right-hand side of inequality ($\star$ ‣ 7.2) is a decreasing function
of $e$. Hence to maximize $\left\lvert\mathscr{M}\right\rvert$ we can assume
$e\leq\frac{b^{2}}{4}$.

_Case 1:_ If $\frac{b-2}{2}\leq a$, then

$\displaystyle\left\lvert M\right\rvert$ $\displaystyle\leq
b\binom{a}{2}+a\left[\binom{b}{2}-e\right]+\frac{e}{2}(b-2)$
$\displaystyle\leq b\binom{a}{2}+a\left[\binom{b}{2}-e\right]+ea$
$\displaystyle=b\binom{a}{2}+a\binom{b}{2}$

which is the size of $\mathscr{M}$ in the first good candidate above.

_Case 2:_ If $\frac{b-2}{2}>a$, then

$\displaystyle\left\lvert M\right\rvert$ $\displaystyle\leq
b\binom{a}{2}+a\left[\binom{b}{2}-e\right]+\frac{e}{2}(b-2)$
$\displaystyle=b\binom{a}{2}+a\binom{b}{2}+e\left(\frac{b-2}{2}-a\right)$
$\displaystyle\leq
b\binom{a}{2}+a\binom{b}{2}+\frac{b^{2}}{4}\left(\frac{b-2}{2}-a\right)$
$\displaystyle=b\binom{a}{2}+a\binom{b}{2}+b\binom{\frac{b}{2}}{2}-\frac{b^{2}}{4}a$
$\displaystyle=b\binom{a}{2}+a\left(\binom{b}{2}-\frac{b^{2}}{4}\right)+b\binom{\frac{b}{2}}{2}$
$\displaystyle=b\binom{a}{2}+2a\binom{\frac{b}{2}}{2}+b\binom{\frac{b}{2}}{2}$
$\displaystyle=b\binom{a}{2}+(2a+b)\binom{\frac{b}{2}}{2}$

which is the size of $\mathscr{M}$ in the second good candidate above.

This expression can be rewritten as

$\frac{b}{2}\binom{a}{2}+\frac{b}{2}\binom{\frac{b}{2}}{2}+a\binom{\frac{b}{2}}{2}+a\binom{\frac{b}{2}}{2}+\frac{b}{2}\binom{\frac{b}{2}}{2}+\frac{b}{2}\binom{a}{2}$

which is equal to

($\star\star$)
$x\binom{y}{2}+x\binom{z}{2}+y\binom{x}{2}+y\binom{z}{2}+z\binom{x}{2}+z\binom{y}{2}$

when $x=z=\frac{b}{2}$ and $y=a$. The expression in ($\star\star$ ‣ 7.2) is
the number of induced $K_{1,2}$s in a complete tripartite graph with part
sizes $x,y$, and $z$. We know that $K_{\frac{n}{2},\frac{n}{2}}$ is the graph
with $n$ vertices which has the maximum number of induced $K_{1,2}$s (Remark
1. in Section 4), so ($\star\star$ ‣ 7.2) attains its maximum value when
$x=z=\frac{n}{2}$ and $y=0$, so $b=n$ and $a=0$. The size of $\mathscr{M}$ for
the first candidate $a\binom{b}{2}+b\binom{a}{2}$ is the value of
($\star\star$ ‣ 7.2) when $x=a$, $y=b$, and $z=0$, so it attains its maximum
value when $a=b=\frac{n}{2}$ and both good candidates have size

$2\cdot\frac{n}{2}\binom{\frac{n}{2}}{2}=\frac{n^{2}(n-2)}{8}=\frac{3}{4}\binom{n}{3}\frac{n}{n-1}$

and $\left\lvert\mathscr{M}\right\rvert$ cannot be bigger. Hence

$\frac{3}{4}\leq\lambda(W_{2},3)\leq\operatorname{\mathit{\lambda}_{\rm
local}}(W_{2},3)\leq\frac{3}{4}.$

∎

We remark that in the construction we have with density $\frac{3}{4}$, of the
vertices not in $S$, $\frac{2}{3}$ of them are in good $Q_{3}$’s only of the
type of the first good candidate (those vertices which have an odd sum in
precisely one of $A$ or $B$) and $\frac{1}{3}$ are in good $Q_{3}$’s only of
the type of the second candidate (those vertices with an odd sum in both $A$
and $B$). The local density at all vertices is $\frac{3}{4}$.

We suspect that no nontrivial $d$-cube density can be bigger than
$\frac{3}{4}$ and that this is the only one bigger than $\frac{2}{3}$.

######  Conjecture 7.3.

If $H$ is a configuration in $Q_{d}$ such that
$\frac{2}{3}<\operatorname{\mathit{\lambda}}(H,d)<1$ then $d=3$ and $H$ is an
exact copy of $W_{2}$.

We will use a _blow-up_ (introduced in [14]) of the miraculous configuration
$T$ in $Q_{6}$ shown in Figure 4 to get a lower bound for $\lambda(W_{10},3)$.
Let $H$ be a configuration in $Q_{d}$. We say the configuration $S$ in $Q_{n}$
is a blow-up of $H$ if it is obtained as follows. We partition $[n]$ into
parts $A_{1},A_{2},\ldots,A_{d}$. For each $v=(x_{1},x_{2},\ldots,x_{n})$ in
$V_{n}$ we define a vector $u=(y_{1},y_{2},\ldots,y_{d})$ in $V_{d}$ by
$y_{j}\equiv\sum_{i\in A_{j}}x_{i}$ mod 2, and put $v$ in $S$ if and only if
$u\in H$. Any sub-$d$-cube of $Q_{n}$ which has one flip bit in each $A_{j}$
will have an exact copy of $H$ (and perhaps others will as well). Using an
equipartition of $[n]$ into $d$ parts shows that
$\lambda(H,d)\geq\frac{d!}{d^{d}}$ for each $H$ in $Q_{d}$ (Proposition 6 of
[14]).

######  Proposition 7.4.

$\operatorname{\mathit{\lambda}}(W_{10},3)\geq\frac{5}{12}$

###### Proof.

Let $S$ be a blow-up in $Q_{n}$ of the configuration $T$ in $Q_{6}$ shown in
Figure 4. If $n$ is large and $[n]$ is equipartitioned into 6 parts, then the
probability that a randomly chosen sub-3-cube has its 3 flip bits in different
parts is $\frac{6}{6}\cdot\frac{5}{6}\cdot\frac{4}{6}=\frac{5}{9}$. To
complete the proof we need to show that $\frac{3}{4}$ of the
$\binom{6}{3}\cdot 2^{3}=160$ sub-3-cubes of $Q_{6}$ have an intersection with
$T$ which is an exact copy of $W_{10}$, since
$\frac{5}{9}\cdot\frac{3}{4}=\frac{5}{12}$.

$\emptyset$$1$124 146 163 135 1521234 1456 1623 1345 156212345623 34 45 56
62235 346 452 563 62423456 Figure 4. The configuration $T$ in $Q_{6}$ used for
Proposition 7.4

It is not hard to check that for each $u,v$ in $T$, there are 10 automorphisms
of $Q_{6}$ which map $u$ to $v$ and $T$ to itself. For example, if $\psi$ is
such an automorphism such that $\psi(\emptyset)=\emptyset$, then $\psi(1)=1$,
$\psi(2)=j$ where $j\in\\{$2,3,4,5,6$\\}$, $\psi(3)=j+1$ ($\psi(3)=2$ if
$j=6$) or $\psi(3)=j-1$ ($\psi(3)=6$ if $j=2$), and that completely determines
$\psi$. That means the group of automorphisms of $Q_{6}$ which fix the set $T$
is vertex transitive within $T$ and outside of $T$. Hence it suffices to show
that 15 of the 20 sub-3-cubes containing a vertex in $T$ (say $\emptyset$)
have exact copies of $W_{10}$ and that 15 of the 20 sub-3-cubes containing a
vertex not in $T$ (say 2) have exact copies of $W_{10}$.

Of the 20 sub-3-cubes containing $\emptyset$, only the ones containing
$234,345,456,562$, and $623$ do not have exact copies of $W_{10}$. For
example, the one with flip bits 2,3, and 5 contains the vertices $\emptyset$,
23, and 235 of $T$, the one with flip bits 1,2, and 3 contains the vertices
$\emptyset$, 1, and 23 of $T$, and the one with flip bits 1, 2, and 4 contains
the vertices $\emptyset$, 1, and 124 of $T$.

Of the 20 sub-3-cubes containing 2, the five which do not have exact copies of
$W_{10}$ are the ones with flip bits 1,3,6; 1,4,5; 2,3,4; 2,3,6; 2,5,6. For
example, the one with flip bits 1,3,5 contains the vertices 23,125, and 235 of
$T$ and the one with flip bits 2,3,5 contains the vertices $\emptyset$, 23,
and 235 of $T$. ∎

We remark that the generic lower bound
$\operatorname{\mathit{\lambda}}(H,d)\geq\frac{d!}{d^{d}}$ is attained by
$Z_{3}$ in $Q_{2}$ and by the perfect 8-cycle $C_{4}$ in $Q_{4}$, but not by
any configuration in $Q_{3}$, since
$\operatorname{\mathit{\lambda}}(H,3)\geq\frac{8}{27}$ for all configurations
$H$ in $Q_{3}$.

##  8\. Configurations in $Q_{4}$

In [14] we determined the $d$-cube-density of the perfect 8-cycle $C_{8}$ in
$Q_{4}$. In this section, we will determine the $d$-cube-density for two other
configurations in $Q_{4}$.

######  Theorem 8.1.

If $Y$ is the configuration $\\{0000,1100,0011,1111\\}$ in $Q_{4}$ (see Figure
5), then $\displaystyle\lambda(Y,4)=\frac{3}{8}$.

Figure 5. The configuration $Y$.

###### Proof.

First we give a construction to show
$\operatorname{\mathit{\lambda}}(Y,4)\geq\frac{3}{8}$. Partition $[n]$ into
sets $A$ and $B$ and let $S$ be the set of all vertices in $Q_{n}$ given by
binary $n$-tuples with even weight in both $A$ and $B$. This gives a “good”
$Q_{4}$ for each $Q_{4}$ with two flip bits in each of $A$ and $B$. If it is
an equipartition and $n$ is large then $\frac{3}{8}$ of the $Q_{4}$s are
“good”.

Suppose $\emptyset\in S$ and let $\mathscr{M}$ be the set of good $Q_{4}$s
containing $\emptyset$. We construct a graph $G_{s}$ with $V(G_{s})=[n]$ and
$E(G_{s})=\\{uv:\emptyset,uv,xy,uvxy$ are the vertices in $S$ of some
$M\in\mathscr{M}\\}$. If $uv$ and $xy$ are in $M\in\mathscr{M}$, then neither
$ux,uy,vx$, nor $vy$ can be in $E(G_{s})$, so
$\left\lvert\mathscr{M}\right\rvert$ is less than or equal to the number of
induced copies of $2K_{2}$ in $G_{s}$. That means
$\operatorname{\mathit{\lambda}_{\rm local(in)}}(Y)\leq
i(2K_{2})=\displaystyle\frac{3}{8}$.

Now suppose $\emptyset\not\in S$. Let $A=\\{i\in[n]:i\in S\\}$,
$B=[n]\setminus A$, $\left\lvert A\right\rvert=a$, and $\left\lvert
B\right\rvert=b$. Let $\mathscr{M}$ be the set of all good $Q_{4}$s containing
$\emptyset$. If $M\in\mathscr{M}$, then the four vertices of $M$ in $S$ have
the structure of Type I or Type II in Figure 6, where $i,j,u,v,x,y\in[n]$ with
$i$ and $j$ in $S$, but $u,v,x,$ and $y$ not in $S$.

Type I$j$$jux$$i$$iux$

Type II$yu$$xy$$vx$$uv$

Figure 6. The two possible structures of vertices in $S$ for $M\in\mathscr{M}$
where $\emptyset\not\in S$.

Define a graph $G_{s}$ by $V(G_{s})=B$ and $E(G_{s})=\\{uv:uv,vx,xy,yu$ are
the vertices in $S$ of some Type II $M\in\mathscr{M}$ for some $x,y$ in
$[n]\\}$. For such an $M$, neither $ux$, nor $vy$ can be in $S$, so the number
of Type II $Q_{4}$s in $\mathscr{M}$ is at most the number of induced copies
of $K_{2,2}$ in $G_{s}$.

######  Lemma 8.2.

Let $G$ be a graph with $n$ vertices where $n$ is even. If $\left\lvert
E(G)\right\rvert=e$, then $G$ has at most
$\min\left\\{\binom{\frac{n}{2}}{2}^{2},\frac{e}{4}\frac{(n-2)^{2}}{4}\right\\}$
induced copies of $K_{2,2}$.

###### Proof.

That it has at most $\binom{\frac{n}{2}}{2}^{2}$ copies of $K_{2,2}$ is proved
in [7] and [6] (the optimizing graph is $K_{\frac{n}{2},\frac{n}{2}}$). If
$uv\in E(G)$, define an auxiliary graph $F$ with $V(F)=V(G)\setminus\\{u,v\\}$
and $E(F)=\\{xy:\\{u,v,x,y\\}$ induces $K_{2,2}\\}$. The graph $F$ is
triangle-free since if $\\{u,v,x,y\\}$ and $\\{u,v,x,z\\}$ both induce
$K_{2,2}$, then either $\\{uy,uz\\}\subseteq E(G)$ or $\\{vy,vz\\}\subseteq
E(G)$. In either case, $\\{u,v,y,z\\}$ induces $K_{1,3}$. Since $F$ is
triangle free, by Turán’s theorem, $uv$ is in at most $\frac{(n-2)^{2}}{4}$
induced $K_{2,2}$s. Finally, summing over all edges $uv$ counts each $K_{2,2}$
four times. ∎

If $L$ is a good Type I in $\mathscr{M}$ where $i,j,iux$, and $jux$ are the
vertices of $L$ in $S$, then $i,j\in A$, $u,x\in B$, but $ux\not\in E(G_{s})$.
If $\left\lvert E(G_{s})\right\rvert=e$, then the number of Type I $Q_{4}$s in
$\mathscr{M}$ is at most $\left[\binom{b}{2}-e\right]\binom{a}{2}$ and of Type
II, by Lemma 8.2, is at most
$\min\left\\{\binom{\frac{b}{2}}{2}^{2},\frac{e}{16}(b-2)^{2}\right\\}$ (with
slight modification if $b$ is odd). If $a$ and $b$ are fixed, then one good
candidate to maximize $\left\lvert\mathscr{M}\right\rvert$ is for
$\mathscr{M}$ to have no Type II $Q_{4}$s. Then $G_{s}$ has no edges and
$\left\lvert M\right\rvert=\binom{a}{2}\binom{b}{2}$. Another good candidate
is when $\mathscr{M}$ has the maximum possible number of Type II $Q_{4}$s.
Then $G_{s}$ is $K_{\frac{b}{2},\frac{b}{2}}$ (assuming $b$ is even) and
$\left\lvert\mathscr{M}\right\rvert=\left[\binom{b}{2}-\frac{b^{2}}{4}\right]\binom{a}{2}+\binom{\frac{b}{2}}{2}^{2}=\frac{b(b-2)}{4}\binom{a}{2}+\binom{\frac{b}{2}}{2}^{2}$.

If $e=E(G_{s})$, we have
$\left\lvert\mathscr{M}\right\rvert\leq\left[\binom{b}{2}-e\right]\binom{a}{2}+\min\left\\{\binom{\frac{b}{2}}{2}^{2},\frac{e}{4}\frac{(b-2)^{2}}{4}\right\\}$.

_Case 1:_ If $e\geq\frac{b^{2}}{4}$, then

$\displaystyle\left\lvert\mathscr{M}\right\rvert$
$\displaystyle\leq\left[\binom{b}{2}-\frac{b^{2}}{4}\right]\binom{a}{2}+\binom{\frac{b}{2}}{2}^{2}$
$\displaystyle=\frac{b(b-2)}{4}\binom{a}{2}+\binom{\frac{b}{2}}{2}^{2}$

which is the size of $\mathscr{M}$ in the second good candidate above.

_Case 2:_ If $e<\frac{b^{2}}{4}$, then

$\displaystyle\left\lvert\mathscr{M}\right\rvert$
$\displaystyle\leq\left[\binom{b}{2}-e\right]\binom{a}{2}+\frac{e}{16}(b-2)^{2}$
$\displaystyle=\binom{a}{2}\binom{b}{2}+e\left[\frac{1}{16}(b-2)^{2}-\binom{a}{2}\right].$

If $\frac{1}{16}(b-2)^{2}\leq\binom{a}{2}$, then
$\left\lvert\mathscr{M}\right\rvert\leq\binom{a}{2}\binom{b}{2}$ which is the
size of $\mathscr{M}$ in the first good candidate above.

If $\frac{1}{16}(b-2)^{2}>\binom{a}{2}$, then

$\displaystyle\left\lvert\mathscr{M}\right\rvert$
$\displaystyle<\binom{a}{2}\binom{b}{2}+\frac{b^{2}}{4}\left[\frac{1}{16}(b-2)^{2}-\binom{a}{2}\right]$
$\displaystyle=\binom{a}{2}\left[\binom{b}{2}-\frac{b^{2}}{4}\right]+\left(\frac{b(b-2)}{8}\right)^{2}$
($*$) $\displaystyle=\frac{b(b-2)}{4}\binom{a}{2}+\binom{\frac{b}{2}}{2}^{2}$

the same upper bound as in Case 1.

Clearly the maximum value of $\binom{a}{2}\binom{b}{2}$ is
$\binom{\frac{n}{2}}{2}\binom{\frac{n}{2}}{2}=\frac{n^{2}(n-2)^{2}}{64}=\frac{3}{8}\binom{n}{4}\frac{n(n-2)}{(n-1)(n-3)}$
(with a slight modification if $n$ is odd).

######  Lemma 8.3.

If $n$ is even and $x,y$, and $z$ are nonnegative integers such that
$x+y+z=n$, then the maximum value of

($**$)
$\binom{x}{2}\binom{y}{2}+\binom{x}{2}\binom{z}{2}+\binom{y}{2}\binom{z}{2}$

is $\binom{\frac{n}{2}}{2}^{2}$.

###### Proof.

This function counts the number of induced copies of $K_{2,2}$ in a complete
tripartite graph with parts $X,Y,$ and $Z$ with part sizes $x,y,$ and $z$,
respectively, subject to the constraint $x+y+z=n$. In [7], it was shown that
for all $n\geq 4$ the maximum number of induced copies of $K_{2,2}$ in any
graph is $\binom{\frac{n}{2}}{2}^{2}$. ∎

If $x=a$ and $y=z=\frac{b}{2}$, then ($**$ ‣ 8.3) reduces to (8.1), so the
maximum of (8.1) occurs when $a=0$ and $b=n$ and is equal to
$\frac{3}{8}\binom{n}{4}\frac{n(n-2)}{(n-1)(n-3)}$. Hence, $\frac{3}{8}$ is an
upper bound for $\operatorname{\mathit{\lambda}_{\rm local(out)}}(Y)$ and
$\operatorname{\mathit{\lambda}_{\rm local(in)}}(Y)$, so
$\frac{3}{8}\leq\lambda(Y,4)\leq\operatorname{\mathit{\lambda}_{\rm
local}}(Y,4)\leq\frac{3}{8}$.

∎

######  Theorem 8.4.

If $Z$ is the configuration $\\{0000,1100,1010,0110\\}$ in $Q_{4}$ (see Figure
7), then $\lambda(Z,4)=\frac{1}{2}$.

Figure 7. The configuration $Z$ for Theorem 8.4.

###### Proof.

The construction to show $\lambda(Z,4)\geq\frac{1}{2}$ is similar to the one
for $Y$ in Theorem 8.1. Partition $[n]$ into sets $A$ and $B$ of size
$\left\lceil\frac{n}{2}\right\rceil$ and $\lfloor\frac{n}{2}\rfloor$ and let
$S$ be the set of all veertices in $Q_{n}$ given by binary $n$-tuples with
even weight in both $A$ and $B$. This gives a good $Q_{4}$ for each $Q_{4}$
with three flip bits in $A$ and one in $B$ or one flip bit in $A$ and three in
$B$. In the limit as $n$ goes to infinity,
$\frac{4}{16}+\frac{4}{16}=\frac{1}{2}$ of the $Q_{4}$’s will be “good”, so
$\lambda(H,4)\geq\frac{1}{2}$.

For the upper bound, suppose $\emptyset\in S$ and let $\mathscr{M}$ be the set
of good $Q_{4}$s containing $\emptyset$. We define a graph $G_{S}$ with
$V(G_{S})=[n]$ and $E(G_{S})=\\{xy:\emptyset,xy,yz,xz$ are the vertices in $S$
of some $M\in\mathscr{M}$ for some $z\in[n]\\}$. If $x,y,z,w$ are the
coordinates of a good $Q_{4}$ where $\emptyset,xy,yz,xz$ are the vertices in
$S$, then $wx,wy,wz$ are not in $E(G_{S})$, so $\\{w,x,y,z\\}$ induces $K_{3}$
plus an isolated vertex in $G_{S}$. Since this is the complement of $K_{1,3}$,
$\operatorname{\mathit{\lambda}_{\rm local(in)}}(H,4)=i(K_{1,3})=\frac{1}{2}$.

Now suppose $\emptyset\not\in S$. Let $A=\\{i\in[n]:i\in S\\}$,
$B=[n]\setminus A$, $\left\lvert A\right\rvert=a$, $\left\lvert
B\right\rvert=b$. Let $\mathscr{M}$ be the set of all good $Q_{4}$s containing
$\emptyset$. If $M\in\mathscr{M}$ then the four vertices of $M$ in $S$ have
the structure of Type I, Type II, or Type III in Figure 8 (where $i,j,k\in A$
and $w,x,y,z\in B$).

Type I$i$$j$$ijk$$k$

Type II$i$$ixy$$iyz$$ixz$

Type III$wx$$wy$$wxyz$$wz$

Figure 8. The three structures of vertices in $S$ for $M\in\mathscr{M}$ where
$\emptyset\not\in S$.

Define a graph $G$ by $V(G)=A\cup B$ and $E(G)=\\{ix:i\in A\textrm{ and
}\allowbreak x\in B\\}\cup\allowbreak\\{wx:wx,\allowbreak wy,\allowbreak
wz,\allowbreak wxyz$ are the vertices in $S$ of a Type III $M\in\mathscr{M}$
for some $y,z\in B\\}$. If $M$ is a Type I $Q_{4}$ with coordinates $i,j,k,x$,
then $\\{i,j,k,x\\}$ induces $K_{1,3}$ in $G$. If $M$ is a Type III $Q_{4}$
with vertices $wx,wy,wz,wxyz$ in $S$, then $\\{w,x,y,z\\}$ induces $K_{1,3}$
in $G$, since $xy,yz$ and $xz$ are not edges in $G$. That means
$\\{i,x,y,z\\}$ induces $K_{1,3}$ in $G$ since $ix,iy,iz$ are all edges. It
also means that the number of Type II $Q_{4}$s in $\mathscr{M}$ is at most the
number of $K_{1,3}$s in $G$ with one vertex in $A$ and three vertices in $B$,
since if $i,x,y,z$ are the coordinates of a Type II M, then $xy,yz,$ and $xz$
are all non-edges. Thus $\left\lvert\mathscr{M}\right\rvert$ is at most the
number of $K_{1,3}$s in $G$ which have precisely 3,1, or 0 vertices in $A$, so
is certainly at most the maximum number of $K_{1,3}$s in a graph with $n$
vertices. Hence $\operatorname{\mathit{\lambda}_{\rm local(out)}}(Z,4)\leq
i(K_{1,3})=\frac{1}{2}$, and
$\frac{1}{2}\leq\lambda(Z,4)\leq\operatorname{\mathit{\lambda}_{\rm
local}}(Z,4)\leq\frac{1}{2}$. ∎

We remark that since the only optimizing host graph which maximizes the number
of induced $K_{1,3}$ subgraphs is complete bipartite, the graph $G$ defined
above can only be optimal if either there are no Type III $M\in\mathscr{M}$
(so both $A$ and $B$ are independent sets), or $A=\emptyset$, each
$M\in\mathscr{M}$ is Type III, and $B$ induces a complete bipartite graph with
parts asymptotically, but not exactly equal in size (Remark 4 in Section 4).

##  9\. Open Problems and conjectures

In this section, we will restate our conjectures stated earlier in the paper,
state some other ones, and discuss some other problems for possible further
research.

###  9.1. Conjectures on $d$-cube density

Baber’s flag algebra upper bounds are within $10^{-9}$ of our lower bounds for
five of the configurations in $Q_{3}$, so we conjecture equality holds for all
of them.

######  Conjecture 9.1.

The lower bounds for $W_{7},W_{8},W_{9},W_{10}$, and $W_{12}$ given in Table 2
are, in fact, the exact 3-cube densities for these configurations.

It follows from Theorem 5.1 that if a configuration $H$ in $Q_{d}$ is not
layered, then $\lambda(H,d)<1$. It is easy to show that the only layered
configurations with $d$-cube density equal to 1 are the trivial ones and that
for each $d\geq 3$, there is a layered configuration in $Q_{d}$ with $d$-cube
density equal to $\frac{2}{3}$. We have an example of a configuration with
5-cube density equal to at least the inducibility of $K_{2,3}$, which is
$\frac{5}{8}$ (configuration $E(5,2)$ in Section 9.2).

######  Conjecture 9.2.

If $H$ is a configuration in $Q_{d}$ such that $\frac{5}{8}<\lambda(H,d)<1$
then either

  1. (1)

$H$ is layered and $\lambda(H,d)=\frac{2}{3}$ or

  2. (2)

$d=3$, $H=W_{2}$, and $\lambda(H,d)=\frac{3}{4}$.

###  9.2. Another Inifinite Family

Let $d$ and $i$ be positive integers with $1\leq i<d$. We define the
configuration $E(d,i)$ in $Q_{d}$ by

$E(d,i)=\left\\{(x_{1},x_{2},\ldots,x_{d})\in
V_{d}{\bigg{|}}\sum_{j=1}^{i}x_{j}\textrm{ and }\sum_{j=i+1}^{d}x_{j}\textrm{
are both even}\right\\}.$

So two weights must be even for each vertex in $E(d,i)$, whereas only one must
be even for each vertex in the configuration $H(d,i)$ of Section 6. Note that
$E(d,d-i)$ is an exact copy of $E(d,i)$ for all $i$ and $d$. We remark that
$E(3,1)$ is the configuration $W_{2}$ in $Q_{3}$ and $E(4,1)$ and $E(4,2)$ are
the configurations $Z$ and $Y$ in $Q_{4}$ of Section 8.

To get a lower bound for $\lambda(E(d,i),d)$ we let $x$ be a real number in
$\left(0,\frac{1}{2}\right]$, $m=\left\lceil
xn\right\rceil\in\left[1,\frac{n}{2}\right]$, and we define a configuration
$S_{x}$ in $Q_{n}$ by $S_{x}=$ $\\{(x_{1},x_{2},\ldots,x_{n})\in
V_{n}:\sum_{j=1}^{m}x_{j}$ and $\sum_{j=m+1}^{n}x_{j}$ are both even$\\}$.
Then any sub-$d$-cube of $Q_{n}$ with precisely $i$ or $d-i$ flip bits in
$[1,m]$ is “good”, and in the limit as $n$ goes to infinity this is a fraction
$f_{d,i}(x)=\binom{d}{i}\left[x^{i}(1-x)^{d-i}+x^{d-i}(1-x)^{i}\right]$ of all
sub-$d$-cubes. The function $f_{d,i}(x)$ is also the fraction of subsets of
$d$ vertices of $K_{m,n-m}$ which induce $K_{i,d-i}$. As shown in [7],
$i(K_{i,d-i})$ is the maximum value of $f_{d,i}(x)$ where
$x\in\left(0,\frac{1}{2}\right]$, so we have shown the following.

######  Proposition 9.3.

For all integers $i$ and $d$ with $1\leq i<d$,
$\operatorname{\mathit{\lambda}}(E(d,i),d)\geq i(K_{i,d-i})$.

In [7], Brown and Sidorenko determined for which complete bipartite graphs
$K_{s,s+t}$ the optimizing host complete bipartite graph on $n$ vertices, as
$n$ goes to infinity, can be taken to be asymptotically equibipartite. It
follows from their work that for $i\in\left[1,\frac{d}{2}\right]$,
$f_{d,i}(x)$ is maximized when $x=\frac{1}{2}$ if and only if
$i\geq\frac{d-\sqrt{d}}{2}$. So $\lambda(E(4,1),4)\geq
f_{4,1}\left(\frac{1}{2}\right)=i(K_{1,3})=\frac{1}{2}$ and
$\operatorname{\mathit{\lambda}}(E(4,2),4)\geq
f_{4,2}\left(\frac{1}{2}\right)=i(K_{2,2})=\frac{3}{8}$ (and Theorems 8.1 and
8.4 say that equality holds).

However, $f_{5,1}(x)$ is maximized when $x=\frac{3-\sqrt{3}}{6}$, so
$\operatorname{\mathit{\lambda}}(E(5,1),5)\geq
f_{5,1}\left(\frac{3-\sqrt{3}}{6}\right)=i(K_{1,4})=\frac{5}{12}$. We believe
equality holds.

######  Conjecture 9.4.

Equality holds in Proposition 9.3.

###  9.3. One Vertex in $Q_{d}$

Let $U_{d}$ be the configuration in $Q_{d}$ consisting of a single vertex. We
have been unable to determine $\lambda(U_{d},d)$ for any $d\geq 2$. Since
$U_{d}$ is a layered configuration (with weight set $\\{0\\}$), it makes sense
to use a layered configuration $S$ in $Q_{n}$ to get a construction for a
lower bound. Letting $S$ be the layered configuration 0 mod $(d+1)$ in $Q_{n}$
shows that $\lambda(U_{d},d)\geq\frac{2}{d+1}$. This is the best lower bound
we have for $\lambda(U_{2},2)$ ($Z_{2}$ in Table 1) and $\lambda(U_{3},3)$
($W_{3}$ in Table 2). The flag algebra upper bounds are somewhat larger:
$\frac{2}{3}\leq\operatorname{\mathit{\lambda}}(U_{2},2)\leq.685714$ and
$\frac{1}{2}\leq\operatorname{\mathit{\lambda}}(U_{3},3)\leq.610043$.

A Hamming perfect code can be used to construct a non-layered configuration
$S$ in $Q_{n}$ which produces a lower bound for
$\operatorname{\mathit{\lambda}}(U_{3},3)$ which is almost as good. Let $H$ be
the configuration in $Q_{7}$ consisting of the 16 vectors in the length 7
dimension 4 Hamming perfect code. (One relization of it is $\emptyset$ (the 0
vector), the 7 incidence vectors of a Fano plane, say the 7 cyclic
permutations of 124, and the complements of these 8 vectors). The minimum
distance in this code is 3, and each vector is Hamming distance 3 from 7 other
vectors. So the number of sub-3-cubes which contain two vertices of $H$ is
$\frac{1}{2}\cdot 16\cdot 7=56$. Since the average number of vertices of $H$
in a sub-3-cube is $\frac{2^{4}}{2^{7}}\cdot 8=1$, there must be 56
sub-3-cubes with no vertices of $H$. Hence there are $\binom{7}{3}\cdot
2^{4}-112=448$ sub-3-cubes which have an exact copy of $U_{3}$, a fraction
$\frac{448}{560}=\frac{4}{5}$ of the sub-3-cubes of $Q_{7}$. If $n$ is large
and $S$ is a blow up of $H$ in $Q_{n}$ (equipartition of $[n]$ into 7 parts)
then a sub-3-cube of $Q_{n}$ with flip bits in different parts will have an
exact copy of a sub-3-cube of the $Q_{7}$ (with configuration $H$), and
$\frac{4}{5}$ of these will have an exact copy of $U_{3}$. Hence
$\lambda(U_{3},3)\geq\frac{7}{7}\cdot\frac{6}{7}\cdot\frac{5}{7}\cdot\frac{4}{5}=\frac{24}{49}$,
not quite as good as the lower bound $\frac{1}{2}$ using the layered
configuration 0 mod 4 in $Q_{n}$.

Another way to get a lower bound for
$\operatorname{\mathit{\lambda}}(U_{d},d)$ is to let $R$ be the configuration
in $Q_{n}$ obtained by the following random process: for each $v\in V_{n}$,
put $v\in R$ with (uniform independent) probability $\frac{1}{2^{d}}$. The
probability that a sub-$d$-cube has an exact copy of $U_{d}$ is
$2^{d}\cdot\frac{1}{2^{d}}\cdot\left(\frac{2^{d}-1}{2^{d}}\right)^{2^{d}-1}$
so $\lambda(U_{d},d)\geq\left(\frac{2^{d}-1}{2^{d}}\right)^{2^{d}-1}$. Of
course this is larger than $\frac{1}{e}$ and, as noted in Section 6, is equal
to $\frac{1}{e}$ in the limit as $d$ goes to infinity. This lower bound is
larger than $\frac{2}{d+1}$ if $d>4$.

######  Conjecture 9.5.

If $d\geq 5$ then
$\lambda(U_{d},d)=\left(\frac{2^{d}-1}{2^{d}}\right)^{2^{d}-1}$.

This has the same flavor as a special case of the edge-statistics conjecture
of Alon et al. [1] which says (though formulated differently) that the limit
as $k$ goes to infinity of the inducibility of a graph with $k$ vertices and
one edge is $\frac{1}{e}$.

## References

  * [1] N. Alon, D. Hefetz, M. Krivelevich, and M. Tyomkyn, _Edge-statistics on large graphs_ , Combinatorics, Probability and Computing 29 (2020), no. 2, 163–189.
  * [2] N. Alon, A. Krech, and T. Szabó, _Turán’s theorem in the hypercube_ , SIAM Journal on Discrete Mathematics 21 (2007), 66–72.
  * [3] N. Alon, R. Radoičić, B. Sudakov, and J. Vondrák, _A Ramsey-type result for the hypercube_ , Journal of Graph Theory 23 (2006), 196–208.
  * [4] M. Axenovich and R. Martin, _A note on short cycles in a hupercube_ , Discrete Mathematics 306 (2006), 2212–2218.
  * [5] R. Baber, private communication, 2014.
  * [6] B. Bollobas, C. Nara, and S. Tachibana, _The maximal number of induced complete bipartite graphs_ , Discrete Mathematics 62 (1986), no. 3, 271–275.
  * [7] J. I. Brown and A. Sidorenko, _The inducibility of complete bipartite graphs_ , Journal of Graph Theory 18 (1994), no. 6, 629–645.
  * [8] F. R. K. Chung, _Subgraphs of the hypercube containing no small even cycles_ , Journal of Graph Theory 16 (1992), 273–286.
  * [9] M. Conder, _Hexagon-free subgraphs of hypercubes_ , Journal of Graph Theory 17 (1993), 477–479.
  * [10] D. Conlon, _An extremal theorem in the hypercube_ , Electronic Journal of Combinatorics 17 (2010), R111.
  * [11] C. Even-Zohar and N. Linial, _A note on the inducibility of 4-vertex graphs_ , Graphs and Combinatorics 31 (2015), 1367–1380.
  * [12] G. Exoo, _Dense packings of induced subgraphs_ , Ars Combinatoria 22 (1986), 5–10.
  * [13] Z. Füredi and L. Ozkahya, _On 14-cycle-free subgraphs of the hypercube_ , Combinatorics, Probability, and Computing 18 (2009), 725–729.
  * [14] J. Goldwasser and R. Hansen, _Maximum density of vertex-induced perfect cycles and paths in the hypercube_ , Discrete Mathematics 344 (2021).
  * [15] J. Goldwasser, B. Lidicky, R. Martin, D. Offner, J. Talbot, and M. Young, _Polychromatic colorings on the hypercube_ , Journal of Combinatorics 9 (2018), 631–657.
  * [16] J. Goldwasser and J. Talbot, _Vertex Ramsey problems in the hypercube_ , SIAM Journal on Discrete Mathematics 26 (2012), 838–853.
  * [17] A. W. Goodman, _Triangles in a complete chromatic graph with three colors_ , Discrete Mathematics 57 (1985), no. 3, 225–235.
  * [18] J. Hirst, _The inducibility of graphs on four vertices_ , Journal of Graph Theory 75 (2014), no. 3, 231–243.
  * [19] J. R. Johnson and J. Talbot, _Vertex turan problems in the hypercube_ , Journal of Combinatorial Theory Series A 117 (2010), 454–465.
  * [20] K. A. Johnson and R. Entringer, _Largest induced subgraphs of the n-cube that contain no 4-cycles_ , Journal of Combinatorial Theory Series B 46 (1989), no. 3, 346–355.
  * [21] E. A. Kostochka, _Piercing the edges of the n-dimensional unit cube_ , Diskret. Analiz Vyp 28 (1976), no. 55-64, 223.
  * [22] N. Pippenger and M. C. Golumbic, _The inducibility of graphs_ , Journal of Combinatorial Theory Series B 19 (1975), 189–203.
  * [23] M. S. Rahman, M. Kaykobad, and Md. T. Kaykobad, _Bipartite graphs, hamiltonicity and $\mathscr{Z}$ graphs_, Electronic Notes in Discrete Mathematics 44 (2013), 307–312.
  * [24] E. Vaughan, _Flagmatic: a tool for researchers in extremal graph theory (version 2.0)_ , 2013, http://flagmatic.org/graph.html.