Lia Morra, Alberto Azzari, Letizia Bergamasco, Marco Braga, Luigi Capogrosso, Federico Delrio, Giuseppe Di Giacomo, Simone Eiraudo, Giorgia Ghione, Rocco Giudice, Alkis Koudounas, Luca Piano, Daniele Rege Cambrin, Matteo Risso, Marco Rondina, Alessandro Sebastien Russo, Marco Russo, Francesco Taioli, Lorenzo Vaiani, and Chiara Vercellino.
Designing logic tensor networks for visual sudoku puzzle classification.
In International Workshop on Neural-Symbolic Learning and Reasoning (NeSy), 2023.

[99]
Neural-Symbolic Learning and Reasoning Workshop at IJCAI, 2005.

[100]
International Conference on Neural-Symbolic Learning and Reasoning, 2024.

[Nocedal and Wright, 2006]
Jorge Nocedal and Stephen J. Wright.
Numerical Optimization.
Springer, second edition, 2006.

[Olausson et al., 2023]
Theo Olausson, Alex Gu, Ben Lipkin, Cedegao Zhang, Armando Solar-Lezama, Joshua Tenenbaum, and Roger Levy.
Linc: A neurosymbolic approach for logical reasoning by combining language models with first-order logic provers.
In EMNLP, 2023.

[OpenAI, 2024]
Gpt-4 technical report.
Technical report, OpenAI, 2024.

[P. Kingma and LeCun, 2010]
Diedrik P. Kingma and Yann LeCun.
Regularized estimation of image statistics by score matching.
In NeurIPS, 2010.

[Pan et al., 2023]
Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang.
Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning.
In EMNLP, 2023.

[Parikh and Boyd, 2013]
Neal Parikh and Stephen Boyd.
Proximal algorithms.
Foundations and Trends in Machine Learning (FTML), 30 (1):0 123–231, 2013.

[Pedregosa, 2016]
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient.
In ICML, 2016.

[Pryor et al., 2023]
Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Yang Wang, and Lise Getoor.
Neupsl: Neural probabilistic soft logic.
In IJCAI, 2023a.

[Pryor et al., 2023]
Connor Pryor, Quan Yuan, Jeremiah Zhe Liu, Seyed Mehran Kazemi, Deepak Ramachandran, Tania Bedrax-Weiss, and Lise Getoor.
Using domain knowledge to guide dialog structure induction via neural probabilistic soft logic.
In Annual Meeting of the Association for Computational Linguistics (ACL), Toronto, Canada, 2023b.

[Rajeswaran et al., 2019]
Aravind Rajeswaran, Chelsea Finn, Sham M. Kakade, and Sergey Levine.
Meta-learning with implicit gradients.
In NeurIPS, 2019.

[Richardson et al., 2003]
Matthew Richardson, Rakesh Agrawal, and Pedro Domingos.
Trust management for the semantic web.
In ISWC, 2003.

[Robinson, 1980]
Stephen Robinson.
Strongly regular generalized equations.
Mathematics of Operations Research, 50 (1):0 43–62, 1980.

[Rockafellar, 1970]
R. Tyrrell Rockafellar.
Convex Analysis.
Princeton University Press, 1970.

[Rockafellar, 1974]
R. Tyrrell Rockafellar.
Conjugate duality and optimization.
In Regional Conference Series in Applied Mathematics, 1974.

[Rockafellar and Wets, 1997]
R. Tyrrell Rockafellar and Roger J-B Wets.
Variational Analysis.
Springer, 1997.

[Rocktäschel and Riedel, 2017]
Tim Rocktäschel and Sebastian Riedel.
End-to-end differentiable proving.
In NeurIPS, 2017.

[Sachan et al., 2018]
Mrinmaya Sachan, Kumar Avinava Dubey, Tom M Mitchell, Dan Roth, and Eric P Xing.
Learning pipelines with limited data and domain knowledge: A study in parsing physics problems.
In NeurIPS, 2018.

[Salakhutdinov and Larochelle, 2010]
Ruslan Salakhutdinov and Hugo Larochelle.
Efficient learning of deep boltzmann machines.
In AISTATS, 2010.

[Scellier and Bengio, 2017]
Benjamin Scellier and Yoshua Bengio.
Equilibrium propagation: Bridging the gap between energy-based models and backpropagation.
Frontiers in Computational Neuroscience, 11, 2017.

[Sen et al., 2008]
Prithviraj Sen, Galileo Mark Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad.
Collective classification in network data.
AI Magazine, 290 (3):0 93–106, 2008.

[Shalev-Shwartz, 2012]
Shai Shalev-Shwartz.
Online learning and online convex optimization.
Foundations and Trends in Machine Learning (FTML), 40 (2):0 107–194, 2012.

[Sikka et al., 2020]
Karan Sikka, Andrew Silberfarb, John Byrnes, Indranil Sur, Ed Chow, Ajay Divakaran, and Richard Rohwer.
Deep adaptive semantic logic (dasl): Compiling declarative knowledge into deep neural networks.
Technical report, SRI International, 2020.

[Singh et al., 2021]
Gurkirt Singh, Stephen Akrigg, Manuele Di Maio, Valentina Fontana, Reza Javanmard Alitappeh, Suman Saha, Kossar Jeddi Saravi, Farzad Yousefia, Jacob Culley, Tom Nicholson, Jordan Omokeowa, Salman Khan, Stanislao Grazioso, Andrew Bradley, Giuseppe Di Gironimo, and Fabio Cuzzolin.
Road: The road event awareness dataset for autonomous driving.
IEEE TPAMI, 45:0 1036–1054, 2021.

[Song and Ermon, 2019]
Yang Song and Stefano Ermon.
Generative modeling by estimating gradient of the data distribution.
In NeurIPS, 2019.

[Sow et al., 2022]
Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang.
A primal-dual approach to bilevel optimization with multiple inner minima.
Arxiv, 2022.

[Sridhar et al., 2016]
Dhanya Sridhar, Shobeir Fakhraei, and Lise Getoor.
A probabilistic approach for collective similarity-based drug-drug interaction prediction.
Bioinformatics, 320 (20):0 3175–3182, 2016.

[Srinivasan et al., 2021]
Sriram Srinivasan, Charles Dickens, Eriq Augustine, Golnoosh Farnadi, and Lise Getoor.
A taxonomy of weight learning methods for statistical relational learning.
Machine Learning, 2021.

[Srivastava et al., 2022]
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W. Kocurek, Ali Safaya, Ali Tazarv, Alice Xiang, Alicia Parrish, Allen Nie, Aman Hussain, Amanda Askell, Amanda Dsouza, Ambrose Slone, Ameet Annasaheb Rahane, Anantharaman S. Iyer, Anders Andreassen, Andrea Madotto, Andrea Santilli, Andreas Stuhlmuller, Andrew M. Dai, Andrew La, Andrew Kyle Lampinen, Andy Zou, Angela Jiang, Angelica Chen, Anh Vuong, Animesh Gupta, Anna Gottardi, Antonio Norelli, Anu Venkatesh, Arash Gholamidavoodi, Arfa Tabassum, Arul Menezes, Arun Kirubarajan, Asher Mullokandov, Ashish Sabharwal, Austin Herrick, Avia Efrat, Aykut Erdem, Ayla Karakacs, and et al.
Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.
ArXiv, 2022.

[Stoian et al., 2023]
Mihaela Cătălina Stoian, Eleonora Giunchiglia, and Thomas Lukasiewicz.
Exploiting t-norms for deep learning in autonomous driving.
In NeSy, 2023.

[Stoyanov et al., 2011]
Veselin Stoyanov, Alexander Ropson, and Jason Eisner.
Empirical risk minimization of graphical model parameters given approximate inference, decoding, and model structure.
In AISTATS, 2011.

[Sutton and Barto, 2018]
Richard Sutton and Andrew Barto.
Reinforcement Learning: An Introduction.
MIT Press, 2018.

[Sutton et al., 1999]
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour.
Policy gradient methods for reinforcement learning with function approximation.
In NeurIPS, 1999.

[Tran and d’Avila Garcez, 2018]
Son N. Tran and Artur S. d’Avila Garcez.
Deep logic networks: Inserting and extracting knowledge from deep belief networks.
IEEE Transactions on Neural Networks and Learning Systems, 290 (2):0 246–258, 2018.

[V. Outrata, 1990]
Jivrí V. Outrata.
On the numerical solution of a class of stackelberg problems.
Methods and Models of Operations Research, 340 (4):0 255–277, 1990.

[van Krieken et al., 2022]
Emile van Krieken, Erman Acar, and Frank van Harmelen.
Analyzing differentiable fuzzy logic operators.
Artificial Intelligence (AI), 302:0 103602, 2022.

[van Krieken et al., 2023]
Emile van Krieken, Thiviyan Thanapalasingam, Jakub M. Tomczak, Frank van Harmelen, and Annette ten Teije.
A-nesi: A scalable approximate method for probabilistic neurosymbolic inference.
In NeurIPS, 2023.

[van Krieken et al., 2024]
Emile van Krieken, Samy Badreddine, Robin Manhaeve, and Eleonora Giunchiglia.
Uller: A unified language for learning and reasoning.
arXiv, 2024.

[Vlastelica et al., 2020]
Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínek.
Differentiation of blackbox combinatorial solvers.
In ICLR, 2020.

[Walker et al., 2012]
Marilyn A Walker, Jean E Fox Tree, Pranav Anand, Rob Abbott, and Joseph King.
A corpus for research on deliberation and debate.
In LREC, 2012.

[Wan et al., 2024]
Zishen Wan, Che-Kai Liu, Hanchen Yang, Chaojian Li, Haoran You, Yonggan Fu, Cheng Wan, Tushar Krishna, Yingyan Lin, and Arijit Raychowdhury.
Towards cognitive ai systems: A survey and prospective on neuro-symbolic ai.
arXiv, 2024.

[Wang et al., 2019]
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter.
Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.
In ICML, 2019.

[Wei et al., 2022]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou.
Chain-of-thought prompting elicits reasoning in large language models.
In NeurIPS, 2022.

[Welling and Teh, 2011]
Max Welling and Yee W Teh.
Bayesian learning via stochastic gradient langevin dynamics.
In ICML, 2011.

[Williams, 1992]
Ronald Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning.
Machine Learning, 8:0 229–256, 1992.

[Winters et al., 2022]
Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt.
Deepstochlog: Neural stochastic logic programming.
In AAAI, 2022.

[Wishart et al., 2006]
David S Wishart, Craig Knox, An Chi Guo, Savita Shrivastava, Murtaza Hassanali, Paul Stothard, Zhan Chang, and Jennifer Woolsey.
Drugbank: a comprehensive resource for in silico drug discovery and exploration.
Nucleic Acids Research (NAR), 34:0 D668–D672, 2006.

[Wu et al., 2019]
Felix Wu, Tianyi Zhang, Amauiri Holanda de Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q. Weinberger.
Simplifying graph convolutional networks.
In ICML, 2019.

[Xu et al., 2018]
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck.
A semantic loss function for deep learning with symbolic knowledge.
In ICML, 2018.

[Yang et al., 2020]
Zhun Yang, Adam Ishay, and Joohyung Lee.
Neurasp: Embracing neural networks into answer set programming.
In IJCAI, 2020.

[Yi et al., 2019]
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Joshua B. Tenenbaum.
Neural-symbolic vqa: Disentanlging reasoning from vision and language understanding.
In NeurIPS, 2019.

[Zhang et al., 2023]
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck.
Tractable control for autoregressive language generation.
In International Conference on Machine Learning (ICML), 2023.

[Zhao et al., 2017]
Junbo Zhao, Michael Mathieu, and Yann LeCun.
Energy-based generative adversarial networks.
In ICLR, 2017.

[Zhou et al., 2023]
Kaiwen Zhou, Kaizhi Zheng, Connor Pryor, Yilin Shen, Hongxia Jin, Lise Getoor, and Xin Eric Wang.
Esc: Exploration with soft commonsense constraints for zero-shot object navigation.
In International Conference on Machine Learning (ICML), 2023.


# Approximate minimum cuts and their enumeration111University of Illinois,
Urbana-Champaign. Email: {calvinb2, karthe<EMAIL_ADDRESS>Supported
in part by NSF grants CCF-1814613 and CCF-1907937.

Calvin Beideman  Karthekeyan Chandrasekaran  Weihang Wang

###### Abstract

We show that every $\alpha$-approximate minimum cut in a connected graph is
the _unique_ minimum $(S,T)$-terminal cut for some subsets $S$ and $T$ of
vertices each of size at most $\lfloor 2\alpha\rfloor+1$. This leads to an
alternative proof that the number of $\alpha$-approximate minimum cuts in a
$n$-vertex connected graph is $n^{O(\alpha)}$ and they can all be enumerated
in deterministic polynomial time for constant $\alpha$.

##  1 Introduction

Let $G=(V,E)$ be a graph with positive edge costs
$c:E\rightarrow\mathbb{R}_{+}$. A partitioning of the vertex set into $2$ non-
empty parts is known as a _cut_. For a non-empty proper subset $U$ of
vertices, we will use $\overline{U}$ to denote $V\setminus U$,
$(U,\overline{U})$ to denote the cut associated with $U$, $\delta(U)$ to
denote the set of edges crossing the cut $(U,\overline{U})$, and
$d(U):=\sum_{e\in\delta(U)}c(e)$ to denote the cut value of $U$. We will use
$\lambda$ to denote the value of a minimum cut in $G$, i.e.,

$\lambda:=\min\\{d(U):\emptyset\neq U\subsetneq V\\}.$

For $\alpha\geq 1$, a cut $(U,\overline{U})$ is an _$\alpha$ -approximate
minimum cut_ if $d(U)\leq\alpha\lambda$. A fundamental graph structural result
states that the number of $\alpha$-approximate minimum cuts in a $n$-vertex
connected graph is $O(n^{2\alpha})$. This structural result forms the backbone
of several algorithmic and representation results in graphs—e.g., fast
randomized construction of skeletons [12], existence of cut sparsifiers which
in turn finds applications in streaming and sketching [1, 2, 3, 14],
approximation algorithms for TSP [17, 4, 6, 5], computing reliability of
probabilistic networks [11], and polynomial time algorithms for connectivity
augmentation [16]. The structural result along with a randomized polynomial-
time algorithm to enumerate all constant-approximate minimum cuts was first
shown via Karger’s random contraction technique [13]. Subsequently, the
splitting-off technique and the tree packing technique have been used to show
the structural result along with a _deterministic_ polynomial-time algorithm
to enumerate all constant-approximate minimum cuts [15, 8].

In this work, we give a fourth technique to bound the number of
$\alpha$-approximate minimum cuts by $n^{O(\alpha)}$ along with a
deterministic polynomial-time algorithm to enumerate all constant-approximate
minimum cuts. Let $S$, $T$ be disjoint non-empty subsets of vertices. A
$2$-partition $(U,\overline{U})$ is an $(S,T)$-terminal cut if $S\subseteq
U\subseteq V\setminus T$. Here, the set $U$ is known as the _source set_ and
the set $\overline{U}$ is known as the _sink set_. An $(S,T)$-terminal cut
with minimum cut value will be denoted as a _minimum $(S,T)$-terminal cut_.
The following is our main result.

######  Theorem 1.1.

Let $G=(V,E)$ be a connected graph with positive edge costs and
$(U,\overline{U})$ be an $\alpha$-approximate minimum cut for some $\alpha\geq
1$. Then, there exist subsets $S,T\subseteq V$ with $|S|,|T|\leq\lfloor
2\alpha\rfloor+1$ such that $(U,\overline{U})$ is the unique minimum
$(S,T)$-terminal cut.

In other words, every $\alpha$-approximate minimum cut $(U,\overline{U})$ in a
connected graph can be recovered as the _unique_ minimum $(S,T)$-terminal cut
for some subsets $S$ and $T$ of sizes at most $\lfloor 2\alpha\rfloor+1$. A
few remarks are in order.

######  Remark 1.1.

An immediate consequence of Theorem 1.1 is that the number of distinct
$\alpha$-approximate minimum cuts in a $n$-vertex connected graph is at most
$n^{4\alpha+2}$ and they can all be enumerated using $n^{4\alpha+2}$ minimum
$(S,T)$-terminal cut computations. We recall that minimum $(S,T)$-terminal cut
in a given graph with given subsets $S$ and $T$ of vertices can be computed in
deterministic polynomial time.

######  Remark 1.2.

The size bound for subsets $S$ and $T$ in Theorem 1.1 is tight up to an
additive factor of one: Consider the $n$-vertex cycle graph $G$ with $\alpha$
being a positive integer where $n\geq 4\alpha$ and with all edge costs being
$1$. Let $(U,\overline{U})$ be a cut in $G$ with $d(U)=2\alpha$ and moreover,
each connected component in $G-\delta(U)$ has at least $2$ vertices (see
Figure 1 for such an example where $\alpha=4$). For such a cut
$(U,\overline{U})$, the only choice of $S$ and $T$ for which
$(U,\overline{U})$ is the _unique_ minimum $(S,T)$-terminal cut is given by

$\displaystyle S$ $\displaystyle:=\\{v\in U:v\text{ is an end vertex of an
edge in }\delta(U)\\}\text{ and}$ $\displaystyle T$
$\displaystyle:=\\{v\in\overline{U}:v\text{ is an end vertex of an edge in
}\delta(U)\\}.$

Hence, this example shows that both $S$ and $T$ need to have at least
$2\alpha$ vertices in order to recover $(U,\overline{U})$ as the _unique_
minimum $(S,T)$-terminal cut.

Figure 1: An example showing the tightness of Theorem 1.1: The set $U$
consists of vertices within all gray boxes and the set $\overline{U}$ consists
of all vertices outside gray boxes; the dotted edges correspond to the edges
in the cut set $\delta(U)$. The only choice of $S$ and $T$ for which
$(U,\overline{U})$ is the unique minimum $(S,T)$-terminal cut is as follows:
$S$ consists of all vertices that are shaded black and $T$ consists of all
vertices that are shaded gray.

Theorem 1.1 is inspired by a result of Goemans and Ramakrishnan [9]. They
showed the following structural theorem for $(4/3-\epsilon)$-approximate
minimum cuts: fix an arbitrary vertex $t$ in a connected graph $G=(V,E)$ and
let $(U,\overline{U})$ be a $(4/3-\epsilon)$-approximate minimum cut with
$t\in\overline{U}$ for some $\epsilon>0$. Then, there exists a subset $S$ of
size at most $2$ such that $(U,\overline{U})$ is the unique minimum
$(S,\\{t\\})$-terminal cut. Their result leads to the following natural
question: for every $\alpha\geq 1$, can every $\alpha$-approximate minimum cut
$(U,\overline{U})$ be obtained as a minimum $(S,T)$-terminal cut for some
subsets $S$ and $T$ of vertices each of size at most some function of
$\alpha$? Our Theorem 1.1 answers this question affirmatively. However, our
proof of Theorem 1.1 deviates significantly from the proof approach of
Goemans-Ramakrishnan’s structural result for $(4/3-\epsilon)$-approximate
minimum cuts. Their proof proceeds via contradiction and relies on the
_submodular triple inequality_ which holds for the graph cut function. The
submodular triple inequality shows that $3$ non-empty sets satisfying certain
crossing properties can be uncrossed to obtain $4$ disjoint non-empty sets
without increasing the sum of their cut values; thus, if all $3$ sets have cut
value less than $(4/3)\lambda$, then one of the $4$ sets should have cut value
strictly smaller than $\lambda$, a contradiction to the definition of
$\lambda$. However, there does not seem to be a generalization of the
submodular triple inequality to larger number of sets. Our proof of Theorem
1.1 circumvents the submodular triple inequality but achieves its intended
purpose in this context—we show that a sufficiently large number of
$\alpha$-approximate minimum cuts with certain crossing properties can be
uncrossed to obtain a cut of value cheaper than $\lambda$, thus leading to a
contradiction again.

###  1.1 Preliminaries

Let $G=(V,E)$ be a graph with positive edge costs
$c:E\rightarrow\mathbb{R}_{+}$. For disjoint non-empty subsets $S,T\subseteq
V$, there can be multiple minimum $(S,T)$-terminal cuts. We will be interested
in _source minimal_ minimum $(S,T)$-terminal cuts. A minimum $(S,T)$-terminal
cut $(U,\overline{U})$ is a source minimal minimum $(S,T)$-terminal cut if for
all minimum $(S,T)$-terminal cut $(X,\overline{X})$, we have $U\subseteq X$.
For every pair of disjoint non-empty subsets $S$ and $T$ of vertices, there
exists a unique source minimal minimum $(S,T)$-terminal cut (this is due to
submodularity—e.g., see [9]).

We recall that the graph cut function $d:2^{V}\rightarrow\mathbb{R}$ is
symmetric and submodular, i.e., $d(A)=d(V\setminus A)$ and $d(A)+d(B)\geq
d(A\cap B)+d(A\cup B)$ for all $A,B\subseteq V$. We will need an uncrossing
result that relies on more careful counting of edges than simply employing the
submodularity inequality. We begin with some notation that will help in such
careful counting. Let $(Y_{1},\ldots,Y_{p},W,Z)$ be a partition of $V$ into
$p+2$ non-empty parts. We define

$\displaystyle\sigma(Y_{1},\ldots,Y_{p},W,Z)$
$\displaystyle:=2\left(\sum_{uv\in E:\ u\in Y_{i},\ v\in Y_{j}\text{ for
distinct }i,\ j\in[p]}c(uv)+\sum_{uv\in E:\ u\in W,\ v\in Z}c(uv)\right)$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad+\sum_{uv\in E:\
u\in\cup_{i\in[p]}Y_{i},\ v\in W\cup Z}c(uv)$

We note that

$\displaystyle\sum_{i\in[p]}d(Y_{i})$
$\displaystyle\leq\sigma(Y_{1},\ldots,Y_{p},W,Z).$ (1)

The following lemma uncrosses a collection of $p$ sets to obtain a partition
of the vertex set into $p+2$ non-empty parts with small $\sigma$-value. The
lemma was shown by Kamidoi, Yoshida, and Nagamochi in the context of minimum
$k$-cuts [10]. It was also extended to hypergraphs by Chandrasekaran and
Chekuri [7]. See Figure 2 for an illustration of the sets that appear in the
statement of the lemma.

######  Lemma 1.1.

[10, 7] Let $G=(V,E)$ be a graph with positive edge costs and $\emptyset\neq
R\subsetneq U\subsetneq V$. Let $S=\\{u_{1},\ldots,u_{p}\\}\subseteq
U\setminus R$ for $p\geq 2$. For each $i\in[p]$, let
$(\overline{A_{i}},A_{i})$ be a minimum $((S\cup
R)\setminus\\{u_{i}\\},\overline{U})$-terminal cut. Suppose that $u_{i}\in
A_{i}\setminus(\cup_{j\in[p]\setminus\\{i\\}}A_{j})$ for every $i\in[p]$. Let

$Z:=\cap_{i=1}^{p}\overline{A_{i}},\ W:=\cup_{1\leq i<j\leq p}(A_{i}\cap
A_{j}),\ \text{and}\ Y_{i}:=A_{i}-W\ \forall i\in[p].$

Then, $(Y_{1},\ldots,Y_{p},W,Z)$ is a partition of $V$ into $p+2$ non-empty
parts with

$\sigma(Y_{1},\ldots,Y_{p},W,Z)\leq\min\\{d(A_{i})+d(A_{j}):i,j\in[p],i\neq
j\\}.$

Figure 2: Illustration of the sets that appear in the statement of Lemma 1.1.

We briefly remark on the lemma: known proofs of the lemma are by induction on
$p$ with an uncrossing argument that involves careful edge counting. The use
of $\sigma(Y_{1},\ldots,Y_{p},W,Z)$ instead of $\sum_{i\in[p]}d(Y_{i})$ on the
LHS is crucial for the induction argument—this is why we prefer to state the
lemma as giving an upper bound on $\sigma(Y_{1},\ldots,Y_{p},W,Z)$ although we
will use it only to conclude an upper bound on $\sum_{i\in[p]}d(Y_{i})$ via
inequality (1).

##  2 Proof of Theorem 1.1

We will derive Theorem 1.1 from the following theorem.

######  Theorem 2.1.

Let $G=(V,E)$ be a connected graph with positive edge costs and
$(U,\overline{U})$ be an $\alpha$-approximate minimum cut for some $\alpha\geq
1$. Then, there exists a subset $S\subseteq U$ with $|S|\leq\lfloor
2\alpha\rfloor+1$ such that $(U,\overline{U})$ is the unique minimum
$(S,\overline{U})$-terminal cut.

###### Proof.

Consider the collection $\mathcal{C}:=\\{Q\subsetneq V:\overline{U}\subsetneq
Q,d(Q)\leq d(U)\\}$. Suppose $\mathcal{C}$ is empty. Let $S=\\{x\\}$ for some
arbitrary $x\in U$ and let $(X,\overline{X})$ be a minimum
$(S,\overline{U})$-terminal cut. Then,
$\overline{U}\subseteq\overline{X}\subsetneq V$ and $d(\overline{X})\leq
d(U)$. Since $\overline{X}\not\in\mathcal{C}$ (because $\mathcal{C}$ is
empty), we must have $\overline{X}=\overline{U}$. Therefore,
$(U,\overline{U})$ is the unique minimum $(S,\overline{U})$-terminal cut.

Next, suppose $\mathcal{C}\neq\emptyset$. Let $S\subseteq U$ be a minimal
transversal of the collection $\mathcal{C}$, i.e., $S\subseteq U$ is a minimal
set with $S\cap Q\neq\emptyset$ for all $Q\in\mathcal{C}$. Proposition 2.1 and
Lemma 2.1 complete the proof of Theorem 2.1. ∎

######  Proposition 2.1.

$(U,\overline{U})$ is the unique minimum $(S,\overline{U})$-terminal cut.

###### Proof.

Suppose $(X,\overline{X})$ be the source minimal minimum
$(S,\overline{U})$-terminal cut with $X\neq U$. Since $(U,\overline{U})$ is a
$(S,\overline{U})$-terminal cut, we have $d(\overline{X})=d(X)\leq d(U)$.
Moreover, we have $\emptyset\neq X\subsetneq U$, which implies that
$\overline{U}\subsetneq\overline{X}\subsetneq V$. Hence, we have
$\overline{X}\in\mathcal{C}$, and thus $S\cap\overline{X}\neq\emptyset$. This
contradicts with the assumption that $(X,\overline{X})$ is a
$(S,\overline{U})$-terminal cut. Therefore, we must have $X=U$. ∎

######  Lemma 2.1.

$|S|\leq\lfloor 2\alpha\rfloor+1$.

###### Proof.

For the sake of contradiction, suppose that $|S|\geq\lfloor 2\alpha\rfloor+2$.
Let $\lambda$ denote the value of a minimum cut in $G$. Our proof strategy is
to arrive at a cut with value cheaper than $\lambda$, thus contradicting the
definition of $\lambda$. For convenience, we will denote $p:=|S|$ and write
$S=\\{u_{1},\ldots,u_{p}\\}$. For each $i\in[p]$, let
$(\overline{A_{i}},A_{i})$ be the source minimal minimum
$(S-u_{i},\overline{U})$-terminal cut.

######  Claim 2.1.

For every $i\in[p]$, we have $d(A_{i})\leq d(U)$ and $u_{i}\in A_{i}$.

###### Proof.

Let $i\in[p]$. Since $S$ is a minimal transversal of the collection
$\mathcal{C}$, there exists a set $B_{i}\in\mathcal{C}$ such that $B_{i}\cap
S=\\{u_{i}\\}$. Hence, $(\overline{B_{i}},B_{i})$ is a
$(S-u_{i},\overline{U})$-terminal cut. Therefore,

$d(A_{i})\leq d(B_{i})\leq d(U).$

We will show that $A_{i}$ is in the collection $\mathcal{C}$. By definition,
$A_{i}\subseteq V\setminus(S-u_{i})\subsetneq V$ and $\overline{U}\subseteq
A_{i}$. If $A_{i}=\overline{U}$, then the above inequalities are equations
(since $d(A_{i})=d(\overline{U})=d(U)$) implying that
$(\overline{B_{i}},B_{i})$ is a minimum $(S-u_{i},\overline{U})$-terminal cut,
and consequently, $(\overline{B_{i}},B_{i})$ contradicts source minimality of
the minimum $(S-u_{i},\overline{U})$-terminal cut $(\overline{A_{i}},A_{i})$.
Therefore, $\overline{U}\subsetneq A_{i}$. Hence, $A_{i}$ is in the collection
$\mathcal{C}$.

We recall that the set $S$ is a transversal for the collection $\mathcal{C}$
and moreover, none of the elements of $S-u_{i}$ are in $A_{i}$ by definition
of $A_{i}$. Therefore, the vertex $u_{i}$ must be in $A_{i}$. ∎

We recall our assumption that $p\geq\lfloor 2\alpha\rfloor+2$. We note that
$p-1>2\alpha\geq 2$. Using Claim 2.1, we observe that the sets $U$,
$R:=\\{u_{p}\\}$, $S=\\{u_{1},\ldots,u_{p-1}\\}$, and partitions
$(\overline{A_{i}},A_{i})$ for $i\in[p-1]$ satisfy the conditions of Lemma
1.1. Therefore, applying Lemma 1.1 shows the existence of a partition
$(Y_{1},\ldots,Y_{p-1},W,Z)$ of $V$ into $p+1$ non-empty parts such that

$\displaystyle\sigma(Y_{1},\ldots,Y_{p-1},W,Z)$
$\displaystyle\leq\min\\{d(A_{i})+d(A_{j}):i,j\in[p-1],i\neq j\\}\leq
2d(U)\leq 2\alpha\lambda.$

By inequality (1), this implies that

$\displaystyle\sum_{i\in[p-1]}d(Y_{i})\leq 2\alpha\lambda.$

Therefore, there exists $i\in[p-1]$ such that

$\displaystyle d(Y_{i})\leq\frac{2\alpha\lambda}{p-1}<\lambda.$

The last inequality is because $p-1>2\alpha$ and $\lambda>0$ since the graph
is connected. Thus, we have a cut $(Y_{i},\overline{Y_{i}})$ with cut value
smaller than $\lambda$, a contradiction to the definition of $\lambda$. ∎

Applying Theorem 2.1 to $(\overline{U},U)$ yields the following corollary.

######  Corollary 2.1.

Let $G=(V,E)$ be a connected graph with positive edge costs and
$(U,\overline{U})$ be an $\alpha$-approximate minimum cut for some $\alpha\geq
1$. Then, there exists a subset $T\subseteq\overline{U}$ with $|T|\leq\lfloor
2\alpha\rfloor+1$ such that $(U,\overline{U})$ is the unique minimum
$(U,T)$-terminal cut.

We now restate Theorem 1.1 and prove it using Theorem 2.1 and Corollary 2.1.

See 1.1

###### Proof.

By Theorem 2.1, there exists a subset $S\subseteq U$ with $|S|\leq\lfloor
2\alpha\rfloor+1$ such that $(U,\overline{U})$ is the unique minimum
$(S,\overline{U})$-terminal cut. By Corollary 2.1, there exists a subset
$T\subseteq\overline{U}$ with $|T|\leq\lfloor 2\alpha\rfloor+1$ such that
$(U,\overline{U})$ is the unique minimum $(U,T)$-terminal cut. For these
choices of subsets $S$ and $T$, we now show that $(U,\overline{U})$ is the
unique minimum $(S,T)$-terminal cut.

Let $(Y,\overline{Y})$ be an arbitrary minimum $(S,T)$-terminal cut. It
suffices to show that $Y=U$. Since $(U,\overline{U})$ is a $(S,T)$-terminal
cut, we have that

$d(Y)\leq d(U).$

Since $(Y\cap U,\overline{Y\cap U})$ is a $(S,\overline{U})$-terminal cut and
$(U,\overline{U})$ is a minimum $(S,\overline{U})$-terminal cut, we have that

$d(U)\leq d(Y\cap U).$

Since $(Y\cup U,\overline{Y\cup U})$ is a $(U,T)$-terminal cut and
$(U,\overline{U})$ is a minimum $(U,T)$-terminal cut, we have that

$d(U)\leq d(Y\cup U).$

Using the above inequalities in conjunction with the submodularity of the cut
function, we obtain that

$2d(U)\leq d(U\cap Y)+d(U\cup Y)\leq d(U)+d(Y)\leq 2d(U).$

Hence, all of the above inequalities should be equations. Consequently,
$(Y\cap U,\overline{Y\cap U})$ is a minimum $(S,\overline{U})$-terminal cut,
and $(Y\cup U,\overline{Y\cup U})$ is a minimum $(U,T)$-terminal cut. This
implies that $Y\cap U=U$ since $(U,\overline{U})$ is the unique minimum
$(S,\overline{U})$-terminal cut and $Y\cup U=U$ since $(U,\overline{U})$ is
the unique minimum $(U,T)$-terminal cut. Thus, we have that $Y=U$. ∎

##  3 An Open Problem

The fundamental structural result that the number of $\alpha$-approximate
minimum cuts in a $n$-vertex connected graph is at most $n^{O(\alpha)}$ has
been extended to $r$-rank hypergraphs (the _rank_ of a hypergraph is the size
of the largest hyperedge): Kogan and Krauthgamer [14] used the random
contraction technique to show that the number of $\alpha$-approximate minimum
cuts in a $r$-rank $n$-vertex connected hypergraph is $O(2^{\alpha
r}n^{2\alpha})$ and they can all be enumerated in randomized polynomial time
for constant $\alpha$ and $r$. It would be interesting to give a
_deterministic_ proof of this bound.

## References

  * [1] K. Ahn and S. Guha, _Graph sparsification in the semi-streaming model_ , Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part II, ICALP, 2009, pp. 328–338.
  * [2] K. Ahn, S. Guha, and A. McGregor, _Analyzing graph structure via linear measurements_ , Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2012, pp. 459–467.
  * [3] , _Graph sketches: Sparsification, spanners, and subgraphs_ , Proceedings of the 31st Symposium on Principles of Database Systems, PODS, 2012, pp. 5–14.
  * [4] A. Benczur, _A representation of cuts within 6/5 times the edge connectivity with applications_ , Proceedings of the 36th Annual IEEE Foundations of Computer Science, FOCS, 1995, pp. 92–102.
  * [5] , _Cut structures and randomized algorithms in edge-connectivity problems_ , Ph.D. thesis, MIT, 1997.
  * [6] A. Benczur and M. Goemans, _Deformable polygon representation and near-mincuts_ , Building Bridges: Between Mathematics and Computer Science, M. Groetschel and G.O.H. Katona, Eds., Bolyai Society Mathematical Studies 19 (2008), 103–135.
  * [7] K. Chandrasekaran and C. Chekuri, _Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time_, Mathematics of Operations Research (2022), Prelim. version in Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) pages 810–821.
  * [8] C. Chekuri, K. Quanrud, and C. Xu, _LP relaxation and tree packing for minimum $k$-cut_, SIAM Journal on Discrete Mathematics 34 (2020), no. 2, 1334–1353.
  * [9] M. X. Goemans and V. S. Ramakrishnan, _Minimizing submodular functions over families of sets_ , Combinatorica 15 (1995), 499–513.
  * [10] Y. Kamidoi, N. Yoshida, and H. Nagamochi, _A Deterministic Algorithm for Finding All Minimum $k$-Way Cuts_, SIAM Journal on Computing 36 (2007), no. 5, 1329–1341.
  * [11] D. Karger, _A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem_ , SIAM Journal on Computing 29 (1999), no. 2, 492–514.
  * [12] , _Minimum cuts in near-linear time_ , Journal of the ACM 47 (2000), no. 1, 46–76.
  * [13] D. Karger and C. Stein, _A new approach to the minimum cut problem_ , Journal of the ACM 43 (1996), no. 4, 601–640.
  * [14] D. Kogan and R. Krauthgamer, _Sketching cuts in graphs and hypergraphs_ , Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS, 2015, pp. 367–376.
  * [15] H. Nagamochi, K. Nishimura, and T. Ibaraki, _Computing all small cuts in an undirected network_ , SIAM Journal on Discrete Mathematics 10 (1997), no. 3, 469–481.
  * [16] D. Naor, D. Gusfield, and C. Martel, _A fast algorithm for optimally increasing the edge connectivity_ , SIAM Journal on Computing 26 (1997), no. 4, 1139–1165.
  * [17] R. Zenklusen, _A $1.5$-Approximation for Path TSP_, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2019, pp. 1539–1549.


We study the effect of the fragility of glass formers on the yielding
transition under oscillatory shear via extensive computer simulations.
Employing sphere assemblies interacting with a harmonic potential as our model
glass former, we tune fragility by changing the system’s density — higher
density corresponds to large fragility. Our study reveals significant
differences in the yielding transition between strong and fragile glass
formers. While both glass formers exhibit similar behaviour for poorly
annealed initial conditions, the yielding transition shifts to larger values
with increased annealing for fragile glasses while remaining relatively
constant for strong glasses. We rationalize our results by introducing a new
elastoplastic model, which qualitatively reproduces the simulation results and
offers valuable insight into the physics of yielding transition under
oscillatory shear deformation.

# Role of Fragility of the Glass Formers in the Yielding Transition under
Oscillatory Shear

Roni Chatterjee  Tata Institute of Fundamental Research, 36/P, Gopanpally
Village, Serilingampally Mandal, Ranga Reddy District, Hyderabad 500046,
Telangana, India  Monoj Adhikari  Tata Institute of Fundamental Research,
36/P, Gopanpally Village, Serilingampally Mandal, Ranga Reddy District,
Hyderabad 500046, Telangana, India  Smarajit Karmakar  Tata Institute of
Fundamental Research, 36/P, Gopanpally Village, Serilingampally Mandal, Ranga
Reddy District, Hyderabad 500046, Telangana, India

Introduction: Understanding the mechanical behavior of amorphous solids is
crucial due to its enormous applications ranging from bulk to nanoscales
Fielding  _et al._ (2000); Falk and Langer (2011); Schuh  _et al._ (2007);
Bonn  _et al._ (2017) in our day-to-day life. Specifically, the study of
amorphous solids under external shear deformation has drawn significant
interest in designing better materials for future applications in recent
years. Among these, a large number of studies focus on comprehending the
response of amorphous solids to uniform shear deformation Shi and Falk (2005);
Shi  _et al._ (2007); Karmakar  _et al._ (2010a, b); Keim and Arratia (2013);
Denisov  _et al._ (2015); Lin  _et al._ (2014); Bhowmik  _et al._ (2019);
Barbot  _et al._ (2020). At small amplitude deformations, the response closely
resembles that of crystalline solids; however, under large deformation,
numerous plastic deformations occur, eventually leading to yielding and the
system starts to flow. Although the nature of the yielding transition is a
subject of debate Kawasaki and Berthier (2016); Procaccia  _et al._ (2017);
Jaiswal  _et al._ (2016); Shrivastav  _et al._ (2016), energy, or stress shows
a discontinuity when driven by oscillatory shear deformation at the yielding
transition Fiocco  _et al._ (2013); Regev  _et al._ (2013); Nagamanasa  _et
al._ (2014); Leishangthem  _et al._ (2017); Parmar  _et al._ (2019).

Recent investigations using cyclic shear predominantly under athermal quasi-
static (AQS) conditions indicate that the yielding transition depends on the
initial sample’s degree of annealing or inherent structure energy. In poorly
annealed systems, stroboscopic energy decreases with increasing amplitude of
deformation until the yielding amplitude, after which it increases again. Near
yielding, the system undergoes an absorbing to diffusing transition: for
smaller amplitudes below yielding, the system reaches a steady state called
the absorbing state with an invariant stroboscopic configuration; for
amplitudes larger than yielding, the steady states are diffusing states where
the configuration keeps changing with the number of cycles. This scenario
changes significantly if the systems are sufficiently annealed so that the
initial energy is below a threshold energy, shown to be the energy at the Mode
Coupling Transition temperature Yeh  _et al._ (2020); Bhaumik  _et al._
(2021). The energy of the system remains constant until reaching the yielding
amplitude, where it undergoes a sudden increase and reaches the diffusive
states. A similar discontinuous jump in energy is also observed under uniform
shear as well Ozawa  _et al._ (2018); Bhaumik  _et al._ (2021). This effect of
annealing on yielding is robust across various model systems Divoux  _et al._
(2023); Ozawa  _et al._ (2018); Barlow  _et al._ (2020); Ozawa  _et al._
(2023); Keim and Medina (2022); Pollard and Fielding (2022); Mutneja  _et al._
(2023), different driving protocols Krishnan  _et al._ (2023); Adhikari  _et
al._ (2022), finite temperature, finite shear rate Singh  _et al._ (2020);
Lamp  _et al._ (2022), and different dimensions Singh  _et al._ (2020); Ozawa
_et al._ (2020); Bhaumik  _et al._ (2022).

For poorly annealed glasses, the stress vs. strain curve exhibits a monotonic
trend, and the transition to a fluid state is smooth or gradual, particularly
under uniform shear conditions. Under cyclic shear, the yielding point is more
precisely defined. However, in both cases, material failure resembles ductile
behavior. As the degree of annealing increases, a large discontinuous stress
drop is observed at yielding in both uniform and cyclic shear, indicating an
abrupt and catastrophic transition, characteristic of brittle behavior. The
observation of two distinct yielding behaviors, solely by adjusting the degree
of annealing, which correlates with the temperature at which the liquid is
prepared, raises questions about the existence of a potential phase
transition. To answer these questions, various coarse-grained models have been
introduced Ozawa  _et al._ (2018); Sastry (2021); Barlow  _et al._ (2020);
Parley  _et al._ (2022); Khirallah  _et al._ (2021); Liu  _et al._ (2022);
Kumar  _et al._ (2022); Rossi  _et al._ (2022); Parley and Sollich (2023).
which successfully reproduce the observed behaviour in simulation and also
attempt to answer the existence of the phase transition. While many of these
models support the notion of a phase transition distinguishing between brittle
and ductile yielding, the question of its persistence in the thermodynamic
limit remains a topic of ongoing debate.

All these studies on yielding described above primarily focused on the initial
energy of the system, providing limited insights into the nature of the
initial glass former, particularly its fragility, which is a crucial parameter
for glass-forming liquids as it connects to various dynamical and structural
properties such as dynamical heterogeneity, configurational entropy, violation
of the Stokes-Einstein relation, glass forming ability and so on Sastry
(2001); Scopigno  _et al._ (2003); Ruocco  _et al._ (2004); Tanaka (2005);
Adhikari  _et al._ (2021); Alba-Simionesco and Tarjus (2022). In this article,
we investigate whether yielding behavior is similar amongst different fragile
glass formers. Through extensive computer simulations, we illustrate that the
nature of the yielding transition can vary depending on the fragility of the
initial glass. Additionally, we introduce an elastoplastic model that
successfully reproduces the simulation results. The analysis of this model
allows us to rationalize the observed changes in yielding behavior,
attributing them to changes in energy barriers with the annealing history.

Figure 1: Oscillatory Shear Yielding Diagram: (A) Relaxation time,
$\tau_{\alpha}$ is plotted as a function of scaled temperature, $T_{g}/T$ for
all the four studied densities. $T_{g}$ is the calorimetric glass transition
temperature (see text for definition). The marked variation in the shape of
the relaxation curve with changing density highlights the large change in
fragility in these systems with increasing density. Inset shows the kinetic
fragility as a function of density. (B) Steady-state energy $E_{SS}$ vs cyclic
shear amplitude $\gamma_{max}$ is plotted for differently annealed samples as
indicated by their parent temperatures ($T_{p}$) for $\rho=0.681$. Notice that
the main characteristic of the absence of any mechanical annealing below a
critical energy scale along with the nearly no shift in the yield strain
($\gamma_{y}$) with increasing annealing in this strong glass former. Similar
phase diagrams for $\rho=0.750$ (C), $\rho=0.8556$ (D) and $\rho=0.943$ (E)
are shown to highlight how yielding transition shifts to higher strain
amplitude as the fragility of the glass formers are systematically changed.
For most fragile glass former (panel E), the shift in the yield strain at low
temperature is very large (nearly $30\%$. (F) Shows the shifting of
$\gamma_{y}$ with increasing annealing for all four densities. The x-axis has
been scaled by their respective MCT temperature, $T_{MCT}$ for better
comparison. Maximum steady state stress, $\sigma^{max}_{xz}$, is plotted
against $\gamma_{max}$ for $\rho=0.750$ (G), $\rho=0.8556$ (H) and
$\rho=0.943$ (I), to highlight the stark difference in the yielding transition
between strong and fragile glass formers. Strong glass formers continued to
show ductile-like yielding with increasing annealing, whereas fragile glass
former showed sharp, brittle yielding with increasing annealing as clear from
the sharp stress drops across the yielding strain.

Simulation details: We investigate a binary mixture ($50:50$) of particles
that interact via harmonic potential given by Durian (1995); Adhikari  _et
al._ (2021):

$\displaystyle V_{\alpha\beta}(r)$ $\displaystyle=$
$\displaystyle\frac{\epsilon_{\alpha\beta}}{2}\left(1-\frac{r}{\sigma_{\alpha\beta}}\right)^{2},\hskip
44.9554ptr_{\alpha\beta}\leq\sigma_{\alpha\beta}$ (1) $\displaystyle=$
$\displaystyle 0,\hskip 112.10393ptr_{\alpha\beta}>\sigma_{\alpha\beta}$

where $\alpha,\;\beta$ $\in$ (A, B) indicates the type of particle. The two
types of particle differ in their size, with $\sigma_{BB}=1.4\sigma_{AA}$ (and
the diameters are additive), with the interaction strengths being the same for
all pairs ($\epsilon_{AA}=\epsilon_{AB}=\epsilon_{BB}$). We have performed
simulation at different packing fractions, $\phi$, which larger than the
$\phi_{J}$ as well as $\phi_{0}$ Adhikari  _et al._ (2023). The relation
between number density $\rho$ and packing fraction $\phi$ for binary mixture
is,

$\displaystyle\phi$ $\displaystyle=$ $\displaystyle\rho
2^{-d}\frac{\pi^{d/2}}{\Gamma(1+\frac{d}{2})}(c_{A}\sigma^{d}_{AA}+c_{B}\sigma^{d}_{BB})$
(2)

where $\rho=N/V$, N is the number of particles, V is the simulation box
volume, and $c_{A}=c_{B}=1/2$. We have done simulations for $N=5000$
particles. We have taken four packing fractions
$\phi=\left[0.667,0.735,0.8384,0.925\right]$ and the corresponding number
densities (from Eqs 2) $\rho=\left[0.681,0.750,0.8556,0.943\right]$ to study
the effect of fragility on yielding transition. For each density, we
equilibrated the samples for a wide range of temperatures, including
temperatures well below the Mode Coupling Temperature, $T_{MCT}$ to study the
effect of annealing on yielding ($T_{MCT}$ are given in the SI). Relaxation
time $\tau_{\alpha}$ ranges from $\sim 100$ to $10^{7}$ for all the cases.
$\tau_{\alpha}$ is defined as the time when the two-point correlation function
becomes $q(t=\tau_{\alpha})=1/e$ (the details are shown in the SI). The
temperature ranges for $\rho=0.681$ is $T\in\left(0.0018,0.0005\right)$, for
$\rho=0.750$ is $T\in\left(0.0030,0.00125\right)$, for $\rho=0.8556$ is
$T\in\left(0.0040,0.0022\right)$ and for $\rho=0.943$ is
$T\in\left(0.0045,0.0030\right)$. We couldn’t achieve $\tau_{\alpha}\sim
10^{7}$ at density $\rho=0.943$ due to the crystallisation effect, but we have
reached up to $\tau_{\alpha}\sim 10^{6}$. We have used the conjugate gradient
(CG) method on these equilibrated configurations to get the energy-minimised
or inherent structure configurations (IS configurations). We then performed
cyclic shear on these IS configurations following the AQS protocol. We chose
the shear direction as the xz plane. The strain $\gamma$ varies as
($0\rightarrow{\gamma_{max}\rightarrow{-\gamma_{max}\rightarrow 0}}$)
indicating a complete cycle, where elementary strain increment,
$d\gamma=2\times 10^{-4}$. For each increment of $d\gamma$ we performed the
following AQS shear protocol - (i) affine transformation of each particle
coordinates (${r_{x}}^{\prime}\rightarrow r_{x}+r_{z}\times d\gamma$,
${r_{y}}^{\prime}\rightarrow r_{y}$, ${r_{z}}^{\prime}\rightarrow r_{z}$) and
then (ii) energy minimisation using CG method. We took $12$ independent
samples for each temperature of each density. See SI for further details.

Simulation Results: In Fig.1A, we show the Angell plot to highlight the large
variation of fragility with densities by plotting the relaxation time,
$\tau_{\alpha}$ against scaled temperature ($T_{g}/T$). Subsequently, we fit
this relaxation time using the Vogel Fulcher Tamannam (VFT) formula:

$\tau_{\alpha}=\tau_{0}\exp\left[{\frac{1}{K_{VFT}(T/T_{VFT}-1)}}\right],$ (3)

where $T_{VFT}$ denotes the temperature at which the relaxation time diverges
and $K_{VFT}$ represents the kinetic fragility. We obtain the Angell plot by
defining the calorimetric glass transition temperature $T_{g}$ such that
$\tau_{\alpha}(T_{g})=10^{7}$. In the inset, we show $K_{VFT}$ as a function
of density. Our observations corroborate with the previous studies that
fragility in this soft sphere glass model increases strongly with increasing
density Berthier and Witten (2009); Adhikari  _et al._ (2021); Tah  _et al._
(2022). Specifically, the system demonstrates behavior reminiscent of a strong
liquid at a density of $\rho=0.681$ with $K_{VFT}\simeq 0.034$. However, as
the density increases, the system becomes more fragile. At the highest density
($\rho=0.943$), $K_{VFT}$ $\simeq$ $0.549$. Thus, The change in fragility
occurred by a factor of around $16$, corresponding to a density change of
$1.38$ times. We then perform cyclic shear in these four glasses at various
degrees of annealing as represented by the parent temperatures ($T_{p}$).
Parent temperature refers to the temperature at which the liquid is
equilibrated before quenching to zero temperature to prepare the amorphous
solid samples. For each chosen cyclic shear amplitude ($\gamma_{max}$), we
perform a couple of hundred to thousand cycles of shear deformation until the
energy reaches a steady state value $E_{SS}$. Using these extensive cyclic
shear simulations, we obtain the yielding diagrams of the systems by plotting
$E_{SS}$ as a function of $\gamma_{max}$ for all the studied parent
temperatures. (Variations of energy with cycles for all the studied systems
are shown in the SI). Panels (B), (C), (D) and (E) shows such yielding
diagrams for densities $\rho=0.681$, $0.750$, $0.8556$ and $0.943$
respectively for glass formers exhibiting different fragility. In poorly
annealed systems, all glass formers behave similarly: the steady-state energy
decreases as $\gamma_{max}$ increases until reaching the critical yielding
point ($\gamma_{Y}^{c}$), after which $E_{SS}$ rises again. For all poorly
annealed systems ($T>T_{MCT}$), the systems yield at the same point. We call
$\gamma_{Y}^{c}$ critical yield strain because this strain demarcates the
difference between the poorly annealed and well-annealed samples. However,
stark differences emerge among different glass formers in the well-annealed
regime. Although $E_{SS}$ remains unchanged with increasing $\gamma_{max}$,
the yielding point shifts to a larger value with increasing annealing for
fragile liquids, whereas it remains nearly the same for strong liquids. The
yielding point for strong liquids (Fig. 1(B)) occurs more or less at the same
point irrespective of the degree of annealing, whereas for the most fragile
liquid (Fig. 1(E)), the yielding point shifts to a larger value with
increasing annealing below the respective MCT parent temperature ($T_{MCT}$).
Just to highlight the changes in the yield strain qualitatively, we estimated
the percentage changes in the yield point with respect to the critical yield
point and for $\rho=0.681$, the percentage change in yield point is around
$15\%$ whereas, for the fragile glass formers, the changes are as large as
$35\%$. These results can provide important insights into observations from
previous studies, which we discuss below.

Figure 2: Mesoscale Elastoplastic Model:  (A) Schematic of Mean barrier as a
function inherent state energy $E_{0}$ following Eq.6 and Eq. 7. (B) Steady-
state energy vs $\gamma_{max}$ for a model strong glass former with energy
barrier depicted by the blue curve in panel (A). The energy barrier saturates
with increasing annealing (equivalent to more negative inherent structure
energy, $E_{0}$). Note that the poorly annealed states show further annealing
with increasing $\gamma_{max}$, but for better-annealed states, there is no
annealing and yield strain does not increase. (C) A similar yielding diagram
for a model system with intermediate fragility is depicted in panel (A) by a
red curve. In this case, the poorly annealed part of the diagram shows similar
results to the strong glass former but notes the better-annealed part. The
yield strain increases with increasing annealing. (D) Shows the results for
the most fragile case. The striking difference is the better-annealed part of
the yielding diagram. The yield strain increases significantly with increasing
annealing in complete agreement with simulation results. (E) Shows the number
of cycles needed to reach steady state ($\tau$) vs $\gamma_{max}$ from
simulation for three densities with increasing fragility. $\tau$ is the
smallest for a given $\gamma_{max}$ for the fragile system with $\rho=0.943$,
indicating the ease of reaching a steady state for fragile glass formers. (F)
Similar timescale data from the elastoplastic model. Excellent qualitative
match with the simulation results is indeed very encouraging. (G)
$\sigma_{max}$ vs $\gamma_{max}$ plot for strong glass-former. (H) and (I)
show a stress-strain curve for intermediate and fragile scenarios. Again, the
qualitative match with the simulation results shown in Fig.1(G)-(H) is very
good. See the text for more discussions.

In ref. Bhaumik  _et al._ (2021), two model liquids with different fragilities
were studied to understand the effect of annealing on yielding. While no
direct comparison of yielding transitions was conducted, their data indicates
that for the strong liquid silica, the yielding point does not change much
with increasing annealing, whereas it shows significant changes for the highly
fragile liquid, KA BMLJ. Recent investigations Sharma and Karmakar (2023);
Goswami  _et al._ (2023) on the shear deformation of active glasses reveal
that the yielding point shows minimal change with increasing annealing. Our
results indicate that these apparent changes in yielding behavior are closely
related to the fragility of the system.

In Fig.1(F), we illustrate $\gamma_{Y}/\gamma_{Y}^{c}$ as a function of
$T_{MCT}/T$, where $\gamma_{Y}$ denotes the yielding point and
$\gamma_{Y}^{c}$ denotes the yielding point of poorly annealed glasses. The
yielding point does not change for different glasses until $T_{MCT}$; however,
below $T_{MCT}$ it increases rapidly with increasing fragility, whereas for
the strong glasses, it remains almost constant. The inset of Fig. 1(F) shows
that for strong glasses, yielding occurs for smaller deformations. These
observations lead to the interesting phenomenon that strong glasses yield
faster.

To further elucidate the yielding transition under cyclic shear, in
Fig.1(G)-(I), we show the maximum steady state stress $\sigma^{max}_{xz}$ as a
function of $\gamma_{max}$ for different parent temperatures. In the case of
strong glass (Fig.1(G)), we observe that for various parent temperatures,
$\sigma^{max}_{xz}$ increases as $\gamma_{max}$ increases until it reaches the
yield point. Interestingly, the yield points appear to be similar across
different parent temperatures. Subsequently, stress drops to a lower value.
This stress-strain behavior not only reaffirms that the yielding point does
not change with the degree of annealing but also suggests that strong glasses
remain ductile even in the most annealed samples. However, the stress-strain
behavior changes significantly for fragile glass (Fig. 1(I)). With increasing
annealing, the yielding point shifts to a larger value and becomes brittle for
well-annealed glasses with sharp stress drops at the yielding strains. Thus,
this result, combined with the yielding diagram described above, reveals that
the nature of yielding is highly dependent on the fragility of the glass
formers.

Elastoplastic Mesomodel Results: We now consider whether the observed
phenomena in simulation can be reproduced and the underlying mechanism could
be understood using a simple mean-field mesoscopic model. While the
understanding of yielding behavior under uniform shear deformations using a
mesoscopic model has been extensively studied Nicolas  _et al._ (2018);
Popović  _et al._ (2018); Barlow  _et al._ (2020); Talamali  _et al._ (2012),
there is a growing interest in comprehending yielding behavior under cyclic
shear deformation recently Sastry (2021); Parley  _et al._ (2021); Khirallah
_et al._ (2021); Rossi  _et al._ (2022); Kumar  _et al._ (2022); Liu  _et al._
(2022); Cochran  _et al._ (2022). The main ingredient of many of these models
is the assumption of a local energy landscape associated with a volume of
material, often referred to as a meso block. However, it is not immediately
clear how large a volume one needs to consider for the validity of the
assumption. One assumes that each of these blocks of materials can be
considered independent from each other, and a collection of such blocks can
constitute a macroscopic body of materials. The absence of interactions
between blocks can be thought of as a mean-field approximation. Within this
approximation, one further assumes that each of these meso-blocks evolves on
the energy landscape when subjected to various deformations, such as
oscillatory shear deformation. When the block reaches its local yield
threshold, it topples to another energy minimum amongst all the accessible
minima it has, and the process continues as long as the body is subjected to
the deformation. In Ref.Sastry (2021), it was assumed that such block is
associated with an absolute energy minimum $E_{0}$ and a strain $\gamma_{0}$
(where energy is minimum as a function of strain). The yield threshold is
modelled via a stability range of strain ($\gamma_{\pm}$), beyond which the
system topples to a new energy minimum. Under strain, a quadratic variation of
energy is considered, assuming Hooke’s law of linear elasticity. It was
further assumed that $E_{0}$ follows a Gaussian distribution,

$P\left(E_{0}\right)=\sqrt{\frac{2}{\pi{\sigma}^{2}}}\exp{\left(-\frac{{E_{0}}^{2}}{2{\sigma}^{2}}\right)},$
(4)

where $-1<E_{0}<0$, $\sigma=0.1$ and energy evolution with strain $\gamma$ is,

$E(\gamma,E_{0},\gamma_{0})=E_{0}+\frac{\mu}{2}(\gamma-\gamma_{0})^{2},$ (5)

where $\mu=1.1$ and the stability limit is,
$\gamma\pm=\gamma_{0}\pm\sqrt{|E_{0}|}$. The yielding diagram of this model
closely resembles what we observed for fragile glass formers. However, neither
this model nor others in the literature Parley  _et al._ (2021); Khirallah
_et al._ (2021); Rossi  _et al._ (2022); Kumar  _et al._ (2022); Liu  _et al._
(2022); Cochran  _et al._ (2022) consider the impact of the initial glass
former’s fragility on the yielding diagram. However, our simulation results
suggest a significant change in the yielding diagram when the fragility of the
initial glass former varies. Therefore, we propose a new model similar to the
concept discussed in Ref. Sastry (2021) but with a crucial difference of
energy barrier playing a crucial role in plasticity.

Previous studies Tah and Karmakar (2022); Tah  _et al._ (2022) have shown that
the energy barrier ($\Delta E$) of the fragile glass-formers increases
strongly with decreasing temperature or increasing annealing, but for strong
glass-formers, the energy barrier increases very slowly. We have introduced
this crucial aspect of variation of energy barrier with parent temperature or
annealing in our version of elastoplastic model. The energy barrier
distribution is assumed to be Gaussian, with the mean energy barrier,
$\langle\Delta E\rangle$, varying with $E_{0}$ or parent temperature, $T_{p}$.
We have chosen two trial functions for $(\langle\Delta E\rangle)$ variation
with annealing ($E_{0}$). For fragile glass-formers, we took

$\langle\Delta E\rangle=a+b|E_{0}|$ (6)

and for strong glass-formers

$\langle\Delta E\rangle=a+b\left(\frac{E_{0}^{2}}{1+E_{0}^{2}}\right)$ (7)

with $a=0.10$, $b=0.80$. A schematic is shown in Fig. 2(A). We propose that
the stability limit should depend on the energy barrier ($\Delta E$) as

$\gamma\pm=\gamma_{0}\pm{[\Delta E]}^{2/3}.$ (8)

The exponent $2/3$ is used instead of $1/2$ as it was already shown that the
energy barrier vanishes as a power-law with exponent $2/3$ as the plastic
strain is approached Karmakar  _et al._ (2010a). We also considered uniform
distribution of $\gamma_{0}\in(-1,1)$ as in Sastry (2021). The cyclic shear in
this model goes as follows.

  1. (i)

start with an initial energy minimum $E_{0}$ and $\gamma_{0}=0$.

  2. (ii)

For this $E_{0}$, get $\langle\Delta E\rangle$ from the equation 6 or 7 and
the corresponding $\Delta E$ is chosen from Gaussian distribution whose width
$\sigma_{\Delta E}$ decreases linearly from 5% to 0.001% of $E_{0}$ with
annealing.

  3. (iii)

Define the stability limit using Eq.8.

  4. (iv)

Energy is then varied with strain as
$E(\gamma,E_{0},\gamma_{0})=E_{0}+\frac{\mu}{2}(\gamma-\gamma_{0})^{2}$ until
the stability limit is reached. $\mu$ is increased linearly from $1$ to $1.5$
with annealing.

  5. (v)

Whenever the system crosses its stability limit $\gamma\pm$, it jumps to any
lower energy mesostate at the transition strain, and a new set of $E_{0}$ and
$\gamma_{0}$ are chosen from the respective distributions, and we repeat the
process from (ii).

The strain $\gamma$ is varied cyclically with amplitude $\gamma_{max}$, and
the number of cycles is around $10000$. If the zero strain energy of the
system doesn’t change with successive cycles, the procedure is terminated. The
average zero strain energies of the last $500$ cycles are calculated to obtain
$E_{SS}$. We took 100 independent samples for better averaging. We studied the
model within the same range of $E_{0}\in(-0.05,-0.70)$ for all the samples.
$E_{SS}$ vs $\gamma_{max}$ is plotted for all the cases for this elastoplastic
model in Fig. 2(B) - (D). As we can see, the yielding point for the strong
model barely shifts below the critical energy, while for the fragile model,
the shift in yielding point with annealing is very large, in complete
agreement with simulation results.

From our modified elastoplastic model, we get additional information about
timescales (the number of cycles needed to reach a steady state) for both the
strong and fragile glass formers. In Fig. 2(E), we show the timescale obtained
from our MD simulations for strong, intermediate and fragile glass-formers.
One can clearly see that the number of cycles needed to reach a steady state
for a strong glass-former is way larger than fragile glass-formers for a given
$\gamma_{max}$. We have fitted the zero strain energy (stroboscopic energy) as
a function of cycles using a stretched exponential function to find the
steady-state energy and the timescale for the most poorly annealed samples for
three densities, $\rho=0.750,0.8556,0.943$. The timescales are found to show a
power-law-like divergence at the respective critical yield strain
$\gamma_{Y}^{c}$, which sifts to a larger strain as the system becomes more
fragile. These simulation outcomes can be qualitatively described by our model
also. A detailed characterization of this divergence is shown in the SI.

Next, in Fig. 2(F), we show the results obtained using our elastoplastic
model, and remarkable agreement with the simulation results suggests the
crucial role played by the energy barrier in modelling these systems even at
the mean-field level. In this model, we considered the number of cycles to
reach the steady state as the characteristic relaxation timescale, and we
found that the power-law divergence exponent is higher for strong glass than
the fragile one, again in agreement with the simulation results. In Fig.
2(G)-(I), we show $\sigma^{max}$ vs $\gamma_{max}$ as obtained from our
elastoplastic model to draw a parallel with the simulations results in Fig.
1(G)-(I). One also sees that for strong liquids, the yield strain does not
change much as well and the stress jump is found to be small compared to the
fragile ones. In fragile glass-formers, the yield strain changes significantly
with annealing, and the corresponding stress drops as the yielding increases,
as seen in the simulations. The remarkable agreement between the mean-field
elastoplastic model and the simulation results is really encouraging,
suggesting that much of the oscillatory shear yielding in a wide variety of
amorphous solids might be possible to understand within the mean-field
framework. In the future, we plan to extend this model to include spatial
dimensions to see whether some of the missing physics can be incorporated into
the elastoplastic model.

Conclusion:  In this study, we show that the fragility of the initial glass
former significantly influences the nature of the yielding transition under
cyclic shear. Fragility of the glass former is an indicator of how quickly
viscosity or relaxation time increases with decreasing temperature in the
supercooled liquid temperature regime. Our findings are particularly
noteworthy because they reveal how the kinetic properties of liquids can
strongly influence the mechanical properties of amorphous solids, providing
new insights into the behavior of these materials. Our results reveal that
while the yielding response of strong and fragile liquids in their poorly
annealed states is similar, a striking difference emerges when they are better
annealed. We found that fragile glass formers show a large increase in
yielding strain with increasing annealing, while strong glass formers show
almost no change in their yielding strain with better annealing. This
difference is also apparent in their stress-strain relationship. Strong glass-
formers show nearly ductile yielding with no significant change in the
characteristic with increasing annealing, whereas fragile glass-formers show
increasingly brittle yielding with increasing annealing, characterized by a
very large stress jump at the yield strain.

Additionally, we observe that strong glass formers take significantly more
shear cycles to reach an absorbing state when the strain amplitude is below
their yield strain, while fragile glass formers reach their absorbing state
much faster at the same strain amplitude. These differences are quite
intriguing and led us to propose a modified mean-field elastoplastic model
that considers the crucial role of energy barriers in amorphous plasticity,
which was previously missing in other works. By introducing a temperature-
dependent growth of energy barrier, particularly a weakly growing energy
barrier for strong glass-formers and a strongly growing energy barrier for
fragile glass-formers with temperature, we could explain the simulation’s
observations with remarkable accuracy. We also found that the yielding diagram
under oscillatory shear can be a useful tool for estimating the growth of
energy barriers in various glass-formers and may help us better understand
their liquid properties. Finally, our results provide insights into how the
variation in energy barrier with annealing can affect the mechanical response
of amorphous solids under oscillatory shear. We believe our findings will
encourage future research to develop a unified description of the mechanical
yielding of a wide variety of amorphous solids using mean-field theories while
considering energy barriers and their essential role in plasticity.

Acknowledgements: We want to thank Srikanth Sastry, Pinaki Chaudhuri, Viswas
Venkatesh and Shiladitya Sengupta for many useful discussions. We acknowledge
funding by intramural funds at TIFR Hyderabad from the Department of Atomic
Energy (DAE) under Project Identification No. RTI 4007. SK acknowledges Swarna
Jayanti Fellowship grants DST/SJF/PSA01/2018-19 and SB/SFJ/2019-20/05 from the
Science and Engineering Research Board (SERB) and Department of Science and
Technology (DST) and the National Super Computing Mission (NSM) grant
$\mathrm{DST/NSM/R\&D\\_HPC\\_Applications/2021/29}$ for generous funding.
Most of the computations are done using the HPC clusters procured using Swarna
Jayanti Fellowship grants DST/SJF/PSA01/2018-19, SB/SFJ/2019-20/05 and Core
Research Grant CRG/2019/005373. MA acknowledges support from NSM grant
$\mathrm{DST/NSM/R\&D\\_HPC\\_Applications/2021/29}$ for financial support.

## References

  * Fielding  _et al._ (2000) S. M. Fielding, P. Sollich, and M. E. Cates, Journal of Rheology 44, 323 (2000).
  * Falk and Langer (2011) M. L. Falk and J. S. Langer, Annu. Rev. Condens. Matter Phys. 2, 353 (2011).
  * Schuh  _et al._ (2007) C. A. Schuh, T. C. Hufnagel, and U. Ramamurty, Acta Materialia 55, 4067 (2007).
  * Bonn  _et al._ (2017) D. Bonn, M. M. Denn, L. Berthier, T. Divoux, and S. Manneville, Reviews of Modern Physics 89, 035005 (2017).
  * Shi and Falk (2005) Y. Shi and M. L. Falk, Physical review letters 95, 095502 (2005).
  * Shi  _et al._ (2007) Y. Shi, M. B. Katz, H. Li, and M. L. Falk, Physical review letters 98, 185505 (2007).
  * Karmakar  _et al._ (2010a) S. Karmakar, E. Lerner, and I. Procaccia, Physical Review E 82, 055103 (2010a).
  * Karmakar  _et al._ (2010b) S. Karmakar, A. Lemaitre, E. Lerner, and I. Procaccia, Physical review letters 104, 215502 (2010b).
  * Keim and Arratia (2013) N. C. Keim and P. E. Arratia, Soft Matter 9, 6222 (2013).
  * Denisov  _et al._ (2015) D. V. Denisov, M. T. Dang, B. Struth, A. Zaccone, G. H. Wegdam, and P. Schall, Scientific Reports 5 (2015), 10.1038/srep14359.
  * Lin  _et al._ (2014) J. Lin, E. Lerner, A. Rosso, and M. Wyart, Proceedings of the National Academy of Sciences 111, 14382 (2014).
  * Bhowmik  _et al._ (2019) B. P. Bhowmik, P. Chaudhuri, and S. Karmakar, Physical review letters 123, 185501 (2019).
  * Barbot  _et al._ (2020) A. Barbot, M. Lerbinger, A. Lemaitre, D. Vandembroucq, and S. Patinet, Physical Review E 101, 033001 (2020).
  * Kawasaki and Berthier (2016) T. Kawasaki and L. Berthier, Physical Review E 94, 022615 (2016).
  * Procaccia  _et al._ (2017) I. Procaccia, C. Rainone, and M. Singh, Physical Review E 96, 032907 (2017).
  * Jaiswal  _et al._ (2016) P. K. Jaiswal, I. Procaccia, C. Rainone, and M. Singh, Physical review letters 116, 085501 (2016).
  * Shrivastav  _et al._ (2016) G. P. Shrivastav, P. Chaudhuri, and J. Horbach, Physical Review E 94, 042605 (2016).
  * Fiocco  _et al._ (2013) D. Fiocco, G. Foffi, and S. Sastry, Phys. Rev. E 88, 020301 (2013).
  * Regev  _et al._ (2013) I. Regev, T. Lookman, and C. Reichhardt, Phys. Rev. E 88, 062401 (2013).
  * Nagamanasa  _et al._ (2014) K. H. Nagamanasa, S. Gokhale, A. Sood, and R. Ganapathy, Physical Review E 89, 062308 (2014).
  * Leishangthem  _et al._ (2017) P. Leishangthem, A. D. Parmar, and S. Sastry, Nature Communications 8, 14653 (2017).
  * Parmar  _et al._ (2019) A. D. Parmar, S. Kumar, and S. Sastry, Physical Review X 9, 021018 (2019).
  * Yeh  _et al._ (2020) W.-T. Yeh, M. Ozawa, K. Miyazaki, T. Kawasaki, and L. Berthier, Physical review letters 124, 225502 (2020).
  * Bhaumik  _et al._ (2021) H. Bhaumik, G. Foffi, and S. Sastry, Proceedings of the National Academy of Sciences 118 (2021).
  * Ozawa  _et al._ (2018) M. Ozawa, L. Berthier, G. Biroli, A. Rosso, and G. Tarjus, Proceedings of the National Academy of Sciences 115, 6656 (2018).
  * Divoux  _et al._ (2023) T. Divoux, E. Agoritsas, S. Aime, C. Barentin, J.-L. Barrat, R. Benzi, L. Berthier, D. Bi, G. Biroli, D. Bonn, _et al._ , arXiv preprint arXiv:2312.14278 (2023).
  * Barlow  _et al._ (2020) H. J. Barlow, J. O. Cochran, and S. M. Fielding, Physical Review Letters 125, 168003 (2020).
  * Ozawa  _et al._ (2023) M. Ozawa, Y. Iwashita, W. Kob, and F. Zamponi, Nature Communications 14, 113 (2023).
  * Keim and Medina (2022) N. C. Keim and D. Medina, Science Advances 8, eabo1614 (2022).
  * Pollard and Fielding (2022) J. Pollard and S. M. Fielding, Physical Review Research 4, 043037 (2022).
  * Mutneja  _et al._ (2023) A. Mutneja, B. P. Bhowmik, and S. Karmakar, arXiv preprint arXiv:2307.01002 (2023).
  * Krishnan  _et al._ (2023) V. V. Krishnan, K. Ramola, and S. Karmakar, Physical Review Applied 19, 024004 (2023).
  * Adhikari  _et al._ (2022) M. Adhikari, M. Mungan, and S. Sastry, arXiv preprint arXiv:2201.06535 (2022).
  * Singh  _et al._ (2020) M. Singh, M. Ozawa, and L. Berthier, Physical Review Materials 4, 025603 (2020).
  * Lamp  _et al._ (2022) K. Lamp, N. Küchler, and J. Horbach, The Journal of Chemical Physics 157 (2022).
  * Ozawa  _et al._ (2020) M. Ozawa, L. Berthier, G. Biroli, and G. Tarjus, Physical Review Research 2, 023203 (2020).
  * Bhaumik  _et al._ (2022) H. Bhaumik, G. Foffi, and S. Sastry, The Journal of Chemical Physics 156 (2022).
  * Sastry (2021) S. Sastry, Physical Review Letters 126, 255501 (2021).
  * Parley  _et al._ (2022) J. T. Parley, S. Sastry, and P. Sollich, Physical Review Letters 128, 198001 (2022).
  * Khirallah  _et al._ (2021) K. Khirallah, B. Tyukodi, D. Vandembroucq, and C. E. Maloney, Phys. Rev. Lett. 126, 218005 (2021).
  * Liu  _et al._ (2022) C. Liu, E. E. Ferrero, E. A. Jagla, K. Martens, A. Rosso, and L. Talon, The Journal of Chemical Physics 156 (2022).
  * Kumar  _et al._ (2022) D. Kumar, S. Patinet, C. E. Maloney, I. Regev, D. Vandembroucq, and M. Mungan, The Journal of Chemical Physics 157 (2022).
  * Rossi  _et al._ (2022) S. Rossi, G. Biroli, M. Ozawa, G. Tarjus, and F. Zamponi, Physical Review Letters 129, 228002 (2022).
  * Parley and Sollich (2023) J. T. Parley and P. Sollich, arXiv preprint arXiv:2310.07843 (2023).
  * Sastry (2001) S. Sastry, Nature 409, 164 (2001).
  * Scopigno  _et al._ (2003) T. Scopigno, G. Ruocco, F. Sette, and G. Monaco, Science 302, 849 (2003).
  * Ruocco  _et al._ (2004) G. Ruocco, F. Sciortino, F. Zamponi, C. De Michele, and T. Scopigno, The Journal of chemical physics 120, 10666 (2004).
  * Tanaka (2005) H. Tanaka, Journal of non-crystalline solids 351, 678 (2005).
  * Adhikari  _et al._ (2021) M. Adhikari, S. Karmakar, and S. Sastry, The Journal of Physical Chemistry B 125, 10232 (2021).
  * Alba-Simionesco and Tarjus (2022) C. Alba-Simionesco and G. Tarjus, Journal of Non-Crystalline Solids: X 14, 100100 (2022).
  * Durian (1995) D. J. Durian, Physical review letters 75, 4780 (1995).
  * Adhikari  _et al._ (2023) M. Adhikari, S. Karmakar, and S. Sastry, Physical Review Letters 131, 168202 (2023).
  * Berthier and Witten (2009) L. Berthier and T. A. Witten, Europhysics Letters 86, 10001 (2009).
  * Tah  _et al._ (2022) I. Tah, S. A. Ridout, and A. J. Liu, The Journal of Chemical Physics 157 (2022).
  * Sharma and Karmakar (2023) R. Sharma and S. Karmakar, arXiv preprint arXiv:2305.17545v1 (2023).
  * Goswami  _et al._ (2023) Y. Goswami, G. Shivashankar, and S. Sastry, arXiv preprint arXiv:2312.01459 (2023).
  * Nicolas  _et al._ (2018) A. Nicolas, E. E. Ferrero, K. Martens, and J.-L. Barrat, Reviews of Modern Physics 90, 045006 (2018).
  * Popović  _et al._ (2018) M. Popović, T. W. de Geus, and M. Wyart, Physical Review E 98, 040901 (2018).
  * Talamali  _et al._ (2012) M. Talamali, V. Petäjä, D. Vandembroucq, and S. Roux, Comptes Rendus Mécanique 340, 275 (2012).
  * Parley  _et al._ (2021) J. T. Parley, S. Sastry, and P. Sollich, (2021), arXiv:2112.11578 [cond-mat.soft] .
  * Cochran  _et al._ (2022) J. O. Cochran, G. L. Callaghan, and S. M. Fielding, arXiv preprint arXiv:2211.11677 (2022).
  * Tah and Karmakar (2022) I. Tah and S. Karmakar, Physical Review Materials 6, 035601 (2022).


$(e_{3}/e_{2})\mid n$, (RHf), and the assertion of Lemma A.1 are either in
(14) or of the form $(e_{1},e_{2},2e_{2})$ when $n=2$, or of the form
$(e_{1},e_{2},e_{2})$ with $n\leq 6$, or one of $(2,3,9)$ with $n=3,6$,
$(2,3,12)$ and $(2,4,8)$ with $n=4$, $(2,4,12)$ with $n=3$, or $(3,3,9)$ with
$n=3$.

The cases of the form $(e_{1},e_{2},e_{2})$ contradict the assumption that
$C_{2}$ is non-maximal, and hence do not appear in this case.

The cases $(e_{1},e_{2},2e_{2})$ where $e_{2}>3$ satisfy the above constraints
only with $n=2$, and the map $T_{0}$ is ramified only over $t_{2}$ and
$t_{3}$. In particular, one obtains the desired ramification type only if
$e_{2}$ is odd. In these cases, consider the product $1$ tuple $(R_{2})$
$x_{1},x_{1}^{-1},x_{3},x_{3}^{-1}$. For such a cover to be a pullback
$f_{T_{0}}$ for some $T_{0}$, we must have all ramification indices over
$t_{2}$ divisible by $e_{2}$, and hence in particular for such $T_{0}$, the
degree $n=\deg T_{0}$ is divisible by $e_{2}$. Applying Lemma A.1 to a
function $T_{0}$ such that $f_{T_{0}}$ corresponds to a tuple
$x_{1}x_{1}^{-1}x_{3}x_{3}^{-1}=1$, we get:

(16)
$\frac{1}{2e_{2}}\geq\biggl{(}\frac{1}{2}-\frac{1}{n}\biggr{)}\biggl{(}1-\frac{1}{e_{1}}-\frac{1}{2e_{2}}\biggr{)}.$

The only tuple $(e_{1},e_{2},2e_{2})$ satisfying (16), with $e_{2}\mid n$, and
$e_{2}$ odd, and (RHf) is $(3,3,6)$, treated at the end of this case.

A direct inspection shows that for $(2,4,12)$ there is no $T_{0}$ of degree
$3$ for which $f_{T_{0}}$ has four branch points with ramification indices
$2,2,4,4$. In the cases $(2,4,8)$ and $(3,3,9)$, the group is a non-cyclic
$p$-group, and hence by Remark A.2 has at least $3$ maximal conjugacy classes
of cyclic groups.

In the cases $(2,3,9)$, and $(2,3,12)$, we claim there is no product $1$ tuple
with only two maximal conjugacy classes $C_{1}$ and $C_{3}$. Indeed, $G$ is
solvable by Remark A.2. Let $N$ be a minimal normal subgroup of $G$. Since $G$
is solvable $N$ is isomorphic either to $(\mathbb{Z}/2\mathbb{Z})^{t}$ or to
$(\mathbb{Z}/3\mathbb{Z})^{t}$ for some $t\geq 1$. In the case $(2,3,9)$
(resp. $(2,3,12)$): if $N\cong(\mathbb{Z}/2\mathbb{Z})^{t}$ then the images of
$x_{2}$ and $x_{3}^{-1}$ in $G/N$ are equal contradicting that their orders
remain $3$ and $9$ (resp. $3$ and ($6$ or $12$)). If
$N\cong(\mathbb{Z}/3\mathbb{Z})^{t}$ then $N$ must contain $C_{2}$: Indeed, as
$C_{2}$ is non-maximal it coincides with a power of $C_{3}^{3}$ (resp.
$C_{3}^{4}$), and hence generates the unique conjugacy class of cyclic
subgroups of order $3$. Hence the images of $x_{1}$ and $x_{3}^{-1}$ coincide
in $G/N$, contradicting that their orders are $2$ and $3$ (resp. $2$ and $4$).

In the case $(3,3,6)$, we may split $x_{3}$ as a product $x_{3}^{4}\cdot
x_{3}^{3}$. Since $C_{3}^{2}$ is a coprime to $3$ power of $C_{2}$, we obtain
a product $1$ tuple in the Nielsen class $C_{1},C_{2},C_{2}^{u},C_{3}^{3}$,
where $u$ is coprime to $3$. It is straightforward to show that a cover with
this ramification type is a pullback $f_{T_{0}}$ for some $T_{0}$ only if
$T_{0}^{-1}(t_{1})$ and $T_{0}^{-1}(t_{2})$ each have a single preimage with
ramification index coprime to $3$, and $T_{0}^{-1}(t_{3})$ has a single
preimage with ramification index divisible by $3$ but not by $6$, and a single
one which is even but not divisible by $6$. The Riemann–Hurwitz formula shows
that this is possible only when $n=\deg T_{0}\leq 3$, and hence there is no
such possible ramification type for $T_{0}$.

Case 3: Finally, assume that $C_{1}$ is the only non-maximal conjugacy class.
We separate here again into two cases. If $C_{1}$ is not a power of $C_{3}$,
then as in Case 1, one has $e_{3}\mid n=\deg T_{0}$, and the same analysis as
in Case 1 applies. Henceforth we assume that $C_{1}$ is a power of $C_{3}$ and
that $e_{3}$ does not divide $n$. Here, we separate into two cases:

Case 3a: Assume $C_{1}$ is a power of $C_{2}$. In this case $e_{1}$ properly
divides $e_{2}$ and $e_{3}$. Moreover, if $f_{T_{0}}$ corresponds to the tuple
$(R_{1})$ $x_{1},x_{1}^{-1},x_{2},x_{2}^{-1}$, then $e_{3}/e_{1}$ divides $n$.
The only tuples satisfying these constraints, the assertion of Lemma A.1, and
(RHf), are $(e_{1},e_{2},e_{3})=(2,4,6)$ which appears in (14), $(e,2e,2e)$
with $n=2$ and $e\geq 3$, $(2,6,6)$ with $n=3$, and $(2,4,8)$. In the latter
case, by Remark A.2 there are more than two maximal conjugacy classes of
cyclic groups. A direct inspection shows that in the cases $(e,2e,2e)$ (resp.
$(2,6,6)$), there is no $T_{0}$ of degree $2$ (resp. $3$) for which
$f_{T_{0}}$ is of ramification $C_{1},C_{1}^{-1},C_{2},C_{2}^{-1}$.

Case 3b: Assume $C_{1}$ is not a power of $C_{2}$. In this case, we consider
the product $1$ tuple $(R_{2})$ corresponding to the ramification
$C_{1},C_{1}^{-1},C_{3},C_{3}^{-1}$ and hence we can assume $e_{2}\mid n=\deg
T_{0}$. The only tuples satisfying this constraint, (16) and (RHf) are
$(3,4,6)$, $(3,3,3\ell)$ for $\ell\geq 2$, $(2,5,6)$, $(2,4,2\ell)$ for
$\ell\geq 3$, and $(2,3,2\ell)$ for $\ell\geq 4$. In the case $(3,3,3\ell)$
Lemma A.1 shows that $f_{T_{0}}$ can have ramification
$C_{1},C_{1}^{-1},C_{2},C_{2}^{-1}$ (corresponding to the tuple $(R_{1})$)
only if $\ell=2$ or $3$. The case $(3,3,9)$ was already ruled out. The case
$(3,3,6)$ is ruled out as in the end of Case 2 (by simply switching the roles
of $C_{1}$ and $C_{2}$). In the cases $(2,4,2\ell)$, Lemma A.1 shows that
there is a pullback $f_{T_{0}}$ with ramification
$C_{1},C_{1}^{-1},C_{2},C_{2}^{-1}$ only if $\ell\leq 4$. Case $(2,4,6)$
appears in (14) and $(2,4,8)$ has more than $2$ maximal conjugacy classes by
Remark A.2.

In the cases $(2,3,2\ell)$, Lemma A.1 and a direct inspection show that
$f_{T_{0}}$ can have ramification $C_{1},C_{1}^{-1},C_{2},C_{2}^{-1}$ only if
$\ell\leq 4$. Case $(2,3,8)$ appears in (14). Finally, Lemma A.1 shows that in
the case $(3,4,6)$ (resp. $(2,5,6)$), there is a pullback $f_{T_{0}}$ with
ramification $C_{1},C_{1}^{-1},C_{2},C_{2}^{-1}$ only when $\deg T_{0}\leq 3$
(resp. $\deg T_{0}\leq 4$), however there is no such $T_{0}$ in these degrees.
∎

### The remaining cases

Finally, we show that if $E$ is in (14), then either the group $G$ has more
than three maximal conjugacy classes of cyclic groups or it does not contain a
product $1$ tuple $x_{i}\in C_{i}$, $i=1,2,3$ that generates $G$. From now on
let $N$ be a minimal normal subgroup of $G$. As before assume $e_{1}\leq
e_{2}\leq e_{3}$.

######  Lemma A.3.

Suppose that every maximal conjugacy class of $G$ is a power of one of
$C_{1},C_{2},C_{3}$ and $x_{i}\in C_{i}$, $i=1,2,3$ are elements with product
$1$.

  1. (1)

If $N\lhd G$ is a proper subgroup, then it contains at most one of the
conjugacy classes $C_{1},C_{2},C_{3}$.

  2. (2)

If $N$ contains $C_{i}$ for some $i\in\\{1,2,3\\}$, then, for the distinct
$j,\ell$ in $\\{1,2,3\\}\setminus\\{i\\}$, there exist integers
$d_{j},d_{\ell}$ such that $e_{j}/d_{j}=e_{\ell}/d_{\ell}$, and $d_{j}$
divides $e_{i}$ and $e_{j}$, and $d_{\ell}$ divides $e_{i}$ and $e_{\ell}$.

###### Proof.

Note that since $N$ is proper it cannot contain all maximal conjugacy classes
of $G$, and note that if $N$ contains an element from $C_{i}$ and $C_{j}$ for
distinct $i,j\in\\{1,2,3\\}$, then it contains $x_{i}$ and $x_{j}$ and hence
by the product $1$ relation all $x_{i}$’s. Thus $N$ may contain at most one of
the conjugacy classes $C_{1},C_{2},C_{3}$. Moreover if it contains $C_{i}$,
then modulo $N$, the product one relation gives $x_{j}N=x_{\ell}^{-1}N$ and
hence these are elements of the same order $e_{j}/d_{j}=e_{\ell}/d_{\ell}$ for
some integer $d_{j}$ (resp. $d_{\ell}$) dividing $e_{j}$ (resp. $e_{\ell}$)
and $e_{i}$, for the distinct $j,\ell$ in $\\{1,2,3\\}\setminus\\{i\\}$. ∎

Case (2,3,7): Since every conjugacy class is minimal, $N$ contains at least
one of $C_{1},C_{2},C_{3}$. If $N=1$ then $G$ is simple, contradicting the
fact that there is no simple group with these element orders [Dea89]. Lemma
A.3(1) shows that $N$ contains exactly one of the conjugacy classes in ${\bf
C}$. Since $2,3,7$ are distinct primes, there are no divisors $d_{j}$ and
$d_{\ell}$ as in Lemma A.3(2).

In the rest of the cases note that there are only two primes dividing the
order of $G$ and hence by Burnside’s theorem $G$ is solvable. Since $G$ is
solvable and $N$ is minimal, $N$ is elementary abelian.

Case (2,3,8): In this case $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$ or
$(\mathbb{Z}/3\mathbb{Z})^{\ell}$ for some $\ell\geq 1$. Moreover, by Lemma
A.3(2), the group $N$ is isomorphic to $(\mathbb{Z}/2\mathbb{Z})^{\ell}$, it
contains $C_{3}^{4}$ but not $C_{1}$. It follows that the elements $x_{i}N$,
$i=1,2,3$, are of order $2,3,4$, respectively, and hence $G/N\cong S_{4}$.
Since $N$ contains only one conjugacy class of $\mathbb{Z}/2\mathbb{Z}$
subgroups, this forces $\ell=1$ or $2$. A Magma check via Remark 4.2 shows
that every such extension $G$ contains an element of order $6$ or a maximal
conjugacy class of order $4$, contradicting that the powers of
$C_{1},C_{2},C_{3}$ are the only maximal conjugacy classes.

Case (2,4,5): In this case $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$ or
$(\mathbb{Z}/5\mathbb{Z})^{\ell}$ for some $\ell\geq 1$. Furthermore by Lemma
A.3(2), $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$, the group $N$ contains
$C_{2}^{2}$ but not $C_{1}$. It follows that the orders of $x_{i}N$, $i=1,2,3$
in $G/N$ are $2,2$, and $5$, respectively. That is, $G/N$ is either cyclic or
dihedral of order $10$. Moreover, since $N$ contains only one conjugacy class
of elements of order $2$, the group $G/N$ acts transitively on the
$\mathbb{Z}/2\mathbb{Z}$ subgroups in $N$, so that $N$ has either $1,2,5$ or
$10$ such groups. Since $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$ this forces
$\ell=1$. However any such extension of $G/N$ by $\mathbb{Z}/2\mathbb{Z}$
contains an element of order $10$, contradicting the maximality of $C_{3}$.

Case (3,3,5): In this case $N\cong(\mathbb{Z}/3\mathbb{Z})^{\ell}$ or
$(\mathbb{Z}/5\mathbb{Z})^{\ell}$ for some $\ell\geq 1$. Furthermore neither
of these is possible in view of Lemma A.3(2).

Case (3,3,4): In this case $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$ or
$(\mathbb{Z}/3\mathbb{Z})^{\ell}$ for some $\ell\geq 1$. Furthermore by Lemma
A.3(2), $N$ is $(\mathbb{Z}/2\mathbb{Z})^{\ell}$ and contains $C_{3}^{2}$.
Thus the images of $x_{1},x_{2},x_{3}$ in $G/N$ are of order $3,3,2$, and
hence $G/N\cong S_{3}$ or $\mathbb{Z}/6\mathbb{Z}$. Since $G/N$ acts
transitively on the $\mathbb{Z}/2\mathbb{Z}$ subgroups of $N$, we have
$\ell=1$ or $2$. A check using Magma, via Remark 4.2, shows that the only
extension of $S_{3}$ by $(\mathbb{Z}/2\mathbb{Z})^{\ell}$ for
$\ell\in\\{1,2\\}$ which does not contain an element of order divisible by $6$
is $S_{4}$. However, transpositions form a maximal conjugacy class in $S_{4}$
which is different from the $C_{i}$’s.

Case (2,4,6): $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$ or
$(\mathbb{Z}/3\mathbb{Z})^{\ell}$ for some $\ell\geq 1$. In the latter case,
$N$ contains $C_{3}^{2}$ and hence the images of $x_{1},x_{2},x_{3}$ in $G/N$
are of order $2,4,2$, respectively, and hence $G/N$ is dihedral of order $8$.
Since $G/N$ acts transitively on the $\mathbb{Z}/3\mathbb{Z}$ subgroups of
$N$, it follows that $\ell=1$ or $2$. In this case a computation using Magma
shows that the orders of the maximal conjugacy classes are not contained in
the multiset $\\{2,4,6\\}$.

In the case $N\cong(\mathbb{Z}/2\mathbb{Z})^{\ell}$, the subgroup $N$ contains
$C_{2}^{2}$ or $C_{3}^{3}$ but does not contain $C_{1}$ by Lemma A.3(2). Thus
the images of $x_{1},x_{2},x_{3}$ in $G/N$ are of orders (A) $2,2,3$ or (B)
$2,2,6$ or (C) $2,4,3$, respectively. Moreover, in cases (B) and (C), $N$
contains a unique conjugacy class of involutions. In cases (B) and (C), $G/N$
is dihedral of order $12$ and $S_{4}$ respectively. As it acts transitively on
the $\mathbb{Z}/2\mathbb{Z}$ subgroup of $N$, this forces $\ell=1$ or $2$. A
check using Magma shows that in both cases, every such group extension $G$
contains a conjugacy class of order different from $2,4,$ and $6$.

In case (A), $G/N$ is $S_{3}$ and has one or two orbits on
$\mathbb{Z}/2\mathbb{Z}$ subgroups of $N$, forcing $\ell\leq 3$. A check using
Magma shows that for all such group extensions $G$, the orders of maximal
conjugacy classes of cyclic groups is not contained in the multiset
$\\{2,4,6\\}$.

##  Appendix B Generic extensions versus generic polynomials

Let $k$ be a field of characteristic zero, $T$ an indeterminate, and $G$ a
non-trivial finite group. Before generic extensions of $k(T)$, a notion of
(one parameter) generic polynomial over $k$ was pre-existing:

######  Definition B.1.

Let $P(T,Y)\in k[T,Y]$ be a monic separable polynomial (in $Y$) of group $G$
over $k(T)$. Say that $P(T,Y)$ is generic if, for every field extension $L/k$
and every Galois extension $E/L$ of group $G$, the field $E$ is the splitting
field over $L$ of the polynomial $P(t_{0},Y)$ for some $t_{0}\in L$.

The following proposition unifies both notions:

######  Proposition B.2.

Let $P(T,Y)\in k[T,Y]$ be a monic separable polynomial (in $Y$) of Galois
group $G$ and splitting field $F$ over $k(T)$. Then, $P(T,Y)$ is generic if
and only if $F/k(T)$ is generic.

###### Proof.

First, assume $P(T,Y)$ is generic. Let $L/k$ be a field extension and $E/L$ a
Galois extension of group $G$. As $P(T,Y)$ is generic, there is $t_{0}\in L$
such that $E$ is the splitting field over $L$ of $P(t_{0},Y)$. In particular,
$P(t_{0},Y)$ has Galois group $G$ over $L$. Since $(FL)_{t_{0}}$ contains the
splitting field over $L$ of $P(t_{0},Y)$ and has degree at most $|G|$, one
sees that $(FL)_{t_{0}}$ and this splitting field coincide. Hence,
$E/L=(FL)_{t_{0}}/L$.

Note that, by using Theorem 5.1 and Proposition 5.3, one can actually show
that, if $L/k$ is a field extension and $E/L$ is Galois of group contained in
$G$, then, there are infinitely many points $t_{0}\in L$ such that
$E/L=(FL)_{t_{0}}/L$. Indeed, assume first
$G\not\subset{\rm{PGL}}_{2}({\mathbb{C}})$. By Theorem 5.1(a), there are
infinitely many Galois extensions of $\overline{k}(U)$ of group $G$ which are
not specializations of $F\overline{k}(U)/\overline{k}(U)(T)$. But, for each
$t_{0}\in\overline{k}(U)$ such that $P(t_{0},Y)$ is separable, the splitting
field of $P(t_{0},Y)$ over $\overline{k}(U)$ and $(F\overline{k}(U))_{t_{0}}$
coincide. Hence, there are infinitely many Galois extensions
$E/\overline{k}(U)$ of group $G$ such that $E$ is the splitting field over
$\overline{k}(U)$ of $P(t_{0},Y)$ for no $t_{0}\in\overline{k}(U)$, which
cannot happen as $P(T,Y)$ is generic. Now, if
$G\subset{\rm{PGL}}_{2}({\mathbb{C}})$, then, by Theorem 5.1, one sees that
one of the conditions (1), (2), and (3) stated before Proposition 5.3 holds.
In particular, our stronger conclusion holds.

Now, assume $F/k(T)$ is generic. By either (the proof of) [JLY02, Proposition
8.1.4] or Theorem 3.1 and Lemma 3.2, the genus $g$ of $F$ is 0. Let $L/k$ be a
field extension and $E/L$ a Galois extension of group $G$. As $F/k(T)$ is
generic, there is $t_{0}\in\mathbb{P}^{1}(L)$ such that $E=(FL)_{t_{0}}$ and,
as ${\rm{Gal}}(E/L)=G$, $t_{0}$ is not a branch point of $F/k(T)$. Then, by
the twisting lemma and as $g=0$, there exist infinitely many such points
$t_{0}$. Hence, $E$ is the splitting field over $L$ of $P(t_{0},Y)$ for
infinitely many points $t_{0}\in L$.

As before, a stronger conclusion can be obtained by using Theorem 5.1 and
Proposition 5.3. Namely, let $L/k$ be a field extension and $E/L$ a Galois
extension of group contained in $G$. As $F/k(T)$ is generic, Theorem 5.1 and
Proposition 5.3 show that there are infinitely many points
$t_{0}\in\mathbb{P}^{1}(L)$ such that $E=(FL)_{t_{0}}$. Hence, $E$ is the
splitting field over $L$ of $P(t_{0},Y)$ for infinitely many points $t_{0}\in
L$. ∎

We then obtain this analog of Corollary 5.4 for one parameter generic
polynomials:

######  Corollary B.3.

Let $P(T,Y)\in k[T,Y]$ be a monic separable polynomial (in $Y$) of Galois
group $G$ and splitting field $F$ over $k(T)$. Denote the branch point set of
$F/k(T)$ by $\bf{t}$. Then, the following two conditions are equivalent:

(a) $P(T,Y)$ is generic,

(b) one of the following three conditions holds:

(i) $G$ is cyclic of even order $n$ such that $e^{2i\pi/n}\in k$, $r=2$, and
${\bf{t}}\subset\mathbb{P}^{1}(k)$,

(ii) $G$ is cyclic of odd order $n$ such that $e^{2i\pi/n}+e^{-2i\pi/n}\in k$
and $r=2$,

(iii) $G$ is dihedral of order $2n$ with $n\geq 3$ odd and
$e^{2i\pi/n}+e^{-2i\pi/n}\in k$, $r=3$, and
${\bf{t}}\subset\mathbb{P}^{1}(k)$.

In particular, $G$ has a one parameter generic polynomial over $k$ iff one of
the following three conditions holds:

$\bullet$ $G$ is cyclic of even order $n$ and $e^{2i\pi/n}\in k$,

$\bullet$ $G$ is cyclic of odd order $n$ and $e^{2i\pi/n}+e^{-2i\pi/n}\in k$,

$\bullet$ $G$ is dihedral of order $2n$ with $n\geq 3$ odd and
$e^{2i\pi/n}+e^{-2i\pi/n}\in k$.

######  Remark B.4.

(a) Definition B.1 is the definition of (one parameter) generic polynomial
that is used in the classical book [JLY02]. Several other choices could have
been possible. For example, a strong variant, used by Kemper (see [Kem01]),
requires Galois extensions $E/L$ of group contained in $G$ to be parametrized.
In [DeM83], DeMeyer even requires every Galois extension $E/L$ of group
contained in $G$ to be realized by a separable specialized polynomial.
However, the proof of Proposition B.2 shows that, for one parameter
polynomials over fields of characteristic zero, these three definitions are
actually equivalent. In particular, one retrieves [Kem01, Theorem 1] in this
situation252525This result asserts more generally that the first two
definitions are equivalent over infinite fields (for polynomials with an
arbitrary number of parameters)..

(b) In the case $k$ contains all roots of unity, the last part of Corollary
B.3262626That is, $G$ has a one parameter generic polynomial over $k$ iff $G$
is either cyclic or odd dihedral. was known from the essential theory of
Buhler-Reichstein; see [BR97] and [JLY02]. The general case, though feasible
with the same tools, does not seem to appear explicitly in the literature.

## References

  * [AC81] Enrico Arbarello and Maurizio Cornalba.  Footnotes to a paper of Beniamino Segre: “On the modules of polygonal curves and on a complement to the Riemann existence theorem” (Italian) [Math. Ann. 100 (1928), 537–551; Jbuch 54, 685]. The number of $g^{1}_{d}$’s on a general $d$-gonal curve, and the unirationality of the Hurwitz spaces of $4$-gonal and $5$-gonal curves.  Math. Ann., 256(3):341–362, 1981.
  * [BR97] J. Buhler and Z. Reichstein.  On the essential dimension of a finite group.  Compositio Math., 106(2):159–179, 1997.
  * [DD97a] Pierre Dèbes and Bruno Deschamps.  The regular inverse Galois problem over large fields.  In Geometric Galois actions, 2, volume 243 of London Math. Soc. Lecture Note Ser., (L. Schneps and P. Lochak ed), pages 119–138. Cambridge Univ. Press, Cambridge, 1997.
  * [DD97b] Pierre Dèbes and Jean-Claude Douai.  Algebraic covers: field of moduli versus field of definition.  Ann. Sci. École Norm. Sup. (4), 30(3):303–338, 1997.
  * [DD09] Tim Dokchitser and Vladimir Dokchitser.  Elliptic curves with all quadratic twists of positive rank.  Acta Arith., 137(2):193–197, 2009.
  * [Dea89] Marian Deaconescu.  Classification of finite groups with all elements of prime order.  Proc. Amer. Math. Soc., 106(3):625–629, 1989.
  * [Dèb99] Pierre Dèbes.  Galois covers with prescribed fibers: the Beckmann-Black problem.  Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4), 28(2):273–286, 1999.
  * [Dèb17] Pierre Dèbes.  On the Malle conjecture and the self-twisted cover.  Israel J. Math., 218(1):101–131, 2017.
  * [Dèb18] Pierre Dèbes.  Groups with no parametric Galois realizations.  Ann. Sci. Éc. Norm. Supér. (4), 51(1):143–179, 2018.
  * [DeM83] Frank R. DeMeyer.  Generic polynomials.  J. Algebra, 84(2):441–448, 1983.
  * [DL13] Pierre Dèbes and François Legrand.  Specialization results in Galois theory.  Trans. Amer. Math. Soc., 365(10):5259–5275, 2013.
  * [DLS66] H. Davenport, D. J. Lewis, and A. Schinzel.  Quadratic Diophantine equations with a parameter.  Acta Arith., 11:353–358, 1965/1966.
  * [FJ08] Michael D. Fried and Moshe Jarden.  Field arithmetic.  Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], 11. Springer-Verlag, Berlin, third edition, 2008.  Revised by Jarden. xxiv+792 pp.
  * [Fri77] Michael D. Fried.  Fields of definition of function fields and Hurwitz families-groups as Galois groups.  Comm. Algebra, 5(1):17–82, 1977.
  * [FV91] Michael D. Fried and Helmut Völklein.  The inverse Galois problem and rational points on moduli spaces.  Math. Ann., 290(4):771–800, 1991.
  * [Jar11] Moshe Jarden.  Algebraic patching.  Springer Monographs in Mathematics. Springer, Heidelberg, 2011.  xxiv+290 pp.
  * [JLY02] Christian U. Jensen, Arne Ledet, and Noriko Yui.  Generic polynomials. Constructive Aspects of the Inverse Galois Problem.  Cambridge University Press, 2002.
  * [Kem01] Gregor Kemper.  Generic polynomials are descent-generic.  Manuscripta Math., 105(1):139–141, 2001.
  * [KLN17] Joachim König, François Legrand, and Danny Neftin.  On the local behaviour of specializations of function field extensions.  International Mathematics Research Notices, 2017.  To appear; doi: 10.1093/imrn/rny016.
  * [KM01] Jürgen Klüners and Gunter Malle.  A database for field extensions of the rationals.  LMS J. Comput. Math., 4:182–196, 2001.
  * [Lan02] Serge Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, revised third edition, 2002.
  * [Leg15] François Legrand.  Parametric Galois extensions.  J. Algebra, 422:187–222, 2015.
  * [Leg16] François Legrand.  Specialization results and ramification conditions.  Israel J. Math., 214(2):621–650, 2016.
  * [Mes90] Jean-François Mestre.  Extensions régulières de $\mathbb{Q}({T})$ de groupe de Galois $\tilde{A}_{n}$. (French).  J. Algebra, 131(2):483–495, 1990.
  * [MM99] Gunter Malle and B. Heinrich Matzat.  Inverse Galois theory.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 1999.
  * [Mül02] Peter Müller.  Finiteness results for Hilbert’s irreducibility theorem.  Ann. Inst. Fourier (Grenoble), 52(4):983–1015, 2002.
  * [Mum99] David Mumford.  The red book of varieties and schemes, volume 1358 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, Second, expanded edition, 1999.  Includes the Michigan lectures (1974) on curves and their Jacobians, With contributions by Enrico Arbarello. x+306 pp.
  * [Pop96] Florian Pop.  Embedding problems over large fields.  Ann. of Math. (2), 144(1):1–34, 1996.
  * [Sad99] Bounab Sadi.  Descente effective du corps de définition des revêtements.  Thèse Univ. Lille 1, 1999.
  * [Sal82] David J. Saltman.  Generic Galois extensions and problems in field theory.  Adv. in Math., 43(3):250–283, 1982.
  * [Sch00] A. Schinzel.  Polynomials with special regard to reducibility, volume 77 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 2000.  With an appendix by Umberto Zannier. x+558 pp.
  * [Ser92] Jean-Pierre Serre.  Topics in Galois Theory.  Research Notes in Mathematics. Jones and Bartlett Publishers, 1992.
  * [Sil09] Joseph H. Silverman.  The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics.  Springer, Dordrecht, second edition, 2009.  xx+513 pp.
  * [Völ96] Helmut Völklein.  Groups as Galois groups, volume 53 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1996.  An introduction. xviii+248 pp.