# Purposeful and Operation-based Cognitive System for AGI

###### Abstract

This paper proposes a new cognitive model, acting as the main component of an
AGI agent. The model is introduced in its mature state, and as an extension of
previous models, DENN, and especially AKREM, by including operational models
(frames/classes) and will. In addition, it is mainly based on the duality
principle in every known intelligent aspect, such as exhibiting both top-down
and bottom-up model learning, generalization verse specialization, and more.
Furthermore, a holistic approach is advocated for AGI designing and cognition
under constraints or efficiency is proposed, in the form of reusability and
simplicity. Finally, reaching this mature state is described via a cognitive
evolution from infancy to adulthood, utilizing a consolidation principle. The
final product of this cognitive model is a dynamic operational memory of
models and instances.

##  1 Introduction

Our consistent goal is to construct a basic realistic model for AGI
(Artificial General Intelligence). It is a gradual process with many versions
along the way. Hence, this paper presents MOM (Model Of Models), the next
version of AKREM (Associative Knowledge Representation) [Komarovsky, 2022b].

AKREM is a mature-state knowledge representation model, based mainly on the
assumption that communication is about encoding the sender’s will into a
sequence of words (a message), and then decoding it by the recipient. The
model proposes a representation of any message, in a hierarchical form based
on grouping, by generating some essence in a given level, from details in the
lower level. The lowest level details are founded upon some DNN (Deep Neural
Network), generating the basic concepts and actions (from which the details
are made of) from unstructured input. Finally, while the will concept exists
in AKREM, it will be expanded upon in this paper.

Following this, new additions to the presented model, including new
associations, operationability, modeling, consolidation, and reusability, are
introduced. First, while AKREM assumes that the learned elements are either
objects or static actions (verbs), new associations are introduced: object’s
attributes and relations. Next, these connections are all static
representations of knowledge, i.e., the hierarchies cannot be changed.
Therefore, operationability introduces a new type of association to objects:
actions that act upon them, thus producing new knowledge elements. This makes
the connections in AKREM’s hierarchies dynamic, hence it allows the freedom to
update and create new hierarchies. Next, modeling introduces some basic
cognitive operations, e.g. abstraction and grouping. Both gather many details
into fewer. Grouping specifically is about connecting elements via some common
property. It could be for example a chronology in a plot or other common
properties/actions grouped into classes. Finally, consolidation is a process
in time, that collapses a huge amount of possibilities into small set of
patterns, of any kind.

All the operations above are considered to be bidirectional, i.e. everything
lies in some range between extremes, i.e. everything has its inverse
(dualism). In grouping, it is from the whole to its parts and vice versa, and
in abstraction, it is from instances to classes and vice versa. Consolidation
is an operation in time, creating models and memory, while its inverse is
forgetting, which is also an operation in time. Will also lies in the
dichotomy of determinism and randomness.

The product of these cognitive operations is a dynamic memory of models,
formed as a semantic network of elements. It encourages a holistic approach
for AGI designing: one simple system for multiple functions, such as short-
term and long-term memories, problem-solving, communication, learning, and any
cognitive function. Moreover, if in the early epoch of AI, symbolic reasoning
was dominant, and nowadays connectionism dominates, then we come to a new era,
where we should combine and include many conflict perspectives, in cooperation
and competition. Our holistic perspective embrace this duality and other
dualities also.

Lastly, operational modeling presents AGI agent’s intelligence in its mature
state, which is the state of how its knowledge should be represented. However,
to accomplish this state, a cognitive evolution over time is required, which
utilizes the consolidation principle.

##  2 Will

In this section, the importance of will as an essential element in human
intelligence is elaborated upon, starting from the previously presented model,
AKREM.

Will in AKREM is represented in the levels of any specific hierarchy. Starting
from the most detailed aspects of will, at the lowest level, and finishing at
the most abstract will or its essence, at the top. The top level represents
some kind of experience uniqueness to differentiate it from other memories
that use the same low-level structures.

This hierarchical will is especially demonstrated in a constrained
environment, as our reality, for topics like problem-solving and
communication. In problem-solving, the main will produces sub-wills in lower
levels, till it reaches the final solution at the bottom level (Fig 1(a)). The
final result is a plan or a sequence of actions. See more in Appendix A.2.
Similarly, in communication, the sender encodes/converts his will into a
sequence of actions (in a language form), while the recipient on the other
side decodes the intention/will from this sequence (Fig 1(b)). In both cases,
evaluation is necessary, hence this top-down process is cyclic and non-linear.

(a) 3-level problem-solving in state space

(b) Communication model

Figure 1: Two cases of will in a constraint environment

All the above are specific cases of will, but there is also a more general
will. As recipients of reality, our main cognitive will is to find the most
appropriate/simple model to fit all the pieces/details in the right place or
to make the most sense of them111Making sense is also important for
explainability, especially storytelling modeling can provide this. Hence,
explainability should be generative and flexible, in its most general
conception. This is similar to decoding a will from a message/mystery/riddle,
and it can be rephrased as a general problem-solving task to comprehend
reality. First, it is done internally, by reorganizing our models (mostly
during a sleep phase), and later it is done externally, in any kind of
problem-solving, or in understanding a
message/story/riddle/situation/phenomena. The best model will allow us to move
from place to place in it easily, perform new actions, and produce
conclusions/solutions easily. This results with an understanding, or the
ability to control any aspect in the complex model. So in a sense, we have two
wills governing our cognition: controlling and subsequently making sense.
Obviously, these wills are enforcing each other.

Additionally, there are different categories of will, such as chronology,
causation, and purposefulness. In stories, they are very intertwined/mixed. It
is because purposefulness is a higher manifestation of will (usually applied
in humans), while causation is a lower one, usually applied to animals/objects
(e.g. ”A causes B”), and chronology is simply the way will is implemented: in
a delay. You first want, and then you try to accomplish it. Or in the case of
causation, there is a law, as a fixed kind of will (e.g. gravity), and then it
is realized. See more in Fig 2.

Figure 2: Types of will

In conclusion, purpose is everywhere, in all of our daily interactions. We try
to figure out animals’ intentions or people’s hidden will, to make sense, or
in our case to make our model complete, i.e. enable prediction. Since a
specific human has his own will, he tries to figure out other people’s will to
enforce its own will over theirs. Sometimes it is via competition, while
sometimes it is through cooperation.

However, how is will actually included in MOM? It is discussed in 5 and
Appendix A.4.

##  3 New Associations

Inspired by semantic nets, some general connections are proposed, such as
inheritance (is-a relation), instance property (is-instance-of relation),
part-whole property (part-of relation), an attribute of an object property
(has relation), assigning a value to attribute (value relation), synonyms,
antonyms/opposites and more, see [Wiktionary, 2022]. All these connections are
static and can represent stories as separate items as it is in AKREM. But to
connect these details, as a sequence of applied actions, operationability is
introduced.

##  4 Operationability

It is hypothesized that thinking is operational. Meaning it is a process,
generating new facts along the way, via some set of actions. Hence, the first
principle added to AKREM is operationability, which turns it from static to
dynamic knowledge representation. That is, unlike static connections as in
AKREM and knowledge/scene-graphs (representing facts or a scene shot) - action
connections in MOM can also be productive (produce new elements). It adds
degrees of freedom to the current cognitive model, to move in new directions
along the hierarchy, i.e. to create new hierarchies on the fly or update old
ones, via admissible actions.

Subsequently, a minimal set of primitive operations is proposed, to function
as basic operations, which can be the building blocks for more complex and
composite operations/actions. Operations such as logical relations (AND, OR,
NOT, all, each, (in)equalities, exists, count), flow operations like loop
operations (while, for) and if-else conditionals, mathematical operations
(+,-,*,/,min,max,norm,log), and other relations. This set of tools can replace
DNN units and DNN’s fixed structure, in a program-search process. It can be
implemented for example via Reservoir network, a random mix of basic rule
components/blocks, yielding an algorithm best describing an operation.

At the same time, prior knowledge is needed to be inserted, within all
elements, by including: number of visits, uncertainty, rate of update, and
measure of consolidation. The measure of consolidation is to prioritize
different options associated to some element, to separate the relevant from
the irrelevant, e.g. admissible actions, which can be used inversely in
creativity mode - by picking the less expected directions to follow.

Moreover, action’s admissibility is needed for two reasons. Firstly, due to
the elimination of entry conditions necessary for an action to be performed,
e.g. on which types (integer, string, etc). And secondly, it is due to the
ability to use High-Order Logic, as in $\lambda$-calculus, which removes any
restrictions on an object’s slot or action’s argument. Hence, relevancy is
needed to constrain action’s admissible space.

##  5 Modeling

If operationability is considered, as the addition of freedom to move in a 2D
knowledge representation, then modeling is an addition of a new dimension,
i.e. converting it to 3D. It is about extending the ”is-a” operation into a
programming abstraction, as in OOP (Object-Oriented Programming), or in
abstract mathematics, such as algebra or category theory222 Group properties
include identity object to use compositionality of an operation and its
inverse operation. This implies duality.. Meaning, that while usually semantic
networks represent this operation in a 2D graph, here the instances are
totally separated from classes, and from classes of classes, and so on.
Resulting with a multi-level of abstractions, while for simplicity two types
of levels can be distinguished, in the final LTM (Long-Term Memory), see Fig.
3. In summary, at first all different associations including operationability
are describing objects, and then abstraction extends objects as instances into
classes, which represent models. Consequently, unlike AKREM, these full models
are important for natural communication, e.g. for context-based conversations,
where undelivered missing information (common sense) is needed to be filled.

This extension has several implications. First, in perception from senses:
from the basic recognition of instances in AKREM, to a multi-level recognition
of instances and classes. Next, every element is learned and can be abstracted
(into class), i.e. objects, actions, relations, and attributes. For example,
action with attributes, relation with attributes such as strength, numeric
attribute/values as class (integer, real), group types (sets, lists, arrays)
with their group operations (slicing, union, sorting), and more. Next, this
extension enables answering the question about how will is implemented in MOM,
see 2. Alternatively to AKREM’s hierarchy by will, which it is not clear how
it can be implemented, it could be generated by abstraction, while the
will/intention will is serving as an additional and independent variable in
the models that construct the hierarchy. Additionally, feeling measures could
be included, as influencing will. Moreover, since there are several levels of
will, correspondingly there are the main variable and secondary variables
representing these wills, perhaps with different significance intensities,
depending on the abstraction level.

Finally, the novelty here, is that unlike DL which performs program-search in
an un-interpretable way, here however, additional inductive bias is
introduced: separating of models and performing program-search to relevant
actions, in consistency with other models and actions. This makes MOM both
usable and interpretable.

###  5.1 Learning the modeling

Here, model learning mechanism is proposed, where two contrary but completing
learning approaches in AI are combined [Day, 2022]: empirical, i.e. from
examples (induction), and expertise (rule-based). This is a learnable symbolic
manipulation, or can also be referred to as a hybrid approach or Neuro-
Symbolic, see [Marcus, 2003]. Empirical is bottom-up (from examples to rules),
e.g. via observation or passive interaction. Rule-based is straight from the
top, via rules in abstract language, e.g. via conversation or observation. It
can then descend to examples of these rules (deduction).

These approaches might contain models of concepts that do not belong to them
both, but only to one of them. For example, concepts that are hard to define,
like love, God, beauty, and tacit/unconscious knowledge like walking and
breathing - all can be modeled simply by examples. Similarly are the sub-
symbolic features, like audio and visual inputs - they do not have
logic/linguistic/symbolic meaning, hence should be modeled by examples, as it
is done in DL nowadays. Hence, these non-symbolic concepts can be learned via
usual non-interpretable DL. On the other hand, abstract concepts, like those
in math and sciences, that appear less in the physical reality, can be learned
solely in the top levels of LTM.

Moreover, in this hybrid approach, DL (Deep Learning) is used twice. On the
one hand, DL is extended from its too constraint program-search to be much
more flexible, if more operations are added as building blocks, see 4. Hence,
symbolism is learned and adaptive just like in DL, differently from
expert/rule-based AI. On the other hand, different input sensors are fused to
represent specific symbols/concepts, i.e., the uninterpreted features in DL
become symbolic tokens (Fig. 3).

Figure 3: Proposed cognitive model basic diagram

The reason the hybrid approach is preferred over DL-only, is that DL usually
does not implement compositionality, modularity and abstraction [Dickson,
2022]. One of the effects of this shortcoming is the shortcut effect, where
the DL categorizes something due to the wrong reasons. It can be solved in a
system, that learns a model with alignment and consistency-check with other
models learned so far, which MOM supplies (continual learning).

Additionally, the topmost level is actually temporal and used for creativity
and problem-solving. In this level, temporal new abstractions are created, by
stripping off attributes/actions/relations, thus connecting distant or
different abstractions to perform analogy or transfer learning between
different domains. For example, the abstraction is via the number of edges in
the polygon classes (Fig. 3).

Furthermore, learning can be divided into online and offline modes. In waking
periods, i.e. when sensors are active, the learning is online and minimal
since most resources are dedicated to fast response (e.g. fast optimization
into local optimums). However, during sleeping periods, sensors are inactive,
and previous memories can be used for improving models to make overall sense,
e.g. larger time scale is used to generate causal relations in models. In such
a case, it is a slow processing, implemented e.g. as a Neural Architecture
Search or a Genetic Algorithm, to get out of local minima and search for a
global one.

Finally, another issue precedes learning: how to obtain separate models at
all. One way, is like the DENN (Dynamic and evolving NN) idea [Komarovsky,
2022a], i.e. always learning the ”model of everything” while refining it more
and more with every new experience, such that new sub-models are produced. The
idea here, is like Jeff’s hierarchy [Hawkins and Blakeslee, 2007], where the
top model is always reached, at perception from senses, and it decides which
lower model will handle the situation. For example, in recognizing a specific
type of problem, it chooses the most appropriate model for solving this
problem. Or, when encountering new knowledge, it selects the most appropriate
model to handle its assimilation in the current memory of models.

Another way to facilitate modeling evolution is via consolidation.

##  6 Consolidation

So far, the cognitive model has been presented in its mature state. Now, the
discussion is about how to reach it. This is a process in time, which is
mainly based on consolidation.

Consolidation is about transforming from chaos to some stable order of
patterns, or from a continuous realm to a discrete one, as in quantum
mechanics. An infinite amount of details is hard to handle (i.e. to understand
and then to control), therefore consolidation to fewer patterns is required.
Consolidation also allows for fuzzy logic and categories [Wyler, 1995].

Consolidation can be expressed in many forms, such as:

  * •

in the conversion of sub-symbolic to symbolic, for any type of element

  * •

in cognitive evolution: from flexible (at infancy) to less flexible (at
adulthood)

  * •

in modeling, at program search, from huge hypothesis space for possible
programs to a small set of hypotheses (as in DL). It is both in the micro
(within models) and in the macro (between models)

  * •

in testing multiple versions of an unknown model, and finally converging into
less/one version(s) that are/is consistent with evidence

  * •

and in grouping/abstraction, where some separate elements become connected

Note that causality is a special case of modeling, a spatio-temporal one,
where re-occurrence is consolidated. More generally, re-occurrence help in
learning both static objects and dynamic basic/composite events (equivalent to
scenarios/scripts in OOP).

Additionally, MOM enables multiple parallel versions of the same thing, since
any specific topic or subject can have multiple theories/models, sometimes in
conflict. Hence, like in the quantum superposition realm, multiple-version
combinations could be tryout, and consolidation can help in collapsing them
into fewer versions. Those versions should make the most sense, i.e. to be
consistent on different occasions or supporting the majority of evidence.
Thus, it just maybe, that at infancy, a highly uncertain period, there are
many versions created, and with time - only the most consistent ones survive
(consolidate).

Lastly, two operations help in producing consolidation. On the one hand, to
deal with a stochastic environment and ambiguous signals, repetition provides
memory prioritized by relevancy. Repetition is never exactly over the same
thing, but rather over many different examples of a thing. Repetition is
needed also with guided tutoring of an AGI agent.Conversely, sparsification is
about reducing irrelevant signals.

###  6.1 Reusability

An additional form of consolidation is reusability, since the more learning
progresses, the fewer new models are proposed in favor of using existing ones.
Hence, reusability is expressed via exploration (mostly at early stages) verse
exploitation (in stable or mature stages), as in Reinforcement Learning. In
the beginning, many possible codes are generated for models, but as time goes
by the process is less exploratory and more exploitative, i.e. there is more
emphasis on retrieving known codes, while testing fewer new codes in parallel.
In addition, reusability aligns perfectly with abstraction/grouping, in a
constrained environment and limited resources. They are both needed to hold
control of as much as possible, with minimum effort, i.e. without generating
many models of each thing.

In practice, reusability is about using less of the initial available tools,
as the learning evolves. Meaning, while regular DL tools (if, sum, activation
function) or the primitive tools 4 can be used for program search of basic
action methods or relation methods, the new methods apply reusability. In such
methods, less primitive tools are used while the current methods are used
more, thus encouraging more connectivity in the network.

Moreover, Functional Programming can be applied to assist reusability. On the
one hand, the general/outer structure is OOP, i.e. elements are grouped in an
OOP fashion. On the other hand, methods are kept in a pure operational
immutable form [Chen, 2019, Van Roy et al., 2009]. Meaning, having small and
simple methods, which maximally reuse other functions, and without inner
variables, due to objects-memory-only assumption. Meaning, methods that are
comprised of other methods, as much as possible. This is
compositionality/grouping applied in actions. See Fig. 4.

Figure 4: Actions, objects, compositionality, and reusability

##  7 Cognitive model comparison

Here all models developed so far are compared, in Fig. 5.

Figure 5: Comparison table of models discussed so far

In summary, DENN stores each new combination of events, while AKREM stores
dynamically in episodic memory any newly encountered combination of basic
events. Events which are stored separately in two types of memory. MOM unites
those separate memories into one dynamic operational memory, consisting of
concepts, actions, relations and any instance of those.

##  8 Conclusion

The following is the summary of the paper including some key takeaways.

First, a new cognitive model is introduced to join the existing cognitive
architectures, in the form of dynamic operational memory of models and
instances. In it, a holistic approach is embraced, assuming that intelligence
should be highly versatile and diverse, instead of ”picking one side”.

Next, our model includes will as an essential part of the modeling process.
Thus, in case of its absence, it turns most of the learned models to be very
partial. In the OOP formulation, the will is an additional variable, and it is
mostly significant in the top level while it is least significant in the
lowest one.

Next, operationability turns static knowledge representation into a dynamic
one, thus enabling cognitive processes. The actions are learned via regular
program search, with either DL or other tools, in a self-supervised manner.

Next, one way to ensure that the continual learning is consistent, is by
implementing local learning, i.e., concentrating on updating only one/some
model(s), while confirming compatibility with other models. A model can be
learned either from examples or directly by using existing operations
(logically). Another way to ensure that learning is consistent, is by a slow
process of consolidation. It is ensured by maintaining a high level of
flexibility over a long period, while pursuing more and more consistency
within and between models.

Next, reusability is utilized to enhance connectivity between models, instead
of learning them as separate entities.

Finally, the cognitive model is designed via inverse engineering. Meaning,
starting from our highly aware and mature cognitive state of mind, and then
tracking back in time to study its evolution.

##  9 Future Work

The main problem is how to implement a cognitive system, that produces the
appropriate models, i.e. how grouping/clustering occur, to generate the right
models. Also, how these models produce new ones by the correct compositions.

In addition, there is the issue of how sub-symbolic become symbolic. Perhaps
the models produce objects and actions directly upon sub-symbolic data.
Furthermore, if continuing this line of thought, then models may be removed at
all, which converts this problem to pure DL-based approach.

Additionally, relevant to the last issue, is model evolving. Is it model
refinement of some main model to sub-models, which controls how models of
knowledge are used, or is it that all the models are separate. And if it is by
refinement, is it one large DL-based model, and all the rest are knowledge
models, or if we continue this line of thought - again, end up with pure DL-
based one huge model, containing implicitly all the different models, their
actions and attributes. But then how elements and abstraction are implemented
in such a model? More about the suggestion above see Appendix A.3.1.

Finally, though hierarchy by abstraction can be implemented, but how can it be
implemented by will, i.e. how to decide when and what to group in such a
hierarchy?

These are all open questions to deal with.

P.S.: Neuro-Symbolic AI for me is merely taking inspiration of class-based
structure, to act as the final stage of learning, while DL is the main tool to
reach it. So it is all about flexibility of DNNs, only that we use
consolidation to finally reach symbols. Another implication of this, is
memory. First, since it is vague and mostly reconstructed. It means it is not
recorded accurately. And second, since it probably used in sleeping periods
similarly in a vague form.

##  Appendix A Appendix

###  A.1 Examples of MOM in action

Fig. 6 contains examples of cognition processes. As seen, actions denoted as
arrows, can perform changes in several objects to their different attributes.
High admissibility expressed via salient color. Fig. 6(b) is a MOM
representation of evolving state, representing a story. A state is consisting
of several objects (joining/leaving as the story evolves), including their
attributes and actions that change the state. The story: ”David entered his
room. He searched for something on the floor. Then he searched in the basket.
Then he searched under his bed, and was thrilled to find the ball there. In
the meanwhile, his mother entered home. She put her keys on the desk. Then she
removed her shoes and put her sunglasses on the desk. Then she searched for
David, found him, and they sat to eat lunch together”. The same story is
represented via AKREM, without the evolution of details, see the video link in
[Komarovsky, 2022b]. Note, that if repeated often, the sequence of David or
anybody searching in some place can be grouped/abstracted as an event class,
also referred to as Trans-Frame [Minsky, 1988].

Next, Fig. 7 contains examples of model learning, based on Fig. 3. The
assumption here, is that similarly to DNN pattern matching and then executing
some task - here it is performed explicitly, via if condition as pattern
matching, and execution following. Each sub-figure contains the type of
interaction (passive or active) and the different modalities involved:
A=audio, V=vision, P=physical act.

As seen, operation in MOM involves time, i.e. it can be either immediate or
include past/future of any scale, which enable causality modeling. Also,
naming, or the inclusion of language to describe objects is not necessary in
model learning. The learning still occurs, even before its name is introduced,
or if it is forgotten for some reason.

Finally, the conditions in Fig. 7 could be alternatively grouped/abstracted as
event classes instead of being learned as an action. Meaning, the pattern
matching can be replaced by event class to be recognized, and the possible
reaction to this pattern can be formed as an admissible action in such a
class. For example, ”OR” can assign the same action to different objects, and
”AND” assigns an action to a group of objects.

(a) Developing equations (grouped chronologically)

(b) A part of a story

Figure 6: Examples of cognition processes

(a) Multi-modal fusion

(b) Causality relation1

(c) Causality relation2

(d) Interaction

(e) Reinforcement Learning (Pavlov experiment)

Figure 7: Examples of model learning

###  A.2 Problem-solving and Designing Appendix

####  A.2.1 Problem-solving

Problem-solving is a broad topic, which is about handling any given situation,
and not only solving puzzles/mysteries/science. In any such situation, we can
either recognize a previous similar pattern (System 1), and apply automatic
reaction, i.e. immediate resolution, or if it is not the case, try to generate
a new solution (System 2). In this section, the latter option is discussed.

In this context, it is represented within some state space, where a problem is
situated at some point or a region in the space. Additionally, a problem is
expressing the current (problematic) situation, involving a general will to
get out of this situation. Hence, a will is not yet formulated at this stage
(Fig. 8(a)). Next, it is about deciding upon some goal states to be reached,
to gain a desired resolution. When goal states are defined, the will become
purposeful. Purpose is a more definite will, because it gives some
“direction”, either a vague direction or a strong one, to specific goal states
(Fig. 8(b)). Since will derives action(s), it is represented similarly to an
action in the state space - as a vector, transmitting one situation to
another. Meaning, will is defining the direction the agent wants to move,
before it found the admissible/legitimate/allowable way to realize it, in the
given environment. Finally, the agent starts to plan how to solve the given
problem, under given constraints, i.e. where one cannot fulfill its will
directly, but instead look for some legitimate way to accomplish this, in the
given circumstances.

(a) First: the problem

(b) Next: will turns into a purpose

Figure 8: Phases of will refinement in problem-solving

After the will is refined and transferred to a purpose, the search for a
solution is initiated, and it is depicted in Fig 1(a). This is the next phase
of problem-solving: realization. The figure demonstrates a coarse-to-fine
hierarchy, where the will along with its refinement, is placed at a top level.
This level is vague, since nothing is perceived clearly about the ground
level. However, descending the levels reveal more and more details, and get
the will more closely to realization. It is similar to the process of zooming
in on a geographical map. Higher levels propose general models as potential
stations in a possible trajectory from a problem state to a goal state. Then
at descending, finer models are proposed, consistent with the upper levels, to
move from a problem to a goal state. The search at any level can be performed
by any heuristic/learned model, such as back/forward chaining, Depth-First
Search/Breadth-First Search techniques, or any combination of those. Note the
mismatch between our model level (proposed solution) and data level (detailed
solution), in Fig 1(a). It is due to our inclination towards abstracting, i.e.
memorizing the essences and less the details, which is essential for efficient
learning, as described also in 6, where it is better to learn several patterns
than to lose yourself in a non-pattern realm, where all we see are details.

In summary, this approach is non-local, i.e. similar to Means-Ends Analysis,
it is looking simultaneously at the whole region, only within different
resolutions. It is also cyclic and non-linear, both in the will-refining stage
and in the realization stage. At will refining, it is since sometimes the goal
states cannot be reached, so other states are needed to be generated,
sometimes as a compromise. At the realization stage, it is since descending in
levels might result in conflicts or failures, due to misalignment between the
lowest models of reality and the actual reality. Hence, returning to higher
levels for trying different solutions is needed.

####  A.2.2 Designing

While in problem-solving, the will was generated from a problem, i.e. growing
from an initial state, in designing it is the opposite. Here, instead, it is
growing from the final state(s), searching for the best state to start the
full solution from. It is like creating a story backward: starting from the
end, to reach some beginning (Fig 9).

In designing there is a goal and a will to go there, but no specification of
the problem or the initial states. So it is an iterative process, starting
from searching for a problem to reach the goal, then continuing with a
specific will connecting the problem with the goal, resulting with a problem
to solve.

Figure 9: Designing approach

####  A.2.3 Summary of Problem-Solving and Designing

One can spot a duality here also. On the one hand, problem-solving is an
analytical perspective, looking for a resolution or finishing a problem, by
usually a systemic view, breaking it to parts and then looking for some
appropriate solution, that serves as a better state than the one we started
with (problem state). On the other hand, designing is based on a holistic
perspective, where instead of finding a fast/analytical resolution to a
problem (“to make everyone happy and go on with our lives”) it is about
empathy/consideration, i.e. it is about looking for the roots of the problem,
and not just shutting it down quickly. It takes the opposite approach: instead
of reducing the problem, it tries to track its sources and thus solving the
causes that generated this problem state/situation. By doing so, it searches
for a better problem to solve, which solves multiple other problems. Either
way, will is either getting somewhere (goal) or getting out of something
(problem).

###  A.3 Implementation

####  A.3.1 Combining Will and Modeling

The final question, is how all the discussed above, i.e. in A.2, and in 2,
i.e. will-related topics, are combined with the operational model. There are a
few options, as discussed in 9, but we emphasize one of them here. One option,
is to have one main supervising model, that depending on the category of the
situation, assigns the proper model to handle it. E.g. model for problem-
solving, for learning, and for story message (where it connects separate
events sequentially). Conversation for example is about taking turns, waiting
till me/other side finished, recognizing our models, etc. Perceiving fictional
information is treated differently than factual information, and so on. In
conclusion, this option derived since problem-solving and alike are very
complex models, which is why the suggestion to separate them from the
knowledge models. But it extends further - perhaps there is separation of
model representation. May be some models can be represented as operational
classes, but others cannot. These others could be not interpretable nor can be
explained by the agent, since they are in the background of thinking itself,
thus they are “hidden” or implicit. See Fig. 10.

Figure 10: Separating cognitive and knowledge models

####  A.3.2 Multi-scale Consolidation in Model Learning

Next question, is how models can be learned separately? One solution is by
assuming some initial network of unlearned models, see Fig. 11(b). But before
that we assume consolidation in multiple scales, as if there is consolidation
also in scaling (discrete amount of them). It can be encountered through many
phenomenon in nature, e.g. in the universe (consolidation into stars/solar-
systems and galaxies), in fractals (such as snow-flakes), and in other
recursive structures. See for example the nested structure in Fig. 11(a), and
in the transition from Fig. 11(b) to Fig. 11(c), consolidation in multiple
levels, both in micro (within models), and in macro (between models). We see
that modeling or reorganization of inner elements, is occuring at many levels
of models, i.e. from the basic models to the most complex ones.

(a) Nested DNN structure

(b) Initial Nested DNN

(c) Learned Nested DNN

Figure 11: Nested DNNs for model learning

###  A.4 Attention

After assuming a bunch of unlearned models, Fig. 11(b), we can assume that
will, acting like a flashlight or a beacon, produce consistent attention (over
time) to learn/attend each model (or several of them) separately.

This explains why an infant is usually very focused over his toys (e.g. a
ball), and tracking them is essential for this process. This effect stick till
adulthood, also in the process of using the cognitive model (i.e. after the
learning stage). It is the need to be attentive only to a limited set of
models ($7\pm 2$ items in WM). See examples in Fig. 12.

(a) Attending specific model1

(b) Attending specific model2

Figure 12: Local model learning via attention

Next question is how this will is applied in story telling/hearing and in
problem solving? For example, in my presentation, the problem-solving
3-layered slide actually showing these beams, searching for solutions!

We can see it in the following Fig. 13.

Figure 13: Learning reframed as problem-solving task

We can say that learning, is making-sense type of problem-solving. So again,
there is will, coming from the top, like a projector, focusing on one/few
models, while tracking it in the real world. More accurately, we should have
changed the top will, not as a purpose to reach but as the point-wise will at
the start of a problem.

Moreover, we could say that the hierarchy is abstraction, as claimed earlier,
and will is actually only on the top but ”shining” directly on the models.
Then, we could say that during waking hours, an infant is gathering instances
of its current models, e.g. a ball, and at sleeping, he uses these instances
to train his models, for the purpose of making sense. The waking hours do not
do it, they can only perform cognitive operations, which is actions in these
models. So first, he tries to figure out different models, then he tries to
model them also in time, thus able eventually to track them, which is a
validation of the correctness of his ”ball” model for example. Because the
final test of his model is prediction, hence temporal modeling is what enables
prediction, or more specifically forecasting (prediction in time).

Note, that attention to a few models also implies that just as humans, AGI
agent need not to understand and model everything, but only what it is focused
on or interested with. Also, there is the idea of bidirectional attention,
which is bottom-up (external) verse top-down (its own will), and describes the
competition between having a (strong) will to be highly influenced by the
outside. In AGI’s case, it should be mostly navigated by external guidance, if
will is not engineered into it.

In addition, attention can have different ”focal length”, like the theory of
vision, having small pinhole perception at lower levels, and a bigger one at
higher ones. Meaning, the ability to sometimes see small details and sometimes
see the big picture. In model attention it is the same: we can both have low-
level more detailed attention on smaller models, upto a high-level attention
for more general or composite models. In comparison to classical object
detection in computer vision, high-level concepts use only the higher-level
features for the classification task, but more generally there is no reason
not to be attentive to low-level features whenever is needed.

Finally, attention in our perspective is very similar to the attention in DL,
only without regulation. Meaning, without considering the ideal state of
consolidating into symbolic reasoning of models and operations and most
importantly allowing for dynamic abstraction. However, DL’s attention is
similar in that it too allow for multiple implicit functions in a given
learning NN, since it react differently depending on the input. In other
words, the DNN can be regarded as a group of undeclared models/functions,
generated by attention units, thus implicitly implement compositionality and
reusability.

## References

  * Chen [2019] Jing Chen.  A brief survey of “programming paradigms”, 2019.  URL https://medium.com/@jingchenjc2019/a-brief-survey-of-programming-paradigms-207543a84e2b.
  * Day [2022] Taylor Day.  Knowledge-based artificial neural network modeling assessment: integrating heterogeneous genomics data to uncover lifespan regulation.  2022\.
  * Dickson [2022] Ben Dickson.  4 deep thoughts on deep learning in 2022, 2022.  URL https://venturebeat.com/ai/four-thoughts-on-ai-deep-learning-in-2022/.
  * Hawkins and Blakeslee [2007] Jeff Hawkins and Sandra Blakeslee.  _On intelligence: How a new understanding of the brain will lead to the creation of truly intelligent machines_.  Macmillan, 2007.
  * Komarovsky [2022a] Shimon Komarovsky.  Dynamic and evolving neural network for event discrimination.  In Ben Goertzel, Matt Iklé, Alexey Potapov, and Denis Ponomaryov, editors, _Artificial General Intelligence_ , pages 40–50. Springer International Publishing, 2022a.  ISBN 978-3-031-19907-3.
  * Komarovsky [2022b] Shimon Komarovsky.  Hierarchical temporal dnn and associative knowledge representation.  In Ben Goertzel, Matt Iklé, Alexey Potapov, and Denis Ponomaryov, editors, _Artificial General Intelligence_ , pages 51–61. Springer International Publishing, 2022b.  ISBN 978-3-031-19907-3.
  * Marcus [2003] Gary F Marcus.  _The algebraic mind: Integrating connectionism and cognitive science_.  MIT press, 2003.
  * Minsky [1988] Marvin Minsky.  _Society of mind_.  Simon and Schuster, 1988.
  * Van Roy et al. [2009] Peter Van Roy et al.  Programming paradigms for dummies: What every programmer should know.  _New computational paradigms for computer music_ , 104:616–621, 2009.
  * Wiktionary [2022] Wiktionary.  Semantic relations, 2022.  URL https://en.wiktionary.org/wiki/Wiktionary:Semantic_relations.
  * Wyler [1995] Oswald Wyler.  Fuzzy logic and categories of fuzzy sets.  In _Non-Classical Logics and Their Applications to Fuzzy Subsets_ , pages 235–268. Springer, 1995.


# On the Ramsey Numbers of Odd-Linked Double Stars

Chaitanya D. Karamchedu
Harvey Mudd College
Claremont, CA, 91711
<EMAIL_ADDRESS>
&Maria M. Klawe
Harvey Mudd College
Claremont, CA, 91711
<EMAIL_ADDRESS>

###### Abstract

The linked double star $S_{c}(n,m)$, where $n\geq m\geq 0$, is the graph
consisting of the union of two stars $K_{1,n}$ and $K_{1,m}$ with a path on
$c$ vertices joining the centers. Its ramsey number $r(S_{c}(n,m))$ is the
smallest integer $r$ such that every $2$-coloring of the edges of a $K_{r}$
admits a monochromatic $S_{c}(n,m)$. In this paper, we study the ramsey
numbers of linked double stars when $c$ is odd. In particular, we establish
bounds on the value of $r(S_{c}(n,m))$ and determine the exact value of
$r(S_{c}(n,m))$ if $n\geq c$, or if $n\leq\lfloor\frac{c}{2}\rfloor-2$ and
$m=2$.

##  1 Introduction

For any graph $G$, the ramsey number $r(G)$ is the smallest positive integer
$r$ such that any $2$-coloring of the edges of the complete graph on $r$
vertices ($K_{r}$) contains a monochromatic subgraph isomorphic to $G$.
Famously, the exact determination of ramsey numbers is an exceedingly
difficult computational problem that becomes intractable beyond small cases.
As such, the ramsey numbers of various classes of graphs must be determined
analytically, and some (such as the ramsey numbers of complete graphs,
$r(K_{n})$) have proved to be notoriously difficult to determine; as such,
there are many open or partially open problems. However, the ramsey numbers of
many classes of simple graphs (including stars, paths, and cycles) have been
determined exactly: see [1] for a survey of known results of ramsey numbers as
of January 2021.

In 1979, Grossman, Harary, and Klawe investigated the ramsey numbers of one
such family of graphs known as double stars ([2]). A double star is defined as
the union of two disjoint stars with an edge joining their centers. Grossman
et al. solved the ramsey numbers of double stars in most cases, and more
recently Norin, Sun, and Zhao have made some progress in the remaining open
cases for double stars ([3]). See Section 4 for more information. Motivated by
the results of Grossman et al. and Norin et al., here we investigate the
ramsey numbers of a generalization of double stars, which we refer to as
linked double stars.

Figure 1: Example of a $S_{5}(7,4)$

We define a linked double star as the union of two disjoint stars with a path
joining their centers. In particular, for $n\geq m\geq 0$, the linked double
star $S_{c}(n,m)$ is the graph on the points
$\\{a_{1},\ldots,a_{c},v_{1},\ldots,v_{n},w_{1},\ldots w_{m}\\}$ with the
edges

$\\{(a_{1},v_{i}),(a_{1},a_{2}),(a_{2},a_{3}),\ldots,(a_{c-1},a_{c}),(a_{c},w_{j}):1\leq
i\leq n,1\leq j\leq m\\}.$

Note that above, $a_{1}$ and $a_{c}$ are the centers of the $n$-star and
$m$-star respectively, and the path from $a_{1}$ to $a_{c}$ is the link
between the two stars. For reference, Figure 1 shows an example of a
$S_{5}(7,4)$.

In this paper, we will primarily be studying the ramsey numbers of odd-linked
double stars. Given the above definition of a linked double star, an odd-
linked double star simply refers to a linked double star wherein the link has
an odd number of vertices (i.e. $c=2p+1$ for some $p\in\mathbb{N}$).

We exactly determine the ramsey numbers of two groups of odd-linked double
stars. In particular, if $c=2p+1$, we find that

  1. 1.

$r(S_{c}(n,m))=2(n+m)+c-2$ if $n\geq c$

  2. 2.

$r(S_{c}(n,2))=n+3p+3$ if $n\leq p-2$.

In Section 2, we establish lower bounds on the ramsey numbers of odd-linked
double stars, which hold irrespective of the relative size of the stars and
the link. In Section 3, we establish upper bounds, which in the particular
cases of the sizes of $n$ and $m$ described above, happen to be precisely
equal to the lower bounds determined in Section 2 (thus determining the ramsey
numbers exactly). Finally, in Section 4, we list open problems suggested by
this work.

##  2 Lower bounds

In this section, we will establish lower bounds on the ramsey numbers of all
odd-linked double stars. From this point forth, we will assume (and use
interchangeably) $c=2p+1$ for some $p\in\mathbb{N}$, where again $c$ is the
number of vertices on the link. The general statement of the lower bounds are
presented in Theorem 2.1, the proof of which will be provided by applying the
subsequent lemmas.

######  Theorem 2.1.

The ramsey numbers of the odd-linked double stars satisfy

$r(S_{c}(n,m))\geq\begin{cases}2(n+m+p)-1&\mbox{for }n+m\geq p+2\\\
n+m+3p+1&\mbox{for }n+m\leq p+2\end{cases}.$

######  Lemma 2.2.

$r(S_{c}(n,m))\geq 2(n+m+p)-1$.

###### Proof.

Consider a $2$-coloring of $K_{2(n+m+p)-2}$, where the red subgraph consists
of $K_{n+m+p-1}\cup K_{n+m+p-1}$, so that the blue subgraph is the complete
bipartite graph $K(n+m+p-1,n+m+p-1)$. It is easy to see that there is no red
$S_{c}(n,m)$, since $S_{c}(n,m)$ is connected and has $n+m+c$ vertices. But
there also cannot be a blue $S_{c}(n,m)$, since when a $S_{c}(n,m)$ is
presented as a subgraph of a bipartite graph there must be $n+m+p$ vertices
that belong to the same partition. ∎

######  Lemma 2.3.

$r(S_{c}(n,m))\geq n+m+3p+1$.

###### Proof.

Consider a $2$-coloring of $K_{n+m+3p}$, where the red subgraph consists of
$K_{p}\cup K_{n+m+2p}$, so that the blue subgraph is the complete bipartite
graph $K(p,n+m+2p)$. It is easy to see that there is no red $S_{c}(n,m)$ since
$S_{c}(n,m)$ is connected and has $n+m+c$ vertices. But there also cannot be a
blue $S_{c}(n,m)$, since when a $S_{c}(n,m)$ is presented as subgraph of a
bipartite graph there must be $n+m+p$ vertices that belong to one partition,
and at least $p+1$ vertices belonging to the other partition. ∎

Combining the results of Lemmas 2.2 and 2.3, the proof of Theorem 2.1 is
completed.

##  3 Upper bounds

In this section, we will establish upper bounds on the ramsey numbers of odd-
linked double stars.

We begin, as before, by stating the main theorem(s), and then prove the
result(s) by a series of lemmas which together imply the desired result(s).

######  Theorem 3.1.

If $n\geq 2p+1$, the ramsey numbers of odd-linked double stars satisfy

$r(S_{c}(n,m))\leq 2(n+m+p)-1.$

######  Theorem 3.2.

If $n\leq p-2$, the ramsey numbers of odd-linked double stars satisfy

$r(S_{c}(n,2))\leq n+3p+3.$

### Proof of Theorem 3.1

We will first introduce some notation which will be used throughout this
section, the approach taken here is largely motivated by the strategy used by
Grossman et al. in [2]. Consider some fixed $2$-coloring of a complete graph
$K$, and let $V$ denote the vertex-set of $K$. For a particular vertex $v\in
V$, let $R(v)$ and $B(v)$ denote the sets of vertices joined to $v$ by a red
and blue edge respectively. In this section, we may often use red-$d(v)$ to
denote $|R(v)|$ and similarly for blue-$d(v)$. For a particular subset of
points, $W\subseteq V$, define red-$d_{W}(v)$ as

$\text{red-}d_{W}(v)=|R(v)\cap W|$

and similarly for blue-$d_{W}(v)$. We will also consider a particular vertex
$u\in V$, where $u$ is chosen to have maximum monochromatic degree. Thus we
may assume without loss of generality that
$\text{red-}d(u)\geq\text{red-}d(v)$ and $\text{red-}d(u)\geq\text{blue-}d(v)$
for all $v\in V$. For convenience, we will define $A=R(u)$ and $B=B(u)$, and
write

$|A|=n+m+p-1+k$

for some integer $k\geq 0$. Finally, unless explicitly stated otherwise, we
shall assume that $p\geq 1$ and $m\geq 1$.

We will now provide a series of lemmas that will be used repeatedly in this
section.

######  Lemma 3.3.

(Due to Yu and Li, see [4]) A broom graph, $B(n,c)$, is equivalent to
$S_{c}(n,0)$. The ramsey numbers of brooms are

$r(B(n,c))=\begin{dcases}n+c+\left\lceil\frac{c}{2}\right\rceil-1&\text{if
}c\geq 2n-1\\\ 2(n+c)-2\left\lceil\frac{c}{2}\right\rceil-1&\text{if }4\leq
c\leq 2n-2\end{dcases}.$

Note that if $n=1$, or $1\leq c\leq 2$, then the ramsey numbers of the
corresponding brooms can be solved exactly by the ramsey numbers of paths and
stars. See [4] for more information. If $c=3$, then since $B(n,3)=S_{2}(n,1)$,
the ramsey numbers of the corresponding brooms are solved by the results of
Grossman et al. See [2] for more information.

######  Lemma 3.4.

If $0\leq k\leq n-p-1$, and $n\geq p+1$, then every such $2$-coloring of a
$K_{r}$ admits a monochromatic $S_{c}(n,m)$, for $r\geq 2(n+m+p)-1$.

###### Proof.

Clearly it is enough to prove the lemma for $r=2(n+m+p)-1$. We will prove this
lemma by induction.

  * •

Base Case:

Let $m=1$. Then we wish to show that every $2$-coloring of a $K_{2n+2p+1}$
satisfying $k\leq n-p-1$ contains a monochromatic $S_{c}(n,1)$. Observe that
$S_{c}(n,1)$ is equivalent to the broom graph $B(n,c+1)$. By Lemma 3.3, we
know that since $n\geq p+1$, every $2$-coloring of a $K_{2n+2p+1}$ admits a
monochromatic $B(n,c+1)$. Thus the base case is completed.

  * •

Inductive Step:

Now, suppose the proposition holds for some fixed $m-1$, and any $n\geq p+1$.
I.e., suppose that any $2$-coloring of a $K_{2n+2(m-1)+2p-1}$, with $k\leq
n-p-1$, must admit a monochromatic $S_{c}(n,m-1)$. Then we wish to show that
any $2$-coloring of a $K_{2(n+m+p)-1}$ must admit a monochromatic
$S_{c}(n,m)$, if $n\geq p+1$ and $k\leq n-p-1$.

Consider some fixed $2$-coloring of a $K_{2(n+m+p)-1}$. From the induction
hypothesis, since

$\displaystyle k$ $\displaystyle\leq n-p-1$ $\displaystyle<(n+1)-p-1$

the $2$-coloring must admit a monochromatic $S_{c}(n+1,m-1)$, which we may
assume is red. Let $Q$ be the red $S_{c}(n+1,m-1)$ and let $x$ be the vertex
in $Q$ at the end of the path of length $2p+1$ that begins at the
$(n+1)$-star. Now, suppose to the contrary that this $2$-coloring avoided a
monochromatic $S_{c}(n,m)$. In order to avoid a red $S_{c}(n,m)$, it must be
the case that $x$ be blue-adjacent to the $n+1$ spoke vertices of the $n+1$
star in $Q$, as well as every vertex in $V\backslash Q$. Thus,

$\displaystyle\text{blue-}d(x)$ $\displaystyle\geq n+1+|V\backslash Q|$
$\displaystyle=2n+m-1.$

But since (by the definition of $k$) the maximum monochromatic degree of any
vertex is $n+m+p-1+k$, it must be the case that

$n+m+p-1+k\geq 2n+m-1.$

Solving for $k$,

$\displaystyle k$ $\displaystyle\geq n-p$

a contradiction.

∎

######  Corollary 3.4.1.

If $0\leq k\leq p$, and $n\geq 2p+1$, then every such $2$-coloring of a
$K_{r}$ admits a monochromatic $S_{c}(n,m)$, for $r\geq 2(n+m+p)-1$.

######  Lemma 3.5.

(Due to Jackson, see [5]) Let $G(a,b,k)$ is a simple bipartite graph with
bipartition $(A,B)$ where $|A|=a\geq 2$, $|B|=b\geq k$, and each vertex of $A$
has degree at least $k$. If a graph $G(a,b,k)$ satisfies $a\leq k$ and

$b\leq 2k-2$

then it contains a cycle of length $2a$.

######  Lemma 3.6.

Consider some fixed $2$-coloring of a $K_{2(n+m+p)-1}$. If $n\geq p+1$, $k\geq
p+1$, and if there is a red cycle $Q$ in $A$ of length $2p$, then this
$2$-coloring admits a monochromatic $S_{c}(n,m)$.

###### Proof.

If $k\geq p+1$, then $|A|\geq n+m+2p$. Suppose there was a red cycle $Q\in A$
of length $2p$. Let $X=(A\cup B)\backslash Q$. Observe $|X|=2n+2m-2$. If any
$q\in Q$ satisfies $\text{red-}d_{X}(q)\geq m$, then there exists a red
$S_{c}(n,m)$ formed by following $Q$ back for $2p$ vertices, starting from
$q$, and connecting the last vertex back to $u$. This defines a red
$S_{c}(n,m)$ with its $m$-star at $q$ and its $n$-star at $u$. Therefore all
$q\in Q$ satisfy

$\displaystyle\text{blue-}d_{X}(q)$ $\displaystyle\geq 2n+m-1$
$\displaystyle\geq n+m+p.$

Now if there is a blue path of length $2p+1$ between $Q$ and $X$ with both
endpoints in $Q$, then there exists a blue $S_{c}(n,m)$ between $Q$ and $X$.
Since $2n+m-1\leq|X|\leq 2(2n+m-1)-2$, we can conclude by Lemma 3.5 that there
is a blue cycle of length $4p$ between $Q$ and $X$, which contains in it a
blue path of length $2p+1$ with both endpoints in $Q$.

∎

######  Lemma 3.7.

Consider some fixed $2$-coloring of a $K_{2(n+m+p)-1}$. If $n\geq p+3$, $k\geq
p+1$, and there is a red cycle $Q$ of length $2p+2$ in $A\cup B$ with
alternating vertices in $A$, then this $2$-coloring admits a monochromatic
$S_{c}(n,m)$.

###### Proof.

If $k\geq p+1$, then $|A|\geq n+m+2p$. Suppose there was a red cycle $Q$ of
length $2p+2$ in $A\cup B$, with alternating vertices in $A$. Let $X=(A\cup
B)\backslash Q$, let $Y\subset A$ be the set of alternating vertices on $Q$ in
$A$, and let $Z=Q\backslash Y$. Observe that $|X|=2n+2m-4$, and $|Y|=|Z|=p+1$.
If any $z\in Z$ satisfies $\text{red-}d_{X}(z)\geq m$, then there exists a red
$S_{c}(n,m)$ formed by following $Q$ back for $2p$ vertices. This will end at
some $y\in Y$, and adding the edge $(u,y)$ will define the link of a red
$S_{c}(n,m)$ with the $n$-star at $u$ and the $m$-star at $z$. Therefore we
may assume that all $z\in Z$ satisfy

$\displaystyle\text{blue-}d_{X}(z)$ $\displaystyle\geq 2n+m-3$
$\displaystyle\geq n+m+p.$

Now if there is a blue path of length $2p+1$ between $Z$ and $X$, with both
endpoints in $Z$, then there exists a blue $S_{c}(n,m)$ between $Z$ and $X$.
Since $2n+m-3\leq|X|\leq 2(2n+m-3)-2$, we can conclude by Lemma 3.5 that there
is a blue cycle of length $2p+2$ between $Z$ and $X$, which contains in it a
blue path of length $2p+1$ with both endpoints in $Z$. ∎

######  Lemma 3.8.

(Due to Faudree, Shelp, and Rosta, see [6] and [7]) Let $C_{n}$ and $C_{m}$
denote cycles of length $n$ and $m$ respectively. Then the ramsey numbers of
cycles satisfy

$R(C_{m},C_{n})=\begin{cases}2n-1&\mbox{for }3\leq m\leq n,m\mbox{ odd
},(m,n)\neq(3,3)\\\ n-1+\frac{m}{2}&\mbox{for }4\leq m\leq n,m\text{ and
}n\mbox{ even },(m,n)\neq(4,4)\\\ \text{max}(2m-1,n-1+\frac{m}{2})&\mbox{for
}4\leq m<n,m\text{ even, and }n\mbox{ odd}\end{cases}.$

######  Lemma 3.9.

Suppose $G$ is a graph in which every vertex has degree at least $s$. Let $z$
be any vertex in $G$. Then $G$ has a path of length $s+1$ with $z$ as an
endpoint.

###### Proof.

For $i=1,\dots,s+1$ we construct a path where $z_{1}=z$, and $z_{i}$ is any
vertex adjacent to $z_{i-1}$. Since every vertex has degree at least $s$, this
yields a path of length $s+1$. ∎

######  Lemma 3.10.

Consider some fixed $2$-coloring of a $K_{2(n+m+p)-1}$. Suppose $n\geq p+3$,
$m\geq 2$, and $k\geq p+1$. Assume there exists a blue $m+2p$ star in $A$,
centered at some $v\in A$, with the set of spoke vertices being $A^{\prime}$.
If there exists a blue cycle $Q$ of length $2p$ in $A$, such that

$|A^{\prime}\cap Q|\geq p+1,$

then this $2$-coloring must admit a monochromatic $S_{c}(n,m)$.

###### Proof.

Let $D\subset A^{\prime}$ be some set of $m$ vertices in $A^{\prime}$ not on
$Q$. Define

$X=V\backslash(Q\cup D\cup\\{v\\}).$

Observe that $|X|=2n+m-2$. Furthermore, let $Q^{\prime}=A^{\prime}\cap Q$, and
let $Q^{\prime\prime}\subset Q$ be the set of vertices that are adjacent to a
vertex in $Q^{\prime}$; note that since $|Q^{\prime}|\geq p+1$, it must also
be the case that $|Q^{\prime\prime}|\geq p+1$. Observe that if any $q\in
Q^{\prime\prime}$ satisfies $\text{blue-}d_{X}(q)\geq n$ then there exists a
blue $S_{c}(n,m)$, formed by following $q$ back for $2p$ vertices on $Q$, and
connecting the last vertex to $v$. This defines a blue $S_{c}(n,m)$ with
$n$-star at $q$ and $m$-star at $v$ (using $D$). Therefore, we may assume that
all $q\in Q^{\prime\prime}$ satisfy $\text{blue-}d_{X}(q)\leq n-1$, and so

$\displaystyle\text{red-}d_{X}(q)$ $\displaystyle\geq 2n+m-2-(n-1)$
$\displaystyle=n+m-1.$

Since $m\geq 2$,

$n+m-1\leq|X|\leq 2(n+m-1)-2$

and so by Lemma 3.5 there must be a red cycle $S$ of length $2p+2$ between
$Q^{\prime\prime}$ and $X$. Now one of two things must be true: either
$u\notin S$ or $u\in S$.

Suppose $u\notin S$. Then $S$ is a red cycle of length $2p+2$ between
$Q^{\prime\prime}$ and $A\cup B$. Since $Q^{\prime\prime}\subset A$, we can
conclude by Lemma 3.7 that this $2$-coloring admits a monochromatic
$S_{c}(n,m)$.

Alternatively, suppose $u\in S$. Define

$Y=V\backslash(Q\cup D\cup S\cup\\{v\\}).$

Observe that $|Y|=2n+m-p-3$. Following $S$ for $2p+1$ vertices from $u$ will
end at some $x\in(S\cap X)$. Now if $\text{red-}d_{Y}(x)\geq m$ then there
exists a red $S_{c}(n,m)$ with the $n$-star at $u$ and $m$-star at $x$.
Therefore we may assume $\text{red-}d_{Y}(x)\leq m-1$, and so

$\displaystyle\text{blue-}d_{Y}(x)$ $\displaystyle\geq(2n+m-p-3)-(m-1)$
$\displaystyle=2n-p-2$ $\displaystyle\geq n+1.$

Let $T=B(x)\cap Y$. Finally, define $Q^{\prime\prime\prime}$ to be the set of
vertices $q\in Q$ such that following $Q$ for $2p-2$ vertices from $q$ ends at
a vertex in $Q^{\prime}$. I.e., if $q\in Q^{\prime\prime\prime}$, then there
exists a vertex $w\in Q^{\prime}$ such that $q$ and $w$ are the endpoints of a
blue path of length $2p-2$ in $Q$. Observe that since $|Q^{\prime}|\geq p+1$,
it must also be the case that $|Q^{\prime\prime\prime}|\geq p+1$. Now if any
$t\in T$ is connected to any $q\in Q^{\prime\prime\prime}$ by a blue edge,
then connecting $t$ to $q$, following $Q$ back for $2p-2$ vertices from $q$,
and connecting the last vertex to $v$, will form a blue $S_{c}(n,m)$ with the
$n$-star at $x$ and $m$-star at $v$. Observe that $x$ has sufficient blue
degree to form the $n$-star without interference since $Y$ and $Q$ are
disjoint. Therefore we may assume there is a red complete bipartite graph
between $Q^{\prime\prime\prime}$ and $T$. This complete bipartite graph
contains a red cycle of length $2p+2$, and since
$Q^{\prime\prime\prime}\subset A$ and $T\subset(A\cup B)$, we may conclude by
Lemma 3.7 that there is a monochromatic $S_{c}(n,m)$. ∎

######  Lemma 3.11.

Consider some fixed $2$-coloring of a $K_{2(n+m+p)-1}$. If $n\geq p+3$, $m\geq
2$, and $k\geq p+1$, then if there is a blue $m+2p$ star in $A$, then this
$2$-coloring admits a monochromatic $S_{c}(n,m)$.

###### Proof.

Suppose that there was such a blue $m+2p$ star in $A$ centered at some vertex
$v\in A$. Let the set of $m+2p$ spoke vertices be $A^{\prime}\subset A$.

First suppose that $m\geq p-1$. Then $|A^{\prime}|\geq 3p-1$, and so by Lemma
3.8 we know there must either be a red cycle of length $2p$ in $A^{\prime}$,
or a blue cycle of length $2p$ in $A^{\prime}$. If there is a red cycle of
length $2p$ in $A^{\prime}$, then by Lemma 3.6 we could conclude that there is
a monochromatic $S_{c}(n,m)$. Therefore we may assume there is no such red
cycle, and so therefore there is a blue cycle $Q\subset A^{\prime}$ of length
$2p$. Now $A^{\prime}$ is a blue $m+2p$ star in $A$ such that there exists a
blue cycle $Q$ in $A$ satisfying $|A^{\prime}\cap Q|\geq p+1$. Thus by Lemma
3.10, this $2$-coloring must admit a monochromatic $S_{c}(n,m)$.

Now assume that $m\leq p-2$. Choose some set of $p-m-1$ vertices from
$A\backslash(A^{\prime}\cup\\{v\\})$. Call this set $D$. Set
$A^{\prime\prime}=D\cup A^{\prime},$ and observe that
$|A^{\prime\prime}|=3p-1$, and so again by Lemma 3.8, there must either be a
red cycle of length $2p$ in $A^{\prime\prime}$, or a blue cycle of length $2p$
in $A^{\prime\prime}$. If red, then by Lemma 3.6 we could conclude that there
is a monochromatic $S_{c}(n,m)$. Therefore we may assume there is a blue cycle
of length $2p$ in $A^{\prime\prime}$. Call this blue cycle $Q$, and observe
that

$|Q\cap D|\leq p-m-1$

and so $|Q\cap A^{\prime}|\geq p+m+1$. Now $A^{\prime}$ is a blue $m+2p$ star
in $A$ such that there exists a blue cycle $Q$ in $A$ satisfying
$|A^{\prime}\cap Q|\geq p+1$. Thus by Lemma 3.10, this $2$-coloring must admit
a monochromatic $S_{c}(n,m)$.

∎

######  Lemma 3.12.

If $p+1\leq k\leq 2p$, $n\geq 2p+1$, and $m\geq 2$, then every such
$2$-coloring of a $K_{r}$ admits a monochromatic $S_{c}(n,m)$, for $r\geq
2(n+m+p)-1$.

###### Proof.

Clearly it is enough to prove the lemma for $r=2(n+m+p)-1$. If $p+1\leq k\leq
2p$, then $n+m+2p\leq|A|\leq n+m+3p-1$. Since $u$ has maximal monochromatic
degree,

$\text{red-}d(v)\geq n+m-p-1$

for all $v\in V$. By Lemma 3.11 we may assume there is no blue $m+2p$ star in
$A$. Therefore, for all $a\in A$, we have $\text{red-}d_{A}(a)\geq n$.

By Lemma 3.3, there must be a monochromatic broom $B(m,2p+1)$ in $A$. If red,
then connecting the second-to-last vertex of the path of the broom to $u$
completes a red $S_{c}(n,m)$. Thus we may there exists a blue $B(m,2p+1)$ in
$A$. Let the last vertex of the path of this broom be $v$, let the set of
$m+2p+1$ vertices that define this broom be $Q$, and let $X=A\cup B\backslash
Q$. Note that $|X|=2n+m-3$. Now clearly if $\text{blue-}d_{X}(v)\geq n$, then
$v$ completes a blue $S_{c}(n,m)$, with $Q$ forming the remainder of the
linked double star. Therefore we may assume $\text{blue-}d_{X}(v)\leq n-1$,
and so

$\displaystyle\text{red-}d_{X}(v)$ $\displaystyle\geq 2n+m-3-(n-1)$
$\displaystyle=n+m-2$ $\displaystyle\geq m+2p-1.$

Finally, note that since $v\in A$, and $\forall a\in A$

$\displaystyle\text{red-}d_{A}(a)$ $\displaystyle\geq n$ $\displaystyle\geq
2p+1,$

by Lemma 3.9 there must be a red path of length $2p$ in $A$, with one endpoint
somewhere in $A$ and the other endpoint at $v$. Since $\text{red-}d_{X}(v)\geq
m+2p-1$, this result implies that there exists a red $B(m,2p)$ in $A\cup B$,
with the endpoint of the tail somewhere in $A$. Connecting the endpoint of the
tail to $u$ will complete a red $S_{c}(n,m)$. ∎

######  Lemma 3.13.

(Due to Parsons, see [8]) The ramsey numbers of paths vs. stars satisfy

$r(P_{l},K_{1,n})\leq n+l-1.$

######  Lemma 3.14.

If $k\geq 2p+1$, and $n\geq p+3$, then every such $2$-coloring of a $K_{r}$
admits a monochromatic $S_{c}(n,m)$, for $r\geq 2(n+m+p)-1$.

###### Proof.

Clearly, it suffices to prove the result for $r=2(n+m+p)-1$. If $k\geq 2p+1$,
then $|A|\geq n+m+3p$. By Lemma 3.11, we may assume that for all $a\in A$,

$\text{blue-}d_{A}(a)\leq m+2p-1$

and so

$\displaystyle\text{red-}d_{A}(a)$ $\displaystyle\geq n-p+k-1$
$\displaystyle\geq n+p+1.$

However, if there is no blue $m+2p$ star in $A$, then by Lemma 3.13 there must
be a red path $P$ of length $2p$ in $A$. Let the vertices of $P$ be

$P=\\{v_{1},v_{2},\ldots,v_{2p-1},v_{2p}\\}$

where $P$ has endpoints $v_{1}$ and $v_{2p}$. Since $v_{1},v_{2p}\in A$,

$\displaystyle\text{red-}d_{A}(v_{1})$ $\displaystyle\geq n-p+k-1$
$\displaystyle\geq m+p$

(and similarly for $v_{2p}$). Now if either $\text{red-}d_{P}(v_{1})\leq p$ or
$\text{red-}d_{P}(v_{2p})\leq p$, then one of $v_{1}$ or $v_{2p}$ forms the
center of a red $m$-star, and connecting the other endpoint of $P$ to $u$ will
complete a red $S_{c}(n,m)$. Therefore we may assume that both
$\text{red-}d_{P}(v_{1})\geq p+1$ and $\text{red-}d_{P}(v_{2p})\geq p+1$. Let
$X=R(v_{1})\cap P$, and $Y=R(v_{2p})\cap P$. Now we claim that there must
exist some vertex $v_{i}\in X$, such that $v_{i-1}\in Y$. Suppose to the
contrary that there was no such $v_{i}$. Observe that every $v_{i}\in X$
corresponds uniquely to a $v_{i-1}$ that (by supposition) must be connected to
$v_{2p}$ by a blue edge. However, this would imply that
$\text{blue-}d_{P}(v_{2p})\geq p$ and so $\text{red-}d_{P}(v_{2p})\leq p-1$, a
contradiction. Therefore, we may assume there exists some $v_{i}\in X$ such
that $v_{i-1}\in Y$. But now these vertices can be used to define a red cycle
$Q$, as follows:

$Q=\\{v_{1},v_{2},\ldots,v_{i-1},v_{2p},v_{2p-1},\ldots,v_{i+1},v_{i},v_{1}\\}.$

Observe that $Q\subset A$ is a red cycle of length $2p$, and so by Lemma 3.6,
this $2$-coloring must admit a monochromatic $S_{c}(n,m)$. ∎

Combining the results of Lemma 3.3, Corollary 3.4.1, Lemma 3.12, and Lemma
3.14, the proof of Theorem 3.1 is complete.

### Proof of Theorem 3.2

As before, we will begin by introducing notation that will be used throughout
this section. Consider some fixed $2$-coloring of a complete graph $K$, and
let $V$ denote the vertex-set of $K$. In this section, we will assume that
$|V|\geq 3p+1$. Therefore, by lemma 3.8, there must exist a monochromatic
cycle of length $2p+2$ in this $2$-coloring.

For every monochromatic cycle in the $2$-coloring of $K$, we will also
identify an associated “primed" vertex. In particular, if $C$ is a blue cycle
of length $2p+2$ in $K$, then its primed vertex $u\in V\backslash C$, is the
vertex such that $\text{blue-}d_{C}(u)\geq\text{blue-}d_{C}(v)$ for all $v\in
V\backslash C$. Similarly, if $C$ is a red cycle of length $2p+2$ then its
primed vertex $u\in V\backslash C$ is the vertex such that
$\text{red-}d_{C}(u)\geq\text{red-}d_{C}(v)$. For a particular monochromatic
cycle $C$ of length $2p+2$, its primed vertex will be denoted $u_{C}$. Now,
using $u_{C}$, we will define three important sets of vertices in $C$. First,
if $C$ is a blue cycle we will define $S_{C}=B(u_{C})\cap C$, and similarly if
$C$ is a red cycle, $S_{C}=R(u_{C})\cap C$. Second, we will define the set
$T_{C}^{i}$ as

$T_{C}^{i}=\\{c\in C:\exists s\in S_{C}\text{ such that }c\text{ and }s\text{
are endpoints of a path of length }i\text{ on }C\\}.$

Finally, define $Z_{C}=V\backslash C$. Note that $u_{C}\in Z_{C}$.

Our proofs focus on a particular cycle $Q$, with length $2p+2$, whose primed
vertex is maximal. Specifically, if $H$ is the set of all monochromatic cycles
of length $2p+2$ in the $2$-coloring of $K$, then $Q\in H$ is the cycle such
that $|S_{Q}|\geq|S_{C}|$ for all $C\in H$. We will assume, without loss of
generality, that $Q$ is blue. For the sake of concision, we shall refer to
$u_{Q}$ simply as $u$, $S_{Q}$ as $S$, $T_{Q}^{i}$ as $T^{i}$, and $Z_{Q}$ as
$Z$.

We will now provide a series of lemmas that will be used repeatedly in this
section. Unless explicitly stated otherwise, we shall assume that $n\leq p-2$.

######  Lemma 3.15.

If $|S|\leq p-1$, and $n\leq p$, then every such $2$-coloring of a $K_{r}$
admits a monochromatic $S_{c}(n,2)$, for $r\geq n+3p+3$.

###### Proof.

Clearly it is enough to prove the lemma for $r=n+3p+3$. If $|S|\leq p-1$, then
by the definition of $S$, it implies that $\forall z\in Z$,
$\text{blue-}d_{Q}(z)\leq p-1$ and so $\text{red-}d_{Q}(z)\geq p+3$. Now
observe that

$p+3\leq|Q|\leq 2(p+3)-2.$

Therefore, by Lemma 3.5, any subset of $p+1$ vertices in $Z$ will define a red
cycle of length $2p+2$ between that subset and $Q$.

Now suppose there is some vertex $z\in Z$, satisfying $\text{red-}d_{Z}(z)\geq
p$. Let $Z^{\prime}\subset Z$ be a set of $p+1$ vertices in
$Z\backslash\\{z\\}$, such that $\text{red-}d_{Z^{\prime}}(z)\geq p$. By the
above reasoning, there must exist a red cycle of length $2p+2$ between
$Z^{\prime}$ and $Q$, call this red cycle $Q^{\prime}$. Since $z\notin
Q^{\prime}$, and $\text{red-}d_{Q^{\prime}}(z)\geq p$, we know that
$|S_{Q^{\prime}}|\geq p$, contradicting the maximality of $Q$. Therefore, we
may assume that $\forall z\in Z$, $\text{red-}d_{Z}(z)\leq p-1$, and so
$\text{blue-}d_{Z}(z)\geq n+1$.

Similarly, suppose there is some $z\in Z$ such that
$\text{red-}d_{Q}(z)=2p+2$. Let $Z^{\prime}\subset Z$ be some set of $p+1$
vertices in $Z\backslash\\{z\\}$. There must exist a red cycle of length
$2p+2$ between $Z^{\prime}$ and $Q$, call this red cycle $Q^{\prime}$. Since
$z\notin Q^{\prime}$, and $\text{red-}d_{Q^{\prime}}(z)\geq p+1$, we know that
$|S_{Q^{\prime}}|\geq p+1$, contradicting the maximality of $Q$. Therefore, we
may assume that $\forall z\in Z$, $\text{blue-}d_{Q}(z)\geq 1$, and so every
$z\in Z$ must be connected to some $q\in Q$ by a blue edge.

Consider some fixed vertex $z\in Z$. Since $\forall z\in Z$ we may assume that
$\text{blue-}d_{Z}(z)\geq n+1$, $z$ is the center of (at least) a blue $n+1$
star. Furthermore, let $q\in Q$ be a vertex such that the edge $(z,q)$ is
blue, which must exist since $\forall z\in Z$, $\text{blue-}d_{Q}(z)\geq 1$.
Connecting $z$ to $q$ and following $Q$ for $2p$ vertices from $q$ defines a
blue path of length $2p+1$ that begins at $z$ and ends at some $q^{\prime}\in
Q$. Observe that this path has an $n+1$-star at $z$, so if
$\text{blue-}d_{Z\backslash\\{z\\}}(q^{\prime})\geq 1$ then this path would
define a blue $S_{c}(n,2)$, with $2$-star at $q^{\prime}$ using one vertex in
$Z\backslash\\{z\\}$ and the vertex on $Q$ following $q^{\prime}$. Therefore
we may assume $\text{blue-}d(q^{\prime})_{Z\backslash\\{z\\}}=0$, and so
$\text{red-}d(q^{\prime})_{Z\backslash\\{z\\}}=n+p$. Now select some arbitrary
set of $p+1$ vertices from these $n+p$, call this set $A$. Since $\forall z\in
Z$ satisfy $\text{red-}d_{Q}(z)\geq p+3$, it follows that
$\text{red-}d_{Q\backslash\\{q^{\prime}\\}}\geq p+2$. But now, since

$p+2\leq|Q\backslash\\{q^{\prime}\\}|\leq 2(p+2)-2$

there must be a red cycle $Q^{\prime}$ of length $2p+2$ between $A$ and
$Q\backslash\\{q^{\prime}\\}$. Since $q^{\prime}\notin Q^{\prime}$, and
$\text{red-}d_{Q^{\prime}}(q^{\prime})\geq p+1$, we know that
$|S_{Q^{\prime}}|\geq p+1$, contradicting the maximality of $Q$. ∎

######  Lemma 3.16.

Let $C$ be a monochromatic cycle of length $2p+2$. Then $\forall i$,
$|T_{C}^{i}|\geq|S_{C}|$.

###### Proof.

Every vertex in $S_{C}$ contributes (at least) one unique vertex to
$T_{C}^{i}$. Simply fix a direction for following $C$, and follow $C$ for $i$
vertices starting from each vertex in $S_{C}$. In this manner, each vertex
$s\in S_{C}$ will map onto a unique vertex that (by the definition of
$T_{C}^{i}$) must belong to $T_{C}^{i}$. Therefore, $|T_{C}^{i}|\geq|S_{C}|$.
∎

######  Lemma 3.17.

Suppose $C$ is a cycle on $2p+2$ vertices. If $|S_{C}|=|T_{C}^{2p}|$, then
$|S_{C}|\geq p+1$.

###### Proof.

First, observe that $T_{C}^{2p}=T_{C}^{4}$, since as $C$ is a cycle, any two
vertices that form the endpoints of a path of length $2p$ on $C$ also form a
path of length $4$ on $C$. It is therefore equivalent to prove the result for
$T_{C}^{4}$.

Consider some fixed $s\in S_{C}$. Observe that $s$ defines exactly two
vertices that belong to $T_{C}^{4}$: one obtained by following $C$ for $4$
vertices starting from $s$ in the “forward" direction, and the other by
following $C$ in the “backward" direction. Call these two vertices the forward
and backward $4$-neighbors of $s$ respectively. Since in this manner every
$s\in S$ defines two vertices in $T_{C}^{4}$, the only way that
$|S_{C}|=|T_{C}^{4}|$ is if every forward $4$-neighbor of a vertex in $S$ is
_also_ a backward $4$-neighbor of some other vertex in $S$.

Now observe that if there are any four consecutive vertices
$x_{1},x_{2},x_{3},x_{4}\in C\backslash S_{C}$, then $|T_{C}^{4}|>|S_{C}|$,
since $x_{4}$ is a forward $4$-neighbor of $x_{1}$, and $x_{4}\notin S$. This
implies that if there are three adjacent vertices $x_{1},x_{2},x_{3}\in
C\backslash S_{C}$ then $S_{C}$ must contain the three vertices before
$x_{1},x_{2},x_{3}$ and the three vertices after $x_{1},x_{2},x_{3}$.
Similarly if there are two adjacent vertices $x_{1},x_{2}\in C\backslash
S_{C}$ then $S_{C}$ must contain the three vertices before and after
$x_{1},x_{2}$. But now $C\backslash S_{C}$ consists of a sequence of intervals
of $C$ of length one, two, or three, and each interval is followed by an
interval in $S$ of equal or greater length, so $|S_{C}|\geq|C\backslash
S_{C}|$. Since $|S_{C}|+|C\backslash S_{C}|=|C|=2p+2$, this necessitates that
$|S_{C}|\geq p+1$. ∎

######  Corollary 3.17.1.

If $C$ is a cycle on $2p+2$ vertices with $|S_{C}|\leq p$, then
$|T_{C}^{2p}|\geq|S_{C}|+1$.

###### Proof.

By Lemma 3.16, we know $|T_{C}^{2p}|\geq|S_{C}|$. However, as shown in Lemma
3.17, equality can only occur if $|S_{C}|\geq p+1$, so if $|S_{C}|\leq p$ then
$|T_{C}^{2p}|\geq|S_{C}|+1$. ∎

######  Lemma 3.18.

If $|S|=p$, and $n\leq p$, then every such $2$-coloring of a $K_{r}$ admits a
monochromatic $S_{c}(n,2)$, for $r\geq n+3p+3$.

###### Proof.

Clearly it is enough to prove the lemma for $r=n+3p+3$. If $|S|=p$, then by
the definition of $S$, it implies that $\forall z\in Z$,
$\text{blue-}d_{Q}(z)\leq p$ and so $\text{red-}d_{Q}(z)\geq p+2$. Now observe
that

$p+2\leq|Q|\leq 2(p+2)-2.$

Therefore, by Lemma 3.5, any subset of $p+1$ vertices in $Z$ will define a red
cycle of length $2p+2$ between that subset and $Q$.

Suppose that there was some $z\in Z$ satisfying $\text{red-}d_{Z}(z)\geq p$.
Let $A\subset Z$ be some subset of $p+1$ vertices in $Z\backslash\\{z\\}$,
including at least $p$ vertices from $R(z)\cap Z$. By Lemma 3.5 there must be
a red cycle $Q^{\prime}$ of length $2p+2$ between $A$ and $Q$. Now if $z$ is
connected to a vertex in $Q^{\prime}\cap Q$ by a red edge, then
$|S_{Q^{\prime}}|\geq p+1$ (since $z\notin Q^{\prime}$, and
$\text{red-}d_{A}(z)\geq p$) contradicting the presumed maximality of $Q$.
Therefore, we may assume that $z$ is connected to every vertex in
$Q^{\prime}\cap Q$ by a blue edge. But now, $\text{blue-}d_{Q}(z)\geq p+1$,
and so $|S|\geq p+1$, contradicting the assumption that $|S|=p$.

Thus, $\forall z\in Z$ we may assume that $\text{red-}d_{Z}(z)\leq p-1$ and so
$\text{blue-}d_{Z}(z)\geq n+1$. Let $Z^{\prime}=Z\backslash\\{u\\}$. Suppose
there as some vertex $z\in Z^{\prime}$ that was connected to some vertex in
$t\in T^{2p}$ by a blue edge. Then following $z$ to $t$, and following $Q$ for
a further $2p$ vertices from $Q$ will end at some $s\in S$. This path forms
the link of a blue $S_{c}(n,2)$, where we use $u$ and the remaining vertex on
$Q$ that is blue-adjacent to $s$ to complete the $2$-star at $s$, leaving at
least $n$ vertices to form the blue $n$-star at $z$ (note that since $z\in
Z^{\prime}$, it follows $z\neq u$). Thus we may assume there is a red complete
bipartite graph between $Z^{\prime}$ and $T^{2p}$. Since (by Corollary 3.17.1)
$|T^{2p}|\geq p+1$, and

$\displaystyle|Z^{\prime}|$ $\displaystyle=n+p$ $\displaystyle\geq p+2,$

this complete bipartite graph contains a red cycle of length $2p+2$, which
leaves one vertex unused in $Z^{\prime}$ which has red degree into the cycle
$\geq p+1$, again contradicting the assumption of the maximality of $Q$. ∎

######  Lemma 3.19.

Suppose $C$ is a blue cycle of length $2p+2$. If any vertex $t\in
T_{C}^{2p+1}$ has $\text{blue-}d_{Z_{C}}(t)\geq n+1$, then this $2$-coloring
admits a blue $S_{c}(n,2)$. The symmetric result holds if $C$ is instead a red
cycle of length $2p+2$.

###### Proof.

Let $C$ be a blue cycle of length $2p+2$, and suppose there existed a $t\in
T_{C}^{2p+1}$ such that $\text{blue-}d_{Z_{C}}(t)\geq n+1$. By the definition
of $T_{C}^{2p+1}$, following $C$ for $2p+1$ vertices from $t$ will end at some
$s\in S_{C}$. Observe now that there exists a $2$-star at $s$, using $u$, and
the remaining vertex on $Q$ that immediately follows $s$. This leaves (at
least) $n$ vertices unused in $B(t)\cap Z_{C}$ to form the $n$-star at $t$, so
this path on $Q$ defines a blue $S_{c}(n,2)$. ∎

######  Lemma 3.20.

Suppose $C$ is a blue cycle of length $2p+2$. Let $T=\\{c\in
C:\text{red-}d_{Z_{C}}(c)\geq p+1\\}$. If $|S_{C}|\geq p+1$ and $|T|\geq p+2$,
then if there exists a vertex $c\in C$ such that $\text{blue-}d_{Z_{C}}(c)\geq
n+1$, then this $2$-coloring admits a monochromatic $S_{c}(n,2)$. The
symmetric result also holds if $C$ is instead a red cycle of length $2p+2$.

###### Proof.

Suppose there existed a vertex $c_{1}\in C$, with
$\text{blue-}d_{Z_{C}}(c)\geq n+1$. Let $c_{3}$ and $c_{2p+1}$ be the vertices
found by following $C$ for $2p+1$ vertices starting at $c_{1}$. If either of
$c_{3}$ or $c_{2p+1}$ has a blue edge into $Z_{C}$, then it would complete a
blue $S_{c}(n,2)$, with the $n$-star at $c_{1}$ and the $2$-star at either
$c_{3}$ or $c_{2p+1}$ (where we have used $c_{2}$ or $c_{2p+2}$ to complete
the $2$-star at $c_{3}$ or $c_{2p+1}$, respectively). Therefore we may assume
that $c_{3}$ and $c_{2p+1}$ are connected to every $z\in Z_{C}$ by a red edge.

Suppose that $c_{2p+1}$ was connected to some vertex $c^{\prime}\in
C\backslash\\{c_{3}\\}$ by a red edge. Let
$T^{\prime}=T\backslash\\{c_{2p+1},c^{\prime}\\}$. Since $|T|\geq p+2$, we
have $|T^{\prime}|\geq p$. Since $T^{\prime}\subseteq T$, we know that
$\forall t\in T^{\prime}$, $\text{red-}d_{Z_{C}}(t)\geq p+1$. Since

$p+1\leq|Z_{C}|\leq 2(p+1)-2,$

by Lemma 3.5, this implies that there exists a red cycle of length $2p$
between $T^{\prime}$ and $Z_{C}$; call this red cycle $C^{\prime}$. If
$c_{3}\in T^{\prime}$, then $C^{\prime}$ contains a path of length $2p$ with
one endpoint at $c_{3}$, and the other endpoint at some $z_{1}\in Z_{C}$. If
$c_{3}\notin T^{\prime}$, then such a red path can be formed by following
$C^{\prime}$ for $2p-1$ vertices starting at some $z_{1}\in Z_{C}\cap
C^{\prime}$; this will end at some other $z_{2}\in Z_{C}$, to which we can
append $c_{3}$ to form the desired red path. In either case, there exists a
red path of length $2p$ between $T^{\prime}$ and $Z_{C}$ with one endpoint at
$c^{\prime}$ and the other endpoint at some $z_{1}\in Z_{C}$. Now this red
path defines a red $S_{c}(n,2)$, as we can use $n$ of the $n+1$ unused
vertices in $Z_{C}$ to complete the $n$-star at $c_{3}$, and can use
$c^{\prime}$ and the remaining unused vertex in $Z_{C}$ to complete the
$2$-star at $c_{2p+1}$. Therefore we may assume that $c_{2p+1}$ must be
connected to every vertex in $C\backslash\\{c_{3}\\}$ by a blue edge. By
symmetric reasoning, we may also assume that $c_{3}$ is connected to every
vertex in $C\backslash\\{c_{2p+1}\\}$ by a blue edge. However, this implies
that every vertex in $C\backslash\\{c_{1}\\}$ can be made the endpoint of a
blue path of length $2p+1$ starting at $c_{1}$. Suppose that we wished to make
some $c_{i}\in C\backslash\\{c_{1}\\}$ such an endpoint of a blue path
starting at $c_{1}$. Then using $c_{3}$ and $c_{2p+1}$, the path

$P=\\{c_{1},c_{2},c_{3},\ldots,c_{i-1},c_{2p+1},c_{2p},\ldots,c_{i+1},c_{i}\\},$

gives the desired blue path of length $2p+1$ (note a similar path exists if
instead $c_{i}=c_{2}$ or $c_{i}=c_{2p+2}$. Thus, if any $c\in
C\backslash\\{c_{1}\\}$ has $\text{blue-}d_{Z_{C}}(c)\geq 2$, there exists a
blue $S_{c}(n,2)$ (note there is one vertex left unused on $C$, $c_{2p+2}$,
that may be used to complete the $n$-star at $c_{1}$, if needed). Thus we may
assume that $\forall c\in C\backslash\\{c_{1}\\}$,
$\text{blue-}d_{Z_{C}}(c)\leq 1$ and so $\text{red-}d_{Z_{C}}(c)\geq n+p$.

Now since $n<p$ we have

$\frac{(n+p)(2p+1)}{n+p+1}>n+p+1,$

and so there must be a vertex $z^{\prime}\in Z_{C}$ such that
$\text{red-}d_{C}(z^{\prime})\geq n+p+2$. Let $W\subseteq C$ be a subset of
$R(z^{\prime})\cap C$ of size $n+p+2$. Now since

$\frac{(n+p-1)(n+p+2)}{n+p}>2$

there must exist a vertex $z\in Z_{C}\backslash\\{z^{\prime}\\}$ such that
$\text{red-}d_{W}(z)\geq 3$. Let $\\{w_{1},w_{2},w_{3}\\}\subseteq R(z)\cap
W$. Choose any $p$ vertices of $W$ including the vertex $w_{1}$, but excluding
$w_{2}$ and $w_{3}$; call this set of vertices $A$. Observe that since
$A\subset C$, we know $\forall a\in A$,
$\text{red-}d_{Z_{C}\backslash\\{z^{\prime}\\}}(a)\geq n+p-1\geq p+1$.
Furthermore, since

$p+1\leq n+p\leq 2(p+1)-2,$

by Lemma 3.5 there must be a red cycle $C^{\prime}$ of length $2p$ between $W$
and $Z_{C}\backslash\\{z^{\prime}\\}$ (where above we have used the fact that
$n\geq 2$ and $n\leq p-1$). Since $C^{\prime}$ contains $w_{1}$, avoids
$w_{2}$ and $w_{3}$, and $z$ is red-adjacent to $\\{w_{1},w_{2},w_{3}\\}$,
this defines a red $S_{2p}(2,0)$, with one endpoint at $z\in
Z_{C}\backslash\\{z^{\prime}\\}$ and the other endpoint somewhere in $W$. But
since $W\subseteq R(z^{\prime})\cap C$, we may append $z^{\prime}$ to the
endpoint in $W$, and since $|W|=n+p+2$, $z^{\prime}$ has sufficient degree to
complete the red $S_{c}(n,2)$ without interference.

∎

######  Corollary 3.20.1.

Let $C$ be a blue cycle of length $2p+2$. If $|S_{C}|\geq p+1$ and
$|T_{C}^{2p+1}|\geq p+2$, then if there exists a vertex $c\in C$ such that
$\text{blue-}d_{Z_{C}}(c)\geq n+1$, then this $2$-coloring admits a
monochromatic $S_{c}(n,2)$.

###### Proof.

By Lemma 3.19, we may assume that every $t\in T^{2p+1}$ satisfies
$\text{red-}d_{Z_{C}}(t)\geq p+1$. In particular, if $T=\\{c\in C:\text{
red-}d_{Z_{C}}(c)\geq p+1\\}$, then $|T|\geq|T_{C}^{2p+1}|$. Therefore if
$|T_{C}^{2p+1}|\geq p+2$, then $|T|\geq p+2$, and so by the result of Lemma
3.20, there must exist a monochromatic $S_{c}(n,2)$. ∎

######  Lemma 3.21.

Let $C$ be a blue cycle of length $2p+2$. If $|S_{C}|=p+1$ and
$|T_{C}^{2p+1}|=p+1$, then if there exists a vertex $c\in C$ such that
$\text{blue-}d_{Z_{C}}(c)\geq n+1$, then this $2$-coloring admits a
monochromatic $S_{c}(n,2)$.

###### Proof.

Suppose there existed a vertex $c_{1}\in C$, with
$\text{blue-}d_{Z_{C}}(q_{1})\geq n+1$. Let $C^{\prime}=C\backslash
T_{C}^{2p+1}$. If any $c\in C^{\prime}$ satisfied $\text{red-}d_{Z_{C}}(c)\geq
p+1$, then by Lemma 3.20, this $2$-coloring would admit a monochromatic
$S_{c}(n,2)$. Therefore, we may assume $\forall c\in C^{\prime}$ that
$\text{red-}d_{Z_{C}}(c)\leq p$ and so $\text{blue-}d_{Z_{C}}(q)\geq n+1$.

Define

$X=\\{c_{i}\in C:\exists c_{j}\in C^{\prime}\text{ such that }c_{i}\text{ and
}c_{j}\text{ are endpoints of a path of length }2p+1\text{ on }C\\}.$

Conceptually, $X$ is the set of all the vertices on $C$ that are found by
following $C$ for $2p+1$ vertices, starting from a vertex in $C^{\prime}$.
Note that $|X|\geq|C^{\prime}|=p+1$. Suppose some $x\in X$ satisfied
$\text{blue-}d_{Z_{C}}(x)\geq 1$, and let $c\in C^{\prime}$ be the vertex
found by following $C$ for $2p+1$ vertices from $x$. Then $c$ and $x$ would
define a blue $S_{c}(n,2)$, with $n$-star at $c$, and $2$-star at $x$ (where
we have used one vertex in $Z_{C}$, and the remaining vertex on $C$ between
$x$ and $c$ to form the $2$-star). Therefore, we may assume that there is a
red complete bipartite graph between $X$ and $Z_{C}$.

Let $X^{\prime}\subseteq X$ be some subset of $p+1$ vertices of $X$, and set
$Y=C\backslash X^{\prime}$. Note that $|X^{\prime}|=|Y|=p+1$. Since
$X^{\prime}\subset X$, we may assume by the argument above that there is a red
complete bipartite graph between $X^{\prime}$ and $Z_{C}$. Now suppose that
some $x\in X^{\prime}$ was connected to some $y\in Y$ by a red edge. Then,
using the complete bipartite graph between $X^{\prime}$ and $Z_{C}$, we may
form a red $S_{c}(n,1)$, with the $n$-star centered at some vertex in
$X^{\prime}\backslash\\{x\\}$, and the $1$-star centered at $x$. Using $y$,
this $1$-star can be made into a $2$-star, completing the red $S_{c}(n,2)$.
Therefore, we may assume there is a blue complete bipartite graph between
$X^{\prime}$ and $Y$.

Suppose that there is a vertex $y\in Y$ such that
$\text{blue-}d_{Z_{C}}(y)\geq n+1$. Now if any vertex $y^{\prime}\in
Y\backslash\\{y\\}$ has $\text{blue-}d_{Z_{C}}(y^{\prime})\geq 1$, then it
will complete a blue $S_{c}(n,2)$. This blue $S_{c}(n,2)$ can be formed using
the blue complete bipartite graph between $X^{\prime}$ and $Y$, to build a
blue path of length $2p+1$ with one endpoint at $y$ and the other endpoint at
$y^{\prime}$; this path defines a blue $S_{c}(n,2)$ with $n$-star at $y$, and
$2$-star at $y^{\prime}$ (where we have used the remaining unused vertex in
$X^{\prime}$ to complete the $2$-star, if necessary). Therefore, we may assume
there is a red complete bipartite graph between $Y\backslash\\{y\\}$ and
$Z_{C}$. Now this implies that $\forall z\in Z_{C}$,

$\displaystyle\text{red-}d_{Y}(z)$ $\displaystyle\geq p$ $\displaystyle\geq
n+2.$

Now using the red complete bipartite graph between $X^{\prime}$ and $Z_{C}$,
there must exist a red path of length $2p+1$ with both endpoints in $Z_{C}$.
By the above reasoning, both endpoints have sufficient red degree to complete
the red $S_{c}(n,2)$.

Therefore we may assume that $\forall y\in Y$, $\text{red-}d_{Z_{C}}(y)\geq
p+1$. Since

$p+1\leq|Z_{C}|\leq 2(p+1)-2,$

by Lemma 3.5 there must be a blue cycle of length $2p+2$ between $Y$ and
$Z_{C}$. This cycle contains a red path of length $2p+1$ with both endpoints
in $Z_{C}$. Since there is a red complete bipartite graph between $Z_{C}$ and
$X^{\prime}$, the endpoints have sufficient red degree to complete a red
$S_{c}(n,2)$.

∎

######  Lemma 3.22.

If $|S|\geq p+1$, and $n\leq p-2$, then every such $2$-coloring of a $K_{r}$
admits a monochromatic $S_{c}(n,2)$, for $r\geq n+3p+3$.

###### Proof.

Clearly it is enough to prove the lemma for $r=n+3p+3$. If $|S|\geq p+1$, then
by the results of Corollary 3.20.1 and Lemma 3.21, we may assume that $\forall
q\in Q$, $\text{blue-}d_{Z}(q)\leq n$ and so $\text{red-}d_{Z}(q)\geq p+1$.
Since

$\frac{(p+1)(2p+2)}{n+p+1}>p+1,$

there must be a vertex $z^{\prime}\in Z$ such that
$\text{red-}d_{Q}(z^{\prime})\geq p+2$. We shall now consider two cases based
on the size of $|S|$.

  * •

If $|S|=p+1$, then let $W\subset Q$ be a subset of $R(z^{\prime})\cap Q$ of
size $n+2$, such that there exists a vertex $w_{1}\in W$ that is not in $S$.
Such a subset must exist since $|R(z^{\prime})\cap Q|\geq p+2$, but $|S|=p+1$.
In particular, let $W=\\{w_{1},w_{2},\ldots,w_{n+1},w_{n+2}\\}$, where
$w_{1}\notin S$. Finally, let $w_{n+2}$ be chosen so that $w_{n+2}$ is not
adjacent to $w_{1}$ on $Q$.

  * •

If $|S|\geq p+2$, then let $W\subset Q$ be any subset of $R(z^{\prime})\cap Q$
of size $n+2$, where as above, $W=\\{w_{1},w_{2},\ldots,w_{n+1},w_{n+2}\\}$.
Similarly, choose $w_{n+2}$ so that it is not adjacent to $w_{1}$ on $Q$.

Given the above definitions of $W$, now choose a subset of $p+1$ vertices of
$Q$ including $w_{n+2}$, but excluding $w_{1},\ldots,w_{n+1}$. Furthermore,
choose these $p+1$ vertices so that neither $w_{1}$, nor the two vertices
adjacent to $w_{1}$ on $Q$ are chosen. If $w_{1}=q_{i}$, then removing
$q_{i-1}$, $q_{i}$, $q_{i+1}$, and $W\backslash\\{w_{n+2}\\}$ from
consideration leaves at least

$\displaystyle 2p+2-(n+1)-2$ $\displaystyle=2p-n-1$ $\displaystyle\geq p+1$

vertices to choose from. Call this set of $p+1$ chosen vertices $A$. Since
$A\subset Q$, it follows that $\forall a\in A$, $\text{red-}d_{Z}(a)\geq p+1$.
Since

$p+1\leq|Z|\leq 2(p+1)-2,$

by Lemma 3.5 there must be a red cycle of length $2p+2$ between $A$ and $Z$,
call this red cycle $Q^{\prime}$.

Now, either $z^{\prime}\in Q^{\prime}$ or $z^{\prime}\notin Q^{\prime}$.
First, suppose that $z^{\prime}\in Q^{\prime}$. Then following $Q^{\prime}$
for $2p+1$ vertices from $z^{\prime}$ ends at some other $z_{1}\in Z$, where
$z_{1}\neq u$. Note that such a path always exists since $Q^{\prime}$ can be
followed in two directions; if following $Q^{\prime}$ for $2p+1$ vertices from
$z^{\prime}$ in the “forward" direction ends at $u$, then simply follow
$Q^{\prime}$ in the “backward" direction instead. Since $Q^{\prime}$ contains
$w_{n+2}$, and avoids $w_{1},\ldots w_{n+1}$, this path defines a red
$S_{c}(n+1,1)$, with the $1$-star at $z_{1}\in Z\backslash\\{u\\}$, and the
$n+1$-star centered at $z^{\prime}$. Alternatively suppose that
$z^{\prime}\notin Q^{\prime}$. Then following $Q^{\prime}$ for $2p$ vertices
from $w_{n+2}$ will end at some $z_{1}\in Z$, where again the direction is
chosen so that $z_{1}\neq u$. Appending $z^{\prime}$ to $w_{n+2}$ will again
result in a red path of length $2p+1$ between $A$ and $Z$, with one endpoint
at $z^{\prime}$ and the other endpoint at $z_{1}$. As before, since
$Q^{\prime}$ contains $w_{n+2}$, and avoids $w_{1},\ldots w_{n+1}$, this path
defines a red $S_{c}(n+1,1)$. In either case, there is the desired
$S_{c}(n+1,1)$, with $n$-star at $z^{\prime}$, and $1$-star at $z_{1}$. Now
observe that this red $S_{2p+1}(n+1,1)$ occupies $p+1$ vertices in $Z$. If
$z_{1}$ is connected to any of the remaining $n$ vertices in $Z$ by a red
edge, it will complete a red $S_{c}(n,2)$. Furthermore, if $z_{1}$ is
connected to any of the vertices in $Q\backslash A$ by a red edge, it will
also complete a red $S_{c}(n,2)$. Therefore, $z_{1}$ must be connected to
every vertex in $Q\backslash A$ by a blue edge. Since
$\\{q_{i-1},q_{i},q_{i+1}\\}\subset A$, this implies that $z_{1}$ must be
connected to every $\\{q_{i-1},q_{i},q_{i+1}\\}$ by blue edges (where recall
$q_{i}=w_{1}$).

Let

$Q^{\prime\prime}=\\{q_{1},q_{2},\ldots,q_{i-1},z,q_{i+1},\ldots,q_{2p+1},q_{2p+2}\\}.$

If $|S|\geq p+2$, then this is a blue cycle of length $2p+2$ with
$|S_{Q^{\prime\prime}}|\geq p+1$ (since $z\neq u$, and removing $q_{i}$
removes at most one vertex that belongs to $S$). Also, $z$ has blue degree
$n+1$ off the cycle, since it is connected to $n$ unused vertices in $Z$ by a
blue edge, and also $q_{i}$ which is no longer on the cycle. Now by either
Corollary 3.20.1 or Lemma 3.21 there must be a monochromatic $S_{c}(n,2)$.
Alternatively if $|S|=p+1$, then in this case recall that $q_{i}$ was chosen
specifically such that $q_{i}\notin S$, and so replacing $q_{i}$ with $z$ does
not remove any vertices in $S$ from Q”. Now by Lemma 3.21 there must be a
monochromatic $S_{c}(n,2)$. ∎

Combining the results of Lemma 3.15, Lemma 3.18, and Lemma 3.22, the proof of
Theorem 3.2 is complete.

##  4 Unsolved Problems and Further Results

Here we have proved the ramsey numbers of odd-linked double stars in all cases
where $n\geq c$, and $n\leq\lfloor\frac{c}{2}\rfloor-2$, $m=2$. However, our
work leaves open the result for all other cases with $n<c$. We possess partial
results in some other cases with $n<c$, but most cases remain open.

Beyond the remaining cases of odd-linked double stars, this result more
generally prompts the question of the ramsey numbers of the even-linked double
stars. Surprisingly, the ramsey numbers of even-linked double stars have
proved to be significantly more challenging to determine than odd-linked
double stars. There are, however, some results for specific cases of even-
linked double stars:

  * •

First we simply note that if $c=2p$ the ramsey numbers of $S_{c}(n,0)$ or
$S_{c}(n,1)$ are solved exactly by the result of Lemma 3.3.

  * •

The ramsey numbers of $S_{4}(n,m)$ (example in Figure 2 below) were solved by
Burr and Erdős to be

$r(S_{4}(n,m))=\text{max}(2n+3,n+2m+5).$

See in [9] for detailed proof.

Figure 2: Example of a $S_{4}(6,4)$

  * •

Finally, the ramsey numbers of $S_{2}(n,m)$ (example in Figure 3 below) were
solved, in most cases, by Grossman et. Al. In particular, they show that for
all $n\leq\sqrt{2}m$ and $n\geq 3m$, the ramsey numbers of $S_{2}(n,m)$
satisfy

$r(S_{2}(n,m))=\left\\{\begin{array}[]{lr}\text{max}(n+2m+1,2n+2),&\text{for
}n\text{ odd},m\leq 2\\\
\text{max}(n+2m+2,2n+2),&\text{otherwise}\end{array}\right\\}.$

See [2] for detailed proof. It was conjectured in [2] that the above result
holds in the range $\sqrt{2}m<n<3m$ as well. Surprisingly however, Norin et.
Al showed in [3] that the conjecture is false, as well as providing asymptotic
results for the ramsey numbers of $S_{2}(n,m)$ in the gap. The exact value of
$r(S_{2}(n,m))$ in the range $\sqrt{2}m<n<3m$, however, remains an open
question.

Figure 3: Example of a $S_{2}(8,5)$

We generally ask then, for either $c\geq 6$ or $c=2$, what are the ramsey
numbers of the even-linked double stars?

## References

  * [1] Radziszowski, S. P. 1994. Small RAMSEY numbers. Electron. J. Combinatorics 1. Revision 16: January 15, 2021.]]
  * [2] J. W. Grossman, F. Harary, and M. Klawe. Generalized Ramsey theory for graphs. X. Double stars. Discrete Mathematics, 28(3):247–254, 1979.
  * [3] Norin, S., Sun, Y. R., and Zhao, Y. Asymptotics of Ramsey numbers of double stars. Preprint 2016, arXiv:1605.03612.
  * [4] Pei Yu and Yusheng Li, All Ramsey Numbers for Brooms in Graphs, Electronic Journal of Combinatorics, http://www.combinatorics.org, 2016.
  * [5] B. Jackson, Cycles in bipartite graphs, J. Combin. Theory Ser. B, 30 (1981), 332-342.
  * [6] R. Faudree and R. Schelp. All Ramsey numbers for cycles in graphs. Discrete Math., 8:35-52,1974
  * [7] V. Rosta, On a Ramsey Type Problem of J.A. Bondy and P. Erdős, I $\&$ II,Journal of CombinatorialTheory,Series B,15(1973) 94-120.
  * [8] T.D. Parsons. Path-star Ramsey numbers. J. Combin. Theory Ser. B, 17 (1974), pp. 51-58
  * [9] S. Burr and P. Erdős, Extremal Ramsey theory for graphs, Utilitas Mathematica 9 (1976) 246-258.