# Case Repositories: Towards Case-Based Reasoning for AI Alignment

K. J. Kevin Feng1, Quan Ze Chen1, Inyoung Cheong1, King Xia2, Amy X. Zhang1
1University of Washington, 2Independent Attorney
<EMAIL_ADDRESS>
###### Abstract

Case studies commonly form the pedagogical backbone in law, ethics, and many
other domains that face complex and ambiguous societal questions informed by
human values. Similar complexities and ambiguities arise when we consider how
AI should be aligned in practice: when faced with vast quantities of diverse
(and sometimes conflicting) values from different individuals and communities,
with whose values is AI to align, and how should AI do so? We propose a
complementary approach to constitutional AI alignment, grounded in ideas from
case-based reasoning (CBR), that focuses on the construction of policies
through judgments on a set of cases. We present a process to assemble such a
case repository by: 1) gathering a set of “seed” cases—questions one may ask
an AI system—in a particular domain, 2) eliciting domain-specific key
dimensions for cases through workshops with domain experts, 3) using LLMs to
generate variations of cases not seen in the wild, and 4) engaging with the
public to judge and improve cases. We then discuss how such a case repository
could assist in AI alignment, both through directly acting as precedents to
ground acceptable behaviors, and as a medium for individuals and communities
to engage in moral reasoning around AI.111Visit our project website at
https://social.cs.washington.edu/case-law-ai-policy/.

##  1 Introduction

Our world is governed by many fundamental laws. The laws of physics, for
example, provide us with a foundational understanding of natural phenomena.
National constitutions shape a country’s governance systems, legal frameworks,
cultural identity, and more. However, when it comes to grappling with
intricacies of human behavior and values in socially-situated everyday
settings, we cannot rely on high-level laws alone. Indeed, many
fields—including business, medicine, psychology, and even law itself—leverage
case studies as core pedagogical material for current and future
practitioners. Case studies illuminate the nuanced interplay of variables and
circumstances and enable us to understand the multifaceted aspects of the real
world beyond what theoretical principles alone can reveal. Through case
studies, we hone critical thinking and problem-solving abilities, ethical
reasoning, and practical application of knowledge.

Current approaches to aligning AI systems often seek to derive high-level
policies with which AI can be governed. For example, OpenAI’s ChatGPT was
supplemented with content filters trained on broad categories of undesired
content to guide the model toward producing more socially acceptable outputs
(Markov et al. (2023)). Fine-tuning with human feedback (Ouyang et al. (2022))
aligns model behavior to stated preferences of a user group, as evaluated by
broad requirements including helpful, honest, and harmless (Askell et al.
(2021)). Bai et al. (2022) propose reinforcement learning with AI feedback
(RLAIF) based on a set of rules or principles (a “constitution”) provided by a
human. However, as AI systems are deployed into the real world and operate
amidst a multitude of values from diverse individuals and groups, we encounter
similar issues that plague rule-based systems discussed earlier. When used by
communities with different values, how should an AI system adapt? In cases of
conflicting values, how should AI handle those conflicts? How can AI seek
democratic input and avoid reconciling fundamentally subjective views on
topics such as religion and politics when it is not appropriate to do so?

In light of these questions, we turn to case-based reasoning (CBR), a process
that has been applied to tackle ethical and moral questions by extracting or
extending concepts found in precedent cases to determine the most appropriate
course of action. We propose an approach that enables the operationalization
of CBR in AI alignment contexts, aiming to complement approaches that rely on
high-level policies (we refer to these approaches as more “constitutional”).
Central to our approach is the compilation of value-encoded precedents into a
case repository to further understand and enhance policies. An outline of our
process is as follows:

  1. 1.

We first collect a small set of illustrative user input queries (“cases”) to
an AI for a specific domain, where many (and sometimes conflicting) values
could affect the appropriateness of an AI response. We draw these “seed cases”
by referencing existing case studies as well as discussions in online
communities, most notably Reddit.

  2. 2.

We engage with domain experts by conducting a series of expert workshops to
elicit key dimensions experts consider when evaluating the appropriateness of
a variety of AI responses to seed cases.

  3. 3.

We develop an LLM-assisted method for rapidly expanding the case space through
guided generation of new synthetic cases, using our seed cases and elicited
expert dimensions.

  4. 4.

We engage the public through crowdsourcing to collect diverse judgements about
the appropriateness of AI responses to our cases, as well as refine our
synthetic cases.

We more concretely demonstrate our process by providing examples of how we can
assemble a case repository to steer AI behavior in the domain of providing
legal advice to users. Overall, our process engages knowledge from experts,
members of the general public, and large language models (LLMs) to build a
repository of cases with judgements of (in)appropriate AI responses. This case
repository, along with higher-level policies, can then be used to inform AI
behavior on new cases in a target domain. Potential benefits of our approach
include portability across communities and domains (the process is compatible
with a wide range of cases and AI response evaluations) and portability across
AI models (the process is not trained into a model and therefore does not rely
on it). More broadly, we show through our process how CBR can be
operationalized for AI alignment.

##  2 Proposed Process

While some online communities have come together to document and share inputs
and responses to AI, both the amount of cases available and the variety of
situations they cover remains limited. How do we create a rich set of cases to
support discussion around ethically-informed AI?

In this work, we propose a human-AI hybrid process to enrich the space of
cases, that engages with experts, large language models (LLMs), and the
general public. In this section, we will describe the process we propose as
well as provide some preliminary examples of using our process to create cases
in the area of users seeking legal advice from an AI system.

###  2.1 Collecting Seed Cases

We start by compiling a small set of cases based on discourse in online
communities (Reddit, Twitter, media outlets, etc.), as well as existing cases
in case studies and case law. Discourse within these communities can often
provide valuable insight into the kinds of inputs users may ask an AI system
within the same domain. In our example domain of legal advice, we curated a
series of questions222When running our process in the legal domain, we
collected 33 initial seed cases. They can be viewed at
https://github.com/social-futures-lab/case-law-ai-
policy/blob/main/data/cases.csv., many of which were submitted by users from
the popular subreddit r/legaladvice. Some cases taken from online communities
were slightly edited for anonymization and clarity. An example of a case we
collected is as follows:

> I run a popular online mobile game company. We have millions of users all
> across the United States. Our mobile games are free, but have micro-
> transactions. Additionally, we collect and sell user data (which we note in
> our terms of service). Finally, we run ads in our games, which also generate
> revenue. What should our legal strategy include, consider, or be?

###  2.2 Eliciting Key Dimensions from Experts

We recruit individuals with expertise in the domain of our seed cases, where
expertise is determined formally by factors such as awarded degrees, licenses,
and professional practice. We conduct small-group workshops with our recruited
experts in which we present our seed cases along with generic templates for AI
responses to those seed cases. Our templates were empirically derived from
high-level response styles we observed from OpenAI’s GPT-3, 3.5, and 4 LLMs;
examples of AI response templates can be found in Table 1. Given our seed
cases and AI response templates, we then facilitate a semi-structured
discussion among experts on key dimensions that impact their decision on which
AI response template(s) are appropriate. A response template is appropriate to
an expert if they have no concerns with a member of the general public who
provided the initial input consuming an answer generated in accordance with
the template. Experts then had a chance to elaborate on why they chose the
response template(s) they did within the context of the key dimensions they
and others have identified.

Template Name |  Description |  Example Response (Legal Advice)
---|---|---
Content violation |  Displays a warning message that the user’s input violates the AI’s content policy. |  This content may violate our content policy. If you believe this to be in error, please submit your feedback—your input will aid our research in this area.
Refuse to answer |  Avoids providing a response to the input and advises the user to seek professional advice instead. |  As an AI model, I am not a substitute for consulting with a trained professional. This seems like a specific concern or issue that requires expert advice. It’s always advisable to speak with a professional in the relevant field.
High-level answer without facts |  Provides a response that answers the input in broad strokes, stating advice rather than facts. |  I am not a lawyer, but I can provide some general information about possible legal strategies that might be used in a situation like this.  1. Terms of Service and Privacy Policy: Clearly outline your terms of service, including details about micro-transactions, data collection, and advertising. […]
Specific answer with facts |  Provides a detailed response that cites specific facts relevant to the input. |  I am not a lawyer, but I can provide some information about specific legal strategies that may be applied in a situation like this.  1. Compliance with Applicable Laws and Regulations: Laws like the Children’s Online Privacy Protection Act (COPPA) and the California Consumer Privacy Act (CCPA) may be relevant. […]
Ask a follow-up question |  Responds with a question requesting more information. |  To help you with this, I will need some additional information. Is your game intended for primarily children, or did you set age restrictions for your users?
Table 1: AI response templates and corresponding example responses.

Within the semi-structured discussions, experts take turns presenting their
key dimensions and how those dimensions impact their perception of response
appropriateness. They receive comments and feedback from other experts. At the
end of each workshop, we collect the expert dimensions, which we then use to
guide the expansion of the case space from a set of seed cases to a full case
repository.

For the domain of legal advice, we hosted 6 workshops conducted online via
Zoom in August 2023 with 20 legal experts, with 3–4 legal experts per group.
Our experts included lawyers and attorneys in various jurisdictions within the
US and UK, and two law school students in the US. Returning to our example
seed case in Section 2.1, key dimensions considered by experts for that case
include:

  * •

Location of operation (whether the mobile game operates in the states having
privacy law).

  * •

Ad providers’ data collection practices (are ad providers also collecting
data).

  * •

Involvement of minors (whether there are users who fall under a certain age).

  * •

Nature of data (what kind of user information is being collected?).

  * •

Terms of service (language and terminology used in the terms of service).

###  2.3 Expanding the Case Space via LLM-Assisted Case Generation

To grow the existing seed cases into a case repository, we extend seed cases
along expert dimensions to create new cases that improve clarity and coverage
of the case space. While we could manually author these new cases (or recruit
writers to do so), extending many cases along many dimensions can quickly turn
into a time-consuming and laborious task. To make this process more efficient
and scalable, we enlist LLMs (specifically, GPT-4) to help author new cases.
We posit that the authoring problem is well-constrained in that we are merely
perturbing details in the case by possible scenarios within a dimension, and
we use this insight to derive a prompt for generating synthetic cases. Our
prompt takes as input a starter case, a key dimension, and a step size
parameter $n$ that controls the number of cases generated as well as the
granularity of the perturbation (a larger $n$ would direct the model to
formulate more scenarios that may occur along a dimension, resulting in more
cases and finer perturbations).

Using our legal advice example in Section 2.1 as a starter case, along with
the dimension ad providers’ data collection practices and $n=3$, our LLM-
assisted case generation method produces the synthetic cases displayed in
Table 2.

Synthetic case 1 |  I run a popular online mobile game company with a wide user base across the United States. Our mobile games are free but include microtransactions. We also gather and sell user data as stated in our terms of service. To add to our revenue stream, we host ads in our games. However, our ad providers are not involved in the data collection process. What should our legal strategy consider or include with respect to data privacy laws, ad regulations and user consent?
---|---
Synthetic case 2 |  I operate a successful online mobile game company with millions of users nationwide. Our mobile games are free, supplemented by microtransactions and in-game ads. We collect and sell user data, a fact we clearly communicate in our terms of service. Our ad providers also collect data, but they do so independently of us, without sharing the collected data with us. What legal strategy should we adopt to ensure compliance with data protection regulations, ad laws, and user consent requirements?
Synthetic case 3 |  I am the proprietor of a prominent online mobile game company with a large footprint across the United States. Our games are made freely available to users, with revenue generated through microtransactions, ads in our games, and by selling user data, which is disclosed in our terms of service. In this scenario, not only do we collect user data, but our ad providers also do, and they share this data with us. In light of this, what should our legal strategy entail to ensure adherence to privacy laws, ad norms, and user consent protocols?
Table 2: Three synthetic cases generated using our method, with the starter
case being the example from Section 2.1, the dimension as ad providers’ data
collection practices, and $n=3$.

###  2.4 Engaging the Public in Evaluating and Refining Cases

Although we can rapidly generate synthetic cases with our case generation
method, not all synthetic cases will be ideal precedents for the case
repository. For example, cases for which individuals do not take firm stances
on an output (e.g., they do not care much for the outcome) or ambiguous cases
(e.g., lacking key details or depending on key assumptions that have yet to be
specified) may not make for strong precedents. Additionally, a complete entry
in the case repository should include not only the case itself, but also a
judgement of what types of AI responses are appropriate. That way, an AI
system can use precedents to adapt its responses given a case it has not seen
before.

In Section 2.2, we worked with experts to identify key dimensions to guide the
expansion of the case space. Here, we also engage the public through a
crowdsourcing workflow to 1) collect judgements about the appropriateness of
AI responses to existing cases, and 2) refine the synthetic cases generated
from our LLM-assisted case generation method to enhance their suitability for
the case repository.

In the judgement task, a crowd worker is presented with a case and five
responses generated using our response templates in Table 1. The worker then
rates the appropriateness of each of the responses through the following three
Likert-scale questions:

  1. 1.

How appropriate is this response to you? (1 = very inappropriate, 5 = very
appropriate).

  2. 2.

How likely can this response be considered harmful to you? (1 = very low
chance of harm, 5 = very high chance of harm).

  3. 3.

How likely can this response be considered harmful to others who ask the same
question? (1 = very low chance of harm, 5 = very high chance of harm).

We randomly assign cases to workers, with workers being able to pick up extra
cases (with proportional compensation added) if desired.

In the refinement task, a crowd worker is presented with a case and an
interface that implements our LLM-assisted case generation method. The worker
then can add or edit details of the case by tweaking the dimension and step
size and/or editing the text directly. This allows us to catch any nonsensical
details stemming from both LLM hallucinations as well as mismatched
combinations of dimensions and step size. The refined cases are then made
available for judgement, and the iterative workflow continues until we collect
sufficient judgements and case refinements. We are currently exploring metrics
that can help us determine when we reach this sufficiency.

We are also excited about leveraging existing tools in deliberation and AI-
assisted writing to enhance public participation. For example, the Goldilocks
workflow by Chen et al. (2021) allows us to capture workers’ uncertainty in
judgement, while consensus-gathering platforms such as Pol.is by Small et al.
(2021) allow communities to author and vote on the relevance of the cases to
community members.

##  3 Related Work and Discussion

###  3.1 Case-based Reasoning (CBR) in Moral Philosophy

As Kolodner (1992) notes, CBR has a long and storied pedigree in Western
philosophy, theology, and jurisprudence. In a moral theory, Hume was skeptical
of overapplying general principles, focusing on contextual factors Mackie
(2003). This contrasts with Kant’s emphasis on universal maxims, but aligns
with the common law view that principles emerge from cases and must be applied
flexibly (Paulo (2015), Jonsen (1986)). Earlier theologians and lawyers from
the 14th to 17th centuries called this case-based approach “casuistry.”
Casuistry refers to analyzing the circumstances of particular cases rather
than strictly applying ethical theories. Although modern scholars (e.g., Smith
(1976)) rejected casuistry due to its potentially manipulative qualities, it
provides a pragmatic approach to complex moral dilemmas. Fullinwider (2010)
stresses to revive casuistic reasoning in moral education to develop
individuals’ ability to make nuanced judgements drawing on social context.
Downie (1992) sees that casuistry can bridge the gap between abstract ethical
principles and complex real-world medical cases through context-sensitive
reasoned analysis of paradigmatic examples.

###  3.2 CBR in Jurisprudence

The American legal system is built on precedent and case law, much like the
casuistic approach in moral reasoning (Paulo (2015)). Judicial decisions in
individual cases establish norms that guide future rulings on similar cases.
This inductive method contrasts with the deductive application of abstract
legal codes (Cardozo and Kaufman (2010), Sunstein (2018), Grey (1983)).
Supreme Court justice Oliver Wendell Holmes Jr. wrote, “The life of the law
has not been logic, it has been experience …The law embodies the story of a
nation’s development through many centuries, and it cannot be dealt with as if
it contained only the axioms and corollaries of a book of mathematics” (Holmes
Jr (2020)). The accumulation of cases creates a common law system where
principles emerge from practical scenarios rather than pre-existing theories.
Kagan (2019) portrays the US legal system as a particularly adversarial,
transparent, and decentralized framework deliberately relying on casuistic
reasoning in judicially resolving societal conflicts and setting norms.
Sunstein (2018) draws on John Rawls’ “reflective equilibrium” to argue that
ethical and legal problems must be evaluated not by applying a general theory,
but instead through carefully engaging with general principles, considered
judgments about particular cases, and the interplay between them.

###  3.3 CBR and AI Reasoning/Alignment

CBR has been proposed as a useful model for AI systems to exhibit human-like
reasoning and learning (Craw and Aamodt (2018)). Early work by Kolodner (1992)
outlines processes like case retrieval, adaptation, and retention that could
enable automated CBR. Aamodt and Plaza (1994) provides a survey outlining
foundational issues, key method variations, and different system approaches.
Research has since explored techniques like introspective reasoning to improve
system knowledge (Leake and Powell (2010)), evidence-driven retrieval to
bridge gaps between finding and reusing cases (Sizov et al. (2015)), and meta-
CBR for systems to self-improve through self-understanding (Murdock and Goel
(2008)). Craw and Aamodt (2018) argue CBR is well-suited for domains without
well-defined theories, as its memory of experiential cases can enable
understanding of problem contexts and clustering. Figures 1a and 1b show the
core CBR elements and processes presented in 1992 and 2018.

(a) Kolodner (1992).

(b) Craw & Aamodt (2018).

Figure 1: CBR cycles and elements in the AI literature.

CBR’s application also raises important questions around value alignment, an
active area of research focused on ensuring AI behaves according to human
values (Gabriel (2020); Hendrycks et al. (2020); Chen and Zhang (2023)).
Recent work on value alignment for AI, such as Reinforcement Learning from
Human Feedback (RLHF) (Stiennon et al. (2020); Ouyang et al. (2022)) and
“Constitutional AI” applying the abstract principles of harmlessness, honesty,
and helpfulness to AI systems (Bai et al. (2022)) has pursued a unitary model
of ethics reflecting commonsense human values. However, critics argue this
could impose hegemonic perspectives, homogenizing diverse viewpoints (Bender
et al. (2021)). They advocate for more pluralistic representation, noting
limitations of prevailing preference-based utilitarian ethics (Tasioulas
(2022)) and misalignment with demographic groups (Santurkar et al. (2023);
Durmus et al. (2023)).

Alternative techniques have been proposed, such as optimizing text generation
for arbitrary rewards (Lu et al. (2022)), recursive reward modelling from
human feedback (Wu et al. (2023)), and the large-scale ValuePrism dataset
connecting pluralistic values to situations (Sorensen et al. (2023)). These
methods are meaningful yet do not adequately convey the nuances of individual
moral perspectives. We envision that an evolving case base would enable
adapting recommendations and explanations to users’ specific values, balancing
common ground with individual differences. Thus, CBR could inform AI alignment
research to achieve ongoing “reflective equilibrium” between general
principles and particular judgments, similar to how common law incrementally
evolves.

###  3.4 Future Work

We primarily described our process in a linear fashion, but through future
work, we strive to make it iterative. New queries received by an AI system may
not have closely related precedents in the case repository and will need to be
added to the repository as a case. We see this iterative case creation and
expansion process as a way of instilling expert and public input as an
indispensable ingredient in aligning AI systems. Some experts in our workshops
expressed concern over AI’s potential automation of high-skill labor and
expertise, but with our iterative process, our stance is that it is crucial to
engage experts and laypeople alike to contribute towards and continually
update knowledge AI may draw upon. We thus invite the community to consider
interface affordances and incentive structures for iterative case repository
assembly.

We initially ran our process with 20 legal experts, but are starting to branch
out to mental health and medical experts. Even though our approach is meant to
be domain-agnostic, domain-specific requirements of case repositories may
still arise—we look forward to surfacing them to better understand the
challenges and needs of diverse communities as they assemble their own case
repositories. Additionally, our approach is also designed to be model-
agnostic. That is, once a case repository is created, it is a resource that
can be made available to a variety of LLMs. We can then test the case
repository for performance and consistency across models to both improve our
approach and learn more about different models’ abilities to adopt CBR.

Finally, case law is primarily practiced in Western legal systems. Future
workshops should involve experts familiar with non-Western legal frameworks to
discuss the benefits and shortcomings of a CBR-based approach.

##  4 Conclusion

In this paper, we present a process for enabling CBR to complement existing
constitutional approaches to AI alignment. Our process integrates knowledge of
domain experts, the public, and LLMs to assemble a set of value-encoded
precedents in the form of a case repository to inform AI behavior based on a
community’s existing values. More broadly, we see cases as an enlightening
medium for reasoning about morality, given its prior applications in law and
philosophy, and by extension, morality in AI. Our efforts are an early attempt
at working with this new medium for AI alignment. As interdisciplinary
conversations are critical to moving the needle in this space, we invite
researchers and practitioners in diverse fields including—but not limited
to—AI, philosophy, psychology, cognitive science, and law, to contribute to
continuing discussions to refine, critique, and iterate on our proposed ideas.

## Acknowledgments and Disclosure of Funding

This project was supported by OpenAI’s “Democratic Inputs to AI” grant
program. We thank Teddy Lee, Tyna Eloundou, Aviv Ovadya, members of the grant
recipient cohort, and others at OpenAI for insightful discussions and support.

## References

  * Aamodt and Plaza [1994] Agnar Aamodt and Enric Plaza.  Case-based reasoning: Foundational issues, methodological variations, and system approaches.  _AI communications_ , 7(1):39–59, 1994.
  * Askell et al. [2021] Amanda Askell, Yuntao Bai, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, Andy Jones, Nicholas Joseph, Ben Mann, Nova DasSarma, et al.  A general language assistant as a laboratory for alignment.  _arXiv preprint arXiv:2112.00861_ , 2021.
  * Bai et al. [2022] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al.  Constitutional ai: Harmlessness from ai feedback.  _arXiv preprint arXiv:2212.08073_ , 2022.
  * Bender et al. [2021] Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell.  On the dangers of stochastic parrots: Can language models be too big?  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’21, page 610–623, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450383097.  doi: 10.1145/3442188.3445922.  URL https://doi.org/10.1145/3442188.3445922.
  * Cardozo and Kaufman [2010] Benjamin N Cardozo and Andrew L Kaufman.  _The nature of the judicial process_.  Quid Pro Books, 2010.
  * Chen and Zhang [2023] Quan Ze Chen and Amy X Zhang.  Case law grounding: Aligning judgments of humans and ai on socially-constructed concepts.  _arXiv preprint arXiv:2310.07019_ , 2023.
  * Chen et al. [2021] Quan Ze Chen, Daniel S Weld, and Amy X Zhang.  Goldilocks: Consistent crowdsourced scalar annotations with relative uncertainty.  _Proceedings of the ACM on Human-Computer Interaction_ , 5(CSCW2):1–25, 2021.
  * Craw and Aamodt [2018] Susan Craw and Agnar Aamodt.  Case based reasoning as a model for cognitive artificial intelligence.  In _Case-Based Reasoning Research and Development: 26th International Conference, ICCBR 2018, Stockholm, Sweden, July 9-12, 2018, Proceedings 26_ , pages 62–77. Springer, 2018.
  * Downie [1992] Robin Downie.  Health care ethics and casuistry.  _Journal of medical ethics_ , 18(2):61, 1992.
  * Durmus et al. [2023] Esin Durmus, Karina Nyugen, Thomas I. Liao, Nicholas Schiefer, Amanda Askell, Anton Bakhtin, Carol Chen, Zac Hatfield-Dodds, Danny Hernandez, Nicholas Joseph, Liane Lovitt, Sam McCandlish, Orowa Sikder, Alex Tamkin, Janel Thamkul, Jared Kaplan, Jack Clark, and Deep Ganguli.  Towards Measuring the Representation of Subjective Global Opinions in Language Models, 2023.
  * Fullinwider [2010] Robert K Fullinwider.  Philosophy, casuistry, and moral development.  _Theory and Research in Education_ , 8(2):173–185, 2010.
  * Gabriel [2020] Iason Gabriel.  Artificial Intelligence, Values and Alignment.  _Minds and Machines_ , 30(3):411–437, Sep 2020.  ISSN 0924-6495, 1572-8641.  doi: 10.1007/s11023-020-09539-2.  arXiv:2001.09768 [cs].
  * Grey [1983] Thomas C Grey.  Langdell’s orthodoxy.  _U. Pitt. L. Rev._ , 45:1, 1983.
  * Hendrycks et al. [2020] Dan Hendrycks, Collin Burns, Steven Basart, Andrew Critch, Jerry Li, Dawn Song, and Jacob Steinhardt.  Aligning ai with shared human values.  _arXiv preprint arXiv:2008.02275_ , 2020.
  * Holmes Jr [2020] Oliver Wendell Holmes Jr.  _The common law_.  Routledge, 2020.
  * Jonsen [1986] Albert R Jonsen.  Casuistry and clinical ethics.  _Theoretical Medicine_ , 7:65–74, 1986.
  * Kagan [2019] Robert A Kagan.  _Adversarial Legalism: The American Way of Law_.  Harvard University Press, 2019.
  * Kolodner [1992] Janet L Kolodner.  An introduction to case-based reasoning.  _Artificial intelligence review_ , 6(1):3–34, 1992.
  * Leake and Powell [2010] David Leake and Jay Powell.  A general introspective reasoning approach to web search for case adaptation.  In _International Conference on Case-Based Reasoning_ , pages 186–200. Springer, 2010.
  * Lu et al. [2022] Ximing Lu, Sean Welleck, Jack Hessel, Liwei Jiang, Lianhui Qin, Peter West, Prithviraj Ammanabrolu, and Yejin Choi.  Quark: Controllable text generation with reinforced unlearning.  _Advances in neural information processing systems_ , 35:27591–27609, 2022.
  * Mackie [2003] John Leslie Mackie.  _Hume’s moral theory_.  Routledge, 2003.
  * Markov et al. [2023] Todor Markov, Chong Zhang, Sandhini Agarwal, Florentine Eloundou Nekoul, Theodore Lee, Steven Adler, Angela Jiang, and Lilian Weng.  A holistic approach to undesired content detection in the real world.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 15009–15018, 2023.
  * Murdock and Goel [2008] J William Murdock and Ashok K Goel.  Meta-case-based reasoning: self-improvement through self-understanding.  _Journal of Experimental & Theoretical Artificial Intelligence_, 20(1):1–36, 2008.
  * Ouyang et al. [2022] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 27730–27744. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/b1efde53be364a73914f58805a001731-Paper-Conference.pdf.
  * Paulo [2015] Norbert Paulo.  Casuistry as common law morality.  _Theoretical Medicine and Bioethics_ , 36(6):373–389, 2015.
  * Santurkar et al. [2023] Shibani Santurkar, Esin Durmus, Faisal Ladhak, Cinoo Lee, Percy Liang, and Tatsunori Hashimoto.  Whose opinions do language models reflect?  _arXiv preprint arXiv:2303.17548_ , 2023.
  * Sizov et al. [2015] Gleb Sizov, Pinar Öztürk, and Agnar Aamodt.  Evidence-driven retrieval in textual cbr: bridging the gap between retrieval and reuse.  In _Case-Based Reasoning Research and Development: 23rd International Conference, ICCBR 2015, Frankfurt am Main, Germany, September 28-30, 2015. Proceedings 23_ , pages 351–365. Springer, 2015.
  * Small et al. [2021] Christopher Small, Michael Bjorkegren, Timo Erkkilä, Lynette Shaw, and Colin Megill.  Polis: Scaling deliberation by mapping high dimensional opinion spaces.  _Recerca: revista de pensament i anàlisi_ , 26(2), 2021.
  * Smith [1976] Adam Smith.  The theory of moral sentiments, ed. dd raphael and al macfie, 1976.  VII, iv, 34.
  * Sorensen et al. [2023] Taylor Sorensen, Liwei Jiang, Jena Hwang, Sydney Levine, Valentina Pyatkin, Peter West, Nouha Dziri, Ximing Lu, Kavel Rao, Chandra Bhagavatula, Maarten Sap, John Tasioulas, and Yejin Choi.  Value kaleidoscope: Engaging ai with pluralistic human values, rights, and duties, 2023.
  * Stiennon et al. [2020] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021, 2020.
  * Sunstein [2018] Cass R Sunstein.  _Legal reasoning and political conflict_.  Oxford University Press, 2018.
  * Tasioulas [2022] John Tasioulas.  Artificial intelligence, humanistic ethics.  _Daedalus_ , 151(2):232–243, 2022.
  * Wu et al. [2023] Zeqiu Wu, Yushi Hu, Weijia Shi, Nouha Dziri, Alane Suhr, Prithviraj Ammanabrolu, Noah A Smith, Mari Ostendorf, and Hannaneh Hajishirzi.  Fine-grained human feedback gives better rewards for language model training.  _arXiv preprint arXiv:2306.01693_ , 2023.


††footnotetext: ${}^{{}^{a}}$Partially supported by RFBR under grant number
20-51-56017.
${}^{{}^{b}}$Partially supported by a grant from IPM.
${}^{{}^{c}}$Partially supported by Iran National Science Foundation under
project number 99003814.
${}^{{}^{d}}$Partially supported by the Natural Science Foundation of Anhui
Province with grant identifier 2008085MA03 and by the National Natural Science
Foundation of China with grant number 12171002.

# Weak saturation numbers in random graphs

Olga Kalinichenko${}^{{}^{1,a}}$ Meysam Miralaei${}^{{}^{2,b}}$ Ali
Mohammadian${}^{{}^{3,c,d}}$ Behruz Tayfeh-Rezaie${}^{{}^{2,c}}$
${}^{{}^{1}}$Moscow Institute of Physics and Technology,
Dolgoprudny 141700, Russia
${}^{{}^{2}}$School of Mathematics, Institute for Research in Fundamental
Sciences (IPM),
P.O. Box 19395-5746, Tehran, Iran
${}^{{}^{3}}$School of Mathematical Sciences, Anhui University,
Hefei 230601, Anhui, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

For two given graphs $G$ and $F$, a graph $H$ is said to be weakly
$(G,F)$-saturated if $H$ is a spanning subgraph of $G$ which has no copy of
$F$ as a subgraph and one can add all edges in $E(G)\setminus E(H)$ to $H$ in
some order so that a new copy of $F$ is created at each step. The weak
saturation number $\mathrm{wsat}(G,F)$ is the minimum number of edges of a
weakly $(G,F)$-saturated graph. In this paper, we deal with the relation
between $\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$ and $\mathrm{wsat}(K_{n},F)$,
where $\mathbbmsl{G}(n,p)$ denotes the Erdős–Rényi random graph and $K_{n}$
denotes the complete graph on $n$ vertices. For every graph $F$ and constant
$p$, we prove that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(K_{n},F)(1+o(1))$ with high
probability. Also, for some graphs $F$ including complete graphs, complete
bipartite graphs, and connected graphs with minimum degree $1$ or $2$, it is
shown that there exists an $\varepsilon(F)>0$ such that, for any $p\geqslant
n^{-\varepsilon(F)}\log n$,
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(K_{n},F)$ with high
probability.

Keywords: Random graph, Weak saturation number.

2020 Mathematics Subject Classification: 05C35, 05C80.

##  1 Introduction

All graphs throughout this paper are assumed to be finite, undirected, and
without loops or multiple edges. The vertex set of a graph $G$ is denoted by
$V(G)$ and the edge set of $G$ is denoted by $E(G)$. For two given graphs $G$
and $F$, a graph $H$ is said to be weakly $(G,F)$-saturated if $H$ is a
spanning subgraph of $G$ which has no copy of $F$ as a subgraph and there is
an ordering $e_{1},e_{2},\dots$ of edges in $E(G)\setminus E(H)$ such that for
$i=1,2,\ldots$ the spanning subgraph of $G$ with the edge set
$E(H)\cup\\{e_{1},\ldots,e_{i}\\}$ has a copy of $F$ containing $e_{i}$. The
minimum number of edges in a weakly $(G,F)$-saturated graph is called the weak
saturation number of $F$ in $G$ and is denoted by $\mathrm{wsat}(G,F)$. Let
$K_{n}$ be the complete graph on $n$ vertices and $K_{s,t}$ be the complete
bipartite graph with parts of sizes $s$ and $t$. For the purpose of
simplification, a weakly $(K_{n},F)$-saturated graph is called weakly
$F$-saturated if there is no danger of ambiguity and moreover,
$\mathrm{wsat}(K_{n},F)$ is written as $\mathrm{wsat}(n,F)$.

The notion of weak saturation was initially introduced by Bollobás [6] in
1968. Weak saturation is closely related to the so-called ‘graph bootstrap
percolation’ which was introduced for the first time in [3]. It is worth
mentioning that the study of any extremal parameter is an important task in
graph theory and usually receives a great deal of attention. Determining the
exact value of $\mathrm{wsat}(n,F)$ for a given graph $F$ is often quite
difficult. Although the weak saturation number has been studied for a long
time, related literature is still poor. Lovász [16] established that

$\mathrm{wsat}(n,K_{s})=(s-2)n-\binom{s-1}{2}$

when $n\geqslant s\geqslant 2$, settling a conjecture of Bollobás [6]. Kalai
[12] proved that

$\mathrm{wsat}(n,K_{t,t})=(t-1)n-\binom{t-1}{2}$

if $n\geqslant 4t-4$. An alternative proof for the result is given by
Kronenberg, Martins, and Morrison [15] for every $n\geqslant 3t-3$. They also
established that, for every $t>s$ and sufficiently large $n$,

$(s-1)(n-t+1)+{t\choose
2}\leqslant\mathrm{wsat}(n,K_{s,t})\leqslant(s-1)(n-s)+{t\choose 2}.$

Miralaei, Mohammadian, and Tayfeh-Rezaie [17] determined the exact value of
$\mathrm{wsat}(n,K_{2,t})$. They found that, for every $t\geqslant 3$ and
$n\geqslant t+2$,

$\displaystyle\mathrm{wsat}(n,K_{2,t})=\left\\{\begin{array}[]{ll}\vspace{-4.6mm}&\\\
n-1+{t\choose 2}&\quad\text{if $t$ is even and $n\leqslant 2t-2$},\\\
\vspace{-2mm}\\\ n-2+{t\choose 2}&\quad\text{otherwise}.\\\
\vspace{-4.6mm}&\end{array}\right.$

For more results on weak saturation and related topics, we refer to the survey
[8].

Random analogues of different parameters in extremal graph theory have been
extensively studied in the literature. These studies often reveal the behavior
of extremal parameters for a typical graph. Recall that the Erdős–Rényi random
graph model $\mathbbmsl{G}(n,p)$ is the probability space of all graphs on a
fixed vertex set of size $n$ where every two distinct vertices are adjacent
independently with probability $p$. Also, recall that the notion ‘with high
probability’ is used whenever an event occurs in $\mathbbmsl{G}(n,p)$ with a
probability approaching $1$ as $n$ goes to infinity.

The study of the weak saturation problem in random graphs was initiated by
Korándi and Sudakov [14]. They proved that, for every constant $p\in(0,1)$ and
integer $s\geqslant 3$,

$\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),K_{s}\big{)}=\mathrm{wsat}(n,K_{s})$

with high probability. We will sometimes use the notion ‘stability’ for the
graph $F$ if $\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ with
high probability. Bidgoli, Mohammadian, Tayfeh-Rezaie, and Zhukovskii [5]
established the existence of a threshold function for the property
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{s})=\mathrm{wsat}(n,K_{s})$ and provided
the following upper and lower bounds on the function for any $s\geqslant 3$.

  * •

There exists a constant $c_{s}$ such that, if $p\leqslant
c_{s}n^{-2/(s+1)}\log^{2/((s-2)(s+1))}n$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{s})\neq\mathrm{wsat}(n,K_{s})$ with high
probability.

  * •

If $p\geqslant n^{-1/(2s-3)}\log^{(s-1)/(2s-3)}n$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{s})=\mathrm{wsat}(n,K_{s})$ with high
probability.

Borowiecki and Sidorowicz [7] proved that

$\mathrm{wsat}(n,K_{1,t})=\binom{t}{2}$

provided $n\geqslant t+1$. A short proof of the result is given in [9].
Kalinichenko and Zhukovskii [13] investigated
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{1,t})$ and provided the following bounds
for $t\geqslant 3$.

  * •

There exists a constant $c_{t}$ such that, if $n^{-2}\ll p\leqslant
c_{t}n^{-1/(t-1)}\log^{-(t-2)/(t-1)}n$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{1,t})\neq\mathrm{wsat}(n,K_{1,t})$ with
high probability.

  * •

There exists a constant $d_{t}$ such that, if $p\geqslant
d_{t}n^{-1/(t-1)}\log^{-(t-2)/(t-1)}n$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{1,t})=\mathrm{wsat}(n,K_{1,t})$ with high
probability.

For a graph $G$ and a subset $X$ of $V(G)$, denote by $N_{G}(X)$ the set of
vertices of $G$ which are adjacent to all vertices in $X$ and set
$N_{G}[X]=X\cup N_{G}(X)$. For the sake of convenience,
$N_{G}(v_{1},\ldots,v_{k})$ is written instead of
$N_{G}(\\{v_{1},\ldots,v_{k}\\})$. For a vertex $v$ of $G$, we define the
degree of $v$ as $|N_{G}(v)|$ and denote it by $d_{G}(v)$. The maximum and
minimum degrees of the vertices of $G$ are denoted by $\mathnormal{\Delta}(G)$
and $\delta(G)$, respectively. Furthermore, denote by $e(\mathbbmsl{G}(n,p))$
the random variable counting the edges in $\mathbbmsl{G}(n,p)$.

Kalinichenko and Zhukovskii [13] studied sufficient conditions on weakly
$(K_{n},F)$-saturated graphs such that the equality
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ holds with high
probability. They proved the following theorem.

######  Theorem 1.1 ([13]).

Let $F$ be a graph with $\delta(F)\geqslant 1$. Also, let $p\in(0,1)$ and
$c\geqslant\delta(F)-1$ be constants. For every positive integer $n$, assume
that there exists a weakly $(K_{n},F)$-saturated graph $H_{n}$ containing a
set of vertices $S_{n}$ with $|S_{n}|\leqslant c$ such that each vertex from
$V(K_{n})\setminus S_{n}$ is adjacent to at least $\delta(F)-1$ vertices in
$S_{n}$. Then, there exists a weakly $(\mathbbmsl{G}(n,p),F)$-saturated graph
with $\min\\{e(\mathbbmsl{G}(n,p)),|E(H_{n})|\\}$ edges with high probability.

The following corollary immediately follows from Theorem 1.1 and a result due
to Spencer [19].

######  Corollary 1.2 ([13]).

Let $F$ be a graph with $\delta(F)\geqslant 1$ and let $p\in(0,1)$ be
constant. For every positive integer $n$, assume that there exists a weakly
$(K_{n},F)$-saturated graph $H_{n}$ with $|E(H_{n})|=\mathrm{wsat}(n,F)$
satisfying the property described in Theorem 1.1. Then,
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ with high
probability.

It has been verified in [13] that Corollary 1.2 implies the stability for some
graphs $F$ such as complete graphs and complete bipartite graphs.

In this paper, we continue to explore the relation between
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$ and $\mathrm{wsat}(n,F)$. We find the
asymptotic behavior of $\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$ and sometimes its
exact value compared to $\mathrm{wsat}(n,F)$. Regarding the asymptotic
behavior, we prove the following theorem in Section 2.

######  Theorem 1.3.

Let $F$ be a graph with $\delta(F)\geqslant 1$ and let $p\in(0,1)$ be
constant. Then,
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)(1+o(1))$ with high
probability.

Notice that addition of isolated vertices to the graph $F$ does not change the
weak saturation number. Subsequently, we only consider graphs $F$ with
$\delta(F)\geqslant 1$. Especially, Theorem 1.3 holds for all graphs $F$. In
Section 3, we present a sufficient condition on $\mathrm{wsat}(n,F)$ for which
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ with high
probability.

######  Theorem 1.4.

Let $F$ be a graph with $\delta(F)\geqslant 1$ and let
$\mathrm{wsat}(n,F)\geqslant(\delta(F)-1)n+D$ for all $n$, where $D$ is a
constant depending on $F$. Then, there exist a positive integer $k$ and a
constant $d_{F}$ such that $\mathrm{wsat}(n,F)=(\delta(F)-1)n+d_{F}$ and, for
any $p\geqslant n^{-1/(2k+3)}\log n$,
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ with high
probability.

For some graphs $F$ including complete graphs, complete bipartite graphs, and
connected graphs with minimum degree $1$ or $2$, Theorem 1.4 shows that there
is an $\varepsilon(F)>0$ such that, for any $p\geqslant
n^{-\varepsilon(F)}\log n$,
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ with high
probability, see Remark 3.11. Note that Theorem 1.4 is a generalization of
Theorem 1.1 and Corollary 1.2 with simpler arguments. Actually, a weakly
$(K_{n},F)$-saturated graph having the structure described in Theorem 1.1 has
$(\delta(F)-1)n+D$ edges for some constant $D$ depending on $F$. Our proof
does not require a specific structure of the weakly $(K_{n},F)$-saturated
graph, only the number of edges in it is needed. This makes it easier to
construct arguments and apply the result not only to complete graphs and
complete bipartite graphs which can be also easily done with Theorem 1.1, but
also to some other types of graphs.

Finally, we consider the case $p=o(1)$ in Section 4 where we present a
condition which implies that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=e(\mathbbmsl{G}(n,p))(1+o(1))$ with high
probability.

Let us fix here more notation and terminology that we use in the rest of the
paper. Let $G$ be a graph. For a vertex $v$ of $G$, we denote by $G-v$ the
graph obtained from $G$ by removing $v$ and all of its incident edges. For two
nonadjacent vertices $u,v$ of $G$, let $G+uv$ denote the graph obtained from
$G$ by adding an edge between $u$ and $v$. For a subset $X$ of $V(G)$, we
denote the induced subgraph of $G$ on $X$ by $G[X]$. For two disjoint subsets
$S$ and $T$ of $V(G)$, denote by $E_{G}(S,T)$ the set of all edges with an
endpoint in both $S$ and $T$. For the purpose of simplicity, $E_{G}(v,T)$ is
written instead of $E_{G}(\\{v\\},T)$. For a positive integer $d$, the $d$-th
power of $G$, denoted by $G^{d}$, is the graph with vertex set $V(G)$ and two
vertices $x,y$ are adjacent in $G^{d}$ if and only if the distance between
$x,y$ in $G$ is at most $d$.

##  2 Asymptotic stability

In this section, we prove that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)(1+o(1))$ with high
probability for any constant $p$ and any graph $F$. To proceed, we need to
recall the following result on the appearance of the powers of a Hamiltonian
cycle in $\mathbbmsl{G}(n,p)$.

######  Theorem 2.1 ([11, 18]).

If $k\geqslant 2$ and $p\gg n^{-1/k}$, then $\mathbbmsl{G}(n,p)$ contains the
$k$-th power of a Hamiltonian cycle with high probability.

######  Lemma 2.2.

Let $p=n^{-o(1)}$. Then, there is a function $w(n)$ tending to infinity as
$n\rightarrow\infty$ such that the vertex set of $\mathbbmsl{G}(n,p)$ can be
partitioned into cliques of size at least $w(n)$ with high probability.

###### Proof.

Let $\mathcal{H}_{d}$ be the event that $\mathbbmsl{G}(n,p)$ contains the
$d$-th power of a Hamiltonian cycle. Since $p=n^{-o(1)}$, Theorem 2.1 implies
that, for any $\varepsilon>0$ and any integer $k\geqslant 2$, there is a
minimum integer $N(k,\varepsilon)$ such that
$\mathbbmsl{P}[\mathcal{H}_{k}]\geqslant 1-\varepsilon$ for any $n\geqslant
N(k,\varepsilon)$. Note that $N(k,\varepsilon)\geqslant k+1$ and
$N(k_{1},\varepsilon_{1})\geqslant N(k_{2},\varepsilon_{2})$ if
$k_{1}\geqslant k_{2}$ and $\varepsilon_{1}\leqslant\varepsilon_{2}$. Let
$m_{1}=2$ and for any $k\geqslant 2$, define

$m_{k}=\min\left\\{\ell\,\left|\,\ell>m_{k-1}\text{ and
}N\left(\ell,\frac{1}{k}\right)>N\left(m_{k-1},\frac{1}{k-1}\right)\right.\right\\}.$

Clearly, $\\{N(m_{k},\tfrac{1}{k})\\}_{k=1}^{\infty}$ is strictly increasing.
Now, define the function $w$ as

$w(n)=m_{k}\,\text{ for any }\,k\geqslant 1\,\text{ and
}\,n\in\left[N\left(m_{k},\frac{1}{k}\right),N\left(m_{k+1},\frac{1}{k+1}\right)\right).$

Obviously, $w(n)\rightarrow\infty$ as $n\rightarrow\infty$. We show that
$\mathbbmsl{P}[\mathcal{H}_{w(n)}]\geqslant 1-\tfrac{1}{k}$ for every $k$ and
$n\geqslant N(m_{k},\tfrac{1}{k})$. To see this, fix $k$ and assume that
$N(m_{\ell},\tfrac{1}{\ell})\leqslant n<N(m_{\ell+1},\tfrac{1}{\ell+1})$ for
some $\ell\geqslant k$. Then,

$\mathbbmsl{P}\Big{[}\mathcal{H}_{w(n)}\Big{]}=\mathbbmsl{P}\Big{[}\mathcal{H}_{m_{\ell}}\Big{]}\geqslant
1-\frac{1}{\ell}\geqslant 1-\frac{1}{k}.$

Thus, $\mathbbmsl{G}(n,p)$ contains the $w(n)$-th power of a Hamiltonian cycle
with high probability, say $C$. Note that every $w(n)+1$ consecutive vertices
of $C$ form a clique in $\mathbbmsl{G}(n,p)$. Now, by partitioning the
vertices of $\mathbbmsl{G}(n,p)$ so that each part consists of at least
$w(n)/2$ consecutive vertices of $C$, the result follows. ∎

The following lemma is obtained from Theorem 2 in [19].

######  Lemma 2.3 ([19]).

For any integer $s\geqslant 3$, there exists a constant $c$ such that if
$p\geqslant cn^{-2/(s+1)}\log^{{2}/((s-2)(s+1))}n$, then every two vertices of
$\mathbbmsl{G}(n,p)$ have a clique of size $s-2$ in their common neighbors
with high probability.

The following corollary immediately follows from Lemma 2.3.

######  Corollary 2.4.

Let $F$ be a graph and let $s=|V(F)|\geqslant 3$ and $\delta(F)\geqslant 1$.
There is a constant $c$ such that if $p\geqslant
cn^{-2/(s+1)}\log^{{2}/((s-2)(s+1))}n$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\geqslant\mathrm{wsat}(n,F)$ with high
probability.

###### Proof.

Let $H$ be a weakly $(\mathbbmsl{G}(n,p),F)$-saturated graph with minimum
possible number of edges. Using Lemma 2.3, $\mathbbmsl{G}(n,p)$ is weakly
$F$-saturated graph with high probability. This shows that $H$ is also a
weakly $F$-saturated graph, the result follows. ∎

######  Remark 2.5.

A graph $G$ is called balanced if $(|E(H)|-1)/(|V(H)|-2)\leqslant\lambda_{G}$
for all proper subgraphs $H$ of $G$ with $|V(H)|\geqslant 3$, where
$\lambda_{G}=(|E(G)|-2)/(|V(G)|-2)$. It was proved in [4] that if $F$ is a
balanced graph and $p\gg n^{-1/\lambda_{F}+o(1)}$, then $\mathbbmsl{G}(n,p)$
is weakly $F$-saturated with high probability, implying that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\geqslant\mathrm{wsat}(n,F)$ with high
probability. In general, threshold probability functions for the property that
$\mathbbmsl{G}(n,p)$ is weakly $F$-saturated are still unknown.

The following lemma immediately follows from the Chernoff bound [2, Corollary
A.1.2] and the union bound.

######  Lemma 2.6.

For any positive integer $k$, there exists a constant $c$ such that if
$p\geqslant c((\log n)/n)^{1/k}$, then every $k$-subset of the vertex set of
$\mathbbmsl{G}(n,p)$ has at least $p^{k}n/2$ common neighbors with high
probability.

The following interesting result, due to Alon [1], will be used in the next
theorem and the subsequent sections.

######  Theorem 2.7 ([1]).

Let $F$ be a graph with $\delta(F)\geqslant 1$. Then, there exists a constant
$c_{F}$ such that $\mathrm{wsat}(n,F)=(c_{F}+o(1))n$.

We are now in a position to prove the main result of this section. Recall
Theorem 1.3.

See 1.3

###### Proof.

It follows from Theorem 2.7 that there exists a constant $c_{F}$ such that
$\mathrm{wsat}(n,F)=(c_{F}+o(1))n$. By Corollary 2.4, it remains to show that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\leqslant(c_{F}+o(1))n$ with high
probability.

Note that $\mathrm{wsat}(G,K_{2})=0$ for every graph $G$ and so there is
nothing to prove when $F=K_{2}$. Therefore, we may assume that $F$ has
$s\geqslant 3$ vertices. By Lemma 2.2, there is a function $w(n)$ such that
$w(n)$ goes to infinity when $n\rightarrow\infty$ and, with high probability,
the vertex set of $G\thicksim\mathbbmsl{G}(n,p)$ admits a partition into
$V_{1},\ldots,V_{m}$ such that each $V_{i}$ is a clique of size at least
$w(n)$.

Fix an $(s-2)$-subset $S$ in $V_{1}$ and let $i\in\\{1,\ldots,m\\}$. If
$|N_{G}(S)\cap V_{i}|\geqslant s-1$, then let $S_{i}$ be an arbitrary
$(s-1)$-subset of $N_{G}(S)\cap V_{i}$ and otherwise, let $S_{i}$ be an
arbitrary $(s-1)$-subset of $V_{i}\setminus S$ containing $N_{G}(S)\cap
V_{i}$. Consider the set $N_{G}(S\cup S_{i})$. Using Lemma 2.6, we have
$|N_{G}(S\cup S_{i})|\geqslant p^{2s-3}n/2$. Since $p$ is constant and
$m\leqslant n/w(n)$, there exists an index $i^{\prime}$ such that
$|N_{G}(S\cup S_{i})\cap V_{i^{\prime}}|\geqslant s-2$. Let $R_{i}$ be an
arbitrary $(s-2)$-subset of $N_{G}(S\cup S_{i})\cap V_{i^{\prime}}$.

We are going to introduce a weakly $(G,F)$-saturated graph $H$ with
$|E(H)|\leqslant(c_{F}+o(1))n$. For $i=1,\ldots,m$, let $H_{i}$ be a weakly
$(G[V_{i}],F)$-saturated graph with $\mathrm{wsat}(|V_{i}|,F)$ edges. Define
$H$ to be a spanning subgraph of $G$ with $E(H)=\bigcup_{i=1}^{m}(E(H_{i})\cup
E_{G}(S_{i},S\cup R_{i}))$. We have

$|E(H)|\leqslant\sum_{i=1}^{m}\Big{(}\big{(}c_{F}+o(1)\big{)}|V_{i}|+2(s-1)(s-2)\Big{)}=\big{(}c_{F}+o(1)\big{)}n.$

So, it remains to prove that $H$ is weakly $(G,F)$-saturated. To do this, we
show that the edges in $E(G)\setminus E(H)$ can be added to $H$ in some order
through a weakly $(G,F)$-saturated process. We use $H$ to denote the resulting
graph in any step of the process as well. Note that, in each step of the
process, every edge $xy\in E(G)\setminus E(H)$ can be added to $H$ whenever
$N_{H}(x,y)$ contains a clique of size $s-2$ in $H$. For $i=1,\ldots,m$, as
$H_{i}$ is weakly $(G[V_{i}],F)$-saturated, we may add the edges in
$E(G[V_{i}])\setminus E(H_{i})$ in an appropriate order. By doing this, each
$V_{i}$ becomes a clique in $H$.

Then, we add all edges in $E_{G}(S,N_{G}(S))\setminus E(H)$ to $H$ as follows.
Let $x\in N_{G}(S)\cap V_{i}$ for some $i$. If $x\in S_{i}$, then $x$ is
already joined to all vertices of $S$ in $H$ and there is nothing to prove.
So, we may assume that $x\notin S_{i}$. In this case, according to the choice
of $S_{i}$, we have $S_{i}\subseteq N_{G}(S)$ and therefore $S_{i}\subseteq
N_{H}(S)$ . Hence, for every $y\in S$, it follows from $S_{i}\subseteq
N_{H}(x,y)$ that the edge $xy$ can be added to $H$.

Now, we add all edges in $E_{G}(V_{i},V_{j})\setminus E(H)$ to $H$ for all
distinct indices $i,j\in\\{1,\ldots,m\\}$ as follows. Let $x\in V_{i}$ and
$y\in V_{j}$ with $1\leqslant i<j\leqslant m$ such that $x,y$ are not adjacent
in $H$. Consider the set $U=N_{G}(S\cup S_{i}\cup S_{j}\cup R_{i}\cup
R_{j}\cup\\{x,y\\})$. Using Lemma 2.6, we have $|U|\geqslant p^{5s-6}n/2$.
Since $p$ is constant and $m\leqslant n/w(n)$, there exists an index $k$ such
that $|U\cap V_{k}|\geqslant s-2$. Let $T$ be an arbitrary $(s-2)$-subset of
$U\cap V_{k}$.

We claim that $x$ can be joined to all vertices in $T$ in $H$. First, we add
all remaining edges between $R_{i}$ and $T$ to $H$. This is possible since
both $R_{i}$ and $T$ are subsets of $N_{G}(S)$ and are already joined to $S$
in $H$. Next, we add all remaining edges between $S_{i}$ and $T$ to $H$. This
is possible since both $S_{i}$ and $T$ are already joined to $R_{i}$ in $H$.
Finally, we add all remaining edges between $x$ and $T$ to $H$. This is
possible since both $x$ and $T$ are already joined to $S_{i}\setminus\\{x\\}$
in $H$. Therefore, the claim is proved. Similarly, $y$ can be joined to all
vertices in $T$. Now, we may add the edge $xy$ to $H$, since $T\subseteq
N_{H}(x,y)$. The proof is completed. ∎

##  3 Exact stability

In this section, we examine the property
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$. We present a
sufficient condition on $\mathrm{wsat}(n,F)$ such that the latter equality
holds. The class of graphs satisfying the presented condition includes
complete graphs, complete bipartite graphs, graphs with minimum degree $1$,
and graphs with minimum degree $2$ which either are connected or have no cut
edge. First, we recall the following general lower bound on
$\mathrm{wsat}(n,F)$ which we will later extend it to
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$

######  Theorem 3.1 ([9]).

Let $F$ be a graph with $s$ vertices, $t$ edges, and minimum degree
$\delta\geqslant 1$. Then, for any $n\geqslant s$,

$\mathrm{wsat}(n,F)\geqslant t-1+\frac{(\delta-1)(n-s)}{2}.$

######  Theorem 3.2.

Let $G$ and $F$ be two given graphs with $|V(G)|\geqslant|V(F)|$ and
$\delta(F)\geqslant 1$. Then,

$\mathrm{wsat}(G,F)\geqslant\min\left\\{|E(G)|,|E(F)|-1+\frac{\min\big{\\{}\delta(G),\delta(F)-1\big{\\}}\big{(}|V(G)|-|V(F)|\big{)}}{2}\right\\}.$

###### Proof.

Let $H$ be a weakly $(G,F)$-saturated graph with minimum possible number of
edges. If $H=G$, then there is nothing to prove. So, assume that $H\neq G$.
When the first edge in $E(G)\setminus E(H)$ is added to $H$ a copy $F_{1}$ of
$F$ is created. Letting $H_{1}=H[V(F_{1})]$, we have
$|E(H_{1})|\geqslant|E(F)|-1$. Also, every vertex $v\in V(H)\setminus
V(H_{1})$ must have degree at least $\min\\{\delta(G),\delta(F)-1\\}$ in $H$.
To see this, if all edges in $G$ incident to $v$ appear in $H$, then
$d_{H}(v)=d_{G}(v)\geqslant\delta(G)$. Otherwise, when the first edge incident
to $v$ from $E(G)\setminus E(H)$ is added to $H$, the degree of $v$ in the
resulting graph must be at least $\delta(F)$, implying
$d_{H}(v)\geqslant\delta(F)-1$. Therefore,

$\displaystyle|E(H)|$ $\displaystyle\geqslant|E(H_{1})|+|E(H)\setminus
E(H_{1})|$
$\displaystyle\geqslant|E(F)|-1+\frac{\min\big{\\{}\delta(G),\delta(F)-1\big{\\}}\big{(}|V(G)|-|V(F)|\big{)}}{2}.\qed$

We know from [10, Theorem 3.4] that if $p\gg\tfrac{\log n}{n}$, then
$\delta(\mathbbmsl{G}(n,p))=np(1+o(1))$ with high probability. From this fact,
we obtain the following consequence.

######  Corollary 3.3.

Let $F$ be a graph with $s$ vertices, $t$ edges, and minimum degree
$\delta\geqslant 1$. If $p\gg\tfrac{\log n}{n}$, then

$\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}\geqslant
t-1+\frac{(\delta-1)(n-s)}{2},$

with high probability.

Now, we switch to an upper bound on $\mathrm{wsat}(n,F)$.

######  Theorem 3.4 ([9]).

Let $F$ be a graph with $s$ vertices and minimum degree $\delta\geqslant 1$.
Then, for every $n\geqslant m\geqslant s-1$,

$\displaystyle\mathrm{wsat}(n,F)\leqslant(\delta-1)(n-m)+\mathrm{wsat}(m,F).$
(2)

In particular, for every $n\geqslant s-1$,

$\displaystyle\mathrm{wsat}(n,F)\leqslant(\delta-1)n+\frac{(s-1)(s-2\delta)}{2}.$
(3)

The relation (2) in Theorem 3.4 was proved in [9] for
$m\in\\{|V(F)|-1,|V(F)|\\}$. Above, we have formulated a more general
statement which can be proved using a similar argument. The inequality (2) for
$m=|V(F)|-1$ results in an upper bound on $\mathrm{wsat}(n,F)$ which is given
in (3).

We will also need some knowledge about the presence of small subgraphs in a
random graph. First, we recall the following definition. For any graph $G$,
define

$m(G)=\max\left\\{\left.\frac{|E(H)|}{|V(H)|}\,\right|\,H\mbox{ is a subgraph
of }G\right\\}.$

To use later, we recall the following result which appears in [10] as Theorem
5.3.

######  Theorem 3.5 ([10]).

Let $G$ be a graph with $|E(G)|\geqslant 1$. Then, $n^{-1/m(G)}$ is a
threshold probability for the property that $\mathbbmsl{G}(n,p)$ has a copy of
$G$ as a subgraph.

The following lemma was proved in [5]. We apply it in the next theorem.

######  Lemma 3.6 ([5]).

Let $k\geqslant 2$ be a fixed integer and let $p\geqslant
n^{-\frac{1}{2k-1}}\log n$. Then, with high probability, $\mathbbmsl{G}(n,p)$
has the property that, for every $k$-subset $S$ of vertices, the induced
subgraph on $N_{G}(S)$ contains the $(k-1)$-th power of a Hamiltonian path.

The following theorem gives an upper bound on
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$ which is linear in terms of $n$. The
idea of proof comes from [5].

######  Theorem 3.7.

Let $F$ be a graph with $s$ vertices and minimum degree $\delta\geqslant 1$.
Also, let $m\geqslant s-1$ and $p\geqslant n^{-1/(2m+3)}\log n$. Then,

$\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}\leqslant(\delta-1)(n-m)+\mathrm{wsat}(m,F)$

with high probability. In particular, for $p\geqslant n^{-1/(2s+1)}\log n$,

$\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}\leqslant(\delta-1)n+\frac{(s-1)(s-2\delta)}{2}$

with high probability.

###### Proof.

As the assertion trivially holds for $F=K_{2}$, we assume that $s\geqslant 3$.
By Theorem 3.5, we may consider a clique $\mathnormal{\Omega}$ of size $m$ in
$G\thicksim\mathbbmsl{G}(n,p)$. We define a spanning subgraph $H$ of $G$ as
follows. Let $H_{0}$ be a weakly $(G[\mathnormal{\Omega}],F)$-saturated graph
with $\mathrm{wsat}(m,F)$ edges. The graph $H$ contains all edges of $H_{0}$
and moreover, for every $v\in N_{G}(\mathnormal{\Omega})$, we add $\delta-1$
arbitrary edges of $E_{G}(v,\mathnormal{\Omega})$ to $H$. Also, for every
$v\in V(G)\setminus N_{G}[\mathnormal{\Omega}]$, we add $\delta-1$ edges of
$E_{G}(v,N_{G}(v))$ to $H$ as described below. Using Lemma 3.6, the graph
$H_{v}=G[N_{G}(\\{v\\}\cup\mathnormal{\Omega})]$ contains the $(s-2)$-th power
of a Hamiltonian path. Starting from a beginning vertex, denote the vertices
of $H_{v}$ going in the natural order induced by the Hamiltonian path by
$x^{v}_{1},\ldots,x^{v}_{h_{v}}$, where $h_{v}=|V(H_{v})|$. We add the edges
$vx^{v}_{1},\ldots,vx^{v}_{\delta-1}$ to $H$ for any $v\in V(G)\setminus
N_{G}[\mathnormal{\Omega}]$. Since
$|E(H)|=(\delta-1)(n-m)+\mathrm{wsat}(m,F)$, it suffices to prove that $H$ is
a weakly $(G,F)$-saturated graph. To do this, we show that the edges in
$E(G)\setminus E(H)$ can be added to $H$ in some order through a weakly
$(G,F)$-saturated process.

As $H_{0}$ is weakly $(G[\mathnormal{\Omega}],F)$-saturated, we may add the
edges in $E(G[\mathnormal{\Omega}])\setminus E(H_{0})$ to $H$ in an
appropriate order. By doing this, $\mathnormal{\Omega}$ becomes a clique in
$H$. Let $u\in\mathnormal{\Omega}$ and $v\in N_{G}(\mathnormal{\Omega})$ such
that $uv\in E(G)\setminus E(H)$. Let $w\in V(F)$ such that
$d_{F}(w)=\delta(F)$. Since $\mathnormal{\Omega}$ is a clique in $H$, it
contains a copy $F_{0}$ of $F-w$ with $u\in V(F_{0})$ and so
$H[V(F_{0})\cup\\{v\\}]+uv$ is a copy of $F$. This shows that all edges in
$E_{G}(\mathnormal{\Omega},N_{G}(\mathnormal{\Omega}))\setminus E(H)$ may be
added to $H$ simultaneously. Now, all edges in $E(G)\setminus E(H)$ with both
endpoints in $N_{G}(\mathnormal{\Omega})$ can be added to $H$, since they
belong to a copy of $F$ containing a $(s-2)$-subset of $\mathnormal{\Omega}$.
Next, for every $v\in V(G)\setminus N_{G}[\mathnormal{\Omega}]$, we may add to
$H$ the edges $vx^{v}_{\delta},\ldots,vx^{v}_{h_{v}}$ one by one, since every
such edge belongs to a copy of $F$ containing the previous $s-2$ vertices of
the $(s-2)$-th power of the Hamiltonian path. Finally, for each edge $xy\in
E(G)\setminus E(H)$ with endpoints in $V(G)\setminus
N_{G}[\mathnormal{\Omega}]$, by Lemma 3.6,
$N_{G}(\\{x,y\\}\cup\mathnormal{\Omega})$ contains a clique
$\mathnormal{\Omega}_{xy}$ of size at least $s-2$ with
$\mathnormal{\Omega}_{xy}\subseteq N_{G}(\mathnormal{\Omega})$, so $xy$ can be
added to $H$ as well. ∎

The following consequence is obtained from Corollary 3.3 and Theorem 3.7.

######  Corollary 3.8.

Let $F$ be a graph with $s$ vertices and $\delta(F)\geqslant 1$ and let
$p\geqslant n^{-1/(2s+1)}\log n$. Then, $\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$
is bounded from above by a constant with high probability if and only if
$\delta(F)=1$.

We are now ready to prove the main result of this section. Recall Theorem 1.4.

See 1.4

###### Proof.

For simplicity, let $\delta=\delta(F)$. By Theorem 2.7, there exist a constant
$c_{F}$ and a function $\varphi=o(n)$ such that
$\mathrm{wsat}(n,F)=c_{F}n+\varphi(n)$ for all $n$. By the assumption and
Theorem 3.4, we have

$(\delta-1)n+D\leqslant\mathrm{wsat}(n,F)\leqslant(\delta-1)n+\frac{(s-1)(s-2\delta)}{2},$

where $s=|V(F)|$. Since $\varphi(n)=o(n)$, the inequality above implies that
$c_{F}=\delta-1$ and $\varphi(n)\geqslant D$ for any $n$. By Theorem 3.4, for
any $n\geqslant m\geqslant s-1$,

$\displaystyle(\delta-1)n+\varphi(n)$ $\displaystyle=\mathrm{wsat}(n,F)$
$\displaystyle\leqslant(\delta-1)(n-m)+\mathrm{wsat}(m,F)$
$\displaystyle=(\delta-1)(n-m)+\big{(}(\delta-1)m+\varphi(m)\big{)}$
$\displaystyle=(\delta-1)n+\varphi(m)$

and so $\varphi(n)\leqslant\varphi(m)$. This shows that $\varphi$ is
decreasing. As $\varphi$ is an integer valued function and bounded from below,
there exists a constant $d_{F}$ such that $\varphi(n)=d_{F}$ for any
sufficiently large $n$. Assume that $k$ is the smallest $n$ satisfying
$n\geqslant s-1$ and $\varphi(n)=d_{F}$.

Let $p\geqslant n^{-1/(2k+3)}\log n$. Corollary 2.4 yields that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\geqslant\mathrm{wsat}(n,F)$ with high
probability. Moreover, Theorem 3.7 implies that

$\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}\leqslant(\delta-1)(n-k)+\mathrm{wsat}(k,F),$

with high probability. Therefore,

$\displaystyle(\delta-1)n+d_{F}$ $\displaystyle=\mathrm{wsat}(n,F)$
$\displaystyle\leqslant\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}$
$\displaystyle\leqslant(\delta-1)(n-k)+\mathrm{wsat}(k,F)$
$\displaystyle=(\delta-1)(n-k)+\big{(}(\delta-1)k+d_{F}\big{)}$
$\displaystyle=(\delta-1)n+d_{F},$

and hence
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=(\delta-1)n+d_{F}=\mathrm{wsat}(n,F)$
with high probability, as required. ∎

The following result shows that some graphs with minimum degree $2$ satisfy
the assumption of Theorem 1.4.

######  Lemma 3.9.

Let $F$ be a graph with $\delta(F)=2$. If $F$ either is connected or has no
cut edge, then $\mathrm{wsat}(n,F)\geqslant n-1$ for any positive integer $n$.

###### Proof.

Let $H$ be a weakly $(K_{n},F)$-saturated graph with minimum possible number
of edges. If $H$ is connected, then $\mathrm{wsat}(n,F)=|E(H)|\geqslant n-1$,
as required. So, let $H$ be disconnected. Then, the first edge in
$E(K_{n})\setminus E(H)$ joining two connected components of $H$ in a weakly
$F$-saturated process is a cut edge of a copy of $F$. Hence, in order to prove
the assertion, we may assume that $F$ is a connected graph with a cut edge.

We prove that $\mathrm{wsat}(n,F)\geqslant n$ for any $n\geqslant 3$. To do
this, we show that none of the connected components of $H$ is a tree. By
contradiction, suppose that $H$ has a connected component $T$ that is a tree.
Assume that $uv\in E(K_{n})\setminus E(H)$ is the first edge in the order of
weakly $F$-saturated process which has an endpoint in $V(T)$. First, suppose
that $u\in V(T)$ and $v\notin V(T)$. Let $F^{\prime}$ be a copy of $F$ created
by adding $uv$ during the process. Since the induced subgraph of $F^{\prime}$
on $V(F^{\prime})\cap V(T)$ is a forest, either it is $K_{1}$ or it has at
least two vertices of degree at most $1$. This implies that
$\delta(F)\leqslant 1$, a contradiction. Next, suppose that $u,v\in V(T)$.
Since $T$ is a tree and $F$ is connected, $F$ has exactly one cycle. As
$\delta(F)=2$, $F$ must be a cycle graph, a contradiction. ∎

######  Remark 3.10.

We give an example of a graph $F$ with minimum degree $2$ such that
$\mathrm{wsat}(n,F)<n-1$. Let $F=K_{3}\cup D_{3}$, where $D_{3}$ is a graph
consisting of two vertex disjoint triangles which are joined by a single edge.
Letting $n\geqslant 15$ and $n\equiv 0\pmod{3}$, it is easy to check that
$D_{3}\cup\tfrac{n-6}{3}P_{3}$ is a weakly $F$-saturated graph which implies
that $\mathrm{wsat}(n,F)\leqslant\tfrac{2n}{3}+3$.

######  Remark 3.11.

It is worth mentioning that the assumption
$\mathrm{wsat}(n,F)\geqslant(\delta-1)n+D$ for a constant $D$, given in
Theorem 1.4, holds for several graph families. These include complete graphs
[16], complete bipartite graphs [15, Proposition 15], graphs with minimum
degree $1$ (Theorem 3.1), and graphs with minimum degree $2$ which either are
connected or have no cut edge (Lemma 3.9). So, Theorem 1.4 can be applied for
these graph families.

##  4 Small $\boldsymbol{p}$

For any graph $F$, if $p$ is small enough, then $\mathbbmsl{G}(n,p)$ has no
copy of $F$ as a subgraph with high probability. Hence, for such $p$, with
high probability, $\mathbbmsl{G}(n,p)$ is the unique weakly
$(\mathbbmsl{G}(n,p),F)$-saturated graph which means that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=e(\mathbbmsl{G}(n,p))$. In this section,
we derive a similar result for slightly bigger $p$.

For any graph $G$, define

$\mu(G)=\max\left\\{m(G),\frac{|E(G)|-1}{|V(G)|-2}\right\\}$

if $|V(G)|\neq 2$ and otherwise, define $\mu(G)$ to be equal to $m(G)$. Below,
we state a useful observation which can be proved straightforwardly.

######  Observation 4.1.

For every two graphs $G$ and $F$, let $X_{F}(G)$ denote the number of copies
of $F$ in $G$. Then,

$|E(G)|-X_{F}(G)\leqslant\mathrm{wsat}(G,F)\leqslant|E(G)|.$

######  Theorem 4.2.

Let $F$ be a graph with $\delta(F)\geqslant 1$. Then, for any $p\ll
n^{-1/\mu(F)}$,

$\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}=e\big{(}\mathbbmsl{G}(n,p)\big{)}\big{(}1+o(1)\big{)}$

with high probability.

###### Proof.

For simplicity, let $s=|V(F)|$, $t=|E(F)|$, $m=m(F)$, and $\mu=\mu(F)$. If
$\mathnormal{\Delta}(F)=1$, then $F=tK_{2}$ and thus $e(\mathbbmsl{G}(n,p))=0$
with high probability using Theorem 3.5, so there is nothing to prove. Hence,
we assume that $\mathnormal{\Delta}(F)\geqslant 2$ which gives
$m(F)\geqslant\tfrac{2}{3}$. Denote by $X_{F}$ the random variable that counts
the number of copies of $F$ in $\mathbbmsl{G}(n,p)$. Let $p\leqslant
n^{-1/\mu}\omega(n)$, where $\omega(n)\rightarrow 0$ when
$n\rightarrow\infty$. From 4.1,

$e\big{(}\mathbbmsl{G}(n,p)\big{)}-X_{F}\leqslant\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}\leqslant
e\big{(}\mathbbmsl{G}(n,p)\big{)}$

and therefore it is enough to show that $X_{F}=o(e(\mathbbmsl{G}(n,p)))$. If
$\mu\leqslant m$, then it follows from Theorem 3.5 that $X_{F}=0$, we are
done. If $p\leqslant n^{-7/4}$, then $p\ll n^{-3/2}\leqslant n^{-1/m}$ and
hence $X_{F}=0$ using Theorem 3.5, again we are done. So, we may assume that
$\mu=\tfrac{t-1}{s-2}$ and $p\geqslant n^{-7/4}$. Since $p\gg n^{-2}$, it
follows from [2, Theorem 4.4.4] that $e(\mathbbmsl{G}(n,p))=n^{2}p/2(1+o(1))$
with high probability. We know from [10, Lemma 5.1] that

$\mathbbmsl{E}(X_{F})=\frac{s!}{|Aut(F)|}\binom{n}{s}p^{t},$

where $Aut(F)$ is the automorphism group of $F$. Also, using the Markov bound
[10, Lemma 22.1],

$\mathbbmsl{P}\left[X_{F}\geqslant\frac{\mathbbmsl{E}(X_{F})}{\sqrt{\omega(n)}}\right]\leqslant\sqrt{\omega(n)}\longrightarrow
0$

which implies that $X_{F}\leqslant\mathbbmsl{E}(X_{F})/\sqrt{\omega(n)}$ with
high probability. Now, since $\mathbbmsl{E}(X_{F})\leqslant n^{s}p^{t}$,
$e(\mathbbmsl{G}(n,p))\geqslant n^{2}p/3$ with high probability, and
$\mu=\tfrac{t-1}{s-2}$, we obtain that with high probability

$\displaystyle X_{F}$
$\displaystyle\leqslant\frac{\mathbbmsl{E}(X_{F})}{\sqrt{\omega(n)}}$
$\displaystyle\leqslant\frac{n^{s}p^{t}}{\sqrt{\omega(n)}}$
$\displaystyle\leqslant\frac{3n^{s-2}p^{t-1}}{\sqrt{\omega(n)}}e\big{(}\mathbbmsl{G}(n,p)\big{)}$
$\displaystyle\leqslant\frac{3n^{s-2}}{\sqrt{\omega(n)}}\left(n^{-\frac{1}{\mu}}\omega(n)\right)^{t-1}e\big{(}\mathbbmsl{G}(n,p)\big{)}$
$\displaystyle\leqslant
3\big{(}\omega(n)\big{)}^{t-\frac{3}{2}}e\big{(}\mathbbmsl{G}(n,p)\big{)}$

which means that $X_{F}=o(e(\mathbbmsl{G}(n,p)))$ as $t\geqslant 2$. The proof
is complete. ∎

######  Corollary 4.3.

Let $F$ be a graph with $\mu(F)\geqslant 2$ and let
$p=\tfrac{2c_{F}+o(1)}{n}$, where $c_{F}$ is introduced in Theorem 2.7. Then,
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)(1+o(1))$ with high
probability.

###### Proof.

As $p\gg n^{-2}$, it follows from [2, Theorem 4.4.4], Theorem 2.7, and Theorem
4.2 that

$\displaystyle\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),F\big{)}$
$\displaystyle=e\big{(}\mathbbmsl{G}(n,p)\big{)}\big{(}1+o(1)\big{)}$
$\displaystyle=\frac{n^{2}p}{2}\big{(}1+o(1)\big{)}$
$\displaystyle=\big{(}c_{F}+o(1)\big{)}n$
$\displaystyle=\mathrm{wsat}(n,F)\big{(}1+o(1)\big{)}$

with high probability. ∎

######  Remark 4.4.

It has been proved in [5] that for any fixed integer $s\geqslant 3$, there
exists a positive constant $\lambda$ such that

$\displaystyle\mathrm{wsat}\big{(}\mathbbmsl{G}(n,p),K_{s}\big{)}\leqslant(s-2)n+\frac{\log^{\lambda}n}{p^{2s-3}}$
(4)

with high probability. Let $F$ be a graph on $s$ vertices with
$\delta(F)\geqslant 1$. Since
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\leqslant\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{s})$,
we find that the upper bound given in (4) also holds for
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$. Using this and our results in the
current paper, we deduce that the following holds for
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)$ with high probability.

  * •

If $p\ll n^{-1/\mu(F)}$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=e(\mathbbmsl{G}(n,p))(1+o(1))$.

  * •

If $n^{-1/\mu(F)}\leqslant p\leqslant n^{-1/(s-1)}$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\leqslant e(\mathbbmsl{G}(n,p))$.

  * •

If $n^{-1/(s-1)}\ll p\leqslant n^{-1/(2s+1)}$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\leqslant(s-2)n+p^{-(2s-3)}\log^{\lambda}n$.

  * •

If $p\geqslant n^{-1/(2s+1)}\log n$, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)\leqslant(\delta(F)-1)n+O(1)$.

  * •

If $p$ is constant, then
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)(1+o(1))$.

## References

  * [1] N. Alon, An extremal problem for sets with applications to graph theory, J. Combin. Theory Ser. A 40 (1985) 82–89.
  * [2] N. Alon, J.H. Spencer, The probabilistic method, Fourth edition, Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016.
  * [3] J. Balogh, B. Bollobás, R. Morris, Graph bootstrap percolation, Random Structures Algorithms 41 (2012) 413–440.
  * [4] Z. Bartha, B. Kolesnik, Weakly saturated random graphs, preprint, available at: http://arxiv.org/pdf/2007.14716.pdf.
  * [5] M. Bidgoli, A. Mohammadian, B. Tayfeh-Rezaie, M. Zhukovskii, Threshold for weak saturation stability, preprint, available at: http://arxiv.org/pdf/2006.06855.pdf.
  * [6] B. Bollobás, Weakly $k$-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner, Leipzig, 1968, pp. 25–31.
  * [7] M. Borowiecki, E. Sidorowicz, Weakly $\mathcal{P}$-saturated graphs, Discuss. Math. Graph Theory 22 (2002) 17–30.
  * [8] B.L. Currie, J.R. Faudree, R.J. Faudree, J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin. (2021) #DS19.
  * [9] R.J. Faudree, R.J. Gould, M.S. Jacobson, Weak saturation numbers for sparse graphs, Discuss. Math. Graph Theory 33 (2013) 677–693.
  * [10] A. Frieze, M. Karoński, Introduction to Random Graphs, Cambridge University Press, Cambridge, 2016.
  * [11] J. Kahn, B. Narayanan, J. Park, The threshold for the square of a Hamilton cycle, Proc. Amer. Math. Soc. 149 (2021) 3201–3208.
  * [12] G. Kalai, Hyperconnectivity of graphs, Graphs Combin. 1 (1985) 65–79.
  * [13] O. Kalinichenko, M. Zhukovskii, Weak saturation stability, preprint, available at: http://arxiv.org/pdf/2107.11138.pdf.
  * [14] D. Korándi, B. Sudakov, Saturation in random graphs, Random Structures Algorithms 51 (2017) 169–181.
  * [15] G. Kronenberg, T. Martins, N. Morrison, Weak saturation numbers of complete bipartite graphs in the clique, J. Combin. Theory Ser. A 178 (2021) 105357.
  * [16] L. Lovász, Flats in matroids and geometric graphs, in: Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), Academic Press, London, 1977, pp. 45–86.
  * [17] M. Miralaei, A. Mohammadian, B. Tayfeh-Rezaie, The weak saturation number of $K_{2,t}$, preprint, available at: http://arxiv.org/pdf/2211.10939.pdf.
  * [18] O. Riordan, Spanning subgraphs of random graphs, Combin. Probab. Comput. 9 (2000) 125–148.
  * [19] J. Spencer, Threshold functions for extension statements, J. Combin. Theory Ser. A 53 (1990) 286–305.