# Memory Sharing for Large Language Model based Agents

Hang Gao, Yongfeng Zhang
Department of Computer Science
Rutgers University
New Brunswick, NJ 08854, USA
{h.gao<EMAIL_ADDRESS>
###### Abstract

In the realm of artificial intelligence, the adaptation of Large Language
Model (LLM)-based agents to execute tasks via natural language prompts
represents a significant advancement, notably eliminating the need for
explicit retraining or fine tuning for fixed-answer tasks such as common sense
questions and yes/no queries. However, the application of In-context Learning
to open-ended challenges, such as poetry creation, reveals substantial
limitations due to the comprehensiveness of the provided examples and agent’s
ability to understand the content expressed in the problem, leading to outputs
that often diverge significantly from expected results. Addressing this gap,
our study introduces the Memory-Sharing (MS) framework for LLM multi-agents,
which utilizes a real-time memory storage and retrieval system to enhance the
In-context Learning process. Each ”memory” within this system captures both
the posed query and the corresponding real-time response from an LLM-based
agent, aggregating these memories from a broad spectrum of similar agents to
enrich the memory pool shared by all agents. This framework not only aids
agents in identifying the most relevant examples for specific tasks but also
evaluates the potential utility of their memories for future applications by
other agents. Empirical validation across three distinct domains involving
specialized functions of agents demonstrates that the MS framework
significantly improve the agent’s performance regrading the open-ended
questions. Furthermore, we also discuss what type of memory pool and what
retrieval strategy in MS can better help agents, offering a future develop
direction of MS. The code and data are available at:
https://github.com/GHupppp/MemorySharingLLM

##  1 Introduction

The emergence of Large Language Model (LLM) has precipitated a transformation
in the field of machine learning, primarily evidenced by the innovation of
model fine-tuning techniques. However, the advent of in-context learning and
prompt engineering heralds a more nuanced evolution, enabling dynamic and
intuitive interactions between the model and the user. This is achieved by
bypassing traditional necessities for parameter updates or explicit model
retraining when adapting to novel tasks. Such advancements underscore the
potential to substantially broaden the capabilities of LLM-based agents
through the strategic conditioning on task-specific prompts, wherein diverse
strategies are employed contingent upon the problem type at hand. Initially,
In-context learning was introduced to facilitate LLM-based agents in achieving
commendable performance with minimal examples (Brown et al., 2020), and
subsequently extended across various domains (Ahmed & Devanbu, 2022; Izacard
et al., 2022). Following this, the proposal of chain-of-thought prompting
significantly augmented the proficiency of LLM-based agents in executing
arithmetic tasks (Wei et al., 2022). Building upon this foundation, innovative
methodologies such as PAL (Gao et al., 2023) and the integration of LLMs with
symbolic solvers (He-Yueya et al., 2023) have been developed to further
enhance agent capabilities in tackling reasoning tasks. Recent works has also
developed agent which can continuously acquire diverse skills and make novel
discoveries (Wang et al., 2023a). Concurrently, the introduction of Retrieval-
Augmented Generation marked a substantial improvement in knowledge-intensive
tasks (Lewis et al., 2020), and subsequently facilitated more effective
generation in open-domain queries (Mao et al., 2020). In recent developments,
self-learning techniques have been integrated with the retrieval mechanism
within in-context learning to refine model performance in text generation
tasks, through the retrieval of examples with the most analogous patterns
(Rubin et al., 2021; Wang et al., 2023b). These innovations collectively
enhance the efficiency of interactions with LLM-based agents across a spectrum
of applications.

Figure 1: The Memory Sharing framework. Whenever a new (Prompt, Answer) pair
is generated, it will be considered to be added to the memory pool and to
train the retriever.

Notwithstanding the proficiency of in-context learning in enhancing model
performance for complex tasks through the meticulous construction of prompts
that furnish explicit instructions and contextual clarity, its applicability
remains diminished in scenarios involving open-ended queries such as poetry
generation or lateral thinking puzzles. The capacity of LLM-based agents to
navigate and resolve such queries will align these entities more closely with
human cognitive processes and bolster their potential to create genuine
novelty by adopting a more flexible and holistic approach to problem-solving.
However, answers to open-ended queries require a comprehensive reference and
better understanding of various knowledge, which is an aspect that current
agents lack. This limitation is further exacerbated when the content of those
knowledge base, often unidimensional and static, is not regularly updated,
thereby compounding the difficulty in addressing open-ended queries with
evolving reference requirements. To address these issues, we introduce the
Memory Sharing (MS) framework among agents, a novel framework specifically
designed to surmount the hurdles associated with ensuring comprehensive
example coverage and enhancing the dynamism of the knowledge base within the
context of in-context learning.

Within the MS framework, the interaction between an agent’s input and its
subsequent output is conceptualized as an “Prompt-Answer” (PA) pair,
collectively forming the agent’s memory pool. This framework introduces an
innovative real-time memory storage and retrieval mechanism, designed to
augment the agent’s memory pool by assimilating PA pairs from a multifaceted
ensemble of agents. During the storage phase, each PA pair is subjected to a
rigorous evaluation by a dedicated LLM scorer, which assesses its
appropriateness for inclusion within the memory pool, thereby potentially
serving as a referential asset in subsequent engagements. This procedure
ensures the memory pool’s capability for dynamic expansion. The retrieval
phase is orchestrated by an autonomous learning retrieval system, calibrated
to ensure the incorporation of exceptionally pertinent memories into prompts,
thereby enhancing the agents’ comprehension of the query’s essence. Fig.1
shows the framework of the MS. It is posited that the incorporation of self-
generated memories into prompts significantly elevates agents’ understanding
of the intended query meaning. Furthermore, the continuous incorporation of
new memories into the pool not only enriches the memory pool but also
perpetually refines the retriever, augmenting its efficiency in selecting
relevant memories. By treating each interaction as a cohesive PA pair, this
framework guarantees that every query posed and response generated is
considered in an integrated manner. Our empirical evidence suggests that this
methodology substantially assists LLM-based agents in generating outputs that
are more aligned with user expectations.

We evaluate the MS framework through three divergent domains where each domain
involved the participation of three agents, each with a specialized task under
their domain. Our finding suggests that incremental additions to the memory
pool have led to enhancements in the precision and relevance of outputs. This
research delineates the MS framework’s capacity to mitigate the inherent
constraints associated with in-context learning, thereby underscoring its
potential applicability and effectiveness.

In the following, Section 2 delineates relevant works. An exhaustive
elucidation of the MS framework, inclusive of its conceptual underpinnings and
operational methodologies, is presented in Section 3. Section 4 provides
empirical validation of the framework’s enhanced capability to address open-
ended queries. The conclusion, presented in the Section 5, not only summarizes
the findings but also explores prospective avenues for future development of
the MS framework, which may better help improve the LLM-based agents.

##  2 Related Work

###  2.1 In-context learning

In-context learning capitalizes on the capacity of Large Language Model to
address tasks by incorporating a minimal number of examples into the prompt,
occasionally rivaling or even surpassing the effectiveness of previous state-
of-the-art fine-tuning methods (Brown et al., 2020). Following this paradigm,
there has been a growing emphasis on the meticulous construction of prompts to
furnish the model with explicit instructions and contextual clarity, thereby
augmenting its proficiency in executing complex tasks (Levine et al., 2021;
Zhou et al., 2022; Liu et al., 2023; White et al., 2023). Subsequent research
has explored the realm of question answering, revealing that crowd-sourced
instructions can notably enhance an agent’s performance in this domain (Mishra
et al., 2021). Moreover, In-context learning has been demonstrated to
facilitate a measure of creative learning within agents (Swanson et al.,
2021). Advancements have also been made through the strategic redesign of
inputs, rendering LLMs increasingly adept at navigating logical dilemmas,
particularly when dealing with interrelated questions and answers (Wiegreffe
et al., 2021; Wu et al., 2022). Elucidating the nexus between examples and
tasks has been shown to significantly benefit LLMs (Lampinen et al., 2022).
Further progress in this domain is attributed to the introduction of
sophisticated methodologies such as chain-of-thought (CoT) prompting (Wei et
al., 2022) and its derivatives, like PAL (Gao et al., 2023), which incorporate
intermediate reasoning steps to bolster performance on complex reasoning
tasks. Nonetheless, in solving the open-ended queries, agent still encounters
two primary hurdles: the insufficiency of problem descriptions, which
undermines agents’ comprehension; and the constraints imposed by the scope of
reference material available in external knowledge base, which, despite their
extensive nature, present a limited range of consultable resources. Our Memory
Sharing (MS) framework has been empirically validated to bolster agents’
proficiency in these respects, thereby enhancing their performance on open-
ended queries.

###  2.2 Retrieval-Augmented Generation

Aiming to solve the Knowledge-Intensive NLP Tasks, Retrieval-Augmented
Generation was proposed, which enhancing LLMs’ capacity for generating
accurate and timely content with methodologies for source attribution through
direct input integration, attention blending, and output interpolation(Lewis
et al., 2020; Ram et al., 2023; Shi et al., 2023). Innovations such as
employing the classical retrieval method BM25 (Luo et al., 2023; Liu et al.,
2022) or SBERT (Reimers & Gurevych, 2019), the most similar utterances with
the query are selected. This approach is further complemented by Dense
Retrieval, leveraging feedback-driven dense retrievers for effective example
retrieval through contrastive learning represent significant strides towards
maximizing the efficacy of In-context learning (Rubin et al., 2021). Based on
this, by repeating the contrastive learning process during the traning of the
retriever, retriever’s performance is further promoted (Wang et al., 2023b).
However, for those retrievers, they all trained once before putting the
retriever into use, so that retriever doesn’t get constant updated and fail to
get the most relevant examples for some new queries. The retriever in the MS
framework has always been get continuous training, once a new memory is added.
This keeps retriever in a process of constant updating and evolution, and the
memory retrieved by the retriever is gradually becoming more and more
relevant.

##  3 The Memory Sharing framework

The Memory Sharing (MS) framework encompasses an suite of functionalities
specifically designed for the memory storage and retrieval. Section 3.1
details the description of the meaning and origin of the memory, and most
importantly, the memory writing mechanism. This process incorporates a
distinctive grading mechanism, enabling the MS to filter out the memory that
not only bear relevance to the topical focus of the current agent but also
possess a universal applicability, thereby facilitating their reference across
agents within the same domain. Section 3.2 illustrates the retrieval mechanism
in detail. This operation is instrumental in pinpointing those memories most
apt for integration into novel prompts tailored to the immediate query, whilst
concurrently leveraging the most recent, high-caliber new memory to refine
model training. A toy example, showing the memory storage and retrieval, is
depicted in Fig.2.

###  3.1 Memory Store

Figure 2: An example of how the Agent (Sonnet) cooperates with the MS
framework. (1) + (2) The retriever take the original query from agent as the
input, retrieve the suitable memories from the memory pool and concatenate
them to the query to form the prompt. (3) The Agent (Sonnet) takes the prompt
and makes an answer, pack them as (Prompt, Answer). (4) Scorer generates a
score according to the designed rubric for (Prompt, Answer), while (Prompt,
Answer) pairs with high scores will be added into the Memory Pool and also be
sent to train the Retriever. All agents share the same Memory Pool; they can
write memories into the pool and retrieve memories from the pool so that they
can share memories with each other.

####  3.1.1 Memory Generation

Each memory is conceptualized as a (Prompt, Answer) pair. Upon the posing of a
query to the agents, the retriever—predicated on the employed strategic (e.g.,
three-shot learning)—determines the quantity of memory to be sourced from the
memory pool. Those memories in conjunction with the original query, are
integrated to form an enhanced prompt. This composite prompt is then
interfaced with the agent to elicit a corresponding answer. Subsequently, this
enhanced prompt and the resultant answer constitute a memory candidate for
potential inclusion in the memory pool, diverging from the conventional
pairing of merely the original query and its output to form a pair. This model
adheres to a real-time memory integration framework, wherein the most recent
prompt and answer of the agent are perpetually considered for being added into
the memory pool and training the retrieval model. The content stored within
the memory, generated by LLM-based agents, encompasses both answers produced
by the agents themselves and prompts that incorporate information previously
furnished by other agents. Consequently, aside from the initial query, the
aggregated memory emanating exclusively from agent contributions serves to
enhance the current agent’s comprehension of the comprehensive prompt.
Additionally, the memory’s origins—stemming from agents aligned with a uniform
overarching objective yet engaged in distinct specialized tasks—facilitate a
multifaceted learning experience. This approach enables the agent to garner
insights across various dimensions of open-ended queries. Furthermore, the
dynamic expansion of the memory pool ensures a continuous influx of novel
information, thereby enriching the agent’s knowledge base. Such a pool proves
instrumental in addressing open-ended queries, as it equips the agent with a
broadened perspective and a deeper understanding, pivotal for generating well-
informed responses.

####  3.1.2 Memory Writing

Each emergent candidate memory is subject to a systematic evaluative procedure
via scoring. Prior to this assessment phase, distinct grading rubrics are
established for each domain, with the responsibility of grading delegated to
the LLM itself. To facilitate the LLM’s comprehension of these rubrics, those
rubrics are autonomously generated by the LLM, under the presumption that it
will more adeptly grasp concepts of its own devising. Consequently, the
establishment of these rubrics precedes the operational deployment of the
entire framework to preclude the variability inherent in LLM-generated
evaluations, which could lead to discrepancies and potentially compromise the
fairness of memory assessments. Thus, all memories produced by the agent
within a given domain are evaluated against this uniform set of criteria,
ensuring consistency across the evaluation process. Prior to their official
implementation, these rubrics undergo a manual review phase. This review not
only assesses the relevance of potential memories to the agent’s current focal
task but also evaluates their pertinence to other agents within the domain to
ascertain their prospective utility. The rationale for not delegating the
evaluation of this component to Large Language Models lies in the enhanced
precision that manual screening provides, thereby refining the existing rubric
to more accurately align with the unique requirements of agents, particularly
concerning potential usage environments. Large Language Models, by their
nature, may not comprehensively account for these nuanced demands
simultaneously. Upon finalizing the appropriate rubric, it is integrated with
newly generated memories for evaluation by the LLM-based scorer. Memories that
surpass a predefined threshold, also determined by the LLM, are incorporated
into the memory pool.

###  3.2 Memory Retrieval

Prior to the operational deployment of the MS, a curated small subset of
instances was manually archived within the memory pool. These instances
fulfill a dual purpose: firstly, they provide a diversified array of memories
upon which each agent may experiment with novel prompts in the face of new
queries; secondly, they constitute the preliminary training corpus for our
retriever. This foundational training regimen mirrors the methodology by which
subsequently archived memories will be assimilated into our model in real
time, thereby facilitating the model’s ongoing adaptive learning and
optimization.

####  3.2.1 Memory Train

Whenever there is a new memory $(X,Y)$ going to be added into the pool, it
will also be used to train our retriever, which help the retriever to
continuously update itself and continuously adapt to new memory. Based on the
new generated memory $(X,Y)$, the classical method BM25 ascertain the most
pertinent top-$n$ candidate pairs $\\{(x_{i},y_{i})\\}_{i=1}^{n}$, sourced
from the diverse and extensive memory pool, labeled as $C$. Each candidate
within $C$ will undergo a evaluation process utilizing the comprehensive
scoring capabilities of LLMs.The scoring mechanism employed is defined by the
following equation:

$p(x_{i},y_{i})=\text{P}(\neg Y\mid(x_{i},y_{i}),\,X),\quad
i\in\\{1,2,\ldots,n\\}$ (1)

This equation seeks to determine, given a input-output pair $(x_{i},y_{i})$ in
$C$ as a condition, the probability that the response generated for the input
in the new memory contradicts the output in the new memory. This grading part
serves as a preparatory step for the subsequent labeling of each candidate
example. It is noteworthy that making $\neg Y$ as the result part is trying to
make sure that the memory that the retriever gets from other agents is of
reference value, but it does not have to be the most relevant to the current
question, which means that it can help the current agent to learn from new
examples. This approach diverges from a simplistic reliance on $Y$ as the
outcome, which tends to restrict the retrieval process to memory previously
stored by the current agent.

Within the defined set $C=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, each candidate now
is ascribed a score. We sort them from the lowest to the highest score and we
select $v$ memory in total to label. The top $\frac{v}{2}$ candidates (lowest
score) in $C$ are identified as being the pair with the reference value to
$(X,Y)$ and accordingly, their labels are set to positive. Conversely, the
bottom $\frac{v}{2}$ candidates are deemed as the least reference value to
$(X,Y)$, and their labels are thus designated as negative. These $v$ memories
are subjected to further differentiation and categorization to elucidate their
relevance and applicability to the context in query. This methodical approach
ensures a systematic and nuanced analysis of the data, facilitating the
identification and labeling of the pertinent memories for subsequent
utilization. Those labeled data will be used to minimize the following
function:

$\text{loss}(x,y)=-\frac{1}{v}\sum_{i=1}^{v}\left[y_{i}\cdot\log\left(\frac{1}{1+e^{-x_{i}}}\right)+(1-y_{i})\cdot\log\left(1-\frac{1}{1+e^{-x_{i}}}\right)\right]$
(2)

It enhances the predictive accuracy, which is especially critical in handling
imbalanced memory pool. This strategic choice underscores our model’s
preparedness to extract meaningful insights from various memory, advancing our
overarching goal of developing a robust and adaptable MS mechanism.

####  3.2.2 Prompt Construction from Memory

After encoding the original query and the memory in the pool, we employ cosine
similarity to navigate through those memories. The selection criterion for the
top-ranking memories is contingent upon the adopted retrieval strategy, which
may vary from one-shot to multi-shot learning. Subsequent to the
identification and selection of the most relevant memories, these are
sequentially concatenated as in-context examples in the prompt, culminating
with the integration of the initial query at the sequence’s end. This
concatenated sequence thus forms a new prompt, which is subsequently furnished
to the agent for processing. This structured procedure not only streamlines
the retrieval of relevant information from the memory pool but also
facilitates the generation of a contextually enriched prompt, poised to elicit
a more informed response from the agent. The integration process employs
memories specifically curated to elucidate the query at hand, with each memory
being generated by agents operating within the same domain. This approach
enables the current agents to process the query through a multifaceted lens,
significantly enhancing their understanding. Furthermore, it fosters a
scenario wherein agents, inspired by their intrinsic reasoning regarding the
open-ended query, achieve a deeper comprehension of its underlying
significance. This methodology not only broadens the scope of query
interpretation but also enriches the agents’ response quality by leveraging
domain-specific insights.

##  4 Experiments

Our experiments are based on GPT-3.5-Turbo (Brown et al., 2020). For the
evaluation Metric, we use BERTScore (Zhang* et al., 2020), ROGUE-2 (Lin, 2004)
and ROGUE-L (Lin, 2004) to help us evaluate the usage of memory in improving
agent performance regarding the mean relevance and the structure relevance of
the answers.

| Zero | One | Two | Three
---|---|---|---|---
Agent | Rogue-2 | Rogue-L | BERT | Rogue-2 | Rogue-L | BERT | Rogue-2 | Rogue-L | BERT | Rogue-2 | Rogue-L | BERT
Limerick | 0.06 | 0.15 | 0.50 | 0.25 | 0.37 | 0.69 | 0.44 | 0.52 | 0.76 | 0.75 | 0.77 | 0.87
Wuyanlvshi | 0 | 0 | 0.66 | 0 | 0 | 0.72 | 0 | 0 | 0.71 | 0 | 0 | 0.72
Sonnet | 0.02 | 0.14 | 0.48 | 0.02 | 0.13 | 0.53 | 0.1 | 0.15 | 0.53 | 0.1 | 0.15 | 0.53
Lateral-think | 0.07 | 0.19 | 0.53 | 0.09 | 0.21 | 0.51 | 0.09 | 0.25 | 0.56 | 0.09 | 0.26 | 0.59
Pun | 0.27 | 0.43 | 0.61 | 0.20 | 0.35 | 0.64 | 0.30 | 0.43 | 0.67 | 0.24 | 0.37 | 0.70
Riddle | 0.71 | 0.80 | 0.86 | 0.32 | 0.48 | 0.64 | 0.44 | 0.56 | 0.70 | 0.62 | 0.75 | 0.88
Fitness | 0.02 | 0.06 | 0.46 | 0.04 | 0.15 | 0.61 | 0.06 | 0.18 | 0.64 | 0.07 | 0.19 | 0.65
Study | 0.008 | 0.04 | 0.44 | 0.01 | 0.15 | 0.65 | 0.01 | 0.17 | 0.60 | 0.02 | 0.14 | 0.63
Travel | 0.03 | 0.06 | 0.45 | 0.02 | 0.12 | 0.55 | 0.14 | 0.28 | 0.71 | 0.12 | 0.18 | 0.71

Table 1: Performance across agents utilizing different amounts memory for
open-ended queries execution. Each domain has its own Domain-pool shared
within its three agents. The highest score within each agent of each metric is
indicated by boldface.

| Metric | Limerick | Wuyanlvshi | Sonnet | Lateral-think | Pun | Riddle | Fitness | Study | Travel
---|---|---|---|---|---|---|---|---|---|---
| Rogue-2 | 0.75 | 0.00 | 0.10 | 0.09 | 0.24 | 0.62 | 0.07 | 0.02 | 0.12
_Domain-pool_ | Rogue-L | 0.77 | 0.00 | 0.15 | 0.26 | 0.37 | 0.75 | 0.19 | 0.14 | 0.18
| BERT | 0.87 | 0.72 | 0.53 | 0.59 | 0.70 | 0.88 | 0.65 | 0.63 | 0.71
| Rouge-2 | 0.05$\downarrow$ | 0.00 | 0.01$\downarrow$ | 0.06$\downarrow$ | 0.26 | 0.60$\downarrow$ | 0.02$\downarrow$ | 0.005$\downarrow$ | 0.02$\downarrow$
_Single-pool_ | Rogue-L | 0.12$\downarrow$ | 0.00 | 0.10$\downarrow$ | 0.19$\downarrow$ | 0.43 | 0.71$\downarrow$ | 0.11$\downarrow$ | 0.07$\downarrow$ | 0.10$\downarrow$
| BERT | 0.60$\downarrow$ | 0.68$\downarrow$ | 0.49$\downarrow$ | 0.54$\downarrow$ | 0.70 | 0.80$\downarrow$ | 0.62$\downarrow$ | 0.63$\downarrow$ | 0.58$\downarrow$

Table 2: Agent performance with Domain-pool vs. Single-pool by utilizing three
suitable memories for open-ended queries.

###  4.1 Experiment Details

We aim to assess the efficacy of the MS framework in processing open-ended
queries across three principal domains: Literary Creation, Unconventional
Logic Problem-solving, and Plan Generation. Within the Literary Creation
domain, we have appointed three specialized agents responsible for generating
Wuyanlvshi (a form of classical Chinese poetry, Chinese form), Limericks, and
Sonnets, respectively. In the Logic Problem-solving domain, dedicated agents
are tasked with addressing Lateral Puzzles, Riddles, and Puns. Meanwhile, for
Plan Generation, we have developed agents to create Study Plans, Travel Plans,
and Fitness Plans. For each agent, a consistent, small subset of pre-provided,
complete instances was selected and incorporated into the memory pool for the
initial phase of retriever training and prompt refinement. Subsequently, for
each agent, an identical number of queries will be introduced to increment the
volume of real-time memory within the pool.

The evaluation of memory impact commenced with the implementation of divergent
retrieval strategies, encompassing zero-shot, one-shot, two-shot, and three-
shot learning modalities. Subsequent to this preliminary phase, the
investigation bifurcated into an assessment of both quantitative analysis and
qualitative analysis. Regarding the qualitative dimensions, the study
delineated two distinct types of memory pools, Domain-pool and Single-pool.
The Domain-pool means a dedicated memory pool is allocated for each domain and
is shared for all agents with this domain, aiming at enhancing the integration
of domain-specific memories. Conversely, the second pool integrates agents
from all domains into a unified memory pool, facilitating an overarching
analysis of cross-domain memory utilization. On the quantitative front, the
experiment was segmented into five discrete phases, with each phase
characterized by the addition of a predetermined quantum of new memories to
the existing memory pool. At the juncture of each phase, an evaluation of
agent performance was conducted to ascertain improvements or regressions. This
dual-faceted approach enabled a thorough exploration of the nuanced impacts
and applicability of authentic memories across diverse domains, thereby
fostering a comprehensive understanding of their differential effects.

###  4.2 Experiment Analysis

The principal outcomes of our experiments are presented in Table.1, which
delineates the performance of each agent under various learning strategies
within the Memory Sharing (MS) framework. Different strategies will help agent
retrieve different numbers of memory to combine. With the increasing of the
memory be used, the performance of most agents is getting better and better,
which means that under the same domain, different types of memory will help
the agent better understand the problem and generate more relevant answers,
rather than interfering with the agent’s learning ability. Specifically,
within the Literal Creation domain and Plan Generation domain, all agents
exhibited enhanced performance after utilizing the memory from other agents,
as evidenced by both ROUGE and BERTScore metrics. This enhancement suggests
that the shared memory enables agents to better comprehend description of the
literary work and produce more pertinent responses. However, for Wuyanlvshi,
the performance didn’t change a lot, which may resulted in the language used
is different when storing memory. Unifying the language used, which may help
improve the performance of MS in the future. Moreover, in the unconventional
Logic Problem-solving domain, while the ROUGE scores remained relatively lower
compared to non-utilization of memory, a improvement in BERTScore indicates a
successful assimilation of diverse knowledge from the memory, leading to
increasingly nuanced and semantically aligned outputs. Conclusively, the MS
framework has facilitated continual performance improvement across agents
through memory sharing, underscoring its potential utility.

Figure 3: Evaluating agent performance on open-ended queries using three
suitable memories and Domain-pool with periodic updates.

Table.2 compares the scenario where all agents use the Domain-pool or Single-
pool under a three-shot learning strategy, since the prior experiments showed
us that most agents achieve the best performance under the three-shot
learning. Excluding Agent-Pun, all other agents exhibited diminished
performance with the Single-pool. The data elucidate a general decrement in
performance relative to scenarios where agents within identical domains
utilize distinct, domain-specific memory pools. This outcome implies that
agents sharing analogous characteristics derive maximal advantage from the
exclusivity of a domain-specific memory pool, as the incorporation of cross-
domain memories may detrimentally impact the learning efficiency of agents.

Furthermore, within the query where three-shot learning is applied and each
agent use the Domain-pool, Figure.3 delineates the variations in performance
across individual agents consequent to the integration of different ratios of
newly generated memories into the pool. Specifically, for the agent-Travel,
there is a consistent enhancement in performance. Conversely, for the majority
of agents, an initial improvement in performance was observed as the volume of
memories within the pool expanded, followed by a subsequent decline. This
pattern suggests that, irrespective of the homogeneity of memory types, an
excessive accumulation of memories may ultimately impede the agent’s learning
efficacy and output quality. Therefore, determining the optimal capacity of a
memory pool for a specific domain emerges as a pertinent inquiry for future
research. Regarding the fluctuations in performance observed for the agent-
Wuyanlvshi, these are tentatively ascribed to language different.

##  5 Conclusions

We introduce a novel framework Memory Sharing, which processes real-time
memory via memory store and retrieval. The findings suggest that augmenting
the volume of high-quality memory enhances the ability of LLM-based agents to
comprehend the nuances of questions and generate more pertinent responses
regarding the open-ended queries. And the production of each high-caliber
memory contributes not only to the augmentation of our memory reservoir but
also to the recurrent training of the Retriever. This systematic process
guarantees that, as the memory pool keep expansion dynamically, the Retriever
maintains the capability to consistently identify and select the most
pertinent memory for utilization by the agent. Regarding future research
directions, it is posited that the efficacy of the Memory Sharing (MS)
framework could be enhanced through the development of methodologies for
determining the optimal size of the memory pool. Presently, the usage of MS
for all agents under the same LLM model is observed. It merits a comprehensive
evaluation of the impact of deploying identical agents within a variety of
foundational models (e.g., GPT-4, LLaMA-2, Claude-2). Such an approach would
capitalize on leveraging memories acquired from diverse Large Language Models
(LLMs). Furthermore, the potential integration of this framework within fine-
tuning processes presents another avenue for exploration. These investigations
into the MS represent a progressive step towards harnessing real-time memory
to augment the capabilities of LLM-based agents, offering substantial
prospects for future research and practical applications within the domain of
artificial intelligence.

## References

  * Ahmed & Devanbu (2022) Toufique Ahmed and Premkumar Devanbu.  Few-shot training llms for project-specific code-summarization.  In _Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering_ , pp. 1–5, 2022.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Gao et al. (2023) Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig.  Pal: Program-aided language models.  In _International Conference on Machine Learning_ , pp. 10764–10799. PMLR, 2023.
  * He-Yueya et al. (2023) Joy He-Yueya, Gabriel Poesia, Rose E Wang, and Noah D Goodman.  Solving math word problems by combining language models with symbolic solvers.  _arXiv preprint arXiv:2304.09102_ , 2023.
  * Izacard et al. (2022) Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave.  Atlas: Few-shot learning with retrieval augmented language models.  _arXiv preprint arXiv:2208.03299_ , 2022.
  * Lampinen et al. (2022) Andrew K Lampinen, Ishita Dasgupta, Stephanie CY Chan, Kory Matthewson, Michael Henry Tessler, Antonia Creswell, James L McClelland, Jane X Wang, and Felix Hill.  Can language models learn from explanations in context?  _arXiv preprint arXiv:2204.02329_ , 2022.
  * Levine et al. (2021) Yoav Levine, Noam Wies, Daniel Jannai, Dan Navon, Yedid Hoshen, and Amnon Shashua.  The inductive bias of in-context learning: Rethinking pretraining example design.  _arXiv preprint arXiv:2110.04541_ , 2021.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474, 2020.
  * Lin (2004) Chin-Yew Lin.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pp. 74–81, Barcelona, Spain, July 2004. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/W04-1013.
  * Liu et al. (2022) Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen.  What makes good in-context examples for GPT-3?  In Eneko Agirre, Marianna Apidianaki, and Ivan Vulić (eds.), _Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures_ , pp. 100–114, Dublin, Ireland and Online, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.deelio-1.10.  URL https://aclanthology.org/2022.deelio-1.10.
  * Liu et al. (2023) Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  _ACM Computing Surveys_ , 55(9):1–35, 2023.
  * Luo et al. (2023) Man Luo, Xin Xu, Zhuyun Dai, Panupong Pasupat, Mehran Kazemi, Chitta Baral, Vaiva Imbrasaite, and Vincent Y Zhao.  Dr. icl: Demonstration-retrieved in-context learning.  _arXiv preprint arXiv:2305.14128_ , 2023.
  * Mao et al. (2020) Yuning Mao, Pengcheng He, Xiaodong Liu, Yelong Shen, Jianfeng Gao, Jiawei Han, and Weizhu Chen.  Generation-augmented retrieval for open-domain question answering.  _arXiv preprint arXiv:2009.08553_ , 2020.
  * Mishra et al. (2021) Swaroop Mishra, Daniel Khashabi, Chitta Baral, and Hannaneh Hajishirzi.  Cross-task generalization via natural language crowdsourcing instructions.  _arXiv preprint arXiv:2104.08773_ , 2021.
  * Ram et al. (2023) Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin Leyton-Brown, and Yoav Shoham.  In-context retrieval-augmented language models.  _Transactions of the Association for Computational Linguistics_ , 11:1316–1331, 2023.
  * Reimers & Gurevych (2019) Nils Reimers and Iryna Gurevych.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _arXiv preprint arXiv:1908.10084_ , 2019.
  * Rubin et al. (2021) Ohad Rubin, Jonathan Herzig, and Jonathan Berant.  Learning to retrieve prompts for in-context learning.  _arXiv preprint arXiv:2112.08633_ , 2021.
  * Shi et al. (2023) Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Rich James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih.  Replug: Retrieval-augmented black-box language models.  _arXiv preprint arXiv:2301.12652_ , 2023.
  * Swanson et al. (2021) Ben Swanson, Kory Mathewson, Ben Pietrzak, Sherol Chen, and Monica Dinalescu.  Story centaur: Large language model few shot learning as a creative writing tool.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: System Demonstrations_ , pp. 244–256, 2021.
  * Wang et al. (2023a) Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar.  Voyager: An open-ended embodied agent with large language models.  _arXiv preprint arXiv:2305.16291_ , 2023a.
  * Wang et al. (2023b) Liang Wang, Nan Yang, and Furu Wei.  Learning to retrieve in-context examples for large language models.  _arXiv preprint arXiv:2307.07164_ , 2023b.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837, 2022.
  * White et al. (2023) Jules White, Quchen Fu, Sam Hays, Michael Sandborn, Carlos Olea, Henry Gilbert, Ashraf Elnashar, Jesse Spencer-Smith, and Douglas C Schmidt.  A prompt pattern catalog to enhance prompt engineering with chatgpt.  _arXiv preprint arXiv:2302.11382_ , 2023.
  * Wiegreffe et al. (2021) Sarah Wiegreffe, Jack Hessel, Swabha Swayamdipta, Mark Riedl, and Yejin Choi.  Reframing human-ai collaboration for generating free-text explanations.  _arXiv preprint arXiv:2112.08674_ , 2021.
  * Wu et al. (2022) Tongshuang Wu, Michael Terry, and Carrie Jun Cai.  Ai chains: Transparent and controllable human-ai interaction by chaining large language model prompts.  In _Proceedings of the 2022 CHI conference on human factors in computing systems_ , pp. 1–22, 2022.
  * Zhang* et al. (2020) Tianyi Zhang*, Varsha Kishore*, Felix Wu*, Kilian Q. Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=SkeHuCVFDr.
  * Zhou et al. (2022) Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba.  Large language models are human-level prompt engineers.  _arXiv preprint arXiv:2211.01910_ , 2022.

##  Appendix A Appendix

###  A.1 Rubrics for scoring

Figure 4: When the Single-Pool is used, the rubrics shared within all the
agents Figure 5: The rubrics for agents in Literal Creation Figure 6: The
rubrics for agents in Unconventional Logic Problem Solving  Figure 7: The
rubrics for agents in Plan generation.

###  A.2 Prompt and Answer

Figure 8: Agent get the query and create a sonnet with using the memory

###  A.3 Dataset

Within the realm of each domain, examples were systematically harvested from
the internet and subsequently utilized as responses to each query posed. In
particular, the selection of Wuyanlvshi—renowned and historically significant
poems within Chinese literature—was meticulously chosen for their fame and
widespread recognition. Furthermore, the sonnets incorporated into our study
originate from the ”quarto” collection authored by Shakespeare in 1609.
Regarding the formulation of questions corresponding to each answer, this task
was entrusted to ChatGPT. The process entailed providing the model with the
selected answers, following which it was instructed to generate relevant
questions. Figure.9 presents an illustrative example detailing the question
generation process based on the provided answers.

Figure 9: Example for make the question of those given answer


# Graph Clustering via Generalized Colorings

András London  Department of Computer Science, University of Szeged and
Department of Operations Research, Poznaǹ University of Economics
<EMAIL_ADDRESS>,  Ryan R. Martin  Department of Mathematics, Iowa
State University<EMAIL_ADDRESS>and  András Pluhár  Department of
Computer Science, University of Szeged<EMAIL_ADDRESS>
###### Abstract.

We propose a new approach for defining and searching clusters in graphs that
represent real technological or transaction networks. In contrast to the
standard way of finding dense parts of a graph, we concentrate on the
structure of edges between the clusters, as it is motivated by some earlier
observations, e.g. in the structure of networks in ecology and economics and
by applications of discrete tomography. Mathematically special colorings and
chromatic numbers of graphs are studied.

###### Key words and phrases:

graph clustering, coloring, special graphs

###### 2020 Mathematics Subject Classification:

05C15, 68Q17, 05C35, 05C80

The first author’s research is partially supported by the National Research,
Development and Innovation Office – NKFIH, Fund No. SNN-135643.

The second author’s research is partially supported by Simons Foundation
Collaboration Grant #353292 and by the J. William Fulbright Educational
Exchange Program.

The third author’s research is partially supported by the project “Deepening
the activities of the Hungarian Industrial Innovation Mathematical Service
Network HUMATHS-IN,” No. EFOP-3.6.2-16-2017-00015.

##  1\. Introduction and Results

One of the main tasks in network theory is clustering vertices, see Newman
[8]. Graph clustering is a well-studied problem and has important applications
in graph mining or model construction. The usual methods try to achieve many
edges inside clusters and only a few between distinct clusters [9]. This
approach generally works well for so-called social graphs, which usually
contain more triangles than a random graph with similar edge density or degree
properties. In contrast technological or transaction graphs contain fewer
triangles and often display tree-like structures. To measure the algorithms’
efficacy the parameter known as Newman modularity is commonly used [8].

However, this standard approach is not always justified. Certain bipartite
graphs, e.g. those that describe pollinator networks or trade networks,
suggest the presence different structures, like the notion of embeddedness,
see Uzzi [10]. That is, the vertices of each color class can be ordered, and
the smaller ranked vertex neighborhood contains the neighborhood of any higher
ranked one. In the context of image processing, Junttila and Kaski [6] call a
binary matrix $A$ (that is, a matrix whose entries are either zero or one)
fully nested if its rows and columns can be reordered such that the ones are
in an echelon form. Let $G_{A}$ be the bipartite graph whose adjacency matrix
is $A$. Then $A$ being fully nested is equivalent to $G_{A}$ satisfying
embeddedness.

Let $X$ (the columns) and $Y$ (the rows) be the bipartition of $G_{A}$. The
matrix $A$ and the graph $G_{A}$ are each said to be $k$-nested with respect
to $X$ if $X$ can be partitioned as $X_{1},\dots,X_{k}$ such that all
subgraphs spanned by $(X_{i},Y)$ are fully nested for $i=1,\dots,k$. The
quantity of interest for any $G_{A}$ is smallest $k$ for which $G_{A}$ is
$k$-nested.

We present a new kind of clustering of general (that is, not necessary
bipartite) transaction graphs via a certain class of proper colorings. The
clusters are the color classes, since we do not want edges inside a cluster,
and we restrict the structure of the edges between the pairs of classes. The
above examples suggest that in some cases there should be a fully nested or,
equivalently, embeddedness relation among any two color classes. We generalize
this notion to an arbitrary host graph $G$ and a forbidden bipartite subgraph
$H$ as follows.

######  Definition 1.

Fix a bipartite graph $H$. A proper coloring of a graph $G$ is an _$H$
-avoiding coloring_ if the union of any two color classes spans an induced
$H$-free graph. Let $\chi_{H}(G)$ be the minimum number of colors in an
$H$-avoiding coloring of $G$.

Note that the function $\chi_{H}(G)$ is not necessarily monotone either in $H$
or in $G$. However, we have a useful property:

######  Observation 2.

For any graphs $H$ and $G$, $\chi(G)\leq\chi_{H}(G)$. If $G$ is $H$-free, then
$\chi(G)=\chi_{H}(G)$.

###  1.1. Complexity issues

We show that that the computation of $\chi_{H}(G)$ is NP-hard for some graphs,
and polynomially computable for others. The most interesting case, when
$H=2K_{2}$, gives back embeddedness as described above. For these generalized
chromatic numbers we derive some theoretical extremal results as well as
results on complexity.111Heuristics for finding $H$-avoiding colorings and
case studies will be presented in a future paper.

In the following we use $K_{n}$, $P_{n}$ and $C_{n}$ for the complete graph,
path and cycle on $n$ vertices, respectively. For graphs $H_{1}$ and $H_{2}$
on disjoint vertex sets, $H_{1}\oplus H_{2}$ denotes their disjoint union.
Theorem 3 gives a characterization of the complexity issues in computing
$\chi_{H}(G)$ depending on the graph $H$.

######  Theorem 3.

The computation of $\chi_{H}(G)$ is polynomial-time solvable if $H$ is
$K_{1}\oplus K_{1}$, $K_{2}$, or $K_{2}\oplus K_{1}$ and is NP-hard for all
other graphs.

It is valuable to spell out special cases since the proofs of these are needed
in proving Theorem 3.

######  Lemma 4.

It is NP-complete to decide if $\chi_{P_{3}}(G)\leq 5$, while it is polynomial
time decidable if $\chi_{P_{3}}(G)\leq 3$.

######  Lemma 5.

It is NP-complete to decide if $\chi_{P_{4}}(G)\leq 3$.

######  Lemma 6.

There is a unique $H$-avoiding coloring of $G$ using exactly $\chi_{H}(G)$
colors if $H=K_{2}\oplus K_{1}$. One can find this coloring in polynomial
time.

Let us note that a $P_{3}$-avoiding coloring of $G$ has a nice combinatorial
meaning, it represents the edges of $G$ as the union of independent matchings.
The computation of $\chi_{P_{3}}(G)$ can be reduced to the normal chromatic
number. Let $P_{3}(G)$ be a graph which made from $G$ by adding an edge to
every induced $P_{3}$, i.e. making a triangle out of these $P_{3}$.

######  Observation 7.

$\chi(P_{3}(G))=\chi_{P_{3}}(G)$.

Note that if a bipartite graph $G_{A}$ is $k$-nested then it has a similar
reduction as in Observation 7.

For a bipartite graph $G_{A}$ with bipartition $(X,Y)$, define the conflict
graph ${\rm co}(X)$ on $X$ such that $(x,x^{\prime})$ is an edge in ${\rm
co}(G)$ for $x,x^{\prime}\in X$ if there are $y,y^{\prime}\in Y$ such that
$\\{x,x^{\prime},y,y^{\prime}\\}$ spans a $2K_{2}$ in $G_{A}$.

######  Observation 8.

The bipartite graph $G_{A}$ is exactly $k$-nested for $X$ if $\chi({\rm
co}(X))=k$.

For applications the computation of $\chi_{2K_{2}}(G)$ seems to be the most
important case.

######  Theorem 9.

It is polynomial time decidable if $\chi_{2K_{2}}(G)\leq 3$.

For a fix graph $H$ there is a linear upper bound on the value of
$\chi_{H}(G)$. In this paper, $\lg n$ is the logarithm of $n$ in base 2 and
$\log n$ is the natural logarithm of $n$.

######  Proposition 10.

Let $H$ be a bipartite graph and let $k_{1}$ be the smallest positive integer
such that each bipartition of $H$ has a part with size at least $k_{1}$. Let
$k_{2}$ be the smallest positive integer such that each bipartition of $H$ has
both parts of size at least $k_{2}$. Let $G$ be an $n$-vertex graph with
chromatic number $\chi$ and independence number $\alpha$. If $k_{2}\geq 3$,
then

$\displaystyle\chi_{H}(G)\leq\min\left\\{\frac{n}{k_{1}-1}+\frac{k_{1}-2}{k_{1}-1}\,\chi,\frac{n}{k_{2}-1}\left(1-\frac{1}{\chi}\right)+\frac{k_{2}-2}{k_{2}-1}(\chi-1)+1\right\\}.$

If $k_{2}=2$, then

$\displaystyle\chi_{H}(G)\leq\min\left\\{\frac{n}{k_{1}-1}+\frac{k_{1}-2}{k_{1}-1}\,\chi,n-\alpha+1\right\\}.$

###  1.2. Random graphs

In the case where $G$ is a random graph drawn from $G(n,p)$, the Erdős-Rényi
random graph on $n$ vertices with edge probability $p$, we establish tight
bounds for $\chi_{H}(G)$. The distribution of $\alpha(G)$, where $G\sim
G(n,p)$ for $p$ fixed, was determined by Bollobás and Erdős [3]. The
distribution of $\chi(G)$ was first proven by in a classic result by Bollobás
[2] and the error terms have been further refined by various authors (see
[1]).

To be precise, whp means _with high probability_ , i.e. a probability
arbitrarily close to one, provided that the number of vertices (or other
natural parameter) is large enough.

######  Theorem 11.

Let $H$ be a bipartite graph with $k_{1}$ and $k_{2}$ defined as in
Proposition 10. Fix $p\in(0,1)$, let $d=1/(1-p)$, and let $G\sim G(n,p)$. If
$k_{1}\geq 3$ and $k_{2}\geq 2$, then there is a $C=C(H,p)$ such that whp

$\displaystyle\frac{n}{k_{1}-1}-C\log
n\leq\chi_{H}(G)\leq\frac{n}{k_{1}-1}+O\left(\frac{n}{\log_{d}n}\right).$

If $k_{1}=k_{2}=2$, then there exists a $C=C(H,p)$ such that whp

$\displaystyle n-C\log n\leq\chi_{H}(G)\leq n-2\log_{d}n+O\left(\log_{d}\log
n\right).$

In particular, if $H=2K_{2}$, then whp

$\displaystyle n-8\log_{1/Q}n+\Omega\left(\log_{1/Q}\log
n\right)\leq\chi_{H}(G)\leq n-2\log_{d}n+O\left(\log_{d}\log n\right),$

where $Q=1-2p^{2}(1-p)^{2}$.

Finally, we mention a useful observation on the $H$-avoiding chromatic number,
see its consequences in Section 5.

######  Observation 12.

If $G$ is a graph such that every $H$-free induced subgraph has at most $\ell$
edges, then $\chi_{H}(G)$ satisfies

$\displaystyle\ell\binom{\chi_{H}(G)}{2}\geq e(G).$

In the rest of the paper we provide the proofs of the main results. In Section
2 we prove Theorem 3. Section 3 contains the proof of Theorem 9, while Section
4 contains the proofs of Proposition 10 and of Theorem 11. In Section 5 we
show some of the consequences of Observation 12. Finally, in Section 6 we list
some unsolved questions which naturally came up during the research.

##  2\. Proof of Theorem 3

We start the proof with the cases in which the graph $H$ is equal to either
$K_{1}\oplus K_{1}$, $K_{2}$ or $K_{2}\oplus K_{1}$. The graph $G$ has
$K_{2}$-avoiding coloring if and only if $G$ is the empty graph.

Proof of Lemma 6. If $H=K_{2}\oplus K_{1}$ then any two color classes in an
$H$-avoiding coloring spans either a complete or empty bipartite graph. (In
the special case if $H=K_{1}\oplus K_{1}$ then there can be only complete
bipartite graphs between any two color classes.) Let us define a binary
relation $\rho$ such that for $x,y\in V(G)$ we have $x\rho y$ iff $N(x)=N(y)$.
Obviously $\rho$ is an equivalence relation, and the equivalence classes
induced by $\rho$ are exactly the color classes of $G$ in the unique
$K_{2}\oplus K_{1}$-avoiding coloring of $\chi_{K_{2}\oplus K_{1}}(G)$
classes. $\Box$

Král, Kratochvíl, Tuza and Woeginger [7] studied the hardness of coloring
$H$-free graphs. They gave a complete description of the problem in the
theorem follows:

######  Theorem 13 (Král-Kratochvíl-Tuza-Woeginger [7]).

The problem $H$-Free Coloring is polynomial-time solvable if $H$ is an induced
subgraph of $P_{4}$ or of $P_{3}\oplus K_{1}$, and NP-complete for any other
$H$.

Combining Theorem 13 and Observation 2, one gets immediately that the
computation of $\chi_{H}(G)$ is NP-complete if $\chi(G)$ is also NP-complete
for $H$-free $G$. On the other hand, the polynomial-time computability of
$\chi$ for $H$-free graphs does not imply the same for $\chi_{H}$. Among the
polynomial cases of Theorem 13 we have checked already the graphs $K_{1}\oplus
K_{1}$, $K_{2}$ and $K_{2}\oplus K_{1}$. Somehow against intuition, the
computation of $\chi_{H}$ is NP-complete for the remaining $H=P_{3}$ and
$H=P_{4}$ cases according to Lemmas 4 and 5.

Proof of Lemma 4. We need to show $L_{5}=\\{G:\chi_{P_{3}}(G)\leq 5\\}$ is NP-
complete language. We use reduction from the language

$L_{3,2}=\\{T:T\>\mbox{\rm is a 3-uniform hypergraph},\chi(T)\leq 2\\},$

which is a well-known NP-complete problem. Let $T$ be an instance, that is
$T\in L_{3,2}$.

We need to assign a graph $G_{T}$ to $T$ such that $\chi_{P_{3}}(G_{T})\leq 5$
if and only if $\chi(T)\leq 2$. It turns out that the greatest difficulty is
to associate the colorings of the graph $G_{T}$ and the hypergraph $T$. The
color of a vertex $t$ of $T$ cannot be encoded in one vertex $x_{t}$ of
$G_{T}$, since the gadgets constructed in $G_{T}$ that enforce the good
coloring of the edges of $T$ containing $t$ would interfere with each other.
The solution is to repeat the actual color of vertex $t$ at least as many
times as the number of edges of $T$ that contain $t$. For simplicity we repeat
the color of any vertex $t$ a total of $m$ times, where $m$ is the number of
edges in $T$, and read out the color of $t$ at most once from each place.

The graph $G_{T}$ will consist of an $n\times m$ matrix of pentagons, in which
the $i$-th row codes the color of the $i$-th vertex in $T$. To assess the
coloring of the $j$-th edge of $T$, the $j$-th column of this matrix is read.
The usual types of gadgets are used in $G_{T}$ representing and evaluating the
edges of $T$, see Figure 1.

$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$
Figure 1. The graph $G_{T}$ with the possible coloring, proof of Lemma 4.
$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$1$$1$$1$$1$$1$$1$$5$$4$$3$$2$$5$$4$$3$$2$$5$$4$$3$$2$$5$$4$$3$$2$$5$$4$$3$$2$$2$$3$$4$$5$$2,3$$2,3$$2,3$$?$$5$$3$$2$$4$
Figure 2. The two cases of colorings with gadgets, proof of Lemma 4.

Before examining the coloring of $G_{T}$, let us examine a $P_{3}$-avoiding
good coloring of just $C_{5}$, since $C_{5}$ is the main building block of our
construction. The vertices are referenced clockwise. If the first vertex is
colored by 1, the second by 2, the third vertex color can be neither 2,
because of adjacency, or 1 since it would create a two colored $P_{3}$. So,
without loss of generality, the first three vertices are colored 1, 2, 3
respectively. The fourth vertex needs the fourth color. It cannot be colored
by 2 or 3 as before. If it would be colored by 1, the first, fifth and fourth
vertices would form a two-colored $P_{3}$. Finally, the fifth vertex needs to
be colored 5, since 1 and 4 are colors of adjacent vertices, while 2 or 3
would create two-colored $P_{3}$’s.

Assuming that the $n$ vertices of $T$ are $x_{1},\dots,x_{n}$ and the $m$
edges are $e_{1},\dots,e_{m}$, the graph $G_{T}$ is first constructed by
taking an $n\times m$ matrix with a $C_{5}$ in each position $(i,j)$. The
$C_{5}$ in the $(i,j)$ position will be referred to as $C_{i,j}$. Second,
connect the third and fourth vertices of $C_{i,j}$ to the first vertex of
$C_{i+1,j}$ for $i=1,\dots,n-1$, $j=1,\dots n$, and similarly from $C_{n,j}$
to $C_{1,j+1}$ for $j=1,\dots,n-1$. Third, draw edges from the fourth vertex
of $C_{i,j}$ to the second vertex of $C_{i,j+1}$ for $i=1,\dots,n$ and
$j=1,\dots,m-1$. See Figure 1.

Without loss of generality, any $P_{3}$-avoiding five-coloring should use
color 1 at the first vertex of any $C_{5}$, should use the colors 2 and 5 in
the second and fifth vertices (although in any order) and the colors 3 and 4
in the third and fourth vertices (again their order is arbitrary).

Furthermore, is easy to verify that a proper $P_{3}$-avoiding five-coloring
must use the same order of colors 2 and 5 within a row, while the order of 2
and 5 can be arbitrary for each row. We will use the $i$-th row to code the
color of the vertex $x_{i}$ of the hypergraph $T$. However, when we read this
“value,” each $C_{5}$ is read only once.

Finally, the gadgets realizing the edges of $T$ are $m$ copies of $K_{1,3}$.
Let $e_{\ell}$ be $\\{x_{p},x_{q},x_{r}\\}$ and connect the leaves of the
$\ell$-th $K_{1,3}$ to the fifth vertex of a yet unused $C_{5}$ in the $p$-th,
$q$-th and $r$-th rows, respectively. The colors the vertices of $e_{\ell}$
receives are the color of the fifth vertices of $C_{5}$-s which were connected
to the leaves of the representing $K_{1,3}$.

Let us check if proper five-colorings of the construction and proper two-
colorings of $T$ correspond to each other. If, for $e_{\ell}$, the vertices in
the graph coloring all receive the color, say 5, then the leaves of the
representative $K_{1,3}$ can be colored 2 or 3. One of these colors appears
two times, and it results in a two-colored $P_{3}$ in the graph coloring. If
$e_{\ell}$ is colored properly, say 5, 5, 2, then the connected vertices in
the representative $K_{1,3}$ may get the colors 2, 3, 5. Giving color 4 to the
3-degree vertex of the representative $K_{1,3}$ we get a proper
$P_{3}$-avoiding five-coloring of $G$. See Figure 2.

The case $\chi_{P_{3}}(P_{k})\leq 3$. If $G$ has a vertex of degree at least
three, then $P_{3}(G)$ has a clique of size at least four, and by Observation
7, $\chi_{P_{3}}(G)\geq 4$. If all vertices have degree at most two, then the
components of $G$ are paths and cycles. The components can be colored
independently of each other in that case, so $G$ has a $P_{3}$-avoiding
3-coloring if and only if all components have. For all $k\in\mathbb{N}$,
$\chi_{P_{3}}(P_{k})\leq 3$, we just repeat the pattern $1,2,3,1,2,3\dots$
starting from one of the ends. The same can be (and must be) done for $C_{k}$
by specifying a starting vertex. However, it is successful only if $k\equiv
0\mod 3$. $\Box$

Proof of Lemma 5. As in the proof of Lemma 4, we use a reduction from the
language $L_{3,2}$, the two-coloring of 3-uniform hypergraphs. Having an
instance $T\in L_{3,2}$ with vertex set $x_{1},\ldots,x_{n}$, $n\geq 4$, the
reduction to a $P_{4}$-avoiding 3-coloring of a graph $G_{T}$ goes as follows.
To each vertex $x_{i}$ of $T$ we create a pair of vertices
$x_{i},x_{i}^{\prime}$ and have the edge $(x_{i},x_{i}^{\prime})$. An
additional special vertex $z$ is adjacent to each $x_{i}$ and to each
$x_{i}^{\prime}$.

$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{1\\}$$\\{1\\}$$\\{1\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$\\{2,5\\}$$\\{3,4\\}$$\\{3,4\\}$$\\{2,5\\}$$1$$1$$1$$1$$1$$1$$5$$4$$3$$2$$5$$4$$3$$2$$5$$4$$3$$2$$5$$4$$3$$2$$5$$4$$3$$2$$2$$3$$4$$5$$2,3$$2,3$$2,3$$?$$5$$3$$2$$4$$x_{i}$$x_{i}^{\prime}$$z$$x_{p}$$a_{1}$$b_{1}$$c_{1}$$1$$x_{q}$$a_{2}$$b_{2}$$c_{2}$$2$$x_{r}$$2$$a_{3}$$1$$b_{3}$$3$$c_{3}$$1$$w_{1}$$w_{2}$$2$$1$$3$$2$$1$$2$$3$$1$$1$$2$$3$$1$$3$$2$$1$$2$$3$$1$$2$$1$$3$$2$$1$$2$$3$$1$$3$$3$
Figure 3. The two cases of colorings with gadgets, proof of Lemma 5.

For each hyperedge $e_{\ell}=\\{x_{p},x_{q},x_{r}\\}$ in $T$, we define a
gadget as follows. Take three disjoint copies of $P_{3}$, $a_{i},b_{i},c_{i}$
for $i=1,2,3$, and vertices $w_{1},w_{2}$, and draw the edges
$(c_{1},w_{1}),(c_{2},w_{1}),(c_{2},w_{2})$ and $(c_{3},w_{2})$. Finally we
set the gadget by drawing the edges $(a_{1},x_{p})$, $(a_{2},x_{q})$ and
$(a_{3},x_{r})$.

We claim that a $G$ has a $P_{4}$-avoiding 3-coloring if and only if $T$ has a
$P_{4}$-avoiding 2-coloring. We may assume vertex $z$ is colored by 3, so
$x_{i}$s are colored 1 or 2, both in the coloring of $G$ and $T$.

If the vertices of an edge $e_{\ell}=\\{x_{p},x_{q},x_{r}\\}$ all receive the
same color, say 2, then in the gadget associated to $e_{\ell}$ the vertices
$a_{1},a_{2},a_{3}$ must receive the color 1. (Indeed, if say $a_{1}$ would be
colored by 3, then take an $x_{i}\not\in\\{x_{p},x_{q},x_{r}\\}$. Either
$x_{i}$ or $x_{i}^{\prime}$ has the color 2, say it is $x_{i}$. But
$a_{1},x_{p},z,x_{i}$ is a 2-colored $P_{4}$.) The vertices $b_{1},b_{2}$ and
$b_{3}$ must get color 3, since if, say $b_{1}$, is of color 2, then
$b_{1},a_{1},x_{p},x_{p}^{\prime}$ would induce a 2-colored $P_{4}$. If
$c_{2}$ has color 1, then both $w_{1}$ and $w_{2}$ have color 2, since
otherwise $w_{1}$ or $w_{2}$, $c_{2}$, $b_{2}$, $a_{2}$ would be a 2-colored
$P_{4}$. But in that case, the color of $c_{3}$ could be only 1, inducing
2-colored $P_{4}$ on the vertices $c_{3},w_{2},c_{2},w_{1}$.

If $c_{2}$ has color 2, and at least one of $c_{1}$ or $c_{3}$ has color 1,
assume $c_{1}$, then $w_{1}$ must be colored 3. But then
$w_{2},c_{1},b_{1},a_{1}$ would be a 2-colored $P_{4}$. Finally, if all
$c_{1},c_{2},c_{3}$ has color 2, then $w_{1}$ and $w_{2}$ must have different
colors in order to avoid the 2-colored $P_{4}$ on $c_{1},w_{2},c_{2},w_{2}$.
But if, say $w_{1}$ has color 3, then we see a 2-colored $P_{4}$ on the
vertices $c_{1},w_{1},c_{2},b_{2}$.

For the other direction, assume that $e_{\ell}=\\{x_{p},x_{q},x_{r}\\}$
received two colors in the hypergraph coloring. Without loss of generality, we
may assume two vertices are colored 1, and one with 2. The vertex colored by 2
is either on one of the side, $x_{p},x_{r}$ or the in the middle, $x_{q}$. Let
us say $x_{p}$ has color 2 and $x_{q},x_{r}$ received color 1. Then the
coloring extends to the gadget of $e_{\ell}$ by coloring $a_{1},c_{2},c_{3}$
by 1, $c_{1},a_{2},a_{3},w_{2}$ by 2, and $b_{1},b_{2},b_{3},w_{1}$ by 3. If
$x_{q}$ has color 2 and $x_{p},x_{r}$ have color 1, then the extension is
$c_{1},a_{2},c_{3}$ is of color 1, $a_{1},c_{2},a_{3}$ is of color 2, and
$b_{1},b_{2},b_{3},w_{1},w_{2}$ is of color 3. Notice that in both cases all
$b$ types vertices received color 3, which “insulates” the gadgets from each
other, so the defined 3-coloring is a $P_{4}$-avoiding one. $\Box$

##  3\. Proof of Theorem 9

Proof of the case $H=2K_{2}$. To see if $\chi_{2K_{2}}(G)\leq 3$ for a given
graph $G$, first we check if $G$ contains $4K_{2}$ as an induced subgraph.
This requires no more than $O(n^{4})$ time. If $G$ does contain a $4K_{2}$,
then $\chi_{2K_{2}}(G)\geq 4$, since between two color classes there can be
only one of those four independent edges. Assume $G$ does not contain
$4K_{4}$, and recall a result of Farber, Hujter and Tuza [4]:

######  Theorem 14 (Farber-Hujter-Tuza [4]).

If the graph $G$ does not contain $(t+1)K_{2}$ as an induced subgraph, then
the number of maximal independent sets in $G$ is at most $\binom{n/t}{t}$.

The following ideas are well-known and perhaps motivated Theorem 14. The set
$\mathcal{M}$ of all maximal independent sets can be found by, for example, a
DFS tree algorithm, and can be listed in no more than
$O(n^{2}|{\mathcal{M}}|)$ time. The decision problem of whether $\chi(G)\leq
k$ can be solved by checking if there is $k$-set from $\mathcal{M}$ covering
the vertex set of $G$. This still can be done in $O(\binom{|\mathcal{M}|}{k})$
time.

Applying Theorem 14 to $G$, $|\mathcal{M}|\leq\binom{n/3}{3}<n^{3}/162$, so
for a possible 3-coloring we have to check a configuration of size no larger
than $O(n^{9})$. A configuration consists of three maximal independent sets
$X_{1},X_{2}$ and $X_{3}$. First, $\cup_{i}X_{i}$ should contain all vertices
of $G$. If this holds, it readily gives a 3-coloring, however it is not
necessarily $2K_{2}$-avoiding. Indeed we are looking for $Y_{i}\subset X_{i}$
for $i=1,2,3$ such that $\cup_{i}Y_{i}$ contains all vertices of $G$,
$Y_{i}\cap Y_{j}=\emptyset$ if $i\not=j$, and the partition
$\\{Y_{1},Y_{2},Y_{3}\\}$ is $2K_{2}$-avoiding.

We can assume that $\cap_{i}X_{i}=\emptyset$, if not, these vertices are
isolated, and can be assigned to any $Y_{i}$ in the end. Then we start with
the sets $Y_{1}:=X_{1}\setminus(X_{2}\cup X_{3})$,
$Y_{2}:=X_{2}\setminus(X_{1}\cup X_{3})$ and $Y_{3}:=X_{3}\setminus(X_{1}\cup
X_{2})$ and try to put the leftover vertices into those. The triple
$\\{Y_{1},Y_{2},Y_{3}\\}$ should be $2K_{2}$-avoiding, otherwise we discard
the configuration. Then we have to decide, for example, if a vertex $x\in
X_{1}\cap X_{2}$ should be put in $Y_{1}$ or $Y_{2}$. If either placement
would give a $2K_{2}$ with the set $Y_{3}$, we discard the configuration; if
only one, we place it to the other; if none, we decide about it later.

At the end of this process we have disjoint sets $Y_{1},Y_{2},Y_{3}$ that are
$2K_{2}$-avoiding, $Y_{i}\subset X_{i}$, and the vertices of
$R_{1,2}:=(X_{1}\cap X_{2})\setminus(Y_{1}\cup Y_{2})$ can be placed both
$Y_{1}$ or $Y_{2}$ (and same for $R_{1,3}$ and $R_{2,3}$). Let us construct a
conflict graph on $R_{1,2}$ and for other indices do similarly. For $x,y\in
R_{1,2}$ there is an edge $(x,y)\in E(R_{1,2})$ if $x$ and $y$ cannot be
placed to $Y_{1}$. (That is, they induce a $2K_{2}$ to $Y_{3}$. It means $x$
and $y$ could not be placed in $Y_{2}$ either.) It is easy to see that if all
those conflict graphs $R_{i,j}$, $i\not=j$ are bipartite, then all vertices
can be placed and we are ready. Otherwise the configuration is to be discarded
and we have to move to the next one. If none of the configurations can be
formed to be a $2K_{2}$-avoiding 3-coloring, then $\chi_{2K_{2}}>3$. $\Box$

##  4\. Proof of Theorem 11

Proof of Proposition 10.

Let $G$ have a coloring with part sizes $s_{1},s_{2},\ldots,s_{\chi}$ and
$s_{1}$ the largest. First, further partition each color class arbitrarily
into subparts of size at most $k_{1}-1$. The number of parts is

$\displaystyle\sum_{i=1}^{\chi}\left\lceil\frac{s_{i}}{k_{1}-1}\right\rceil\leq\sum_{i=1}^{\chi}\left(\frac{s_{i}}{k_{1}-1}+\frac{k_{1}-2}{k_{1}-1}\right)=\frac{n}{k_{1}-1}+\frac{k_{1}-2}{k_{1}-1}\,\chi,$

which is an upper bound that holds regardless of the value of $k_{2}$.

Second, if $k_{2}\geq 3$, partition each color class except the largest
arbitrarily into subparts of size at most $k_{2}-1$. The number of parts is

$\displaystyle
1+\sum_{i=2}^{\chi}\left\lceil\frac{s_{i}}{k_{2}-1}\right\rceil$
$\displaystyle\leq
1+\sum_{i=2}^{\chi}\left(\frac{s_{i}}{k_{2}-1}+\frac{k_{2}-2}{k_{2}-1}\right)=1+\frac{n-s_{1}}{k_{2}-1}+\frac{k_{2}-2}{k_{2}-1}(\chi-1)$
$\displaystyle\leq
1+\frac{n-n/\chi}{k_{2}-1}+\frac{k_{2}-2}{k_{2}-1}(\chi-1).$

Third, if $k_{2}=2$, color $G$ by giving the largest independent set one color
and every other vertex an individual color. The number of parts is
$n-\alpha+1$. Trivially, each of these partitions is an $H$-free coloring. All
three combined bounds give the result in the proposition.

$\Box$

Proof of Theorem 11.

To obtain the upper bound, in the case of $k_{1}\geq 3$, we use Proposition 10
together with the result from Bollobás [2] that, whp
$\chi\left(G(n,p)\right)=(1+o(1))\frac{n}{2\log_{d}n}$. Hence,

$\displaystyle\chi_{H}(G)\leq\frac{n}{k_{1}-1}+O\left(\frac{n}{\log_{d}n}\right).$

In the case of $k_{1}=2$, the upper bound comes from Proposition 10 together
with the result from Bollobás and Erdős [3] that, whp
$\alpha\left(G(n,p)\right)=2\log_{d}n-2\log_{d}\log n+O(1)$. Hence,

$\displaystyle\chi_{H}(G)\leq n-2\log_{d}n+O\left(\log_{d}\log n\right).$

Now we proceed to the lower bound. An $(\ell;k)$-complex is a family of $\ell$
disjoint independent sets, each of size $k$, $A_{1},\ldots,A_{\ell}$ such that
each pair $(A_{i},A_{j})$, $1\leq i<j\leq\ell$ induces a graph that has no
induced copy of $H$. The key to the proof is to show that for certain values
of $k$ and $\ell=\ell(n)$, the probability that a $(\ell;k)$-complex exists
goes to zero.

If no $(\ell;k)$-complex exists, then whenever there is a coloring with color
classes of size $n_{1},\ldots,n_{t}\geq k$ it is the case that
$\sum_{i=1}^{t}\lfloor n_{i}/k\rfloor<\ell$. Thus,

$\displaystyle\frac{1}{k}\sum_{i=1}^{t}n_{i}-\frac{k-1}{k}t\leq\sum_{i=1}^{t}\left\lfloor\frac{n_{i}}{k}\right\rfloor$
$\displaystyle<\ell$ $\displaystyle\sum_{i=1}^{t}n_{i}$
$\displaystyle<k\ell+(k-1)t,$

while the leftover vertices are in color classes of size at most $k-1$. So, if
there are $t$ color classes of size at least $k$, then

(1) $\displaystyle\chi_{H}(G)\geq
t+\frac{n-k\ell-(k-1)t}{k-1}=\frac{n}{k-1}-\frac{k}{k-1}\ell.$

For the graph $H$, let $Q=Q(H,p)$ be the probability that a $k_{1}\times
k_{1}$ random bipartite graph has no induced copy of $H$. Taking the product
over all $\binom{\ell}{2}$ pairs $(A_{i},A_{j})$ and multiplying by the
probability that each $G[A_{i}]$ induces an independent set, we obtain:

(2) $\displaystyle\mathbb{P}\left[\exists\text{ an
}(\ell;k_{1})\text{-complex}\right]$
$\displaystyle=\frac{(n)_{k_{1}\ell}}{\ell!(k_{1}!)^{\ell}}Q^{\binom{\ell}{2}}(1-p)^{\ell\binom{k_{1}}{2}}$
$\displaystyle<\left[\left(\sqrt{\frac{e}{\ell}}\right)nQ^{(\ell-1)/(2k_{1})}(1-p)^{(k_{1}-1)/2}\right]^{k_{1}\ell},$

which is obtained from the inequalities $(n)_{k_{1}\ell}\leq n^{k_{1}\ell}$,
$\ell!\geq(\ell/e)^{\ell}$, and $k_{1}!\geq 1$.

Let $C^{\prime}=C^{\prime}(H,p)=\frac{2k_{1}}{\log(1/Q)}$. For $n$
sufficiently large, if $\ell>C^{\prime}\log n$, then the probability in (2)
goes to zero. By (1), it is the case that whp

$\displaystyle\chi_{H}(G)\geq\frac{n}{k_{1}-1}-C^{\prime}\frac{k_{1}}{k_{1}-1}\log
n.$

Thus the general lower bound is satisfied.

In the special case where $H=2K_{2}$, we observe that
$Q(2K_{2},p)=1-2p^{2}(1-p)^{2}$.

$\displaystyle\mathbb{P}\left[\exists\text{ an
}(\ell;2)\text{-complex}\right]$
$\displaystyle=\frac{(n)_{2\ell}}{\ell!2^{\ell}}Q^{\binom{\ell}{2}}(1-p)^{\ell}$
$\displaystyle<\left[\left(\sqrt{\frac{e}{2\ell}}\right)nQ^{(\ell-1)/4}(1-p)^{1/2}\right]^{2\ell}.$

If $\ell>\frac{4\log n}{\log(1/Q)}-\frac{4\log\log n}{\log(1/Q)}+\log\log\log
n$ and $n$ is sufficiently large, then whp no $(\ell;2)$-complex exists. By
(1), it is the case that whp

$\displaystyle\chi_{2K_{2}}(G)\geq n-(1-o(1))\frac{8\log n}{\log(1/Q)},$

where $Q=1-2p^{2}(1-p)^{2}$.

$\Box$

Similar results can be obtained as long as
$\min\\{p,1-p\\}=\omega\left(\frac{\log n}{n}\right)$ but express our results
in the case where $p$ is a fixed constant.

##  5\. Examples for Observation 12

An easy consequence of Observation 12 is as follows:

######  Corollary 15.

$\displaystyle\chi_{2K_{2}}(P_{n})\geq\sqrt{2\left\lceil\frac{n-1}{3}\right\rceil+\frac{1}{4}}+\frac{1}{2}.$

A more refined argument gives the value of $\chi_{2K_{2}}(P_{n})$ as follows:

######  Corollary 16.

If $k$ is the least integer that satisfies

$\displaystyle\left\lfloor\frac{k+1}{2}\right\rfloor(k-2)\geq\left\lceil\frac{n-1}{3}\right\rceil$

then $\chi_{2K_{2}}(P_{n})=k$.

Proof. Let $\ell=\left\lceil\frac{n-1}{3}\right\rceil$. In particular, this
means $n-1\leq 3\ell\leq n+1$.

Choose $k$ to be the least integer so that

(5) $\displaystyle\left\\{\begin{array}[]{lll}\binom{k}{2}&\geq\ell+1,&\mbox{
if $k$ is odd;}\\\ \binom{k}{2}-\frac{k}{2}+1&\geq\ell+1,&\mbox{ if $k$ is
even.}\end{array}\right.$

This value is chosen because the longest Eulerian trail in $K_{k}$ has
$\binom{k}{2}$ edges if $k$ is odd and has $\binom{k}{2}-\frac{k}{2}+1$ edges
if $k$ is even. The latter case occurs when a matching of size $k/2-1$ is
removed from $K_{k}$.

Let $a_{1},a_{2},\ldots,a_{\ell},a_{\ell+1}$ be an Eulerian trail in $K_{k}$.
Enumerate the vertices of $P_{n}$ as $1,2,\ldots,n$. Let the coloring of the
vertices of $P_{n}$ be
$f:[n]\rightarrow\\{a_{1},a_{2},\ldots,a_{\ell},a_{\ell+1}\\}$, defined as
follows:

$\displaystyle f(1)=f(3)$ $\displaystyle=a_{1}.$ $\displaystyle
f(3i-4)=f(3i-2)=f(3i)$ $\displaystyle=a_{i},$ for $i=2,\ldots,\ell-1$.
$\displaystyle f(3\ell-4)=f(3\ell-2)$ $\displaystyle=a_{\ell}.$ $\displaystyle
f(3\ell)$ $\displaystyle=a_{\ell},$ if $3\ell\leq n$. $\displaystyle
f(3\ell-1)$ $\displaystyle=a_{\ell+1}.$ $\displaystyle f(3\ell+1)$
$\displaystyle=a_{\ell+1},$ if $3\ell+1\leq n$.

Note that $3\ell+2\geq n+1$ by our choice of $\ell$, so there are no other
vertices to color.

For all $j\in\\{1,\ldots,\ell-1\\}$ each pair of color classes $a_{j}a_{j+1}$
induces a $P_{4}$ plus some isolated vertices. The pair $a_{\ell}a_{\ell+1}$
also induces a path plus isolated vertices and the path is either $P_{2}$,
$P_{3}$, or $P_{4}$, depending on the remainder of $n$ modulo 3. Therefore,
this coloring is a $2K_{2}$-free coloring.

To see that equality holds, consider a $2K_{2}$-free $k$-coloring of $P_{n}$.
Every pair of color classes either induces an empty graph or a graph whose
only nontrivial component is $P_{2}$, $P_{3}$, or $P_{4}$. Thus, the edges of
$P_{n}$ can be partitioned according to which unique pair of colors induce a
particular subpath. Furthermore, subpaths that share a vertex must share a
color. Thus, we can construct an auxiliary graph $\Gamma$ on
$\\{1,\ldots,k\\}$ where $ij$ is an edge if and only if the pair of colors
$\\{i,j\\}$ induces a path on at least two vertices. Because consecutive small
paths must share a vertex and hence a color, the edges of $\Gamma$ form a
trail on $K_{k}$. Since each edge of $\Gamma$ corresponds to at most 3 edges
of $P_{n}$, the number of edges in $P_{n}$ is at most three times the length
of a longest trail in $K_{k}$. That is,

$\displaystyle n-1\leq 3\cdot\left\\{\begin{array}[]{ll}\binom{k}{2},&\mbox{
if $k$ is odd;}\\\ \binom{k}{2}-\frac{k}{2}+1,&\mbox{ if $k$ is
even.}\end{array}\right.$

Finally, we return to (5) and observe that the condition on $k$ is equivalent
to

$\displaystyle\left\lfloor\frac{k+1}{2}\right\rfloor(k-2)\geq\ell.$

The statement then follows. See Table 1 for small values of
$\chi_{2K_{2}}(P_{n})$. $\Box$

$n\in$ | [2,4] | [5,7] | [8,13] | [14,28] | [29,37] | [38,61] | [62,73] | [74,106] | [107,121]
---|---|---|---|---|---|---|---|---|---
$\chi_{2K_{2}}(P_{n})$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
Table 1. $\chi_{2K_{2}}(P_{n})$ for small values of $n$.

######  Corollary 17.

$\displaystyle\chi_{2K_{2}}\left(\frac{n}{2}\cdot
K_{2}\right)=\left\lceil\sqrt{n+\frac{1}{4}}+\frac{1}{2}\right\rceil.$

Proof. If $k=\chi_{2K_{2}}\left(\frac{n}{2}\cdot K_{2}\right)$, then
$\binom{k}{2}\geq\frac{n}{2}$ by Observation 12, which establishes a lower
bound of $\left\lceil\sqrt{n+\frac{1}{4}}+\frac{1}{2}\right\rceil$. This is
also sufficient in that the vertices of each edge of $\frac{n}{2}\cdot K_{2}$
can be independently assigned to distinct endvertices of $K_{k}$ where $k$ is
the value given. $\Box$

Bounds on some other graphs are given as follows:

######  Corollary 18.

Let $n$ be odd and let $T$ be the tree formed when each edge of
$K_{1,(n-1)/2}$ is subdivided (by a vertex) exactly once.

$\displaystyle\chi_{2K_{2}}(T)=\left\lceil\sqrt{n-\frac{3}{4}}+\frac{1}{2}\right\rceil.$

The proof for Corollary 18 is nearly identical to that of Corollary 17 so it
is left to the reader.

######  Corollary 19.

Let $Q_{d}$ be the $d$-dimensional hypercube. Then

$\displaystyle\chi_{2K_{2}}(Q_{2})$ $\displaystyle=2,$
$\displaystyle\chi_{2K_{2}}(Q_{3})$ $\displaystyle=4,$

and if $d\geq 4$ then

$\displaystyle\chi_{2K_{2}}(Q_{d})$
$\displaystyle\geq\sqrt{\frac{d}{2d-1}2^{d}}+\frac{1}{2}$
$\displaystyle=\sqrt{\frac{n}{2}\frac{1}{1-1/(2\lg n)}}+\frac{1}{2}.$

Proof. The case of $Q_{2}$ is trivial. It takes some small work to show that
for $Q_{3}$ there is no $Q_{3}$-avoiding $3$-coloring and there is a
$Q_{3}$-avoiding $4$-coloring. In the case where $d\geq 4$, we use Observation
12, where $k=\chi_{2K_{2}}(Q_{d})$,

$\displaystyle(2d-1)\binom{k}{2}\geq d2^{d-1},$

because the only graphs that can occur between pairs of color classes are
double-stars (at most $2d-1\geq 7$ edges) and $K_{2,2}$ ($4$ edges).

$\Box$

######  Definition 20.

Let $p$ be a prime power and let $G(p)$ be the bipartite graph on
$n=2(p^{2}+p+1)$ vertices defined by the projective plane of order $p+1$. That
is, there are $p^{2}+p+1$ points and $p^{2}+p+1$ lines and a point is adjacent
to a line if and only the point is in the line in the projective plane. This
graph is $(p+1)$-regular with no $K_{2,2}$.

######  Corollary 21.

If $G(p)$ is the graph in Definition 20 then,

$\displaystyle\chi_{2K_{2}}(G(p))$
$\displaystyle\geq\sqrt{\frac{2(p^{2}+p+1)(p+1)}{2p+1}}+\frac{1}{2}$
$\displaystyle\geq\sqrt{\frac{n}{2}+\frac{\sqrt{n}}{4}}+\frac{1}{2}.$

Proof. With $k=\chi_{2K_{2}}(G)$, we use the inequality

$\displaystyle(2d+1)\binom{k}{2}\geq(p^{2}+p+1)(p+1).$

$\Box$

##  6\. Questions

The proof method of Theorem 9 suggests the following problem:

######  Question 1.

Is it polynomial time decidable if $\chi_{2K_{2}}(G)\leq k$ for any fixed
$k\in\mathbb{N}$?

The structure of $P_{4}$-free graphs is very nice, which allows easy
computation of chromatic number, clique number etc. In fact $P_{4}$-free
bipartite graphs, called difference graphs [5], are well-studied. It is quite
surprising that the function $\chi_{P_{4}}$ is NP-hard.

######  Question 2.

Is it true that determining whether $\chi_{P_{4}}(G)\leq 3$ is NP-hard?

######  Question 3.

What is $\chi_{2K_{2}}(Q_{d})$?

######  Question 4.

What is $\max\\{\chi_{2K_{2}}(T):v(T)=n,T\textrm{ is a tree}\\}$?

######  Question 5.

Is it true that $\chi_{2K_{2}}(G)=n-(1+o(1))2\log_{2}n$ whp if $G\sim
G(n,1/2)$?

## References

  * [1] Alon, N. and Spencer, J.H., 2016. The probabilistic method. Fourth edition. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Hoboken, NJ, 2016. xiv+375pp.
  * [2] Bollobás, B., 1988. The chromatic number of random graphs. Combinatorica, 8, pp. 49–55.
  * [3] Bollobás, B. and Erdős, P., 1976. Cliques in random graphs, Math. Proc. Cambridge Phil. Soc., 80, pp. 419–427.
  * [4] Farber, M., Hujter, M. and Tuza, Z., 1993. An upper bound on the number of cliques in a graph. Networks, 23(3), pp. 207–210.
  * [5] Hammer, P.L., Peled, U.N. and Sun, X. 1990. Difference graphs. Discrete Applied Mathematics, 28, pp. 35–44.
  * [6] Junttila, E. and Kaski, P., 2011. Segmented nestedness in binary data. In Proceedings of the 2011 SIAM International Conference on Data Mining, pp. 235–246.
  * [7] Král, D., Kratochvíl, J., Tuza, Z. and Woeginger, G.J., 2001. Complexity of coloring graphs without forbidden induced subgraphs. In Graph-theoretic concepts in computer science (Boltenhagen, 2001), Springer Verlag, pp. 254–262
  * [8] Newman, M.E. and Girvan, M., 2004. Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
  * [9] Schaeffer, S. E., 2007. Graph clustering. Computer Science Review, 1(1), pp. 27-64.
  * [10] Uzzi, B., 1996. The sources and consequences of embeddedness for the economic performance of organizations: The network effect. American Sociological Review, pp. 674-698.