# Retrieving non-stabilizerness with Neural Networks

Antonio Francesco Mello  International School for Advanced Studies (SISSA),
34136 Trieste, Italy  Guglielmo Lami  International School for Advanced
Studies (SISSA), 34136 Trieste, Italy  Laboratoire de Physique Théorique et
Modélisation, CY Cergy Paris Université, CNRS, F-95302 Cergy-Pontoise, France
Mario Collura  International School for Advanced Studies (SISSA), 34136
Trieste, Italy  INFN Sezione di Trieste, 34136 Trieste, Italy

###### Abstract

Quantum computing’s promise lies in its intrinsic complexity, with
entanglement initially heralded as its hallmark. However, the quest for
quantum advantage extends beyond entanglement, encompassing the realm of
nonstabilizer (magic) states. Despite their significance, quantifying and
characterizing these states pose formidable challenges. Here, we introduce a
novel approach leveraging Convolutional Neural Networks (CNNs) to classify
quantum states based on their magic content. Without relying on a complete
knowledge of the state, we utilize partial information acquired from
measurement snapshots to train the CNN in distinguishing between stabilizer
and nonstabilizer states. Importantly, our methodology circumvents the
limitations of full state tomography, offering a practical solution for real-
world quantum experiments. In addition, we unveil a theoretical connection
between Stabilizer Rényi Entropies (SREs) and the expectation value of Pauli
matrices for pure quantum states. Our findings pave the way for experimental
applications, providing a robust and accessible tool for deciphering the
intricate landscape of quantum resources.

## Introduction. –

The intrinsic exponential complexity of quantum systems plays a key role
within the realm of quantum computation, allowing for the possibility to
overcome certain limitations of the classical counterpart in solving a variety
of problems. Entanglement has been first identified as the foremost feature
encoding this complexity and has henceforth been extensively studied as a
crucial quantum resource [1, 2, 3, 4]. Nevertheless, quantum advantage does
not rely uniquely on entanglement. Indeed, Gottesman-Knill theorem shows that
many quantum protocols encompassing highly entangled states can be efficiently
simulated with classical resources [5, 6, 7]. Those states, referred to as
stabilizer states, are defined through the action of the Clifford group, which
maps Pauli strings into Pauli strings, on the computational basis state
$\ket{0\dots 0}$.

Consequently, entanglement is not the sole resource playing a role in
determining the potential of quantum computing. Nonstabilizerness, or quantum
magic, has in fact been introduced as the quantity accounting for the
difficulty involved in simulating a quantum non Clifford circuit on a
classical device. Several measures of nonstabilizerness, such as stabilizer
nullity [8] and robustness of magic [9, 10] have been proposed. These
quantities, however, are generally difficult to compute even numerically since
often require solving challenging optimization problems. More recently, the
Stabilizer Rényi Entropies (SREs) [11] have been introduced, attracting
significant attention due to the relative ease with which they can be
calculated [12, 13, 14, 15, 16, 17, 18, 19] and to their suitability for
experimental measurements [20, 21]. SREs possess good properties, but cannot
be considered as genuine magic monotones for Rényi index $>2$ (since they are
not non-increasing under projective measurements [19]). Accordingly,
considerable endeavours are still devoted to trying to find nicely behaved and
readily evaluable quantities enabling a profound characterization of this
resource.

Quantum mechanical curse of dimensionality indeed poses a significant obstacle
when dealing with such problems even when the task of quantification boils
down to classification. In other words, even distinguishing between stabilizer
and nonstabilizer states can turn to be complicated especially for approaches
that require the full knowledge of quantum states (tomography).

In recent years, Neural Networks (NNs) have emerged as valuable instruments in
various fields of physics, ranging from condensed matter and quantum physics
[22] to high-energy [23]. Among the others, several efforts have been focused
on their employment in phases of matter classification [24, 25, 26, 27] and
entanglement detection, both in the context of supervised [28] and
unsupervised learning [29]. Another notable example concerns NN ansatz for the
many-body quantum problem [30, 31, 32, 33]. Recently the problem of
determining entanglement properties of a quantum state with classical
artificial NN has been addressed in several works. However, it is often
assumed to possess a complete knowledge of the state [34], thus requiring a
full state tomography that is experimentally highly demanding for large
systems [35, 36, 37]. In a realistic setup, nonetheless, the state
$\ket{\psi}$ of the system is known only through a limited amount of
measurements outcomes.

In this work, we introduce a novel approach to classify quantum states based
on their magic content. For this purpose, we leverage a Convolutional Neural
Network (CNN) to identify nonstabilizer states starting from a partial
knowledge about them. In particular, we train the NN with a large set of
measurement outcomes (snapshots) obtained from simple product states. Each
sequence of snapshots is categorized as ’stabilizer’ (0) or ’non-stabilizer’
(1) based on the state’s nature. Subsequently, the NN is trained to function
as a binary classifier following the supervised learning approach, and its
performance is assessed across diverse scenarios. Notably, the model’s
predictions are found to be robust under Clifford evolution, proving reliable
even in presence of entanglement. This approach hence provides an accessible
and versatile black-box tool being remarkably suitable for experimental
applications. As a side effect we also establish a theoretical direct
connection between SREs and the expectation value of a string of Pauli
matrices for a pure quantum state.

## Preliminaries. –

Let us consider a $N$-qubits system. The Pauli group $\mathcal{P}_{N}$ is
defined as the set of all $N$ Pauli strings taken with proper phase factors:
$\mathcal{P}_{N}=\\{\pm\left(i\right)\\{\sigma^{0},\sigma^{1},\sigma^{2},\sigma^{3}\\}^{\otimes
N}\\}$, where we denote by $\\{\sigma^{\alpha}\\}\
\left(\alpha=0,1,2,3\right)$ the set of Pauli matrices
($\sigma^{0}=\mathbb{1}$). The $N$-qubits Clifford group is the normalizer of
$\mathcal{P}_{N}$, meaning that $\mathcal{C}_{N}=\\{V\in
U_{2^{N}}|V\mathcal{P}_{N}V^{\dagger}=\mathcal{P}_{N}\\}$ [38].
$\mathcal{C}_{N}$ is generated by the set of unitaries $\\{CNOT,H,S\\}$ [7].
The latter, nonetheless, does not constitute a universal set for quantum
computation. Indeed, in order to achieve universality this set needs to be
complemented through the addition of the non Clifford $T=\sqrt{S}$ gate [38].
Given a subgroup $G$ of $\mathcal{P}_{N}$, a stabilizer subspace can be
defined as $S_{G}=\\{\ket{\psi}\text{ s.t. }M\ket{\psi}=\ket{\psi}\forall M\in
G\\}$. If $S_{G}$ is one dimensional, it identifies a single state which is
named stabilizer state. As mentioned, starting from the reference basis state
$\ket{0\dots 0}$ which is a stabilizer, Clifford circuits ensure classically
simulable states [39]. A state $\ket{\psi}$ is indeed a stabilizer if and only
if $\ket{\psi}=C|0\dots 0\rangle$ with $C\in\mathcal{C}_{N}$.

In the quest for experimentally viable techniques to design magic witnessess
relying on readily available state specifics, measurements stand out as the
most natural operations to be performed on quantum systems and CNNs as
promising candidates to handle the classification task.

Notably SREs, which are given by
$M_{\alpha}(\ket{\psi})=\frac{1}{1-\alpha}\log{\left(\sum_{\pmb{\sigma}\in\mathcal{P}_{N}}\frac{1}{2^{N}}\bra{\psi}\pmb{\sigma}\ket{\psi}^{2\alpha}\right)}$
[11], can be seen as the Rényi Entropies for the probability distribution on
the set of Pauli strings given by

$\displaystyle\Pi_{\rho}\left(\pmb{\sigma}\right)=\frac{1}{2^{N}}\textnormal{Tr}\left[\rho\,\pmb{\sigma}\right]^{2}$
(1)

with $\pmb{\sigma}$ being a string of Pauli matrices and
$\rho=|\psi\rangle\langle\psi|$ a pure state.

As a consequence, in order to enhance the deployed neural network with
relevant features and achieve precise state classification, we employ two
alternative methods for assessing information from the state:

  1. 1.

by sampling the many-body wave function according to its probability in the
computational basis;

  2. 2.

by sampling the state over the Pauli string configurations according to
$\Pi_{\rho}\left(\pmb{\sigma}\right)$.

Figure 1: $a)$ We consider the case of a pure quantum state $\ket{\psi}$ on a
$N$-qubits system, undergoing either projective measurements of the $z$
component of the spin $S^{z}=\frac{1}{2}\sigma^{3}$ or in the Pauli basis
$\\{\sigma^{\alpha}\\}$. $b)$ A Convolutional Neural Network (CNN) is employed
to process the results of projective measurements. The convolutional layer
outputs are then flattened and passed as input to a feedforward neural network
with fully connected layers, ultimately generating the prediction outcome.

## Network technicalities. –

Similarly to Ref. [40], we use a CNN consisting of three convolutional layers
with $16,32,64$ learnable filters respectively and ReLU activations. Input
shape and specifics vary according to the chosen measurement basis (see
Methods). The output volume is flattened and put through a sigmoid classifier.
Its outcomes, as a standard practice, are interpreted as probabilities for the
states to be stabilizer or not. The CNN is trained with Adam optimizer [41]
and binary crossentropy is chosen as loss function. Overfitting is prevented
by implementing L2 and dropout regularization schemes. Hyperparameters,
including the number of epochs and the batch size, are properly tuned to speed
learning up.

## Methods 1 - computational basis sampling. –

Let $\ket{\psi}$ be the normalized state for a $N$-qubits system. The total
Hilbert space is $\mathcal{H}=\bigotimes_{j=1}^{N}\mathcal{H}_{j}$, where
$\mathcal{H}_{j}$ is the local Hilbert space spanned by the eigenstates
$\\{\ket{0},\ket{1}\\}$ of the Pauli
$\sigma^{3}=\textnormal{diag}\left(1,-1\right)$. An orthonormal basis for
$\mathcal{H}$ is $\\{\ket{s_{1}\dots s_{N}}\\}=\\{\ket{\pmb{s}}\\}$ with
$s_{j}\in\\{0,1\\}$, therefore the state of the system can be written as
$\ket{\psi}=\sum_{\pmb{s}}\psi_{\pmb{s}}\ket{\pmb{s}}$. Our first
investigation is based on sampling $\mathcal{N}$ configurations from the state
$\ket{\psi}$ according to the probability distribution given by
$|\psi_{\pmb{s}}|^{2}$. The snapshots of the analyzed system correspond to
real measurements in the computational basis on each qubit as depicted in Fig.
1 $a)$. After collecting a batch of samples, they can be arranged in a
$\mathcal{N}\times N$ binary matrix, with different rows corresponding to
different snapshots, and associated to the respective source state. The
training dataset consists of random product states and random tensor products
of single qubit stabilizer states, thus enhancing the feasible applicability
of the proposed protocol. Snapshots originating from random product states are
labelled as magic states, whereas the others are labelled as stabilizer
states. As shown in Fig. 1 $b)$, the core of the approach lies in using the
sampled one-channel images to feed a CNN.

After completing the training process, a central test of the efficient
learning of the distinctive features of nonstabilizerness is conducted by
evaluating the model’s performance on states undergoing random Clifford
evolutions of increasing depth. Since quantum magic is Clifford invariant, a
well trained model is expected to produce robust predictions - at least for
shallow circuits - on snapshots of states subject to Clifford dynamics.

We apply such protocol to a system of size $N=18$ qubits. Specifically, we
build a training set consisting of $10000$ product states, equally divided
between stabilizer and nonstabilizer. After sampling $\mathcal{N}=1000$
configurations for each state, we arrange them in $\mathcal{N}\times N$ B/W
images and feed the CNN. Learning is completed successfully, achieving
satisfactory accuracy. Fig. 2 shows the performance of the CNN on samples
deriving from product states undergoing random Clifford circuits of increasing
depth $0pt$ (with $0pt=0$ corresponding to product states different from the
ones seen during training). The number of samples and of evolving states, as
well as the equal partitioning between categories, are left unchanged.

Figure 2: CNN’s average predictions on $m=5000$ magic and stabilizer product
states undergoing random Clifford evolution of increasing depth $0pt$ for a
$N=18$ qubits system sampled in the computational basis. Error bars are
evaluated from the standard deviation of the average prediction $\bar{p}$.
Inset: average predictions as function of the density of magic of the input
states. Higher values of $M_{2}/N$ favour the model in the classification
task, specifically for larger depths $0pt$.

The model is found to correctly generalize to unseen snapshots sampled from
new product states ($0pt=0$). A more remarkable result, however, lies in the
robustness of the network’s classification under random Clifford evolution.
The average predictions in fact prove reasonably reliable also for $0pt>0$,
allowing to assess the quantum resource content even of arbitrarily entangled
states. Focusing on second order SREs, the inset in Fig. 2 shows that higher
values of $M_{2}$ in the sampled states favour the CNN in correctly
classifying them.

Computational basis snapshots can also be analyzed without necessarily relying
on a neural network, as will be discussed in the following paragraph.

## Pauli averages as nonstabilizerness witness.–

For any stabilizer $\ket{\psi}$ and $\pmb{\sigma}\in\mathcal{P}_{N}$ it holds
$\bra{\psi}\pmb{\sigma}\ket{\psi}\in\\{0,\pm 1\\}$ [42]. If snapshots in the
computational basis are provided, one can estimate the expectation values of
$\sigma^{3}_{j}$ through local sample averages. A naïve classifier can operate
by verifying whether these estimators for each $j$ are compatible with $0,\pm
1$ within the statistical uncertainty (resulting in the classification
’stabilizer’), or if they do not (resulting in the classification ’non-
stabilizer’). Yet, there are states which are misclassified by this tool, e.g.
those of the form
$\ket{\psi}=\otimes^{N}_{j=1}\frac{1}{\sqrt{2}}\left[|0\rangle+e^{i\phi}|1\rangle\right]$.
One approach is to apply a shallow Clifford circuit to the state, and to
repeat the classification with snapshots from the new state. This effectively
allows access to $\bra{\psi}\pmb{\sigma}\ket{\psi}$, where
$\pmb{\sigma}=U^{{\dagger}}\sigma^{3}_{j}U$, and $U\in\mathcal{C}_{N}$. This
classifier, operating through the evaluation of $U^{\dagger}\sigma^{3}_{j}U$,
demonstrates remarkable performance by achieving nearly perfect classification
accuracy, surpassing traditional neural networks. Moreover, it’s possible to
establish a direct connection between the expectation values of Pauli strings
$\pmb{\sigma}$, and the concept of non-stabilizerness. In fact, for any
$\pmb{\sigma}\in\tilde{\mathcal{P}}_{N}=\mathcal{P}_{N}/U(1)$ with
$\pmb{\sigma}\neq\mathbb{1}^{\otimes N}$, one gets (see Supplemental Material
for details)

$\displaystyle\mathbb{E}_{U\in\mathcal{C}_{N}}\left[\left(\bra{\psi}U^{\dagger}\pmb{\sigma}U\ket{\psi}\right)^{4}\right]=\frac{1}{d+1}-\frac{d}{d^{2}-1}\,M_{\text{lin}}\left(\ket{\psi}\right),$
(2)

where $d=2^{N}$ and
$M_{\text{lin}}\left(\ket{\psi}\right)=1-d\lVert\Pi_{\rho}\rVert^{2}$ is the
stabilizer linear entropy linked to $M_{2}$ through
$M_{2}=-\log{\left(1-M_{\text{lin}}\right)}$, and we defined $\Pi_{\rho}$ as
the vector of probabilities in Eq. (1). Nevertheless, conducting experimental
assessments of $\bra{\psi}U^{\dagger}\pmb{\sigma}U\ket{\psi}$ remains
challenging, whether for classification purposes or for explicitly evaluating
Eq. (2). Clifford unitaries cannot in fact be applied to computational basis
snapshots and, although in principle Pauli strings transform easily under
elements of $\mathcal{C}_{N}$, computing their expectation value would in
general result in a costly procedure requiring the full state knowledge.

## Methods 2 - Pauli sampling. –

As seen, Pauli strings allow to directly handle the action of Clifford
unitaries. Hence the basis of Pauli matrices provides an alternative approach
to gain valuable insight regarding the magic content of quantum states. In
light of this, we expand our strategy to encompass a different setup, in which
$\mathcal{N}$ Pauli snapshots from the state $\rho=\ket{\psi}\bra{\psi}$ are
sampled according to $\Pi_{\rho}\left(\pmb{\sigma}\right)$. As shown in the
lower part of Fig. 1 a), the latter can in turn be regarded as $4-$channels
images, with each colour corresponding to a different Pauli matrix, that can
be used to feed our CNN. An important advantage of this strategy is that it
allows us to partially enforce Clifford invariance into the learning process.
The training dataset is indeed built starting from random product states and
random tensor products of single qubit stabilizer which are sampled in the
Pauli basis and evolved through $l$ Clifford layers. Contrarily to the
computational basis case, within this approach Clifford evolution can be
effectively performed on Pauli snapshots using [43], leveraging the tableau
formalism.

The CNN receives as input an array of shape $\mathcal{N}\times l\times N$
whose slices refer to different steps of the random Clifford evolution. In
other words, each instance presented to the architecture intrinsically
provides information about a portion of the Clifford orbit associated to the
initial product state. The employment of $3-$dimensional inputs allows to
extend further the testing process, accessing deeply evolved states.
Additionally, product states based learning along with handily implemented
Clifford evolution preserve the straightforward realization of the procedure.

In the context of this scheme, we consider $10000$ stabilizer and magic
product states for $N=8,12,14$ qubits systems and sample $\mathcal{N}=1000$
Pauli strings for each of them. In order to construct our training set, we let
these $N\times\mathcal{N}$ images evolve under $l=5$ Clifford layers, thus
resulting in the desired $\mathcal{N}\times l\times N$ inputs. In complete
analogy with the previous testing procedure, we evaluate the model’s
performance on samples collected from $10000$ product states evolved through
random Clifford circuits of increasing depth $0pt$ and on which $l=5$ random
Clifford layers are applied. Remarkably, the trained model is $l-$independent
since a global pooling layer is added before the final sigmoid classifier
[44]. In essence, once a set of snapshot has been sampled for a given state,
it can undergo an arbitrarily deep Clifford circuit before being passed to the
CNN.

Figure 3: CNN’s average predictions on $m=5000$ stabilizer and magic states
undergoing random Clifford evolution of increasing depth $0pt$ for $N=8,12,14$
qubits systems sampled in the Pauli basis. Input volumes are obtained through
$l=5$ Clifford layers evolution , but the same NN can be employed for deeper
evolutions. Blue and orange lines respectively refer to magic and stabilizer
states. Error bars are evaluated from the standard deviation of the average
prediction $\bar{p}$.

Fig. 3 shows that even for large systems, where in principle a proper
description demands substantial information, the CNN exhibits satisfactory
generalization capabilities. Besides the noteworthy predictions for $0pt=0$
(test set of unseen product states), it also yields appropriate outcomes on
deeply Clifford evolved and entangled states, thereby strengthening the
validity of such protocol.

## Conclusions and outlook. –

We introduced a novel approach to deal with nonstabilizer states
classification. In our protocol, readily obtainable snapshots of random
quantum states are used to train a CNN. We showed that snapshots in the
computational basis are applicable in the context of both training a neural
network and devising a naïve magic witness based on the evaluation of
$\bra{\psi}\sigma^{3}_{j}\ket{\psi}$. Although the latter is hindered by the
requirement of complete wavefunction knowledge for applying Clifford layers,
further investigation has been conducted. Indeed, an analytical relation
between expectation values of a Pauli string and SREs for a pure quantum state
has been derived. Additionally, the challenge of applying Clifford unitaries
has been circumvented by resorting to sampling the state in the Pauli basis.
We have hence shown that a CNN can be trained with a limited amount of
information on simple states and employed as a black-box tool to single out
magic states across various scenarios. Starting from product states, the CNN
has in fact been able to provide reliable predictions also on entangled
states. Furthermore, the choice of Pauli basis allowed to explore sufficiently
large portions of the Clifford orbit.

Our work sets the stage for novel and cost effective studies on quantum
resources, bridging the gap between numerical computations and experimental
applications. The protocol may be used to efficiently gain a deeper insight on
quantum states in different settings. Moreover, the classification task may be
extended to a quantification one.

## Acknowledgments. –

We are particularly grateful to M. Dalmonte, E.Tirrito and P. Tarabunga for
inspiring discussions. This work was supported by the PNRR MUR project
PE0000023-NQSTI, and by the PRIN 2022 (2022R35ZBF) - PE2 - “ManyQLowD”. G.L.
were partially founded by ANR-22-CPJ1-0021-01.

## References

  * Cirac and Zoller [2012] J. I. Cirac and P. Zoller, Nature physics 8, 264 (2012).
  * Eisert  _et al._ [2010] J. Eisert, M. Cramer, and M. B. Plenio, Reviews of modern physics 82, 277 (2010).
  * Houck  _et al._ [2012] A. A. Houck, H. E. Türeci, and J. Koch, Nature Physics 8, 292 (2012).
  * Preskill [2012] J. Preskill, “Quantum computing and the entanglement frontier,” (2012), arXiv:1203.5813 [quant-ph] .
  * Gottesman [1997] D. Gottesman, “Stabilizer Codes and Quantum Error Correction,”  (1997).
  * Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Physical Review A 70 (2004), 10.1103/physreva.70.052328.
  * Gottesman [1998a] D. Gottesman, Phys. Rev. A 57, 127 (1998a).
  * Beverland  _et al._ [2020] M. Beverland, E. Campbell, M. Howard, and V. Kliuchnikov, Quantum Science and Technology 5, 035009 (2020).
  * Heinrich and Gross [2019] M. Heinrich and D. Gross, Quantum 3, 132 (2019).
  * Howard and Campbell [2017] M. Howard and E. Campbell, Phys. Rev. Lett. 118, 090501 (2017).
  * Leone  _et al._ [2022] L. Leone, S. F. E. Oliviero, and A. Hamma, Phys. Rev. Lett. 128, 050402 (2022).
  * Lami and Collura [2023] G. Lami and M. Collura, Phys. Rev. Lett. 131, 180401 (2023).
  * Lami and Collura [2024] G. Lami and M. Collura, “Learning the stabilizer group of a Matrix Product State,” (2024), arXiv:2401.16481 [quant-ph] .
  * Rattacaso  _et al._ [2023] D. Rattacaso, L. Leone, S. F. E. Oliviero, and A. Hamma, “Stabilizer entropy dynamics after a quantum quench,” (2023), arXiv:2304.13768 [quant-ph] .
  * Tirrito  _et al._ [2023] E. Tirrito, P. S. Tarabunga, G. Lami, T. Chanda, L. Leone, S. F. E. Oliviero, M. Dalmonte, M. Collura, and A. Hamma, “Quantifying non-stabilizerness through entanglement spectrum flatness,” (2023), arXiv:2304.01175 [quant-ph] .
  * Tarabunga  _et al._ [2023] P. S. Tarabunga, E. Tirrito, T. Chanda, and M. Dalmonte, “Many-body magic via Pauli-Markov chains – from criticality to gauge theories,” (2023), arXiv:2305.18541 [quant-ph] .
  * Oliviero  _et al._ [2022a] S. F. E. Oliviero, L. Leone, and A. Hamma, Phys. Rev. A 106, 042426 (2022a).
  * Haug and Piroli [2023a] T. Haug and L. Piroli, Physical Review B 107 (2023a), 10.1103/physrevb.107.035148.
  * Haug and Piroli [2023b] T. Haug and L. Piroli, Quantum 7, 1092 (2023b).
  * Oliviero  _et al._ [2022b] S. F. E. Oliviero, L. Leone, A. Hamma, and S. Lloyd, npj Quantum Information 8, 148 (2022b).
  * Niroula  _et al._ [2023] P. Niroula, C. D. White, Q. Wang, S. Johri, D. Zhu, C. Monroe, C. Noel, and M. J. Gullans, “Phase transition in magic with random quantum circuits,” (2023), arXiv:2304.10481 [quant-ph] .
  * Carrasquilla and Torlai [2021] J. Carrasquilla and G. Torlai, PRX Quantum 2, 040201 (2021).
  * Chen  _et al._ [2022] S. Y.-C. Chen, T.-C. Wei, C. Zhang, H. Yu, and S. Yoo, Phys. Rev. Res. 4, 013231 (2022).
  * Carrasquilla [2020] J. Carrasquilla, Advances in Physics: X 5, 1797528 (2020).
  * van Nieuwenburg  _et al._ [2017] E. P. L. van Nieuwenburg, Y.-H. Liu, and S. D. Huber, Nature Physics 13, 435 (2017).
  * Wu  _et al._ [2023] Y.-D. Wu, Y. Zhu, Y. Wang, and G. Chiribella, “Learning global quantum properties from local measurements with neural networks,” (2023), arXiv:2310.11807 [quant-ph] .
  * Wang [2016] L. Wang, Physical Review B 94 (2016), 10.1103/physrevb.94.195105.
  * Asif  _et al._ [2023] N. Asif, U. Khalid, A. Khan, T. Q. Duong, and H. Shin, Scientific Reports 13, 1562 (2023).
  * Chen  _et al._ [2021] Y. Chen, Y. Pan, G. Zhang, and S. Cheng, Quantum Science and Technology 7, 015005 (2021).
  * Carleo and Troyer [2017] G. Carleo and M. Troyer, Science 355, 602 (2017).
  * Hibat-Allah  _et al._ [2020] M. Hibat-Allah, M. Ganahl, L. E. Hayward, R. G. Melko, and J. Carrasquilla, Physical Review Research 2 (2020), 10.1103/physrevresearch.2.023358.
  * Lami  _et al._ [2022] G. Lami, G. Carleo, and M. Collura, Phys. Rev. B 106, L081111 (2022).
  * Hartmann and Carleo [2019] M. J. Hartmann and G. Carleo, Phys. Rev. Lett. 122, 250502 (2019).
  * Ureña  _et al._ [2023] J. Ureña, A. Sojo, J. Bermejo, and D. Manzano, “Entanglement detection with classical deep neural networks,” (2023), arXiv:2304.05946 [quant-ph] .
  * Barreiro  _et al._ [2005] J. T. Barreiro, N. K. Langford, N. A. Peters, and P. G. Kwiat, Phys. Rev. Lett. 95, 260501 (2005).
  * Chapman  _et al._ [2016] R. J. Chapman, C. Ferrie, and A. Peruzzo, Phys. Rev. Lett. 117, 040402 (2016).
  * Koutný  _et al._ [2023] D. Koutný, L. Ginés, M. Moczała-Dusanowska, S. Höfling, C. Schneider, A. Predojević, and M. Ježek, Science Advances 9, eadd7131 (2023), https://www.science.org/doi/pdf/10.1126/sciadv.add7131 .
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010).
  * Gottesman [1998b] D. Gottesman, “The heisenberg representation of quantum computers,” (1998b), arXiv:quant-ph/9807006 [quant-ph] .
  * Bohrdt  _et al._ [2021] A. Bohrdt, S. Kim, A. Lukin, M. Rispoli, R. Schittko, M. Knap, M. Greiner, and J. Léonard, Physical Review Letters 127, 150504 (2021).
  * Kingma and Ba [2014] D. P. Kingma and J. Ba, arXiv preprint arXiv:1412.6980 (2014).
  * Garcia and Markov [2014] H. J. Garcia and I. L. Markov, IEEE Transactions on Computers 64, 2323 (2014).
  * Gidney [2021] C. Gidney, Quantum 5, 497 (2021).
  * Cantori  _et al._ [2023] S. Cantori, D. Vitali, and S. Pilati, Quantum Science and Technology 8, 025022 (2023).
  * Mele [2023] A. A. Mele, “Introduction to haar measure tools in quantum information: A beginner’s tutorial,” (2023), arXiv:2307.08956 [quant-ph] .

##  Appendix A SUPPLEMENTAL MATERIAL

We here provide a proof of equation $\eqref{clifford_eq}$. We rewrite the
expectation value as follows

$\displaystyle\mathbb{E}_{U\in\mathcal{C}_{N}}\left[\left(\bra{\psi}U^{\dagger}\pmb{\sigma}U\ket{\psi}\right)^{4}\right]$
$\displaystyle=\mathbb{E}_{U\in\mathcal{C}_{N}}\left[tr\left(\ket{\psi}\bra{\psi}^{\otimes
4}U^{\dagger^{\otimes 4}}\pmb{\sigma}^{\otimes 4}U^{\otimes 4}\right)\right]$
$\displaystyle=\mathbb{E}_{U\in\mathcal{C}_{N}}\left[tr\left(\pmb{\sigma}^{\otimes
4}U^{\otimes 4}\ket{\psi}\bra{\psi}^{\otimes 4}U^{\dagger^{\otimes
4}}\right)\right]$ $\displaystyle=tr\left(\pmb{\sigma}^{\otimes
4}\mathbb{E}_{U\in\mathcal{C_{N}}}\left[U^{\otimes
4}\ket{\psi}\bra{\psi}^{\otimes 4}U^{\dagger^{\otimes 4}}\right]\right).$ (3)

It is now possible to use the fact that [15]

$\displaystyle\mathbb{E}_{U\in\mathcal{C}_{N}}\left[\left(U\ket{\psi}\bra{\psi}U^{\dagger}\right)^{\otimes
4}\right]=\alpha QP^{(4)}_{symm}+\beta P^{(4)}_{symm}$

where $\displaystyle
Q=\frac{1}{4^{N}}\sum_{\pmb{\sigma}\in\mathcal{P}_{N}}\pmb{\sigma}^{\otimes
4}$ and $\displaystyle P^{(4)}_{symm}=\frac{1}{4!}\sum_{\pi\in S_{4}}T_{\pi}$,
with $P^{(4)}_{symm}$ being the projector onto the symmetric subspace of the
symmetric group $S_{4}$ and $T_{\pi}$ unitary representations of $\pi\in
S_{4}$. The factors $\alpha$ and $\beta$ are

$\displaystyle\alpha$
$\displaystyle=\frac{6d(d+3)||\Pi_{\rho}||^{2}-24}{(d^{2}-1)(d+2)(d+4)},$
$\displaystyle\beta$
$\displaystyle=\frac{24(1-||\Pi_{\rho}||^{2})}{(d^{2}-1)(d+2)(d+4)}\,.$

with $d=2^{N}$. Now we have to evaluate the following two traces

  1. 1.

$tr\left(\pmb{\sigma}^{\otimes 4}P^{(4)}_{symm}\right)$

  2. 2.

$tr\left(\pmb{\sigma}^{\otimes 4}QP^{(4)}_{symm}\right)$.

Let us start from the term $1$. By direct evaluation of the $4!=24$
contributions of the $T_{\pi},\pi\in S_{4}$, it is easy to find

$\displaystyle\begin{split}&tr\left(\pmb{\sigma}^{\otimes
4}P^{(4)}_{symm}\right)=\\\
&=\frac{1}{24}\big{(}\left[tr(\pmb{\sigma})\right]^{4}+6tr(\pmb{\sigma}^{2})\left[tr(\pmb{\sigma})\right]^{2}+8tr(\pmb{\sigma})tr(\pmb{\sigma}^{3})+3tr(\pmb{\sigma}^{2})tr(\pmb{\sigma}^{2})+6tr(\pmb{\sigma}^{4})\big{)}\end{split}$
(4)

and, if one assume $\pmb{\sigma}\neq\mathbb{1}^{\otimes N}$,

$\displaystyle tr\left(\pmb{\sigma}^{\otimes
4}P^{(4)}_{symm}\right)=\frac{1}{8}\left(d^{2}+2d\right)\,.$

For the term $2$, we have

$\displaystyle tr\left(\pmb{\sigma}^{\otimes
4}QP^{(4)}_{symm}\right)=\frac{1}{d^{2}}\sum_{\pmb{\sigma}^{\prime}\in\mathcal{P}_{N}}tr\left(\pmb{\sigma}^{\otimes
4}\pmb{\sigma}^{\prime\otimes 4}P^{(4)}_{symm}\right)\,.$ (5)

The summation in last line of Eq.5 can be performed by splitting the two
contribution $\pmb{\sigma}=\pmb{\sigma}^{\prime}$ and
$\pmb{\sigma}\neq\pmb{\sigma}^{\prime}$. The first gives
$tr\left(P^{(4)}_{symm}\right)$, which is (using Eq.4) [45]:

$tr\left(P^{(4)}_{symm}\right)=\frac{1}{24}\big{(}d^{4}+6d^{3}+11d^{2}+6d\big{)}=\binom{d+3}{4}.$

For the second contribution, as
$\pmb{\sigma}\pmb{\sigma}^{\prime}\in\mathcal{P}_{N}$ for the group closure
property, we can use Eq.4. Finally we get

$\displaystyle tr\left(\pmb{\sigma}^{\otimes 4}QP^{(4)}_{symm}\right)$
$\displaystyle=\frac{1}{d^{2}}\bigg{(}(d^{2}-1)\frac{1}{8}(d^{2}+2d)+\binom{d+3}{4}\bigg{)}=\frac{1}{6}(1+d)(2+d)\,.$
(6)

Combining all together, we obtain

$\mathbb{E}_{U\in\mathcal{C}_{N}}\left[\left(\bra{\psi}U^{\dagger}\pmb{\sigma}U\ket{\psi}\right)^{4}\right]=\frac{1}{d+1}-\frac{d}{d^{2}-1}\,M_{\text{lin}}\left(\ket{\psi}\right).$
(7)

Figure 4 shows a comparison between the numerical evaluation of the Clifford
average and the one predicted by (2) for a $N=4$ qubits system. The numerical
evaluation of the average is performed for $50$ random product states,
harnessing the direct application of Clifford unitaries on Pauli strings.

Figure 4: Clifford average
$\mathbb{E}_{U\in\mathcal{C}_{N}}\left[\left(\bra{\psi}U^{\dagger}\pmb{\sigma}U\ket{\psi}\right)^{4}\right]$
for $50$ random product states starting from a random Pauli string
$\pmb{\sigma}$ as a function of their stabilizer linear entropy
$M_{\text{lin}}$. Error bars are evaluated from the standard deviation of the
average.


11institutetext: Manning College of Information and Computer Sciences,
University of Massachusetts Amherst, MA, 01002 22institutetext: Institute for
Applied Life Sciences, University of Massachusetts Amherst, MA, 01003
33institutetext: Department of Biomedical Engineering, University of
Massachusetts Amherst, MA, 0100244institutetext: Department of Neurology,
Baystate Medical Center, and UMass Chan Medical School - Baystate Campus,
Springfield, MA 01199
44email<EMAIL_ADDRESS>
# Automated ensemble method for pediatric brain tumor segmentation

Shashidhar Reddy Javaji 1*1* Advait Gosai 1*1* Sovesh Mohapatra 112*2*
Gottfried Schlaug 223344

###### Abstract

Brain tumors remain a critical global health challenge, necessitating
advancements in diagnostic techniques and treatment methodologies. A tumor or
its recurrence often needs to be identified in imaging studies and
differentiated from normal brain tissue. In response to the growing need for
age-specific segmentation models, particularly for pediatric patients, this
study explores the deployment of deep learning techniques using magnetic
resonance imaging (MRI) modalities. By introducing a novel ensemble approach
using ONet and modified versions of UNet, coupled with innovative loss
functions, this study achieves a precise segmentation model for the BraTS-PEDs
2023 Challenge. Data augmentation, including both single and composite
transformations, ensures model robustness and accuracy across different
scanning protocols. The ensemble strategy, integrating the ONet and UNet
models, shows greater effectiveness in capturing specific features and
modeling diverse aspects of the MRI images which result in lesion wise Dice
scores of 0.52, 0.72 and 0.78 on unseen validation data and scores of 0.55,
0.70, 0.79 on final testing data for the ”enhancing tumor”, ”tumor core” and
”whole tumor” labels respectively. Visual comparisons further confirm the
superiority of the ensemble method in accurate tumor region coverage. The
results indicate that this advanced ensemble approach, building upon the
unique strengths of individual models, offers promising prospects for enhanced
diagnostic accuracy and effective treatment planning and monitoring for brain
tumors in pediatric brains.

###### Keywords:

UNet ONet Hybrid Loss Majority Ensemble

* contributed equally

##  1 Introduction

Brain tumor has been a major global health challenge, impacting not only
adults but also children and adolescents [1]. In 2022, the United States alone
reported an estimated 40,594 individuals, from infancy to 19 years of age,
diagnosed with primary brain or other central nervous system (CNS) tumors.
Among these, pilocytic astrocytoma was the predominant histopathologic group,
accounting for 8,264 cases. Given that survival rates following a diagnosis
are particularly low among infants, there is a huge need to develop age-
specific segmentation models [2]. These models could enable precise and
automated detection of tumor regions within pediatric brains, thereby
facilitating more efficient and fast diagnosis and treatment.

With the increasing use of deep learning techniques in conjunction with
different modalities of MRI, different models, especially the U-shaped
architectures, have demonstrated precise and accurate performance across
various medical image segmentation tasks [3, 4, 5]. Various models have been
employed for whole brain segmentation, yet certain architectural designs have
been observed to perform better in segmenting specific regions within the
brain [6]. This phenomenon can be attributed to the intricate relationship
between the complexities inherent in both the architecture and the brain’s
structure. Just as different modalities provide complementary information
about anomalous regions in the brain, different architectures may be more
adept at handling particular areas of the brain[7].

In this paper, we are focused on using the CBTN-CONNECT-DIPGr-ASNR-MICCAI
BraTS-PEDs 2023 Challenge data which constitutes four different modalities
(native T1, post-contrast T1-weighted (T1Gd), T2-weighted (T2), and T2 Fluid
Attenuated Inversion Recovery (T2-FLAIR)) [8]. We introduce a novel ensemble
approach using ONet and various modified versions of UNet along with modified
loss functions which yielded a more precise segmentation for the pediatric
tumors.

##  2 Methodology

Figure 1: Comprehensive workflow visualizing the end-to-end process with model
training and ensemble approaches.

###  2.1 Data Augmentation

Due to the inherent variability and noise that can occur during acquisition
using different scanners, the integration of various physics-inspired
augmentation techniques is essential. By populating the training data with
these techniques, the model becomes robust and accurate across diverse
scanning protocols.[9]

In this study, we used two different approaches of augmentation: single and
composite transformation. For the single transformation, we used techniques
like flip, affine transformation, elastic deformation, noise, rescale
Intensity, and random bias field. Additionally, in composite transformation, a
combination of some or all of the aforementioned techniques was applied to
further enrich the dataset.[10, 11, 12, 13]

###  2.2 Model Architectures

####  2.2.1 UNet3D Family

In this work, we implemented eight unique variations using two fundamental
base architectures, each paired with different loss functions (further
explained in Section 2.3) and tailored hyperparameters. Figure 3 illustrates
the architecture for one of the variants of the UNet3D configurations.

Figure 2: Core UNet3D Architecture.

The UNet variations are as follows:

  * •

3D UNet: This is the standard configuration utilizing an input channel size of
4, output class size of 3, and a channel size of 32.

  * •

3D UNet GELU: A variant of the standard 3D UNet where the ReLU activation
function is substituted with GELU (Gaussian Error Linear Unit) to potentially
improve non-linear learning capabilities.

  * •

3D UNet SingleConv: This version modifies the typical double convolution
process in each upscaling and downscaling step, replacing it with a single
convolution, which might affect the model’s ability to capture complex
features.

  * •

3D UNet Attention: Incorporates an attention mechanism into the 3D UNet
structure, aiming to enhance the model’s focus on relevant features for
improved segmentation.

  * •

3D UNet Dropout: Introduces dropout layers into the 3D UNet architecture to
prevent overfitting and promote generalization.

####  2.2.2 ONet3D Family

We also explore variations within the ONet3D family, which differs from the
UNet3D by concatenating the encoder-decoder sections before the output
convolution layer:

  * •

3D ONet SingleConv Kernel_1: Utilizes a single convolution with a kernel size
of 1 in the ONet3D architecture.

  * •

3D ONet SingleConv Kernel_5: Adopts a single convolution with a kernel size of
5, offering a broader receptive field compared to Kernel_1.

  * •

3D ONet DoubleConv Kernel_1: Features double convolution operations with a
kernel size of 1, potentially enhancing the model’s ability to extract fine-
grained features.

###  2.3 Loss Functions

In our segmentation framework, we explored different loss functions to
optimize the model performance. Specifically, we employed two distinct loss
combinations: Binary Cross-Entropy (BCE)[14] plus Dice Loss, and Generalized
Dice Loss[15] plus BCE. The choice of these loss functions is motivated by
their abilities to tackle the class imbalance problem often encountered in
medical image segmentation.

####  2.3.1 Binary Cross-Entropy combined with Dice Loss

The Binary Cross-Entropy (BCE) loss is commonly used for binary classification
tasks and computes the cross-entropy between the true labels and predicted
probabilities. To enhance the model’s sensitivity to the region of interest,
we combined BCE with Dice Loss. The Dice Loss computes the overlap between the
predicted segmentation and the ground truth, providing a spatially aware
metric that is sensitive to the shape of the segmented structures.

The BCE loss is defined as:

$BCE(y,\hat{y})=-\frac{1}{N}\sum_{i=1}^{N}\left(y_{i}\log(\hat{y}_{i})+(1-y_{i})\log(1-\hat{y}_{i})\right)$
(1)

and the Dice Loss is defined as:

$Dice(y,\hat{y})=1-\frac{2\sum_{i=1}^{N}y_{i}\hat{y}_{i}+\varepsilon}{\sum_{i=1}^{N}y_{i}+\sum_{i=1}^{N}\hat{y}_{i}+\varepsilon}$
(2)

where $\varepsilon$ is a small constant to avoid division by zero. The
combined loss function is:

$Loss(y,\hat{y})=\alpha\cdot BCE(y,\hat{y})+\beta\cdot Dice(y,\hat{y})$ (3)

where $\alpha$ and $\beta$ are weights that balance the contribution of each
term.

####  2.3.2 Generalized Dice Loss combined with BCE

Recognizing the limitations of standard Dice Loss in handling cases with
varying object sizes, we also experimented with Generalized Dice Loss (GDL).
GDL extends the traditional Dice Loss by incorporating class-wise weights,
thus accommodating the imbalanced class distribution. This loss function is
especially well-suited to medical image segmentation where certain classes or
labels may be underrepresented.

The GDL is defined as:

$GDL(y,\hat{y})=1-\frac{2\sum_{c=1}^{C}w_{c}\sum_{i=1}^{N}y_{ci}\hat{y}_{ci}+\varepsilon}{\sum_{c=1}^{C}w_{c}(\sum_{i=1}^{N}y_{ci}+\sum_{i=1}^{N}\hat{y}_{ci})+\varepsilon}$
(4)

where $C$ is the number of classes, $w_{c}$ is the weight for class $c$,
defined as:

$w_{c}=\frac{1}{(\sum_{i=1}^{N}y_{ci})^{2}}$ (5)

Here, $\varepsilon$ is again a small constant to avoid division by zero.

###  2.4 Ensemble Strategy

The ensemble strategy integrates the predictive capabilities of ONet and UNet
models, capitalizing on their complementary strengths. Initial predictions
from the models are combined through a summation of logits, followed by
thresholding. A majority vote across the models for each voxel finalizes the
ensemble prediction, aiming to capture specific features and model diverse
aspects of the MRI images.

###  2.5 Post Processing

Post-processing techniques are applied to the combined predictions to refine
segmentation quality:

  * •

Size Filtering Based on Voxel Volumes: This technique removes small isolated
regions, eliminating noise.

  * •

Morphological Reconstruction: A more advanced method for interpolation of
voxels violating constraints and smoothing boundaries for all labels.

##  3 Results

###  3.1 Evaluation Metrics

The BraTS challenge evaluates submitted models using two primary metrics: the
lesion-wise (LW) Dice score and the 95th percentile lesion-wise Hausdorff
distance (HD95). These metrics are used to assess segmentations across three
distinct tumor sub-regions: the whole tumor (WT), tumor core (TC) , and
enhancing tumor (ET).

The Lesion-wise Dice Score and 95th Percentile Lesion-wise Hausdorff Distance
(HD95) are key metrics for evaluating segmentation models in medical imaging.
The Dice score, ranging from 0 (no overlap) to 1 (perfect overlap), measures
the accuracy of predicted segmentations against the true segmentations on a
lesion-by-lesion basis, penalizing False Positives and False Negatives by
assigning a 0 score. The HD95 metric quantifies the maximum deviation between
predicted and actual segmentations for each lesion, with False Positives and
False Negatives receiving a fixed penalty value of 374. Mean scores for both
metrics are calculated across case IDs. These evaluations offer a detailed
insight into the model’s segmentation performance, highlighting areas for
potential enhancement

###  3.2 Quantitative Performance

Table 1: Comparison of evaluation metrics for Enhancing Tumor on validation data Models |  LW Dice $\uparrow$ |  Dice $\uparrow$ |  LW HD95 $\downarrow$ |  HD95 $\downarrow$
---|---|---|---|---
UNet3D | 0.43 | 0.44 | 168.68 | 114.03
ONet3D | 0.52 | 0.48 | 131.28 | 121.74
Ensemble (BCE, Dice) | 0.38 | 0.38 | 186.73 | 141.84
Ensemble (BCE, GD) | 0.52 | 0.49 | 127.11 | 105.46
Table 2: Comparison of evaluation metrics for Tumor Core on validation data Models |  LW Dice $\uparrow$ |  Dice $\uparrow$ |  LW HD95 $\downarrow$ |  HD95 $\downarrow$
---|---|---|---|---
UNet3D | 0.70 | 0.75 | 44.68 | 12.19
ONet3D | 0.71 | 0.74 | 33.26 | 19.82
Ensemble (BCE, Dice) | 0.64 | 0.73 | 60.00 | 17.68
Ensemble (BCE, GD) | 0.72 | 0.74 | 23.84 | 11.48
Table 3: Comparison of evaluation metrics for Whole Tumor on validation data Models |  LW Dice $\uparrow$ |  Dice $\uparrow$ |  LW HD95 $\downarrow$ |  HD95 $\downarrow$
---|---|---|---|---
UNet3D | 0.75 | 0.82 | 45.51 | 11.85
ONet3D | 0.76 | 0.80 | 32.88 | 19.31
Ensemble (BCE, Dice) | 0.70 | 0.82 | 61.74 | 15.97
Ensemble (BCE, GD) | 0.78 | 0.82 | 25.88 | 10.89

In our assessment of various models, we submitted the results to the synapse
portal for testing the results on the validation. The findings revealed that
the ensemble training approach demonstrates better effectiveness in comparison
to the single model training approach, across almost all of the validation
cases.

Furthermore, an individual evaluation of predictions indicated that the
single-model training approach of the ONet3D model matches the ensemble
training approach for lesion-wise dice as outlined in Table 1. This indicates
that there can be an ensemble model which might be robust and be generalizable
for a larger dataset. However for specific types of segmentation and
evaluation metrics, the approaches might differ.

Table 4: Evaluation metrics for sub-regions on Final Test Data Sub-region |  LW Dice $\uparrow$ |  Dice $\uparrow$ |  LW HD95 $\downarrow$ |  HD95 $\downarrow$
---|---|---|---|---
ET | 0.55 | 65.23 | 0.55 | 0.99
TC | 0.71 | 31.61 | 0.61 | 0.99
WT | 0.79 | 22.36 | 0.70 | 0.99

In the evaluation of our brain tumor segmentation model on the BraTS test set,
the results demonstrate varying degrees of performance across different tumor
sub-regions, indicating the model’s proficiency in distinguishing between
tumor core (TC), enhancing tumor (ET), and whole tumor (WT) regions.
Specifically, the model achieved Dice scores of 0.5519, 0.7054, and 0.7938 for
ET, TC, and WT, respectively, suggesting a higher accuracy in segmenting the
whole tumor region compared to the more challenging enhancing tumor and tumor
core regions. Similarly, the Hausdorff distance (95th percentile) metrics,
which assess the model’s precision in outlining tumor boundaries, show values
of 65.23, 31.61, and 22.36 for ET, TC, and WT, respectively, indicating the
model’s increased boundary precision in WT segmentation. The sensitivity
scores—0.5544 for ET, 0.6096 for TC, and 0.7010 for WT—further highlight the
model’s ability to correctly identify tumor pixels, with WT regions being most
accurately detected. In contrast, the specificity scores, which are
consistently high across all regions (0.9997 for ET, 0.9998 for TC, and 0.9999
for WT), underscore the model’s effectiveness in correctly classifying non-
tumor pixels. These results collectively underscore the model’s robustness in
brain tumor segmentation, with notable strengths in whole tumor delineation
and high specificity across tumor sub-regions. In the end it’s evident from
the validation and test results that the model generalizes well.

###  3.3 Visual Comparison

Figure 3 illustrates a side-by-side comparison of prediction results derived
from two separate methodologies for modeling: individual model training and
the ensemble approach.

The comparison reveals a noticeable difference between the two approaches. The
predictions stemming from the single model training method, as evidenced by
UNet3D and ONet3D, demonstrate to capture less core tumor region and region
affected by the tumor (enhancing tumor). This limitation is contrasted by the
predictions generated through the ensemble training method.

Figure 3: A, B, and C depict three slice planes (sagittal, coronal, axial)
from the same CaseID, showcasing predictions generated by three different
models—UNet3D, ONet3D, and the ensemble model respectively.

The ensemble approach adds the strengths of multiple individual models,
potentially leading to more accurate and robust predictions. In the context of
the figure, it becomes evident that employing the ensemble method results in
more effective coverage of tumor regions. This might suggest that the ensemble
training not only compensates for the limitations observed in the single model
training but possibly enhances the overall predictive capability.

##  4 Discussion and Conclusion

The integration of ONet and UNet models through an ensemble technique,
together with the novel proposed post-processing strategy, creates an advanced
approach to medical image segmentation. This method builds upon the unique
strengths of both ONet and UNet models, combining them in an interdependent
manner that leverages their individual capabilities. By doing so, the approach
not only amplifies the robustness of the segmentation but also adds a level of
precision that might be unattainable with a single-model training strategy.
The clinical significance of this methodology lies in its potential to offer
enhanced diagnostic accuracy and effective treatment planning.

## References

  * [1] Mackay, A., et al. “Integrated Molecular Meta-Analysis of 1,000 Pediatric High-Grade and Diffuse Intrinsic Pontine Glioma.” _Cancer Cell_ , vol. 32, no. 5, 2017, pp. 520–537.e5.
  * [2] Ostrom, Quinn T., et al. “CBTRUS Statistical Report: Pediatric Brain Tumor Foundation Childhood and Adolescent Primary Brain and Other Central Nervous System Tumors Diagnosed in the United States in 2014-2018.” _Neuro-oncology_ , vol. 24, Suppl 3, 2022, pp. iii1-iii38. 10.1093/neuonc/noac161
  * [3] Ronneberger, O., Fischer, P., & Brox, T. “U-Net: Convolutional Networks for Biomedical Image Segmentation.” _Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015_ , Springer International Publishing, 2015, pp. 234–241.
  * [4] Hatamizadeh, A., et al. “Swin UNETR: Swin Transformers for Semantic Segmentation of Brain Tumors in MRI Images.” _Brandlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries_ , Springer International Publishing, 2022, pp. 272–284.
  * [5] Heiliger, L., et al. “AutoPET Challenge: Combining nn-Unet with Swin UNETR Augmented by Maximum Intensity Projection Classifier.” _arXiv_ [eess.IV], 2022.
  * [6] Mohapatra, S., et al. “Meta-Analysis of Transfer Learning for Segmentation of Brain Lesions.” _arXiv_ [eess.IV], 2023
  * [7] Ranjbarzadeh, Ramin et al. “Brain tumor segmentation based on deep learning and an attention mechanism using MRI multi-modalities brain images.” _Scientific Reports_ , vol. 11, no. 1, 2021, p. 10930.
  * [8] Kazerooni, A. F., et al. “The Brain Tumor Segmentation (BraTS) Challenge 2023: Focus on Pediatrics (CBTN-CONNECT-DIPGR-ASNR-MICCAI BraTS-PEDs).” _arXiv_ , 2023.
  * [9] Alsaif, Haitham, et al. “A Novel Data Augmentation-Based Brain Tumor Detection Using Convolutional Neural Network.” _Applied Sciences_ , vol. 12, no. 8, 2022, 3773. https://doi.org/10.3390/app12083773
  * [10] Nalepa, Jakub et al. “Data Augmentation for Brain-Tumor Segmentation: A Review.” _Frontiers in Computational Neuroscience_ , vol. 13, 2019, 83. doi:10.3389/fncom.2019.00083
  * [11] Castro, E., Cardoso, J. S., and Pereira, J. C. “Elastic deformations for data augmentation in breast cancer mass detection,” _2018 IEEE EMBS International Conference on Biomedical & Health Informatics (BHI)_, Las Vegas, NV, USA, 2018, pp. 230-234, doi: 10.1109/BHI.2018.8333411.
  * [12] Abdalla, P.A., Mohammed, B.A., and Saeed, A.M. “The impact of image augmentation techniques of MRI patients in deep transfer learning networks for brain tumor detection.” _Journal of Electrical Systems and Information Technology_ , vol. 10, 2023, 51. https://doi.org/10.1186/s43067-023-00119-9
  * [13] Kalaivani, S., Asha, N., Gayathri, A. “Geometric Transformations-Based Medical Image Augmentation.” In: Solanki, A., Naved, M. (eds) _GANs for Data Augmentation in Healthcare_. Springer, Cham, 2023. https://doi.org/10.1007/978-3-031-43205-7_8
  * [14] Cox, D. R. “The Regression Analysis of Binary Sequences.” _Journal of the Royal Statistical Society. Series B (Methodological)_ , vol. 20, no. 2, 1958, pp. 215–242. [Online]. Available: http://www.jstor.org/stable/2983890. Accessed: Mar. 13, 2024.
  * [15] Sudre, Carole Helene, et al. “Generalised Dice overlap as a deep learning loss function for highly unbalanced segmentations.” _Deep Learning in Medical Image Analysis and Multimodal Learning for Clinical Decision Support: Third International Workshop, DLMIA 2017, and 7th International Workshop, ML-CDS 2017, held in conjunction with MICCAI 2017 Quebec City, QC,… 2017_ , 2017, pp. 240–248.


# On Turán-good graphs

Dániel Gerbner111Alfréd Rényi Institute of Mathematics, E-mail:
<EMAIL_ADDRESS>Research supported by the National Research,
Development and Innovation Office – NKFIH under the grants FK 132060,
KKP-133819, KH130371 and SNN 129364.

###### Abstract

For graphs $H$ and $F$, the generalized Turán number $\mathrm{ex}(n,H,F)$ is
the largest number of copies of $H$ in an $F$-free graph on $n$ vertices. We
say that $H$ is $F$-Turán-good if $\mathrm{ex}(n,H,F)$ is the number of copies
in the $(\chi(F)-1)$-partite Turán graph, provided $n$ is large enough.

We present a general theorem in case $F$ has an edge whose deletion decreases
the chromatic number. In particular, this determines
$\mathrm{ex}(n,P_{k},C_{2\ell+1})$ and $\mathrm{ex}(n,C_{2k},C_{2\ell+1})$
exactly, if $n$ is large enough. We also study the case when $F$ has a vertex
whose deletion decreases the chromatic number.

##  1 Introduction

A basic result in extremal Combinatorics is Turán’s theoem [18]. It states
that a $K_{k}$-free graph on $n$ vertices cannot have more edges than the
Turán graph $T_{k-1}(n)$, which is the complete $(k-1)$-partite graph where
each partite class has cardinality $\lfloor n/(k-1)\rfloor$ or $\lceil
n/(k-1)\rceil$. In general, Turán theory deals with the function
$\mathrm{ex}(n,F)$, which is the largest number of edges in $n$-vertex
$F$-free graphs. Let ${\mathcal{N}}(H,G)$ denote the number of copies of $H$
in $G$. Generalized Turán theory deals with
$\mathrm{ex}(n,H,F):=\max\\{{\mathcal{N}}(H,G):G\text{ is an $n$-vertex
$F$-free graph}\\}$, i.e. the largest number of copies of $H$ in $F$-free
graphs on $n$ vertices.

After several sporadic results (see e.g. [2, 11, 13, 15, 12, 19]), the
systematic study of this problem was initiated by Alon and Shikhelman [1].
Since then, this problem has attracted several researchers, see e.g. [3, 4, 5,
7, 8, 9, 10, 14, 16].

However, there are not many exact results in this area (by exact result we
mean that for given $H$ and $F$, we know the value of $\mathrm{ex}(n,H,F)$ for
every $n$ large enough). Most of the exact results are when the Turán graph
contains the most copies of $H$. Győri, Pach and Simonovits [13] examined for
what graphs $H$ do we have that
$\mathrm{ex}(n,H,K_{k+1})={\mathcal{N}}(H,T_{k}(n))$. Gerbner and Palmer [9]
extended these investigations for arbitrary $k$-chromatic graphs. Following
them, given a graph $F$ with $\chi(F)=k$, we say that $H$ is $F$-Turán-good if
$\mathrm{ex}(n,H,F)={\mathcal{N}}(H,T_{k-1}(n))$ and $H$ does not contain $F$.
If $F=K_{k}$, we use the briefer term $k$-Turán good. Let us state the main
result of Győri, Pach and Simonovits [13] using this term.

######  Theorem 1.1 (Győri, Pach and Simonovits [13]).

Let $r\geq 3$ and let $H$ be a $(k-1)$-partite graph with $m>k-1$ vertices,
containing $\lfloor m/(k-1)\rfloor$ vertex disjoint copies of $K_{k-1}$.
Suppose further that for any two vertices $u$ and $v$ in the same connected
component of $H$, there is a sequence $A_{1},\dots,A_{s}$ of $(k-1)$-cliques
in $H$ such that $u\in A_{1}$, $v\in A_{s}$, and for any $i<s$, $A_{i}$ and
$A_{i+1}$ share $k-2$ vertices. Then $H$ is $k$-Turán-good. Moreover, if $n$
is large enough, the Turán graph is the only $K_{k}$-free graph with
$\mathrm{ex}(n,H,K_{k})$ copies of $H$.

Gerbner and Palmer [9] obtained a theorem of a similar flavor.

######  Theorem 1.2 (Gerbner, Palmer [9]).

Let $H$ be a $k$-Turán-good graph. Let $H^{\prime}$ be any graph constructed
from $H$ in the following way. Choose a complete subgraph of $H$ with vertex
set $X$, add a vertex-disjoint copy of $K_{k-1}$ to $H$ and join the vertices
in $X$ to the vertices of $K_{k-1}$ by edges arbitrarily. Then $H^{\prime}$ is
$k$-Turán-good.

Neither of the above two theorems imply the other. The main difference is that
vertices in the additional clique can be connected to anything in Theorem 1.1,
but only to vertices of another clique in Theorem 1.2. The trade-off is the
necessity of the strong connection property of the cliques in Theorem 1.1. Let
us remark that for $k=3$, the assumptions of Theorem 1.1 are nothing else but
that $H$ is bipartite and has a matching of size $\lfloor|V(H)|/2\rfloor$; the
property of the sequence of 2-cliques reduces to the property that every
connected component is connected.

Observe that on their own, both theorems use $K_{k-1}$ as building blocks, and
can be used only for graphs mostly covered by vertex-disjoint copies of
$K_{k-1}$. Therefore, another difference is that in Theorem 1.2 we can start
with an arbitrary $k$-Turán-good graph, and add cliques afterwards. Here we
prove such a strengthening for Theorem 1.1.

######  Proposition 1.3.

Let $H$ be a $k$-Turán-good graph with a unique proper $(k-1)$-coloring. Let
$H^{\prime}$ consist of $H$ and a copy $K$ of $K_{k-1}$ with vertices
$v_{1},\dots,v_{k-1}$, with additional edges between $V(H)$ and $V(K)$ such
that for every $i\leq k-1$, there is a copy of $K_{k-1}$ in $H^{\prime}$
containing $v_{i}$, but not containing any $v_{j}$ for $j>i$. If $H^{\prime}$
has chromatic number $k-1$, then $H^{\prime}$ is $k$-Turán-good.

Let us show an example where this proposition is stronger then the above
theorems. We will start with a slightly unbalanced complete bipartite graph.
Ma and Qiu [16] showed that $K_{s,t}$ with $s\leq t$ is 3-Turán-good if and
only if $t<s+1/2+\sqrt{2s+1/4}$. Proposition 1.3 implies that if the vertices
of a connected bipartite graph $H$ can be vertex-disjointly covered by one
such $K_{s,t}$ and a matching, then $H$ is 3-Turán-good.

Let us turn our attention to $F$-Turán-good graphs where $F$ is not a clique.
We show a weak version of the above results for this case. We say that an edge
of a graph $G$ is a color-critical edge if deleting it from $G$ decreases its
chromatic number. An $m$-chromatic graph $F$ with a color-critical edge often
behaves similarly to $K_{m}$ in extremal problems. In particular, Simonovits
[17] showed that for $n$ large enough, the Turán graph $T_{m-1}(n)$ contains
the most number of edges, and it was extended by Ma and Qiu [16], who showed
that $T_{m-1}(n)$ also contains the most number of $K_{r}$ for $r<m$. Gerbner
[6] proved a stability version.

######  Lemma 1.4 (Gerbner [6]).

Let $F$ be a $k$-chromatic graph with a color-critical edge and $r<k$. If $G$
is an $n$-vertex $F$-free graph with chromatic number more than $k-1$, then
$ex(n,K_{r},F)-N(G,K_{r})=\Omega(n^{r-1})$.

Using this, we can extend the above theorems from $K_{k}$ to certain graphs
with color-critical edges. The main idea is that if an $F$-free graph does not
have too many copies of $K_{k}$, then those create only a negligible amount of
copies of $H$.

######  Theorem 1.5.

Let $F$ be a $k$-chromatic graph with a color-critical edge such that
$\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$, and $H$ be a graph that is both
$F$-Turán-good and $k$-Turán-good. Let $H^{\prime}$ be any graph constructed
from $H$ in the following way. Choose a complete subgraph of $H$ with vertex
set $X$, add a vertex-disjoint copy of $K_{k-1}$ to $H$ and join the vertices
in $X$ to the vertices of $K_{k-1}$ by edges arbitrarily. Then $H^{\prime}$ is
$F$-Turán-good. Moreover, if $G$ is an $n$-vertex $F$-free graph with
chromatic number more than $m-1$, then
$\mathrm{ex}(n,H^{\prime},F)-N(H^{\prime},G)=\Omega(n^{|V(H^{\prime})|-1})$.

######  Proposition 1.6.

Let $F$ be a $k$-chromatic graph with a color-critical edge such that
$\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$. Let $H$ be a graph that is both
$F$-Turán-good and $k$-Turán-good with a unique proper $(k-1)$-coloring. Let
$H^{\prime}$ consist of $H$ and a copy $K$ of $K_{k-1}$ with vertices
$v_{1},\dots,v_{k-1}$, with additional edges between $V(H)$ and $V(K)$ such
that for every $i\leq k-1$, there is a copy of $K_{k-1}$ in $H^{\prime}$
containing $v_{i}$, but not containing $v_{j}$ for $j>i$. If $H^{\prime}$ has
chromatic number $k-1$, then $H^{\prime}$ is $F$-Turán-good. Moreover, if $G$
is an $n$-vertex $F$-free graph with chromatic number more than $m-1$, then
$\mathrm{ex}(n,H^{\prime},F)-N(H^{\prime},G)=\Omega(n^{|V(H^{\prime})|-1})$.

Let us note the extra assumption $\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$. For
$k=3$, an example is $F=C_{2\ell+1}$, as
$\mathrm{ex}(n,K_{3},C_{2\ell+1})=O(n^{1+1/\ell})$ due to Győri and Li [12].
Another example is the book $B_{t}$, which consists of an edge $uv$ and $t$
other vertices, that are adjacent to both $u$ and $v$. Alon and Shikhelman [1]
showed $\mathrm{ex}(n,K_{3},B_{t})=o(n^{2})$.

Gerbner and Palmer [9] conjectured that paths $P_{m}$ and even cycles $C_{2m}$
are $C_{2\ell+1}$-Turán-good for any $m$ and $\ell$. They proved this
conjecture for $P_{4}$ and $\ell=2$. They also showed that if $P_{2m}$ is
$C_{2\ell+1}$-Turán-good, then $C_{2m}$ is $C_{2\ell+1}$-Turán-good too. Thus
we can fully resolve their conjecture using Theorem 1.5 or Proposition 1.6.

######  Corollary 1.7.

For any positive integers $m$ and $\ell$, $P_{m}$ and $C_{2m}$ are
$C_{2\ell+1}$-Turán-good.

Gerbner and Palmer [9] also showed that $P_{4}$ is $B_{2}$-Turán-good. We can
generalize it as follows.

######  Corollary 1.8.

For any positive integers $m$ and $t$, $P_{m}$ is $B_{t}$-Turán-good.

Gerbner and Palmer [9] showed an example where a graph $H$ is $F$-Turán-good,
and $F$ does not have a color-critical edge ($H=C_{4}$ and $F$ is the 2-fan,
two triangles sharing a vertex). Observe that one can add additional edges to
the Turán graph without violating the $F$-free property in this case. However,
those edges cannot create additional copies of $H$. A natural question is for
what graphs $F$ can we find an $H$ such that $H$ is $F$-Turán-good?

We say that a vertex $v$ of a graph $G$ is color-critical if by deleting $v$
from $G$ we obtain a graph with smaller chromatic number.

######  Theorem 1.9.

There exists an $F$-Turán-good graph if and only if $F$ has a color-critical
vertex.

We prove Proposition 1.3, Theorem 1.5 and Proposition 1.6 in Section 2, and we
prove Theorem 1.9 in Section 3. We finish the paper with some concluding
remarks in Section 4.

##  2 Graphs with a color-critical edge

We start with the proof of Proposition 1.3, that we restate here for
convenience.

######  Proposition.

Let $H$ be a $k$-Turán-good graph with a unique proper $(k-1)$-coloring. Let
$H^{\prime}$ consist of $H$ and a copy $K$ of $K_{k-1}$ with vertices
$v_{1},\dots,v_{k-1}$, with additional edges between $V(H)$ and $V(K)$ such
that for every $i\leq k-1$, there is a copy of $K_{k-1}$ in $H^{\prime}$
containing $v_{i}$, but not containing $v_{j}$ for $j>i$. If $H^{\prime}$ has
chromatic number $k-1$, then $H^{\prime}$ is $k$-Turán-good.

###### Proof.

Let $G$ be a $K_{k}$-free graph on $n$ vertices. We will count the copies of
$H^{\prime}$ in $G$ the following way. First we pick a copy $K$ of $K_{k-1}$,
then a vertex-disjoint copy $H^{\prime}$ of $H$. Then we pick an actual
embedding of $H$ into $H^{\prime}$, and afterwards an actual embedding of $K$
into $K^{\prime}$ such that the images of the remaining edges of $H^{\prime}$
are present in $G$. We claim that $T_{k-1}(n)$ gives the maximum for each of
the above four factors, finishing the proof.

We have ${\mathcal{N}}(K_{k-1},G)\leq{\mathcal{N}}(H,T_{k-1}(n))$ by a theorem
of Zykov [19] (this particular case also follows from Theorem 1.1), thus the
number of ways to pick a copy $K^{\prime}$ of $K_{k-1}$ in $G$ is the largest
if $G$ is the Turán graph. Then there are at most $\mathrm{ex}(n-k+1,H,K_{k})$
ways to pick a vertex-disjoint copy of $H$, which is at most $T_{k-1}(n-k+1)$
for $n$ large enough, as $H$ is $k$-Turán-good. Observe that we have equality
here in case $G=T_{k-1}(n)$, as removing a maximal clique from the Turán graph
gives a smaller Turán graph. The number of ways $H$ can be embedded into
$H^{\prime}$ is the number of isomorphisms of $H$ and does not depend on $G$.

After $H$ is embedded, we claim that there is at most one way to finish the
embedding. We pick the images of the vertices $v_{i}$ from $K$ one by one, in
the order of their indices. For each $v_{i}$, it is contained in a copy
$K^{\prime\prime}$ of $K_{k-1}$ that is already embedded. The other $k-2$
vertices of $K^{\prime\prime}$ are already embedded, and their images have at
most one common neighbor in $K^{\prime}$, as $G$ is $K_{k}$-free. This means
we only have one vertex that can be picked as $v_{i}$.

Finally, we show that in the Turán graph, there is a way to finish the
embedding. The other $k-2$ vertices of $K^{\prime\prime}$ that are already
embedded must belong to different partite classes of the Turán graph, thus
$v_{i}$ must be from the remaining partite class. We have to show that this
way the $v_{i}$’s are mapped to different vertices. This is where we use the
unique coloring property of $H$. Let $j$ be a color class in this unique
coloring, then all the vertices of color $j$ are mapped to the same partite
class $A_{j}$ of the Turán graph. If $v_{i}$ is of color $j$ in $H^{\prime}$,
then the other $k-2$ vertices of $K^{\prime\prime}$ are not of color $j$, thus
they are not in $A_{j}$, hence $v_{i}$ is mapped to the vertex of $K^{\prime}$
that belong to $A_{j}$. As the vertices of $K$ belong to different color
classes in $H$, they are mapped to different partite classes of the Turán
graph, finishing the proof. ∎

Let us continue with the proof of Theorem 1.5, that we restate here for
convenience.

######  Theorem.

Let $F$ be a $k$-chromatic graph with a color-critical edge such that
$\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$, and $H$ be a graph that is both
$F$-Turán-good and $k$-Turán-good. Let $H^{\prime}$ be any graph constructed
from $H$ in the following way. Choose a complete subgraph of $H$ with vertex
set $X$, add a vertex-disjoint copy of $K_{k-1}$ to $H$ and join the vertices
in $X$ to the vertices of $K_{k-1}$ by edges arbitrarily. Then $H^{\prime}$ is
$F$-Turán-good. Moreover, if $G$ is an $n$-vertex $F$-free graph with
chromatic number more than $m-1$, then
$\mathrm{ex}(n,H^{\prime},F)-N(H^{\prime},G)=\Omega(n^{|V(H^{\prime})|-1})$.

###### Proof.

By a result of Ma and Qiu [16], if $n$ is large enough, then the maximum
number of copies of $K_{k-1}$ in an $F$-free graph is achieved by the Turán
graph $T_{k-1}(n)$. Since $H$ is $F$-Turán-good, the Turán graph
$T_{k-1}(n-k+1)$ has the maximum number of copies of $H$ among $F$-free graphs
on $n-k+1$ vertices. We will show that $T_{k-1}(n)$ has the maximum number of
copies of $H^{\prime}$.

Let $G$ be an $F$-free graph on $n$ vertices with the maximum number of copies
of $H^{\prime}$. If $G$ has chromatic number at most $k-1$, then $G$ is
$K_{k}$-free, thus we are done by Theorem 1.2. If $G$ has chromatic number
more than $k-1$, then by Lemma 1.4 we have
${\mathcal{N}}(K_{k-1},T_{k-1}(n))-{\mathcal{N}}(K_{k-1},G)=\Omega(n^{k-2})$.

We follow the proof of Theorem 1.2 from [9]. We take a complete subgraph $Y$
of $G$, disjoint from $K$, and consider the bipartite subgraph $G^{\prime}$ of
$G$ consisting of the edges between $K$ and $Y$. It was shown in [9] that if
$G$ is $K_{k}$-free, then a matching covering $Y$ is missing from
$G^{\prime}$. It is easy to see that if such a matching is not missing, then
not only there is a $K_{k}$ in $G$, but there is a $K_{k}$ with vertices in
$Y\cup V(K)$. For sake of completeness, we repeat the argument here. By Hall’s
theorem, there is a subset $Y^{\prime}\subset Y$ such that all the vertices of
$Y^{\prime}$ are connected to all but less than $Y^{\prime}$ vertices of $K$.
Then $Y^{\prime}$ and those vertices form a clique of size at least $k$.

Let us count first the copies of $H^{\prime}$ such that there is no $K_{k}$ in
$G$ on the vertex sets of them. For those copies there is a matching missing
from $G^{\prime}$. Observe that in the Turán graph between a clique of size
$k-1$ and a clique of size $|Y|$, only a matching covering the smaller clique
is missing. This implies that after picking a copy of $H$, there are at least
as many ways to connect the appropriate subclique of it to $K$ in the Turán
graph, as in $G$.

The number of such copies of $H^{\prime}$ is at most the product of the number
of copies of $K_{k-1}$, the number of copies of $H$ on the remaining $n-k+1$
vertices and the number of ways to join the vertices of $K_{k-1}$ and $H$, all
divided by the number of times a copy of $H^{\prime}$ was counted. The first
quantity is less than ${\mathcal{N}}(K_{k-1},T_{k-1}(n))$ by
$\Omega(n^{k-2})$. The second quantity is maximized by the Turán graph and is
$O(n^{|V(H)|})$, the third quantity is also maximized by the Turán graph,
while the last quantity depends only on $H^{\prime}$. This implies that the
number of such copies of $H^{\prime}$ is
${\mathcal{N}}(H^{\prime},T_{k-1}(n))-\Omega(n^{|V(H^{\prime})|-1})$.

Let us continue with the copies of $H^{\prime}$ that contain a vertex set of
$K_{k}$ in $G$. As $G$ is $F$-free, there are $o(n^{k-1})$ copies of $K_{k}$
in $G$, thus $o(n^{|V(H^{\prime})|-1})$ copies of $H^{\prime}$. Adding up the
two bounds finishes the proof. ∎

Let us continue with Proposition 1.6 that we restate here for convenience, We
only give a sketch of the proof, as it can be easily obtained by combining the
above two proofs. We assume familiarity with those proofs.

######  Proposition.

Let $F$ be a $k$-chromatic graph with a color-critical edge such that
$\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$. Let $H$ be an $F$-Turán-good graph with a
unique proper $(k-1)$-coloring. Let $H^{\prime}$ consist of $H$ and a copy $K$
of $K_{k-1}$ with vertices $v_{1},\dots,v_{k-1}$, with additional edges
between $V(H)$ and $V(K)$ such that for every $i\leq k-1$, there is a copy of
$K_{k-1}$ in $H^{\prime}$ containing $v_{i}$, but not containing $v_{j}$ for
$j>i$. If $H^{\prime}$ has chromatic number $k-1$, then $H^{\prime}$ is
$F$-Turán-good. Moreover, if $G$ is an $n$-vertex $F$-free graph with
chromatic number more than $m-1$, then
$\mathrm{ex}(n,H^{\prime},F)-N(H^{\prime},G)=\Omega(n^{|V(H^{\prime})|-1})$.

###### Sketch of proof.

Let $G$ be an $F$-free graph on $n$ vertices. If $G$ has chromatic number
$k-1$, then it is $K_{k}$-free and we are done. If $G$ has chromatic number at
least $k$, then by Lemma 1.4 $G$ has less copies of $K_{k-1}$ than the Turán
graph by $\Omega(n^{k-2})$.

First we count copies of $H^{\prime}$ in $G$ such that there are no $k$
vertices in that copy that induce a clique in $G$. For them, we can follow the
proof of Proposition 1.3, with one exception: the number of $(k-1)$-cliques is
less by $\Omega(n^{k-2})$, which implies that the number of copies of $H$ is
less by $\Omega(n^{|V(H^{\prime})|-1})$.

Then we count the other copies of $H^{\prime}$: as there are $o(n^{k-1})$
copies of $K_{k}$ in $G$, we have that there are $o(n^{|V(H^{\prime})|-1})$
such copies of $H$. Adding up the two bounds finishes the proof. ∎

##  3 Graphs with a color-critical vertex

We will use progressive induction. This is a version of induction that can be
used to prove combinatorial statements that hold only for $n$ large enough. It
was introduced by Simonovits [17]. It was used for a generalized Turán problem
in [5]. The statement in [17] is very general, here we state a version adapted
for generalized Turán problems.

For a graph $G$ and a subgraph $G^{\prime}$, we denote by
${\mathcal{N}}_{I}(H,G,G^{\prime})$ the number of copies of $H$ in $G$ that
contain at least one vertex from $G^{\prime}$. Given $H$ and $F$, we say that
$G$ is an extremal graph if $\mathrm{ex}(n,H,F)={\mathcal{N}}(H,G)$.

######  Lemma 3.1.

Let $F$ and $H$ be graphs and $G_{n}$ be an $F$-free graph for every $n$. Let
${\mathcal{G}}_{n}$ be a family of $n$-vertex $F$-free graphs for every $n$,
such that if $G_{1},G_{2}\in{\mathcal{G}}_{n}$, then
${\mathcal{N}}(H,G_{1})={\mathcal{N}}(H,G_{2})$. Assume that there is an
$n_{0}$ such that for every $n\geq n_{0}$, for every extremal graph $G$ on $n$
vertices, there is a subgraph $H^{\prime}$ of $G$ with $|V(H^{\prime})|\leq
n/2$, such that $H^{\prime}$ is also the subgraph of some
$G_{n}\in{\mathcal{G}}_{n}$ and we have the following:
${\mathcal{N}}_{I}(H,G,H^{\prime})\leq{\mathcal{N}}_{I}(H,G_{n},H^{\prime})$,
with equality only if $G\in{\mathcal{G}}_{n}$.

Then for $n$ large enough, $\mathrm{ex}(n,H,F)={\mathcal{N}}(H,G_{n})$ for
some $G_{n}\in{\mathcal{G}}_{n}$. Moreover, every extremal graph belongs to
${\mathcal{G}}_{n}$.

We omit the proof of this specialized version. It follows from the original
version [17] in a straightforward way, but it is also easy to see why it holds
without knowing the original proof. For small $n$ it is possible that some
graph has more copies of $H$ than any $G_{n}\in{\mathcal{G}}_{n}$. However,
this means a surplus of constant many copies of $H$, and then this surplus
starts decreasing when $n\geq n_{0}$, and eventually vanishes.

We will also use the following result.

######  Theorem 3.2 (Gerbner and Palmer [8]).

Let $H$ be a graph and $F$ be a graph with chromatic number $k$, then
$\mathrm{ex}(n,H,F)\leq\mathrm{ex}(n,H,K_{k})+o(n^{|V(H)|})$.

The harder part of Theorem 1.9 follows from the next theorem.

######  Theorem 3.3.

Let $H$ be a complete $k$-partite graph $K_{b,\dots,b}$ and $F$ be a complete
$(k+1)$-partite graph $K_{1,a,\dots,a}$ such that $b>2a-2$. Then $H$ is
$F$-Turán-good. Moreover, every extremal graph contains $T_{k}(n)$.

###### Proof.

Let ${\mathcal{G}}_{n}$ be the family of $F$-free graphs containing
$T_{k}(n)$, and observe that they each contain the same number of copies of
$H$. Indeed, fix a $G_{n}\in{\mathcal{G}}_{n}$ and a copy of $T_{k}(n)$ in it,
and let us call the edges not in that copy extra edges. Then a vertex $v$ can
be incident to at most $a-1$ extra edges. If a copy of $H$ contains an extra
edge between $u$ and $v$, that means each other vertex of that $H$ is adjacent
to at least one of $u$ and $v$, thus $H$ contains at most $2a-4$ other
vertices from that partite set of $T_{k}(n)$ where $u$ and $v$ belong.
Therefore, if a copy of $H$ in $G_{n}$ contains a set $U$ of more than $2a-2$
vertices from a partite set of $T_{k}(n)$, then there are no extra edges
inside $U$, thus no edges at all inside $U$. Thus $U$ is a subset of a partite
set of $H$, in particular $|U|\leq b$. Thus the only way to choose $kb$
vertices from the $k$ partite sets of $T_{k}(n)$ is to choose $b$ from each,
and they have to form the partite sets of $H$, thus $H$ does not use any extra
edge.

Let $G$ be an $F$-free graph on $n$ vertices with
${\mathcal{N}}(H,G)=\mathrm{ex}(n,H,F)$ and assume indirectly that progressive
induction (Lemma 3.1) cannot be applied to finish the proof, i.e. for any
subgraph $H^{\prime}$ of $G$ with $|V(H^{\prime})|\leq n/2$, we do not have
that ${\mathcal{N}}_{I}(H,G,H^{\prime})\leq{\mathcal{N}}_{I}(H,G,T_{k}(n))$
with equality only if $G\in{\mathcal{G}}_{n}$. Let $x$ denote the minimum
number of copies of $H$ that a vertex in the Turán graph $T_{k}(n)$ is
contained in.

######  Claim 3.4.

Every vertex $v$ is contained in at least $x$ copies of $H$ in $G$.

###### Proof.

Otherwise let $H^{\prime}$ be the graph containing only $v$, and we can apply
Lemma 3.1 to finish the proof, a contradiction. ∎

Observe that if the degree of $v$ is $o(n)$, then we are in this situation:
every copy of $H$ that contains $v$ also contains at least one vertex in its
neighborhood, thus we can count the copies of $H$ containing $v$ by picking a
neighbor of $v$ ($o(n)$ ways), then picking $|V(H)|-2$ other vertices
($O(n^{|V(H)|-2})$ ways).

Therefore, we can assume that every vertex has linear degree. We will try to
apply Lemma 3.1 with $H^{\prime}$ being the complete $k$-partite graph
$K_{c,\dots,c}$ with $c=2a-1$. If $H^{\prime}$ is not a subgraph of $G$, then
${\mathcal{N}}(H,G)=0$. We pick a copy of $H^{\prime}$ with partite sets
$A_{1},\dots,A_{k}$, and with a slight abuse of notation we denote that copy
by $H^{\prime}$ and its vertex set by $U^{\prime}$, and we also denote a copy
of $H^{\prime}$ in $T_{k}(n)$ by $H^{\prime}$.

To apply Lemma 3.1 in this case, we need to show that
${\mathcal{N}}_{I}(H,G,H^{\prime})\leq{\mathcal{N}}_{I}(H,T_{k}(n),H^{\prime})$,
with equality only if $G\in{\mathcal{G}}_{n}$. Assume that
${\mathcal{N}}_{I}(H,G,H^{\prime})\geq{\mathcal{N}}_{I}(H,T_{k}(n),H^{\prime})$.
Observe that the number of copies of $H$ containing $t$ vertices from
$U^{\prime}$ is $\Theta(n^{|V(H)|-t})$ in $T_{k}(n)$, and $O(n^{|V(H)|-t})$ in
$G$. Therefore, we will focus on the main term $n^{|V(H)|-1}$, thus on the
copies of $H$ that contain exactly one vertex from $U^{\prime}$. Let $H_{0}$
denote the complete $k$-partite graph $K_{b-1,b,b,\dots,b}$.

Let $G^{\prime}$ be the subgraph of $G$ induced on the vertices not in
$U^{\prime}$. Observe that if a vertex in $G^{\prime}$ is connected to each
$A_{i}$ by at least $a$ vertices, then they form a copy of $F$, a
contradiction. Thus for each vertex $v$ of $G^{\prime}$, there is at least one
$A_{i}$ such that $v$ is connected to at most $a-1$ vertices of $A_{i}$. Note
that $v$ can be connected to each vertex of some other $A_{j}$. We say that a
copy of $H_{0}$ in $G^{\prime}$ is nice if all the vertices of the $k-1$
larger parts of this copy are connected to all the $c$ vertices in some
$A_{j}$.

######  Claim 3.5.

All but $o(n^{|V(H_{0})|})$ copies of $H_{0}$ in $G^{\prime}$ are nice.

###### Proof.

Let us consider a copy of $H$ that contains exactly one vertex from
$U^{\prime}$. It means it contains a copy of the complete $k$-partite graph
$H_{0}:=K_{b-1,b,b,\dots,b}$ in $G^{\prime}$. By Theorem 3.2, $G^{\prime}$
contains at most $(1+o(1))\mathrm{ex}(n-kc,H_{0},K_{k+1})$ copies of $H_{0}$.
Theorem 1.1 shows that $T_{k}(m)$ is $(k+1)$-Turán-good for every $m$, thus we
have that $\mathrm{ex}(n-kc,H_{0},K_{k+1})={\mathcal{N}}(H_{0},T_{k}(n-kc))$.

It is easy to see that in the Turán graph, every copy of $H_{0}$ that avoids
the selected copy of $H^{\prime}$ can be extended to a copy of $H$ with one of
$c$ vertices of that copy of $H^{\prime}$ (those in the same partite class of
the Turán graph). We claim that in $G$, every copy of $H_{0}$ can be extended
to a copy of $H$ with at most $c$ of the vertices of $H^{\prime}$. Indeed, let
$U^{\prime\prime}$ be the set of vertices in $U^{\prime}$ that are connected
to every vertex in the $(k-1)$ larger partite sets of $H_{0}$. If
$U^{\prime\prime}$ intersects some partite sets in at least $a$ vertices, and
has another vertex $v$ in another partite set, then $v$, those $a$ vertices,
and $a$ vertices from each of the the $k-1$ larger partite sets of $H_{0}$
form a copy of $F$, a contradiction. If $|U^{\prime\prime}|>c$, then this is
the case. Moreover, if $|U^{\prime\prime}|=c$, then we have the same
situation, unless $U^{\prime\prime}$ is a partite set of $H^{\prime}$.

The main term of ${\mathcal{N}}_{I}(H,G,H^{\prime})$ is at most
$(1+o(1)){\mathcal{N}}(H_{0},T_{k}(n-kc))$ times $c$, minus the number of
those copies of $H_{0}$ in $G^{\prime}$ that are not connected to the $c$
vertices of one part of $H^{\prime}$ (as they should be counted at most $c-1$
times). If the last term is $\Omega(n^{|V(H_{0})|})$, then the main term is
smaller than the main term of ${\mathcal{N}}_{I}(H,T_{k}(n),H^{\prime})$, a
contradiction finishing the proof of the claim. ∎

Let us return to the proof of the theorem. Consider a copy of $H$ in
$G^{\prime}$. We say that a vertex $v$ of it is replaceable (with respect to
that copy) if deleting $v$ we obtain a nice copy of $H_{0}$, ie. all the
vertices of the $k-1$ larger parts of that copy of $H_{0}$ are connected to
the $c$ vertices of one part of $H^{\prime}$. If that part is $A_{i}$, we say
that $v$ is replaceable by $A_{i}$.

Consider an arbitrary vertex $v$ in $G^{\prime}$. We know that $v$ is in
$\Omega(n^{|V(H)|-1})$ copies of $H$ in $G$, and $\Omega(n^{|V(H)|-2})$ of
those share a vertex with $H^{\prime}$. This implies that there are
$\Omega(n^{|V(H)|-1})$ copies of $H_{0}$ in $G^{\prime}$ that can be extended
to a copy of $H$ with $v$. $\Omega(n^{|V(H)|-1})$ of those copies of $H_{0}$
can also be extended to a copy of $H$ with any one vertex from $A_{i}$ for
some $i\leq k$ by Claim 3.5, i.e. $v$ is replaceable with respect to
$\Omega(n^{|V(H)|-1})$ copies of $H$. Let $B_{i}$ denote the set of vertices
in $G^{\prime}$ such that there are $\Omega(n^{|V(H)|-1})$ copies of $H_{0}$
in $G^{\prime}$ that can be extended to a copy of $H$ with $v$ or with any
vertex of $A_{i}$, i.e. $v$ is replaceable by $A_{i}$ with respect to
$\Omega(n^{|V(H)|-1})$ copies of $H$.

Observe that every $v\in B_{i}$ is connected to less than $a$ vertices of
$A_{i}$. Indeed, let us consider a copy of $H_{0}$ that $v$ extends to a copy
of $H$. If $v$ is connected to $a$ vertices of $A_{i}$, then we can take $a$
vertices from each of the $k-1$ larger partite classes of $H_{0}$, $a$
neighbors of $v$ from $A_{i}$ and $v$ to obtain a copy of $F$.

######  Claim 3.6.

All but $o(n)$ vertices in $B_{i}$ are connected to all the vertices in every
$A_{j}$ with $j\neq i$.

###### Proof.

Consider a copy of $H$ in $G^{\prime}$ containing a vertex $v\in B_{i}$. If a
vertex of it is replaceable by $A_{j}$ with respect to $H$, then $v$ is
connected to all the vertices in $A_{j}$. Otherwise every copy of $H_{0}$
obtained by removing a vertex of $H$ not in $B_{i}$ must belong to the
$o(n^{|V(H_{0})|})$ exceptional copies in Claim 3.5. Observe that only
vertices in one part of $H$ can belong to $B_{i}$, as vertices in other parts
are connected to $c\geq a$ vertices of $A_{i}$.

For each vertex $v$, $\Theta(n^{|V(H)|-1})$ copies of $H$ contain $v$, thus we
obtain $\Omega(n^{|V(H)|-2})$ copies of $H_{0}$ this way, as a copy of $H_{0}$
might be obtained $O(n)$ ways. If we have $\Omega(n)$ exceptional vertices,
they would belong to $\Omega(n^{|V(H)|-1})=\Omega(n^{|V(H_{0})|})$ not nice
copies of $H_{0}$, a contradiction with Claim 3.5. ∎

######  Claim 3.7.

For every $i$, every vertex of $B_{i}$ is connected to less than $a$ vertices
of $B_{i}$.

###### Proof.

Recall that we started with picking an arbitrary $H^{\prime}$. We obtained
that $n-o(n)$ vertices of $G$ must be connected to every vertex of $k-1$
partite classes of that $H^{\prime}$, let $Q$ be their set. Consider an
arbitrary $u\in Q$, that belongs to, say $B_{1}$. Then we obtain another copy
of $H^{\prime}$ from the original one if we delete a vertex of $A_{1}$ and add
$u$ instead. Let us denote this copy by $H^{\prime\prime}$. Applying the same
for $H^{\prime\prime}$, we obtain that $n-o(n)$ vertices of $G$ are connected
to every vertex of $k-1$ partite classes of $H^{\prime\prime}$. In particular,
if $v\in B_{j}$ is connected to every vertex of $k-1$ partite classes of
$H^{\prime\prime}$, the missing partite class has to be $A_{j}$ (which is a
partite class of $H^{\prime\prime}$). Therefore, $v$ is connected to the first
partite class of the new copy of $H^{\prime}$, in particular to $u$. Thus
every $u\in Q\cap B_{1}$ is connected to all but $o(n)$ vertices in every
$B_{j}$ for $j>1$.

If a vertex in $B_{j}\cap Q$ is connected to $a$ vertices in $B_{j}\cap Q$,
then these $a+1$ vertices with $a$ vertices from classes of $H^{\prime}$ form
a copy of $F$, a contradiction. This implies that for every $j$, $|B_{j}\cap
Q|=n/k+o(n)$. Indeed, the copies of $H$ inside $Q$ are all formed by taking a
partite class from every $B_{j}$ by the above observation, thus their number
is at most $y:=\prod_{j=1}^{k}\binom{|B_{j}\cap
Q|}{b}\leq{\mathcal{N}}(H,T_{k}(n))$. It is easy to see that if the sizes of
the sets $B_{j}$ are less balanced, then $y$ decreases by
$\Omega(n^{|V(H)|})$. On the other hand, the number of copies of $H$
containing a vertex outside $Q$ is $o(n^{|V(H)|})$, thus the total number of
copies of $H$ in $G$ is less than ${\mathcal{N}}(H,T_{k}(n))$, a
contradiction.

This also shows that for every copy of $H_{0}$ inside $Q$, its partite sets
are contained in distinct $B_{j}$’s. Indeed, we can essentially repeat the
argument from the first paragraph of the proof of this theorem. Again, we call
an edge $uv$ an extra edge if $u,v\in B_{j}\cap Q$. If a copy of $H_{0}$
contains the extra edge $uv$, that means each other vertex of that $H_{0}$ is
adjacent to at least one of $u$ and $v$, thus $H_{0}$ contains at most $2a-4$
other vertices from $B_{j}\cap Q$. Therefore, if a copy of $H_{0}$ inside $Q$
contains a set $U$ of more than $2a-2$ vertices from $B_{j}$, then there are
no extra edges inside $U$, thus no edges at all inside $U$. Thus $U$ is a
subset of a partite set of $H$, in particular $|U|\leq b$. Therefore, the only
way to choose $kb-1$ vertices from the sets $B_{j}\cap Q$ is to choose $b-1$
vertices from one of them and $b$ vertices from the other sets, and they have
to form the partite sets of $H$.

Consider a vertex $v\in B_{i}\setminus Q$. Assume first that for some $j\neq
i$, $v$ is connected to at most $\alpha n$ vertices of $B_{j}$ for some
$\alpha<1/k$. Consider the copies of $H$ containing $v$. There are
$o(n^{|V(H)|-1})$ copies of $H$ containing $v$ that also contain another
vertex outside $Q$. Consider those copies of $H$ that have all the vertices in
$Q$ (except for $v$), i.e. a copy of $H_{0}$ inside $Q$ that forms a copy of
$H$ with $v$. Then one of the partite classes of that $H_{0}$ is inside
$B_{j}$, thus the vertices are chosen from the $\alpha n$ neighbors of $v$ in
$B_{j}$. This shows that $v$ is in less than $x$ copies of $H$ altogether, a
contradiction with Claim 3.4.

Assume now that a vertex $v\in B_{i}$ is connected to $a$ vertices of $B_{i}$.
Then for $j\neq i$, $v$ has $n/k-o(n)$ neighbors in $B_{j}$. We will build a
copy of $F$. The one-element partite class is $v$. Its $a$ neighbors in
$B_{i}$ form another partite class. Then we go through the sets $B_{j}\cap Q$
($j\neq i$) one by one. We always have that the $a+1$ vertices we picked from
$B_{i}$ have $n/k-o(n)$ neighbors in $B_{j}\cap Q$, and the already picked
other vertices are connected to all of those, except for $o(n)$. Therefore, we
can always pick $a$ vertices from $B_{j}\cap Q$ that are connected to all the
vertices picked earlier. This way we obtain a copy of $F$, a contradiction. ∎

The above claim implies that in a copy of $H$, vertices of $B_{i}$ cannot
belong to two different partite classes. Therefore, every $B_{i}$ contains a
partite class. Let $G^{\prime\prime}$ be the graph we obtain by deleting the
edges inside $B_{i}$ for every $i$. Then
${\mathcal{N}}(H,G)={\mathcal{N}}(H,G^{\prime\prime})\leq{\mathcal{N}}(H,T_{k}(n))$,
where the inequality follows from the facts that $G^{\prime\prime}$ is
$K_{k+1}$-free and $H$ is $(k+1)$-Turán-good. ∎

Now we can prove Theorem 1.9, which we restate here for convenience.

######  Theorem.

There exists an $F$-Turán-good graph if and only if $F$ has a color-critical
vertex.

###### Proof.

Assume first that $F$ does not have a color-critical vertex and let
$k=\chi(F)$. Let $T^{\prime}_{k-1}(n)$ be obtained from $T_{k-1}(n)$ by taking
a vertex $v$ from a largest partite set of $T_{k-1}(n)$, and connect it to
every other vertex. Then deleting $v$ from $T^{\prime}_{k-1}(n)$ we obtain a
$(k-1)$-partite graph. As deleting any vertex from $F$ we obtain a
$k$-chromatic graph, $T^{\prime}_{k-1}(n)$ is $F$-free.

We claim that for any graph $H$, for $n$ large enough, either
${\mathcal{N}}(H,T^{\prime}_{k-1}(n))>{\mathcal{N}}(H,T_{k-1}(n))$ or
${\mathcal{N}}(H,T^{\prime}_{k-1}(n))={\mathcal{N}}(H,T_{k-1}(n))=0$. Indeed,
if there is an $H$ in $T_{k-1}(n)$, then there is one avoiding $v$, but using
a vertex $u$ from the same partite set, and a vertex $w$ from another partite
set. Then we can replace $w$ with $v$ to obtain a copy of $H$ that is in
$T^{\prime}_{k-1}(n)$, but not in $T_{k-1}(n)$.

If ${\mathcal{N}}(H,T_{k-1}(n))=0$, then the Turán graph may be extremal if
$H$ contains $F$, but then $H$ is not $F$-Turán-good. If
${\mathcal{N}}(H,T^{\prime}_{k-1}(n))>{\mathcal{N}}(H,T_{k-1}(n))$, then the
Turán graph is not extremal, finishing the proof.

Assume now that $F$ has a color-critical vertex. Then $F$ is a subgraph of a
complete $k$-partite graph $K_{1,a,\dots,a}$, thus Theorem 3.3 finishes the
proof. ∎

##  4 Concluding remarks

$\bullet$ We showed that if a $k$-chromatic graph $F$ has a color-critical
edge and $\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$, then several $k$-Turán-good
graphs are also $F$-Turán-good. The proof deals only with those copies of
$K_{k}$ that are in the vertex set of a copy of $H$. This suggests to study a
local variant of generalized Turán problems. We say that a subgraph
$G^{\prime}$ of $G$ is $F$-free with respect to $G$ if there is no copy of $F$
induced on $V(G^{\prime})$. How many subgraph of an $n$-vertex graph $G$ can
be isomorphic to $H$ and be $F$-free with respect to $G$ at the same time?

If $F=K_{k}$ and the largest number as an answer to the above question is
obtained when $G=T_{k-1}(n)$, then it is immediate that $H$ is $k$-Turán-good.
The argument used in the proof of Theorem 1.5 shows that for any other $F$
with a color-critical edge and $\mathrm{ex}(n,K_{k},F)=o(n^{k-1})$, we have
that $H$ is also $F$-Turán-good.

$\bullet$ A theme of this paper is to extend some results on $k$-Turán good
graphs to $F$-Turán good graphs when $F$ is a $k$-chromatic graph with a color
critical edge. This motivates the question: is every $k$-Turán-good graph also
$F$-Turán-good?

$\bullet$ Maybe even more is true than what is suggested in the previous
paragraph. Let us call a graph $H$ weakly $F$-Turán-good if the number of
copies of $H$ is maximized by complete multipartite graph among $F$-free
graphs on $n$ vertices, provided $n$ is large enough. Is every weakly
$K_{k}$-Turán-good graph also weakly $F$-Turán-good?

## References

  * [1] N. Alon and C. Shikhelman. Many T copies in H-free graphs. Journal of Combinatorial Theory, Series B, 121:146–172, 2016.
  * [2] B. Bollobás, E. Győri. Pentagons vs. triangles. Discrete Mathematics, 308(19), 4332–4336, 2008.
  * [3] D. Chakraborti, D.Q. Chen. Exact results on generalized Erdős-Gallai problems, arXiv preprint arXiv:2006.04681, 2020.
  * [4] Z. Chase, A Proof of the Gan-Loh-Sudakov Conjecture, arXiv preprint arXiv:1911.08452, 2019.
  * [5] D. Gerbner. Generalized Turán problems for small graphs. arXiv preprint arXiv:2006.16150, 2020.
  * [6] D. Gerbner. Counting multiple graphs in generalized Turán problems. arXiv preprint arXiv:2007.11645, 2020.
  * [7] D. Gerbner, E. Győri, A. Methuku, M. Vizer. Generalized Turán numbers for even cycles. Journal of Combinatorial Theory, Series B, 145, 169–213, 2020.
  * [8] D. Gerbner, C. Palmer. Counting copies of a fixed subgraph in $F$-free graphs. European Journal of Combinatorics 82, 103001
  * [9] D. Gerbner, C. Palmer. Some exact results for generalized Turán problems, arXiv preprint arXiv:2006.03756, 2020.
  * [10] L. Gishboliner, A. Shapira. A Generalized Turán Problem and its Applications. Proceedings of STOC 2018 Theory Fest: 50th Annual ACM Symposium on the Theory of Computing June 25-29, 2018 in Los Angeles, CA, 760–772, 2018.
  * [11] A. Grzesik, On the maximum number of five-cycles in a triangle-free graph. Journal of Combinatorial Theory, Series B, 102, 1061–1066, 2012.
  * [12] E. Győri and H. Li. The maximum number of triangles in $C_{2k+1}$-free graphs. Combinatorics, Probability and Computing 21, 187–191, 2011.
  * [13] E. Győri, J. Pach, and M. Simonovits. On the maximal number of certain subgraphs in $K_{r}$-free graphs. Graphs and Combinatorics, 7(1):31–37, 1991.
  * [14] E. Győri, N. Salia, C. Tompkins, O. Zamora. The maximum number of $P_{l}$ copies in $P_{k}$-free graphs. Acta Mathematica Universitatis Comenianae, 883, 773–778, 2019.
  * [15] H. Hatami, J. Hladký, D. Král’, D. Norine, A. Razborov. On the number of pentagons in triangle-free graphs. Journal of Combinatorial Theory, Series A 120, 722–732, 2012.
  * [16] J. Ma, Y. Qiu. Some sharp results on the generalized Turán numbers. European Journal of Combinatorics, 84, 103026, 2020.
  * [17] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, Academic Press, New York, pp. 279–319, 1968.
  * [18] P. Turán. Egy gráfelméleti szélsőértékfeladatról. Mat. Fiz. Lapok, 48, 436–452, 1941.
  * [19] A. A. Zykov. On some properties of linear complexes. Matematicheskii sbornik, 66(2):163–188, 1949.