#  Gallai-Ramsey numbers involving a rainbow $4$-path 111Supported by the
National Science Foundation of China (Nos. 12061059, 11601254, 11551001) and
the Qinghai Key Laboratory of Internet of Things Project (2017-ZJ-Y21).

Jinyu Zou 222Department of Basic Research, Qinghai University, Xining, 810016,
China<EMAIL_ADDRESS>Zhao Wang333College of Science, China Jiliang
University, Hangzhou 310018, China<EMAIL_ADDRESS>Hong-Jian
Lai444Department of Mathematics, West Virginia University, Morgantown, WV
26506-6310, USA<EMAIL_ADDRESS>Yaping Mao555School of Mathematics and
Statistis, Qinghai Normal University, Xining, Qinghai 810008, China.
<EMAIL_ADDRESS>666Academy of Plateau Science and Sustainability, Xining,
Qinghai 810008, China. 777Corresponding author

###### Abstract

Given two non-empty graphs $G,H$ and a positive integer $k$, the Gallai-Ramsey
number $\operatorname{gr}_{k}(G:H)$ is defined as the minimum integer $N$ such
that for all $n\geq N$, every $k$-edge-coloring of $K_{n}$ contains either a
rainbow colored copy of $G$ or a monochromatic copy of $H$. In this paper, we
got some exact values or bounds for $\operatorname{gr}_{k}(P_{5}:H)\ (k\geq
3)$ if $H$ is a general graph or a star with extra independent edges or a
pineapple.
Keywords: Ramsey theory; Gallai-Ramsey number; Pineapple; Star with extra
independent edges
AMS subject classification 2020: 05D10; 05C15.

##  1 Introduction

All graphs considered are finite, simple and undirected. We follow the
notation and terminology of Bondy [1]. Let $V(G)$, $E(G)$, $e(G)$, $\delta(G)$
be the vertex set, edge set, size, minimum degree of graph $G$, respectively.
We use $G-X$ to denote the subgraph of $G$ obtained by removing all the
vertices of $X$ together with the edges incident with them from $G$;
similarly, we use $G\setminus M$ to denote the subgraph of $G$ obtained by
removing all the edges of $M$ from $G$. The union $G\cup H$ of two graphs $G$
and $H$ is the graph with vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup
E(H)$. We call the path $P_{t+1}$, of order $t+1$ and having $t$ edges, a _$t$
-path_. A complete graph is a graph in which every pair of vertices are
adjacent, and a complete graph on $n$ vertices is denoted by $K_{n}$. Let
$[a,b]$ be the interval from $a$ to $b$.

An $k$-edge-coloring is _exact_ if all colors are used at least once. In this
work, we consider only exact edge-colorings of graphs. An edge colored graph
is called rainbow if all edges have different colors and monochromatic if all
edges have a single color.

###  1.1 Classical Ramsey number

Ramsey theory were introduced in 1930; see [24]. The main subject of the
theory are complete graphs whose subgraphs can have some regular properties.

######  Definition 1.

Given $k$ graphs $H_{1},H_{2},\ldots,H_{k}$, the _Ramsey number_
$\operatorname{R}(H_{1},H_{2},\ldots,H_{k})$ is defined as the minimum number
of vertices $n$ needed so that every $k$-edge-coloring of $K_{n}$ contains a
monochromatic $H_{i}$, where $1\leq i\leq n$.

If $H_{1}=H_{2}=\cdots=H_{k}$, then we write the number as
$\operatorname{R}_{k}(H)$. If $H_{i}=K_{k_{i}}\ (1\leq i\leq k)$, then we use
the abbreviation $\operatorname{R}(k_{1},\dots,k_{k})$.

Ramsey number has its applications on the fields of communications,
information retrieval in computer science, and decision-making; see [25, 26]
for examples. We refer the interested reader to [23] for a dynamic survey of
small Ramsey numbers.

###  1.2 Gallai-Ramsey number

Edge colorings of complete graphs that contain no rainbow triangle have very
interesting and somewhat surprising structure. In 1967, Gallai [10] first
examined this structure under the guise of transitive orientations of graphs
and it can also be traced back to [2]. For this reason, colored complete
graphs containing no rainbow triangle are called _Gallai colorings_. Gallai’s
result was restated in [11] in the terminology of graphs. For the following
statement, a trivial partition is a partition into only one part.

######  Theorem 1.1.

[2, 10, 11] In any coloring of a complete graph containing no rainbow
triangle, there exists a nontrivial partition of the vertices (called a Gallai
partition), say $H_{1},H_{2},\ldots,H_{t}$, satisfying the following two
conditions.

$(a)$ The number of colors on the edges among $H_{1},H_{2},\ldots,H_{t}$ are
at most two.

$(b)$ For each part pair $H_{i},H_{j}\ (1\leq i\neq j\leq t)$, all the edges
between $H_{i}$ and $H_{j}$ receive the same color.

The induced subgraph of a Gallai colored complete graph constructed by
selecting a single vertex from each part of a Gallai partition is called the
_reduced graph_. By Theorem 1.1, the reduced graph is a $2$-colored complete
graph. This kind of restriction on the distribution of colors has led to a
variety of interesting works like [14].

######  Definition 2.

Given two graphs $G$ and $H$, the _general $k$-colored Gallai-Ramsey number_
$\operatorname{gr}_{k}(G:H)$ is defined to be the minimum integer $m$ such
that every $k$-coloring of the complete graph on $m$ vertices contains either
a rainbow copy of $G$ or a monochromatic copy of $H$.

With the additional restriction of forbidding the rainbow copy of $G$, it is
clear that $\operatorname{gr}_{k}(G:H)\leq\operatorname{R}_{k}(H)$ for any
$G$. Till now, most work focuses on the case $G=K_{3}$; see [3, 6, 8, 11, 11,
15, 16, 20, 21, 22, 30, 33]. For more details on the Gallai-Ramsey numbers, we
refer to the book [19] and a survey paper [7].

###  1.3 Structural theorems and main results

Thomason and Wagner [29] obtained the structural theorems for $P_{4}$ and
$P_{5}$.

######  Theorem 1.2.

[29] Let $K_{n}$, $n\geq 4$, be edge colored so that it contains no rainbow
$3$-path $P_{4}$. Then one of the following holds:

$(a)$ at most two colors are used;

$(b)$ $n=4$ and three colors are used, each color forming a $1$-factor.

In an edge-colored graph, define $V^{(j)}$ as the set of vertices with at
least one incident edge in color $j$ and denote $E^{(j)}$ to be the set of
edges of color $j$ for a given color $j$.

######  Theorem 1.3.

[29] Let $K_{n}$, $n\geq 5$, be edge colored so that it contains no rainbow
$4$-path $P_{5}$. Then, after renumbering the colors, one of the following
must hold:

$(a)$ at most three colors are used;

$(b)$ color $1$ is dominant, meaning that the sets $V^{(j)}$, $j\geq 2$, are
disjoint;

$(c)$ $K_{n}-a$ is monochromatic for some vertex $a$;

$(d)$ there are three vertices $a,b,c$ such that $E^{(2)}=\\{ab\\}$,
$E^{(3)}=\\{ac\\}$, $E^{(4)}$ contains $bc$ plus perhaps some edges incident
with $a$, and every other edge is in $E^{(1)}$;

$(e)$ there are four vertices $a,b,c,d$ such that $\\{ab\\}\subseteq
E^{(2)}\subseteq\\{ab,cd\\}$, $E^{(3)}=\\{ac,bd\\}$, $E^{(4)}=\\{ad,bc\\}$ and
every other edge is in $E^{(1)}$;

$(f)$ $n=5$, $V(K_{n})=\\{a,b,c,d,e\\}$, $E^{(1)}=\\{ad,ae,bc\\}$,
$E^{(2)}=\\{bd,be,ac\\}$, $E^{(3)}=\\{cd,ce,ab\\}$ and $E^{(4)}=\\{de\\}$.

Li et al. [18] got some exact values and bounds of
$\operatorname{gr}_{k}(P_{5}:K_{t})$, and investigated the edge-colorings of
complete graphs and complete bipartite graphs without rainbow $4$-path and
$5$-path. Fujita and Magnant [9] got the structural theorem for $G=S_{3}^{+}$
like Theorem 1.1. Li and Wang [17] studied the monochromatic stars in rainbow
$K_{3}$-free and $S_{3}^{+}$-free colorings.

We now give the definitions of two graph classes.

  * The graph $S_{t}^{r}$ is obtained from a star of order $t$ by adding an extra $r$ independent edges between the leaves of the so that there are $r$ triangles and $t-2r-1$ pendent edges in $S_{t}^{r}$. For $r=0$ we obtain $S_{t}^{r}=K_{1,t-1}$, which are called _stars_. For $r=\frac{t-1}{2}$, if $t$ is odd we obtain $S_{t}^{r}=F_{\frac{t-1}{2}}$, which are called _fans_.

  * A _pineapple_ $PA_{t,\omega}$ is a graph obtained from the complete graph $K_{\omega}$ by attaching $t-\omega$ pendent vertices to the same vertices of $K_{\omega}$, we suppose that $t\geq\omega+1$.

In Section $2$, we get some exact values or bounds for
$\operatorname{gr}_{k}(P_{5}:H)$, where $H$ is a general graph. In Section
$3$, we obtain some results when $H=S_{t}^{r}$, where $t\geq 2r+2$ and $r\geq
1$. We also get some results in Section $4$ when $H$ is a pineapple.

##  2 General results

In this section, we assume that $H$ is a graph of order $t$.

######  Theorem 2.1.

For two integers $k,t$ with $k\geq 7$ and $k\geq t+1$, we have

$\operatorname{gr}_{k}(P_{5}:H)=\left\lceil\frac{1+\sqrt{1+8k}}{2}\right\rceil.$

###### Proof.

Let $N_{k}$ be an integer with $N_{k}=\lceil\frac{1+\sqrt{1+8k}}{2}\rceil$.
For the lower bound, if there is a $k$-edge-coloring $\chi$ of a complete
graph $K_{N_{k}-1}$, then $k\leq\tbinom{N_{k}-1}{2}$, contradicting with
$N_{k}=\lceil\frac{1+\sqrt{1+8k}}{2}\rceil$. It follows that
$\operatorname{gr}_{k}(P_{5}:H)\geq N_{k}$.

It suffices to show that $\operatorname{gr}_{k}(P_{5}:H)\leq N_{k}$. Let
$\chi$ be any $k$-edge-coloring of $K_{n}\ (n\geq N_{k})$ containing no
rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is
true, let $V^{(2)},V^{(3)},\ldots,V^{(k)}$ be a partition of $V(K_{n})$ such
that there are only edges of color $1$ or $i$ within $V^{(i)}$ for $2\leq
i\leq k$, and hence there are only edges of color $1$ among the parts. Choose
one vertex of $V^{(i)}$, say $v_{i}$. Then the subgraph induced by
$\\{v_{2},v_{3},\ldots,v_{k}\\}$ is a complete graph $K_{k-1}$. For $k\geq
t+1$, there exists a monochromatic copy of $K_{t}$ colored by $1$, and hence
there is a monochromatic copy of $H$ colored by $1$. If $(c)$ is true, then
there is a vertex $v$ such that $K_{n}-v$ is monochromatic and $n\geq k$. For
$k\geq t+1$ and $n\geq t+1$, there is a monochromatic copy of $K_{t}$, and so
we can find a monochromatic copy of $H$. ∎

######  Theorem 2.2.

Let $k,t$ be two integers with $k=5,6$, $k\geq t+1$ and $t\geq 3$. Then
$\operatorname{gr}_{k}(P_{5}:H)=5$.

###### Proof.

For the lower bound, we first suppose $k=5$. Let $G_{1}$ denote a colored
complete graph $K_{4}$ with $V(K_{4})=\\{v_{i}\,|\,1\leq i\leq 4\\}$ under the
$5$-edge-coloring $\chi$ such that $\chi(v_{1}v_{2})=\chi(v_{3}v_{4})=1$,
$\chi(v_{1}v_{3})=2$, $\chi(v_{1}v_{4})=3$, $\chi(v_{2}v_{3})=4$ and
$\chi(v_{2}v_{4})=5$. Next, we suppose $k=6$. Let $G_{2}$ denote a colored
complete graph $K_{4}$ with $V(K_{4})=\\{v_{i}\,|\,1\leq i\leq 4\\}$ under the
$6$-edge-coloring $\chi$ such that $\chi(v_{1}v_{2})=1$, $\chi(v_{3}v_{4})=2$,
$\chi(v_{1}v_{3})=3$, $\chi(v_{1}v_{4})=4$, $\chi(v_{2}v_{3})=5$ and
$\chi(v_{2}v_{4})=6$. Since both $G_{1}$ and $G_{2}$ contain neither a rainbow
copy of $P_{5}$ nor a monochromatic copy of $H$, it follows that
$\operatorname{gr}_{k}(P_{5}:H)\geq 5$ for $k=5,6$.

It suffices to show that $\operatorname{gr}_{k}(P_{5}:H)\leq 5$. Suppose $G$
is any $k\ (k=5,6)$-edge-coloring of $K_{n}\ (n\geq 5)$ which contains no
rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ is true, and the
proof is similar to Theorem 2.1. ∎

For $k=t$, we first show that $H$ is not a complete graph.

######  Theorem 2.3.

Let $k,t$ be two integers with $k\geq 5$ and $k=t$. Then

$\operatorname{gr}_{k}(P_{5}:H)=t+1.$

###### Proof.

For the lower bound, from Theorem 2.1, let $G_{3}$ be a complete graph
obtained from a $K_{t-1}$ with vertex set $\\{u_{1},u_{2},\ldots,u_{t-1}\\}$
colored with $1$ by adding a new vertex $u$ and edges $u_{i}u(1\leq i\leq
t-1)$ colored by $i+1$. Note that there is neither a rainbow copy of $P_{5}$
nor a monochromatic copy of $H$. Thus $\operatorname{gr}_{k}(P_{5}:H)\geq
t+1$.

It suffices to show that $\operatorname{gr}_{k}(P_{5}:H)\leq t+1$. Let $\chi$
be any $k$-edge-coloring of $K_{n}\ (n\geq t+1)$ containing no rainbow copy of
$P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is true, choose
one vertex of $V^{(i)}(2\leq i\leq k)$, say $v_{i}$. Then
$\\{v_{2},v_{3},\ldots,v_{k}\\}$ induced a complete graph $K_{k-1}$. For
$k\geq t$, there exists a monochromatic copy of $K_{t-1}$ with color $1$. As
$|V^{(i)}|\geq 2$, we can choose another vertex of $V^{(2)}$, say $u$. Note
that $\\{u,v_{2},v_{3},\ldots,v_{k}\\}$ induced a monochromatic $K_{t}-e$,
$e=uv_{2}$. Then there is a copy of $H$ with color $1$. If $(c)$ is true,
there is a vertex $v$ such that $K_{n}-v$ is monochromatic. For $n\geq t+1$,
there is a monochromatic copy of $K_{t}$, we can find a monochromatic copy of
$H$. ∎

Next we obtain the result on $H$ is not a complete graph by the following
lemma.

######  Lemma 2.1.

For $4\leq k\leq a$, if $H_{t}$ is a graph of order $t$ and $K_{a}\ (a\geq 3)$
be the maximal clique of $H_{t}$, then
$\operatorname{gr}_{k}(P_{5}:H_{t})\geq(a-1)(t-1)+1$.

###### Proof.

Let $G_{4}$ be a complete graph with $V(G_{4})=U_{2}\cup U_{3}\cup\cdots\cup
U_{a}$ such that the graph induced by $U_{i}\ (2\leq i\leq a)$ is a complete
graph $K_{t-1}$, the set $\\{U_{2},U_{3},\ldots,U_{a}\\}=X_{2}\cup\cdots\cup
X_{k}$ with each $K_{t-1}$ of $X_{j}\ (2\leq j\leq k)$ colored by $j$ and
$|X_{j}|=\lfloor\frac{a-1}{k-1}\rfloor$ or $\lfloor\frac{a-1}{k-1}\rfloor+1\
(2\leq j\leq k)$, $|X_{2}|+|X_{3}|+\cdots+|X_{k}|=a-1$, all edges between
$U_{i}$ and $U_{s}\ (i\neq s)$ are colored by $1$. Thus
$|V(G_{4})|=(a-1)(t-1)$. It is clear that $G_{4}$ contains neither a rainbow
copy of $P_{5}$ nor a monochromatic copy of $H_{t}$, and so
$\operatorname{gr}_{k}(P_{5}:H_{t})\geq(a-1)(t-1)+1$. ∎

Next, we suppose that $H$ is a complete graph $K_{t}$.

######  Theorem 2.4.

For two integers $k,t$ with $k\geq 5$ and $k=t$,
$\operatorname{gr}_{k}(P_{5}:K_{t})=(t-1)^{2}+1$.

###### Proof.

From Lemma 2.1, we have $\operatorname{gr}_{k}(P_{5}:H)\geq(t-1)^{2}+1$. It
suffices to show that $\operatorname{gr}_{k}(P_{5}:H)\leq(t-1)^{2}+1$. Suppose
that $\chi$ is any $k$-edge-coloring of $K_{n}\ (n\geq(t-1)^{2}+1)$ containing
no rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$
is true, we can choose one vertex of $V^{(i)}\ (2\leq i\leq k)$, say $v_{i}$,
then $\\{v_{2},v_{3},\ldots,v_{k}\\}$ induces a monochromatic copy of
$K_{t-1}$. If there is a vertex of $V^{(i)}\ (2\leq i\leq k)$, say $V^{(2)}$
and $u_{2}\in V^{(2)}$, such that $\chi(v_{2}u_{2})=1$, then the graph induced
by $\\{u_{2},v_{2},v_{3},\ldots,v_{k}\\}$ is a monochromatic copy of $K_{t}$
colored by $1$. If the graph induced by $V^{(i)}\ (2\leq i\leq k)$ contains no
edges colored by $1$, as $n\geq(t-1)^{2}+1$, there is $|V^{(i)}|\geq t\ (2\leq
i\leq k)$, say $|V^{(2)}|\geq t$. Thus the graph induced by $V^{(2)}$ is a
monochromatic copy of $K_{t}$ colored by $2$. ∎

######  Remark 2.1.

For two integers $k,t$ with $k\geq 5$ and $k=t$, if $H$ is not a complete
graph and $|V(H)|=t$, then
$\operatorname{gr}_{k}(P_{5}:K_{t})-\operatorname{gr}_{k}(P_{5}:H)=(t-1)^{2}+1-(t+1)=(t-1)(t-2)-1$
can be arbitrarily large.

From Theorems 2.1, 2.2, 2.3 and 2.4, we obtain the following corollary.

######  Corollary 2.5.

For integers $k\geq 5$ and $k\geq t$,

$\operatorname{gr}_{k}(P_{5}:H)=\begin{cases}\max{\\{\lceil\frac{1+\sqrt{1+8k}}{2}\rceil,5\\}},&k\geq
t+1;\\\ t+1,&k=\text{t and H is not a complete graph};\\\
(t-1)^{2}+1,&k=\text{t and H is a complete graph}.\end{cases}$

The following theorem shows the result on the graph $H$ obtained from a
complete graph $K_{t}$ by deleting a maximally matching $M$.

######  Theorem 2.6.

For two integers $k,t$ with $\lceil\frac{t+2}{2}\rceil\leq k\leq t-1$ and
$k\geq 5$, if $H$ is a graph obtained from a complete graph $K_{t}$ by
deleting a maximally matching $M$, then

$\operatorname{gr}_{k}(P_{5}:H)=\max\left\\{\left\lceil\frac{1+\sqrt{1+8k}}{2}\right\rceil,t+1\right\\}.$

###### Proof.

From Theorem 2.3, we have
$\operatorname{gr}_{k}(P_{5}:H)\geq\lceil\frac{1+\sqrt{1+8k}}{2}\rceil$. Let
$G_{5}$ be a complete graph obtained from a $K_{t-1}$ with vertex set
$\\{w_{1},w_{2},\ldots,w_{t-1}\\}$ colored by $1$ by adding a new vertex $w$
and edge set $\\{w_{i}w\,|\,1\leq i\leq t-1\\}=W_{1}\cup W_{2}\cup\cdots\cup
W_{k}$ with
$|W_{i}|=\lfloor\frac{t-1}{k-1}\rfloor\text{or}\lfloor\frac{t-1}{k-1}\rfloor+1$,
$|W_{1}|+\cdots+|W_{k}|=t-1$. Clearly, $G_{5}$ contains neither a rainbow copy
of $P_{5}$ nor a monochromatic copy of $H$, and hence
$\operatorname{gr}_{k}(P_{5}:H)\geq t+1$. So
$\operatorname{gr}_{k}(P_{5}:H)\geq\max{\\{\lceil\frac{1+\sqrt{1+8k}}{2}\rceil,t+1\\}}$.

It suffices to show that
$\operatorname{gr}_{k}(P_{5}:H)\leq\max{\\{\lceil\frac{1+\sqrt{1+8k}}{2}\rceil,t+1\\}}$.
Let $N$ be an integer with
$N=\max{\\{\lceil\frac{1+\sqrt{1+8k}}{2}\rceil,t+1\\}}$. Suppose that $\chi$
is any $k$-edge-coloring of $K_{n}\ (n\geq N)$ containing no rainbow copy of
$P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is true, then for
$|V^{(i)}|\geq 2\ (2\leq i\leq k)$, we choose two vertices from $V^{(i)}\
(2\leq i\leq k)$, say $u_{i},v_{i}$. Then
$\\{u_{2},v_{2},u_{3},v_{3},\ldots,u_{k},v_{k}\\}$ induced a monochromatic
copy of graph $K_{2k-2}\setminus M$ with color $1$, where $M$ is a maximally
matching of $K_{2k-2}$. Since $2k-2\geq t$, it follows that there is a copy of
graph $H$ with color $1$. If $(c)$ is true, then there is a vertex $v$ such
that $K_{n}-v$ is monochromatic. For $n\geq t+1$, there is a monochromatic
$K_{t}$, we can find a monochromatic copy of $H$. ∎

The lower and upper bounds of $\operatorname{gr}_{k}(P_{5}:H)$ on $\Delta(H)$
is shown in the following theorem.

######  Theorem 2.7.

Let $k,t,p,q$ be four positive integers with $5\leq k\leq t-1$. If
$\Delta(H)-1=p(k-2)+q,q\in\\{0,1,\ldots,k-3\\}$ and
$\operatorname{R}_{2}(H)\geq t+1$, then

$\max{\\{\Delta(H)+p,t+1\\}}\leq\operatorname{gr}_{k}(P_{5}:H)\leq\operatorname{R}_{2}(H).$

###### Proof.

We first show that
$\operatorname{gr}_{k}(P_{5}:H)\geq\max{\\{\Delta(H)+p,t+1\\}}$. Let $G_{6}$
be a complete graph with $V(G_{6})=U_{2}\cup U_{3}\cup\cdots\cup U_{k}$ such
that the graph induced by $U_{i}\ (2\leq i\leq k)$ is a monochromatic graph
with color $i$, and all edges between $U_{i}$ and $U_{j}\ (i\neq j)$ are
colored by $1$, $|U_{i}|=p+1\ (2\leq i\leq q+1)$, $|U_{i}|=p\ (q+2\leq i\leq
k)$. Thus $|V(G_{6})|=(k-1)p+q$. Choose any $k-2$ $U_{i}$’s from
$\\{U_{2},U_{3},\ldots,U_{k}\\}$, say $U_{2},\ldots,U_{k-1}$. Then
$|U_{2}|+\cdots+|U_{k-1}|\leq\Delta(H)-1$. For any vertex of $U_{i}$, say
$u_{i}\ (2\leq i\leq k)$, the degree of $u_{i}$ in $G_{6}$ is at most
$\Delta(H)-1$. Note that both $G_{5}$ and $G_{6}$ have neither a rainbow copy
of $P_{5}$ nor a monochromatic copy of $H$. So
$\operatorname{gr}_{k}(P_{5}:H)\geq\max{\\{(k-1)p+q+1,t+1\\}}$.

It suffices to show that
$\operatorname{gr}_{k}(P_{5}:H)\leq\operatorname{R}_{2}(H)$. Let $\chi$ be any
$k$-edge-coloring of $K_{n}\ (n\geq\operatorname{R}(H))$ containing no rainbow
copy of $P_{5}$, From Theorem 1.3, $(b)$ or $(c)$ is true. We first consider
$(b)$ is true. Let $V^{(2)},V^{(3)},\ldots,V^{(k)}$ be a partition of
$V(K_{n})$ such that there are only edges of color $1$ or $i$ within $V^{(i)}$
for $2\leq i\leq k$, and there are only edges of color $1$ between the parts.
Now we recolor the edges of $K_{n}$ to make a $2$-edge coloring of $K_{n}$
such that all edges with color $i\ (3\leq i\leq k)$ of $V^{(i)}\ (3\leq i\leq
k)$ are changed to color $2$. Let $F$ denote the resulting graph. Since
$|V(F)|=n\geq\operatorname{R}_{2}(H)$, it follows that $K_{n}$ must contain a
monochromatic copy of $H$. If $(c)$ is true, as $\operatorname{R}_{2}(H)\geq
t+1$, there is a vertex $v$ such that $K_{\operatorname{R}_{2}(H)}-v$ is
monochromatic, say color $1$, and so there is a monochromatic copy of $H$. ∎

##  3 Results for the rainbow $4$-path and monochromatic $S_{t}^{r}$

From the result on general results in Section $2$, we investigate the case
$3\leq k\leq t-1$ for the graph $S_{t}^{r}$. First we consider $5\leq k\leq
t-1$.

######  Theorem 3.1.

Let $k,r,t$ be three integers with $5\leq k\leq t-1$ and $1\leq r\leq k-2$.
Then

$\operatorname{gr}_{k}(P_{5}:S_{t}^{r})=\max{\\{t+p-1,t+1\\}},$

where $t-2=p(k-2)+q$, $q\in\\{0,1,\ldots,k-3\\}$.

###### Proof.

From Theorem 2.7, we have
$\operatorname{gr}_{k}(P_{5}:S_{t}^{r})\geq\max{\\{t+p-1,t+1\\}}$. It suffices
to show that
$\operatorname{gr}_{k}(P_{5}:S_{t}^{r})\leq\max{\\{t+p-1,t+1\\}}$. Let
$N=\max{\\{t+p-1,t+1\\}}$. Suppose $G$ is any $k$-edge-coloring of $K_{n}\
(n\geq N)$ which contains no rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$
or $(c)$ is true. We first consider $(b)$ is true. As $N\geq t+p-1$, there
must be $k-2$ $V^{(i)}$’s of $\\{V^{(2)},V^{(3)},\ldots,V^{(k)}\\}$, say
$V^{(2)},V^{(3)},\ldots,V^{(k-1)}$, such that
$|V^{(2)}|+\cdots+|V^{(k-1)}|\geq t-1$. Choose one vertex $u$ of $V^{(k)}$,
and $\ell_{i}\ (\ell_{i}\geq 2,\sum_{2\leq i\leq k-1}\ell_{i}=t-1)$ vertices
of $V^{(i)}\ (2\leq i\leq t-1)$, and $|V^{(i)}|\geq 2\ (2\leq i\leq k)$,
$\Delta(S_{t}^{r})=t-1$, the graph induced by these vertices contains a
monochromatic copy of $S_{t}^{r}$. If $(c)$ is true, as $n\geq t+1$, there is
a vertex $v$ such that $K_{n}-v$ is monochromatic, say color $1$, and hence
there is monochromatic copy of $S_{t}^{r}$. ∎

Next, we show the result on the case $k=4$ for $S_{t}^{r}$.

######  Theorem 3.2.

Let $k,t,r$ be three integers with $k=4$, $t\geq 6$ and $r=1,2$. Then

$\operatorname{gr}_{4}(P_{5}:S_{t}^{r})=t+p-1,$

where $t-2=2p+q$ and $q\in\\{0,1\\}$.

###### Proof.

For the lower bound, let $F_{1}$ be a $4$-edge-coloring complete graph with
$V(F_{1})=U_{2}\cup U_{3}\cup U_{4}$, and the graph induced by
$U_{2},U_{3},U_{4}$ are $K_{p+1}$ if $q=1$ or $K_{p}$ if $q=0$ colored by $2$,
$K_{p}$ colored by $3$, $K_{p}$ colored by $4$ respectively, and there are
only edges of color $1$ between the parts. Then $|V(F_{1})|=3p+q$. Let $F_{2}$
be a complete graph obtained from a $K_{t-1}$ with vertex set
$\\{w_{1},w_{2},\ldots,w_{t-1}\\}$ colored by $1$ by adding a new vertex $w$
and edge set $\\{w_{i}w,1\leq i\leq t-1\\}=W_{1}\cup W_{2}\cup W_{3}\cup
W_{4}$ with
$|W_{i}|=\lfloor\frac{t-1}{3}\rfloor\text{or}\lfloor\frac{t-1}{3}\rfloor+1$,
$|W_{1}|+|W_{2}|+|W_{3}|+|W_{4}|=t-1$. Note that both $F_{1}$ and $F_{2}$
contain neither a rainbow copy of $P_{5}$ nor a monochromatic copy of
$S_{t}^{r}$. So $\operatorname{gr}_{k}(P_{5}:S_{t}^{r})\geq t+p-1$.

It suffices to show that $\operatorname{gr}_{k}(P_{5}:S_{t}^{r})\leq t+p-1$.
Suppose $G$ is any $4$-edge-coloring of $K_{n}$ where $n\geq t+p-1$ which
contains no rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$
or $(e)$ is true. Suppose that $(b)$ is true. Let $V^{(2)},V^{(3)},V^{(4)}$ be
a partition of $V(G)$ such that there are only edges of color $1$ or $i$
within $V^{(i)}$ for $2\leq i\leq 4$. Then there are only edges with color $1$
among the parts. Since $n\geq t+p-1$, it follows that there exist two
$V^{(i)}$’s of $\\{V^{(2)},V^{(3)},V^{(4)}\\}$, say $V^{(2)},V^{(3)}$, such
that $|V^{(2)}|+|V^{(3)}|\geq t-1$, otherwise $n<t$, a contradiction. Choose
one vertex of $V^{(4)}$, say $v$, $\ell_{1}\ (\ell_{1}\geq 2)$ vertices of
$V^{(2)}$, say $\\{u_{1},\ldots,u_{\ell_{1}}\\}$ and $\ell_{2}\ (\ell_{2}\geq
2)$ vertices of $V^{(3)}$, say $\\{w_{1},\ldots,w_{\ell_{2}}\\}$,
$\ell_{1}+\ell_{2}=t-1$. Then the subgraph induced by
$\\{v,u_{1},\ldots,u_{\ell_{1}},w_{1},\ldots,w_{\ell_{2}}\\}$ contains a
monochromatic copy of $S_{t}^{r}$. Suppose that $(c)$ is true. Since $n\geq
t+p-1$, $t-2=2p+q$ and $q\in\\{0,1\\}$, it follows that $n\geq t+1$, and hence
there is a vertex $v$ such that $K_{n}-v$ is monochromatic, say color $1$, and
hence there is monochromatic copy of $S_{t}^{r}$. Suppose that $(d)$ or $(e)$
is true. Since $t\geq 6$ and $n\geq 7$, it follows that there is a
monochromatic copy of $S_{t}^{r}$. ∎

######  Lemma 3.1.

$\operatorname{gr}_{4}(P_{5}:S_{4}^{1})=6$.

###### Proof.

Let $F_{3}$ be a colored complete graph $K_{5}$ with $V(K_{5})=\\{v_{i}|1\leq
i\leq 5\\}$ under the $4$-edge-coloring $\chi$ such that
$\chi(v_{1}v_{4})=\chi(v_{1}v_{5})=\chi(v_{2}v_{3})=1$,
$\chi(v_{1}v_{3})=\chi(v_{2}v_{4})=\chi(v_{2}v_{5})=2$,
$\chi(v_{1}v_{2})=\chi(v_{3}v_{4})=\chi(v_{3}v_{5})=3$, and
$\chi(v_{4}v_{5})=4$. Since there is neither a rainbow copy of $P_{5}$ nor a
monochromatic copy of $S_{4}^{1}$ under the coloring $\chi$, it follows that
$\operatorname{gr}_{4}(P_{5}:S_{4}^{1})\geq 6$. It suffices to show
$\operatorname{gr}_{4}(P_{5}:S_{4}^{1})\leq 6$. Suppose $G$ is any $4$-edge-
coloring of $K_{n}$ where $n\geq 6$ containing no rainbow copy of $P_{5}$.
From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$ is true. If $(b)$ is true,
then there is a monochromatic $S_{4}^{1}$ with color $1$. If $(c)$ is true,
then $K_{n}-v$ is monochromatic, and hence there is a monochromatic
$S_{4}^{1}$. If $(d)$ or $(e)$ is true, there is a monochromatic $S_{4}^{1}$
with color $1$. ∎

######  Lemma 3.2.

$\operatorname{gr}_{4}(P_{5}:S_{5}^{1})=6$.

###### Proof.

Since $F_{3}$ contains neither a rainbow copy of $P_{5}$ nor a monochromatic
copy of $S_{5}^{1}$ under the coloring $\chi$, it follows that
$\operatorname{gr}_{4}(P_{5}:S_{5}^{1})\geq 6$. It suffices to show
$\operatorname{gr}_{4}(P_{5}:S_{5}^{1})\leq 6$. Suppose that $G$ is any
$4$-edge-coloring of $K_{n}$ where $n\geq 6$ containing no rainbow copy of
$P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$ is true. If $(b)$
is true, then there is a monochromatic $S_{5}^{1}$ with color $1$. If $(c)$ is
true, then $K_{n}-v$ is monochromatic, and hence there is a monochromatic
$S_{5}^{1}$. If $(d)$ or $(e)$ is true, we can find a monochromatic copy of
$S_{5}^{1}$ with color $1$. ∎

The following corollary follows from Theorem 3.2, Lemma 3.1 and Lemma 3.2.

######  Corollary 3.3.

Let $k,t,r$ be three integers with $k=4$, $t\geq 6$ and $r=1,2$. Then

$\operatorname{gr}_{4}(P_{5}:S_{t}^{r})=\begin{cases}6,&t=4,5;\\\ t+p-1,&t\geq
6.\end{cases}$

######  Theorem 3.4.

If $r\geq 3$ and $t$ is odd, then

$\operatorname{gr}_{4}(P_{5}:S_{t}^{r})=\begin{cases}\frac{3t-5}{2},&3\leq
r\leq\lfloor\frac{t-1}{4}\rfloor;\\\ t+2r-2,&\lceil\frac{t-1}{4}\rceil\leq
r\leq\frac{t-3}{2}.\end{cases}$

###### Proof.

Suppose $3\leq r\leq\lfloor\frac{t-1}{4}\rfloor$. For the lower bound, let
$F_{4}$ be a $4$-edge-coloring complete graph with $V(F_{4})=U_{2}\cup
U_{3}\cup U_{4}$ and the graph induced by $U_{2}$ is a complete graph
$K_{\frac{t-1}{2}}$ colored by $2$, and the graph induced by $U_{i}\ (i=3,4)$
is a complete graph $K_{\frac{t-3}{2}}$ colored by $i$, and there are only
edges of color $1$ between the parts, and so $|V(G_{1})|=\frac{3t-7}{2}$.
Since $F_{4}$ contains no rainbow copy of $P_{5}$ and no monochromatic copy of
$S_{t}^{r}$, it follows that
$\operatorname{gr}_{4}(P_{5}:S_{t}^{r})\geq\frac{3t-5}{2}$.

It suffices to show that
$\operatorname{gr}_{4}(P_{5}:S_{t}^{r})\leq\frac{3t-5}{2}$. Suppose that $G$
is any $4$-edge-coloring of $K_{n}$ where $n\geq\frac{3t-5}{2}$ containing no
rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(d)$ is
true. If $(b)$ is true, let $V^{(2)},V^{(3)},V^{(4)}$ be a partition of $V(G)$
such that there are only edges of color $1$ or $i$ within $V^{(i)}$ for $2\leq
i\leq 4$, and there are only edges of color $1$ between the parts. Without
loss of generality, suppose $|V^{(2)}|\geq|V^{(3)}|\geq|V^{(4)}|$. If
$|V^{(3)}|\leq r-1$, then $|V^{(4)}|\leq r-1$ and
$|V^{(2)}|\geq\frac{3t-5}{2}-2(r-1)=\frac{3t-4r-1}{2}$.

######  Claim 1.

The subgraph induced by edges with color $1$ of $V^{(2)}$ contains a maximally
matching with at most $r-3$ edges.

###### Proof.

Let $M$ be the maximally matching of the subgraph induced by edges colored by
$1$ of $V^{(2)}$. Suppose $|M|\geq r-2$, and $|V^{(3)}|\geq 2$, $|V^{(4)}|\geq
2$. We can find a monochromatic copy of $S_{t}^{r}$ colored by $1$, a
contradiction. ∎

From Claim 1, there exists no edges colored by $1$ within $V^{(2)}$ by
deleting at most $2r-6$ vertices, and so
$|V^{(2)}|-2(r-3)\geq\lceil\frac{3t-4r-1}{2}\rceil-(2r-6)=\lceil\frac{3t-8r+11}{2}\rceil$.
Since $r\leq\lfloor\frac{t-1}{4}\rfloor$ and
$\lceil\frac{3t-8r+11}{2}\rceil\geq 2r+7$, it follows that there is a
monochromatic copy of $K_{2r+7}$ colored by $2$. For
$|V^{(2)}|\geq\frac{3t-4r-1}{2}\geq t$ and $r\leq\lfloor\frac{t-1}{4}\rfloor$,
we can find a monochromatic copy of $S_{t}^{r}$ colored by $2$ within
$V^{(2)}$. Thus we can assume that $|V^{(3)}|\geq r$, and
$|V^{(2)}|\geq|V^{(3)}|\geq r$.

######  Claim 2.

$|V^{(2)}|+|V^{(3)}|\geq t-1$.

###### Proof.

Suppose that $|V^{(2)}|+|V^{(3)}|\leq t-2$, then $|V^{(2)}|+|V^{(4)}|\leq t-2$
and $|V^{(3)}|+|V^{(4)}|\leq t-2$,
$|V^{(2)}|+|V^{(3)}|+|V^{(4)}|\leq\frac{3t-6}{2}<n$, a contradiction. ∎

From Claim 2, choose one vertex of $V^{(4)}$, say $v$, $\ell_{1}\
(\ell_{1}\geq r)$ vertices of $V^{(2)}$, say $u_{1},\ldots,u_{\ell_{1}}$ and
$\ell_{2}\ (\ell_{2}\geq r)$ vertices of $V^{(3)}$, say
$w_{1},\ldots,w_{\ell_{2}}$, where $\ell_{1}+\ell_{2}=t-1$. Then the graph
induced by $\\{v,u_{1},\ldots,u_{\ell_{1}},w_{1},\ldots,w_{\ell_{2}}\\}$
contains a monochromatic copy of $S_{t}^{r}$ colored by $1$.

Since $r\geq 3$, $t$ is odd, and $3\leq r\leq\lfloor\frac{t-1}{4}\rfloor$, it
follows that $t\geq 13$, and hence $n\geq\frac{3t-5}{2}\geq t+4$. For
$(b),(c),(d),(e)$, there is a monochromatic copy of $S_{t}^{r}$.

Suppose $\lceil\frac{t-1}{4}\rceil\leq r\leq\frac{t-3}{2}$. For the lower
bound, let $F_{5}$ be a $4$-edge-coloring complete graph with
$V(F_{6})=U_{2}\cup U_{3}\cup U_{4}$ and the graph induced by $U_{2}$ is a
complete graph $K_{t-1}$ colored by $2$, and the graph induced by $U_{i}\
(i=3,4)$ is a complete graph $K_{r-1}$ colored by $i$, and there are only
edges of color $1$ between the parts, and so $|V(F_{5})|=t+2r-3$. Since
$F_{5}$ contains no rainbow copy of $P_{5}$ and no monochromatic copy of
$S_{t}^{r}$, it follows that $\operatorname{gr}_{4}(P_{5}:S_{t}^{r})\geq
t+2r-2$.

It suffices to show that $\operatorname{gr}_{4}(P_{5}:S_{t}^{r})\leq t+2r-2$.
Suppose $G$ is any $4$-edge-coloring of $K_{n}$ where $n\geq t+2r-2$ which
contains no rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$
or $(d)$ is true. If $(b)$ is true, let $V^{(2)},V^{(3)},V^{(4)}$ be a
partition of $V(G)$ such that there are only edges of color $1$ or $i$ within
$V^{(i)}$ for $2\leq i\leq 4$, and there are only edges of color $1$ between
the parts. Without loss of generality, suppose
$|V^{(2)}|\geq|V^{(3)}|\geq|V^{(4)}|$. If
$2\leq|V^{(3)}|\leq\lfloor\frac{r-4}{2}\rfloor$, then
$|V^{(4)}|\leq\lfloor\frac{r-4}{2}\rfloor$ and $|V^{(2)}|\geq
t+2r-2-2\lfloor\frac{r-4}{2}\rfloor\geq t+r+2$. From Claim 1, the subgraph
induced by edges colored by $1$ of $V_{2}$ has a maximally matching containing
at most $r-3$ edges. Therefore there exists no edge colored by $1$ within
$V^{(2)}$ by deleting at most $2r-6$ vertices. Since $|V^{(2)}|-(2r-6)\geq
t+r+2-(2r-6)=t-r+8\geq r+11$ for $\lceil\frac{t-1}{4}\rceil\leq
r\leq\frac{t-3}{2}$, it follows that there is a monochromatic copy of
$K_{r+11}$. Since $|V^{(2)}|\geq t+5$, it follows that there is a
monochromatic copy of $S_{t}^{r}$ colored by $2$.

If $\lceil\frac{r-4}{2}\rceil\leq|V^{(3)}|\leq r-1$, then $|V^{(2)}|\geq
t+2r-2-2(r-1)=t$. From Claim 1, the subgraph induced by edges colored by $1$
of $V^{(2)}$ has a maximally matching containing at most $r-|V^{(3)}|-1$
edges. Therefore, there exists no edge colored by $1$ within $V^{(2)}$ by
deleting at most $2(r-|V^{(3)}|-1)$ vertices. Then
$|V^{(2)}|-2(r-|V^{(3)}|-1)\geq t-2r+2|V^{(3)}|+2\geq r+1$ for
$\lceil\frac{r-4}{2}\rceil\leq|V^{(3)}|\leq r-1$, and so there is a
monochromatic copy of $K_{r+1}$. As $|V^{(2)}|\geq t$, there is a
monochromatic copy of $S_{t}^{r}$ colored by $2$.

Thus we can assume that $|V^{(3)}|\geq r$, and $|V^{(2)}|\geq|V^{(3)}|\geq r$.
From Claim 2, $|V^{(2)}|\geq|V^{(3)}|\geq t-1$, choose one vertex of
$V^{(4)}$, say $v$, $\ell_{1}\ (\ell_{1}\geq r)$ vertices of $V^{(2)}$, say
$u_{1},\ldots,u_{\ell_{1}}$ and $\ell_{2}\ (\ell_{2}\geq r)$ vertices of
$V^{(3)}$, say $w_{1},\ldots,w_{\ell_{2}}$. Then the graph induced by
$\\{v,u_{1},\ldots,u_{\ell_{1}},w_{1},\ldots,w_{\ell_{2}}\\}$ contains a
monochromatic copy of $S_{t}^{r}$ with color $1$.

Suppose that $(c)$ is true. Since $r\geq 3$ and $n\geq t+2r-2\geq t+4$, it
follows that there is a vertex $v$ such that $K_{n}-v$ is a complete graph
colored by $1$, and hence there is a monochromatic copy of $S_{t}^{r}$ colored
by $1$.

Suppose that $(d)$ is true. Since $n\geq t+2r-2\geq t+4$, it follows that
$K_{n}-\\{v_{1},v_{2},v_{3}\\}$ is a complete graph with color $1$, and hence
there is a monochromatic copy of $S_{t}^{r}$ with color $1$.

Suppose that $(e)$ is true. Since $n\geq t+2r-2\geq t+4$, it follows that
$K_{n}-\\{v_{1},v_{2},v_{3},v_{4}\\}$ is a complete graph colored by $1$, and
so there is a monochromatic copy of $S_{t}^{r}$ colored by $1$.

∎

######  Theorem 3.5.

Let $k,r,t$ be three integers with $k=4$ and $r\geq 3$. If $t$ is even, then

$\operatorname{gr}_{4}(P_{5}:S_{t}^{r})=\begin{cases}\frac{3t-4}{2},&3\leq
r\leq\lfloor\frac{t}{4}\rfloor;\\\ t+2r-2,&\lceil\frac{t}{4}\rceil\leq
r\leq\frac{t-2}{2}.\end{cases}$

###### Proof.

Suppose $3\leq r\leq\lfloor\frac{t}{4}\rfloor$. For the lower bound, let
$F_{6}$ be any $4$-edge-coloring complete graph with $V(F_{6})=U_{2}\cup
U_{3}\cup U_{4}$ and the graph induced by $U_{i}\ (2\leq i\leq 4)$ is a
complete graph $K_{\frac{t-2}{2}}$ colored by $i$, and there are only edges of
color $1$ between the parts, thus $|V(F_{6})|=\frac{3t-6}{2}$. Note that
$F_{6}$ contains no rainbow copy of $P_{5}$ and no monochromatic copy of
$S_{t}^{r}$. Thus $\operatorname{gr}_{4}(P_{5}:S_{t}^{r})\geq\frac{3t-4}{2}$.
For the upper bound, the proof is similar to Theorem 3.4.

Suppose $\lceil\frac{t}{4}\rceil\leq r\leq\frac{t-2}{2}$. The proof is similar
to Theorem 3.4. ∎

We obtain the result on the case $k=3$ for $S_{t}^{r}$ in the following
lemmas.

######  Lemma 3.3.

[23, 31, 32] $\operatorname{R}_{2}(K_{3},K_{5})=14$;
$\operatorname{R}_{3}(S_{4}^{1})=17$; $\operatorname{R}_{3}(S_{5}^{1})=21$;
$\operatorname{R}_{3}(S_{6}^{1})=26$.

######  Lemma 3.4.

$\max\\{5t-4,2\operatorname{R}_{2}(S_{t}^{r})-1\\}\leq\operatorname{R}_{3}(S_{t}^{r})\leq
3\operatorname{R}_{2}(S_{t}^{r})+6r-6$.

###### Proof.

For the lower bound, let $F_{7}$ denote a $3$-edge-coloring complete graph by
making five copies of $K_{t-1}$ colored by $1$ and inserting edges of colors
$2$ and $3$ between the copies to form a unique $2$-edge-coloring $K_{5}$
which contains no monochromatic triangle, $|V(F_{7})|=5(t-1)$. Let
$F^{\prime}$ be a $2$-edge-coloring complete graph colored by $1$ and $2$ on
$\operatorname{R}_{2}(S_{t}^{r})-1$ vertices containing no monochromatic copy
of $S_{t}^{r}$. We construct $F_{8}$ by making two copies of $F^{\prime}$ and
inserting all edges between the copied in color $3$,
$|V(F_{8})|=2(\operatorname{R}_{2}(S_{t}^{r})-1)$. Note that both $F_{7}$ and
$F_{8}$ contain no monochromatic copy of $S_{t}^{r}$, it follows that
$\operatorname{R}_{3}(S_{t}^{r})\geq\max\\{5t-4,2\operatorname{R}_{2}(S_{t}^{r})-1\\}$.

It suffices to show that $\operatorname{R}_{3}(S_{t}^{r})\leq
3\operatorname{R}_{2}(S_{t}^{r})+6r-6$. Suppose $G$ is any $3$-edge-coloring
of $K_{n}\ (n\geq 3\operatorname{R}_{2}(S_{t}^{r})+6r-6)$ which is colored by
$1,2,3$. For a any vertex $v\in V(G)$, and $n\geq
3\operatorname{R}_{2}(S_{t}^{r})+6r-6$, there are at least
$\operatorname{R}_{2}(S_{t}^{r})+2r-2$ edges incident with $v$ colored by $i\
(i=1,2,3)$, say $1$. Without loss of generality, the end vertices of these
edges except $v$ are denoted by
$u_{1},u_{2},\ldots,u_{\operatorname{R}_{2}(S_{t}^{r})+2r-2}$. Let
$G^{\prime}$ be the subgraph induced by
$\\{u_{1},u_{2},\ldots,u_{\operatorname{R}_{2}(S_{t}^{r})+2r-2}\\}$, and from
Claim 1 of Theorem 3.4, the subgraph induced by edges colored by $1$ of
$G^{\prime}$ contains a maximal matching which has at most $r-1$ edges,
otherwise there is a monochromatic copy of $S_{t}^{r}$ colored by $1$. Thus
$G^{\prime}$ contains no edge colored by $1$ by deleting at most $2(r-1)$
vertices, and the resulting graph is denoted by $R$. Since
$|V(R)|\geq|V(G^{\prime})|-2(r-1)\geq\operatorname{R}(S_{t}^{r})$, it follows
that there must be a monochromatic copy of $S_{t}^{r}$ colored by $2$ or $3$,
completing the proof. ∎

Finally, we show the result on $S_{4}^{1},S_{5}^{1},S_{6}^{1}$.

######  Theorem 3.6.

For integers $k\geq 3$, we have

$\operatorname{gr}_{k}(P_{5}:S_{4}^{1})=\begin{cases}17,&k=3;\\\ 6,&k=4;\\\
5,&k=5,6;\\\ \ell,&{\ell-1\choose 2}+1\leq k\leq{\ell\choose 2}\ and\ \ell\geq
5.\end{cases}$

###### Proof.

If $k=3$, then it follows from Lemma 3.3 that
$\operatorname{gr}_{3}(P_{5}:S_{4}^{1})=\operatorname{R}_{3}(S_{4}^{1})=17$.
If $k=4$, then it follows from Lemma 3.1 that
$\operatorname{gr}_{4}(P_{5}:S_{4}^{1})=6$.

Suppose that $k=5$. Let $F_{9}$ be a colored complete graph $K_{4}$ with
$V(K_{4})=\\{u_{i}|1\leq i\leq 4\\}$ under the $5$-edge-coloring $\chi$ such
that $\chi(v_{2}v_{3})=\chi(v_{2}v_{4})=1$, $\chi(v_{1}v_{2})=2$,
$\chi(v_{1}v_{3})=3$, $\chi(v_{1}v_{4})=4$ and $\chi(v_{3}v_{4})=5$. Since
there is neither a rainbow copy of $P_{5}$ nor a monochromatic copy of
$S_{4}^{1}$ under the coloring $\chi$, it follows that
$\operatorname{gr}_{5}(P_{5}:S_{4}^{1})\geq 5$. It suffices to show
$\operatorname{gr}_{5}(P_{5}:S_{4}^{1})\leq 5$. Let $\chi$ be any $5$-edge-
coloring of $K_{n}\ (n\geq 5)$ containing no rainbow copy of $P_{5}$. From
Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is true, then $\chi$ contains at
most $3$ colors, a contradiction. If $(c)$ is true, then there exists a vertex
$v$ such that $K_{n}-v$ is monochromatic, and hence there is a monochromatic
copy of $S_{4}^{1}$.

Suppose $k=6$. Let $F_{10}$ be a colored complete graph $K_{4}$ with
$V(K_{4})=\\{u_{i}\,|\,1\leq i\leq 4\\}$ under the $5$-edge-coloring $\chi$
such that $\chi(v_{2}v_{3})=1$, $\chi(v_{1}v_{2})=2$, $\chi(v_{1}v_{3})=3$,
$\chi(v_{1}v_{4})=4$, $\chi(v_{3}v_{4})=5$ and $\chi(v_{2}v_{4})=6$. Since
there is neither a rainbow copy of $P_{5}$ nor a monochromatic copy of
$S_{4}^{1}$ under the coloring $\chi$, it follows that
$\operatorname{gr}_{6}(P_{5}:S_{4}^{1})\geq 5$. It suffices to show
$\operatorname{gr}_{6}(P_{5}:S_{4}^{1})\leq 5$. Let $\chi$ be any $6$-edge-
coloring of $K_{n}(n\geq 5)$ containing no rainbow copy of $P_{5}$. From
Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is true, then $\chi$ contains at
most $4$ colors, a contradiction. If $(c)$ is true, then there exists a vertex
$v$ such that $K_{n}-v$ is monochromatic, and hence there is a monochromatic
copy of $S_{4}^{1}$.

Suppose ${\ell-1\choose 2}+1\leq k\leq{\ell\choose 2}$ and $\ell\geq 5$. For
$k\geq{\ell-1\choose 2}+1$, there is no $k$-edge-coloring $\chi$ of
$K_{\ell-1}$, and so $\operatorname{gr}_{k}(P_{5}:S_{4}^{1})\geq\ell$. It
suffices to show $\operatorname{gr}_{k}(P_{5}:S_{4}^{1})\leq\ell$. Suppose
that there is a coloring $\chi$ of $K_{n}(n\geq\ell)$ containing no rainbow
copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is true,
then $\ell\geq 2(k-1)>2({\ell-1\choose 2}-1)$, and hence $\ell\leq 4$, a
contradiction. If $(c)$ is true, then there is a vertex $v$ such that
$K_{n}-v$ is monochromatic, and hence there is a monochromatic copy of
$S_{4}^{1}$. ∎

######  Theorem 3.7.

For integers $k\geq 3$, we have

$\operatorname{gr}_{k}(P_{5}:S_{5}^{1})=\begin{cases}21,&k=3;\\\ 6,&k=4,5;\\\
5,&k=6;\\\ \left\lceil\frac{1+\sqrt{1+8k}}{2}\right\rceil,&k\geq
7.\end{cases}$

###### Proof.

If $k=3$, then it follows from Lemma 3.3 that
$\operatorname{gr}_{3}(P_{5}:S_{5}^{1})=\operatorname{R}_{3}(S_{5}^{1})=21$.
If $k=4$, then it follows from Lemma 3.1 that
$\operatorname{gr}_{4}(P_{5}:S_{5}^{1})=6$.

Suppose $k=5$. Let $F_{11}$ be a colored complete graph obtained from a
$K_{4}$ with vertex set $\\{u_{1},u_{2},u_{3},u_{4}\\}$ colored by $1$ by
adding a new vertex $v$ and edges $u_{i}v\ (1\leq i\leq 4)$ colored by $i+1$.
Since there is neither a rainbow copy of $P_{5}$ nor a monochromatic copy of
$P_{5}$ under the coloring, it follows that
$\operatorname{gr}_{5}(P_{5}:S_{5}^{1})\geq 6$. It suffices to show
$\operatorname{gr}_{5}(P_{5}:S_{5}^{1})\leq 6$. Let $\chi$ be any $5$-edge-
coloring of $K_{n}\ (n\geq 6)$ containing no rainbow copy of $P_{5}$. From
Theorem 1.3, $(b)$ or $(c)$ is true. If $(b)$ is true, then $\chi$ contains at
most $4$ colors, a contradiction. If $(c)$ is true, then there exists a vertex
$v$ such that $K_{n}-v$ is monochromatic, and hence there is a monochromatic
copy of $S_{5}^{1}$.

For $k=6$, the result follows from Theorem 2.2. For $k\geq 7$, the result
follows from Theorem 2.1. ∎

######  Theorem 3.8.

For integer $k\geq 3$, we have

$\operatorname{gr}_{k}(P_{5}:S_{6}^{1})=\begin{cases}26,&k=3;\\\ 7,&4\leq
k\leq 6;\\\ \lceil\frac{1+\sqrt{1+8k}}{2}\rceil,&k\geq 7.\end{cases}$

###### Proof.

If $k=3$, then it follows from Lemma 3.3 that
$\operatorname{gr}_{3}(P_{5}:S_{6}^{1})=\operatorname{R}_{3}(S_{6}^{1})=26$.
If $k=4$, then it follows from Theorem 3.2 that
$\operatorname{gr}_{4}(P_{5}:S_{6}^{1})=7$. If $k=5$, then it follows from
Theorem 3.1 that $\operatorname{gr}_{5}(P_{5}:S_{6}^{1})=7$. If $k=6$, then it
follows from Theorem 2.3 that $\operatorname{gr}_{6}(P_{5}:S_{6}^{1})=7$. If
$k\geq 7$, then it follows from Theorem 2.1 that
$\operatorname{gr}_{k}(P_{5}:S_{6}^{1})=\lceil\frac{1+\sqrt{1+8k}}{2}\rceil$,
completing the proof. ∎

From Theorems 2.1, 2.3, 3.1, 3.2 and Lemma 3.4, we can obtain the result.

######  Theorem 3.9.

For integer $k\geq 3,t\geq 6,r=1,2$, we have

$\operatorname{gr}_{k}(P_{5}:S_{t}^{r})=\begin{cases}[\max\\{5t-4,2\operatorname{R}(S_{t}^{r})-1\\},3\operatorname{R}(S_{t}^{r})+6r-6],&k=3;\\\
t+p-1,&4\leq k\leq t-1;\\\ t+1,&k=t;\\\
\lceil\frac{1+\sqrt{1+8k}}{2}\rceil,&k\geq t+1.\end{cases}$

##  4 Results for the rainbow $4$-path and monochromatic pineapples

In this section, we will get some exact values or bounds for
$\operatorname{gr}_{k}(P_{5}:H)$ when $H$ is a pineapple.

######  Theorem 4.1.

Let $k,t,\omega$ be three integers with $k=\omega$ and $k\geq 4$. Then

$\operatorname{gr}_{k}(P_{5}:PA_{t,\omega})=(\omega-1)(t-1)+1.$

###### Proof.

From Lemma 2.1, we have
$\operatorname{gr}_{k}(P_{5}:PA_{t,\omega})\geq(\omega-1)(t-1)+1$. It suffices
to show that
$\operatorname{gr}_{k}(P_{5}:PA_{t,\omega})\leq(\omega-1)(t-1)+1$. Let $G$ be
any $k$-edge-coloring of $K_{n}$ where $n\geq(\omega-1)(t-1)+1$ which contains
no rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$
is true if $k=4$, and $(b)$ or $(c)$ is true if $k\geq 5$.

For $k\geq 4$, suppose that $(b)$ is true. Let
$V^{(2)},V^{(3)},\ldots,V^{(k)}$ be a partition of $V(G)$ such that there are
only edges of color $1$ or $i$ within each $V^{(i)}$ for $2\leq i\leq k$, and
there are only edges with color $1$ among the parts. Then there exists some
$V^{(i)}\ (2\leq i\leq k)$ with $|V^{(i)}|\geq t$, otherwise
$|V^{(2)}|+|V^{(3)}|+\cdots+|V^{(k)}|\leq(\omega-1)(t-1)+1<n$, a
contradiction. Without loss of generality, let $|V^{(2)}|\geq t$. Suppose that
$V^{(2)}$ contains one edge with color $1$, say $v_{2}u_{2}$. Choose one
vertex of $V^{(i)}\ (2\leq i\leq k)$, say $v_{i}$. Then the subgraph induced
by $\\{u_{2},v_{2},v_{3},\ldots,v_{k}\\}$ is a copy of $K_{\omega}$ with color
$1$. Since $|V^{(2)}|\geq t$, it follows that there is a copy of $PA_{t,4}$
with color $1$. Therefore, $V^{(2)}$ contains no edges with color $1$, and
hence the subgraph induced by $V^{(2)}$ is a monochromatic copy of $K_{t}$
with color $2$, and so there is a monochromatic copy of $PA_{t,\omega}$ with
color $2$.

Suppose that $(c)$ is true. Since $n\geq(\omega-1)(t-1)+1\geq t+1$ for
$\omega\geq 4$ and $t\geq 5$, it follows that there is a vertex $v$ such that
$K_{n}-v$ is a complete graph colored by $1$, and hence there is a
monochromatic copy of $PA_{t,\omega}$ colored by $1$.

For $k=4$, then $(d)$ or $(e)$ is true. Suppose that $(d)$ is true. Since
$n\geq 3t-2\geq t+8$, it follows that $K_{n}-\\{v_{1},v_{2},v_{3}\\}$ is a
complete graph colored by $1$, and so there is a monochromatic copy of
$PA_{t,4}$ colored by $1$. Suppose that $(e)$ is true. Since $n\geq 3t-2\geq
t+8$, it follows that $K_{n}-\\{v_{1},v_{2},v_{3},v_{4}\\}$ is a complete
graph colored by $1$, and hence there is a monochromatic copy of $PA_{t,4}$
colored by $1$.

∎

######  Theorem 4.2.

Let $k,t,\omega$ be three integers with $k=4,\omega=5$ and $t\geq 8$. Then

$\operatorname{gr}_{4}(P_{5}:PA_{t,\omega})=4t-3.$

###### Proof.

From Lemma 2.1, we know that $\operatorname{gr}_{4}(P_{5}:PA_{t,\omega})\geq
4t-3$. It suffices to show that
$\operatorname{gr}_{4}(P_{5}:PA_{t,\omega})\leq 4t-3$. Let $G$ be any
$4$-edge-coloring of $K_{n}$, where $n\geq 4t-3$, which contains no rainbow
copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$ is true.
Suppose that $(b)$ is true and $|V^{(2)}|\geq|V^{(3)}|\geq|V^{(4)}|$. To avoid
a monochromatic copy of $K_{5}$ colored by $1$,
$|V(G)|-\sum^{4}_{i=2}|V^{(i)}|\leq 1$. If $|V(G)|-\sum^{4}_{i=2}|V^{(i)}|=0$,
$\sum^{4}_{i=2}|V^{(i)}|\geq 4t-3$, $|V^{(2)}|\geq\lceil\frac{4t-3}{3}\rceil$,
otherwise $|V^{(2)}|+|V^{(3)}|+|V^{(4)}|<4t-3\leq n$, a contradiction.

######  Claim 3.

Both $V^{(3)}$ and $V^{(4)}$ contain no edges with color $1$.

###### Proof.

Assume, to the contrary, that both $V^{(3)}$ and $V^{(4)}$ contain one edge
with color $1$, say $v_{3}u_{3}$ and $v_{4}u_{4}$. Choose one vertex of
$V^{(2)}$, say $v_{2}$. Then the subgraph induced by
$\\{v_{2},v_{3},u_{3},v_{4},u_{4}\\}$ contains a copy of $K_{5}$ with color
$1$. Since $|V^{(2)}|\geq\lceil\frac{4t-3}{3}\rceil\geq t+1$ for $\omega=5$
and $t\geq 8$, it follows that there is a copy of $PA_{t,5}$ with color $1$.
If either $V^{(3)}$ or $V^{(4)}$ contains one edge with color $1$, say
$V^{(3)}$ and $v_{3}u_{3}$ with color $1$, then $V^{(2)}$ contains no edges
with color $1$, otherwise there is a copy of $PA_{t,5}$ with color $1$ by the
above proof. Thus the subgraph induced by $V^{(2)}$ is monochromatic copy of
complete graph with color $2$, and hence
$|V^{(2)}|\geq\lceil\frac{4t-3}{3}\rceil\geq t+1$, and so there is a
monochromatic copy of $PA_{t,5}$ with color $2$. ∎

From Claim 3, both $V^{(3)}$ and $V^{(4)}$ contain no edges with color $1$.
Then $|V^{(3)}|\leq t-1$, $|V^{(4)}|\leq t-1$, otherwise there is a
monochromatic copy of $K_{t}$ colored by $3$ or $4$. If $V^{(2)}$ contains
three vertices which induce a monochromatic copy of $K_{3}$ with color $1$,
say $u_{2},w_{2},x_{2}$, choose one vertex $w_{i}$ of $V^{(i)}(i=3,4)$, then
the subgraph induced by $\\{u_{2},w_{2},x_{2},w_{3},w_{4}\\}$ is a
monochromatic copy of $K_{5}$ with color $1$. Choose $t-5$ vertices of
$V^{(2)}$, say $y_{1},\ldots,y_{t-5}$, then the subgraph induced by
$\\{u_{2},w_{2},x_{2},w_{3},w_{4},y_{1},\ldots,y_{t-5}\\}$ contains a
monochromatic copy of $PA_{t,5}$ colored by $1$. It follows that the subgraph
induced by color $1$ within $V_{2}$ must not be $K_{3}$. Since $n\geq 4t-3$,
it follows that $|V^{(2)}|\geq 2t-1\geq t+7\geq 15$ for $t\geq 8$. From Lemma
3.3, $\operatorname{R}_{2}(K_{3},K_{5})=14$, and hence there is a
monochromatic copy of $K_{5}$ with color $2$ in $V^{(2)}$.

For any vertex $v\in V^{(2)}$, let $Q_{i}\ (i=1,2)$ be the set of vertices
such that the edges from any vertex of $Q_{i}$ to $v$ is with color $i$.

######  Claim 4.

$|Q_{1}|\leq t-1$.

###### Proof.

Assume, to the contrary, that $|Q_{1}|\geq t$. If the subgraph induced by
$Q_{1}$ contains one edge with color $1$, say $w_{1}w_{2}$, then
$\\{w_{1},w_{2},v\\}$ induces a monochromatic copy of $K_{3}$ colored by $1$,
a contradiction. That means that $Q_{1}$ contains no edges colored by $1$ and
there is a monochromatic copy of $K_{t}$ colored by $2$. So there is a
monochromatic copy of $PA_{t,5}$ colored by $2$. ∎

From Claim 4, we have $|Q_{2}|\geq t-1$, and hence $V^{(2)}$ contains a
monochromatic copy of $PA_{t,5}$ colored by $2$. If
$|V(G)|-\sum^{4}_{i=2}|V^{(i)}|=1$, then $V^{(2)}$ contains no edge colored by
$1$, otherwise there is a monochromatic copy of $K_{5}$. Since
$\sum^{4}_{i=2}|V^{(i)}|\geq 4t-4$, it follows that
$|V^{(2)}|\geq\lceil\frac{4t-4}{3}\rceil\geq t+1$ for $t\geq 8$, and hence
$V^{(2)}$ contains a monochromatic copy of $PA_{t,5}$ colored by $2$.

Suppose that $(c)$ or $(d)$ or $e$ is true. Since $n\geq 4t-3\geq t+21$ for
$t\geq 8$, it follows that there is a monochromatic copy of $K_{t+17}$.

∎

######  Theorem 4.3.

Let $k,t,\omega$ be three integers with $k=4$, $\omega=5$ and $t=6$. Then

$\operatorname{gr}_{4}(P_{5}:PA_{6,5})=24.$

###### Proof.

For the lower bound, let $F_{12}$ be a complete graph with
$V(F_{12})=U_{2}\cup U_{3}\cup U_{4}$, the subgraph induced by $U_{2}$ is
$K_{13}$ colored by $1$ and $2$ which contains neither a monochromatic copy of
$K_{3}$ nor a monochromatic copy of $K_{5}$, the subgraph induced by
$U_{i}(i=3,4)$ is $K_{5}$ colored by $i$, and all edges between $U_{i}$ and
$U_{j}(i,j\in\\{{2,3,4}\\},i\neq j)$ are colored by $1$. It is clear that
$F_{12}$ contains neither a rainbow copy of $P_{5}$ nor a monochromatic copy
of $PA_{6,5}$, and $\operatorname{gr}_{4}(P_{5}:PA_{6,5})\geq 24$.

It suffices to show that $\operatorname{gr}_{k}(P_{5}:PA_{6,5})\leq 24$. Let
$G$ be any $4$-edge-coloring of $K_{n}$, where $n\geq 24$, which contains no
rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$ is
true. By the proof of Theorem 4.2, we know that the upper bound holds.

∎

######  Theorem 4.4.

Let $k,t,\omega$ be three integers with $k=4$, $\omega=5$ and $t=7$. Then

$\operatorname{gr}_{4}(P_{5}:PA_{7,5})=26.$

###### Proof.

For the lower bound, let $F_{13}$ be a complete graph with
$V(F_{12})=U_{2}\cup U_{3}\cup U_{4}$. Then the subgraph induced by $U_{2}$ is
$K_{13}$ colored by $1$ and $2$ which contains neither a monochromatic copy of
$K_{3}$ nor a monochromatic copy of $K_{5}$, and the subgraph induced by
$U_{i}\ (i=3,4)$ is $K_{6}$ colored by $i$, and all edges from $U_{i}$ to
$U_{j}$ ($i,j\in\\{{2,3,4}\\},\ i\neq j$) are colored by $1$. It is clear that
$F_{13}$ contains neither a rainbow copy of $P_{5}$ nor a monochromatic copy
of $PA_{7,5}$, and hence $\operatorname{gr}_{4}(P_{5}:PA_{7,5})\geq 26$.

It suffices to show that $\operatorname{gr}_{k}(P_{5}:PA_{7,5})\leq 26$. Let
$G$ be any $4$-edge-coloring of $K_{n}$, where $n\geq 26$, which contains no
rainbow copy of $P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$ is
true. By the proof of Theorem 4.2, we know that the upper bound holds.

∎

######  Theorem 4.5.

Let $k,t,\omega$ be three integers with $k=4$ and $\omega\geq 6$. Then

$(\omega-1)(t-1)+1\leq\operatorname{gr}_{4}(P_{5}:PA_{t,\omega})\leq
3\operatorname{R}_{2}(PA_{t,\omega})-2.$

###### Proof.

From Lemma 2.1, we can obtain the lower bound. For the upper bound, let $G$ be
any $4$-edge-coloring $K_{n}$, where $n\geq
3\operatorname{R}_{2}(PA_{t,\omega})-2$, containing no rainbow copy of
$P_{5}$. From Theorem 1.3, $(b)$ or $(c)$ or $(d)$ or $(e)$ is true. Suppose
that $(b)$ is true. Let $V^{(2)},V^{(3)},V^{(4)}$ be a partition of $V(G)$
such that there are only edges of color $1$ or $i$ within $V^{(i)}$ for $2\leq
i\leq 4$, and there are only edges of color $1$ between the parts. There
exists some $V^{(i)}\ (2\leq i\leq 4)$ with
$|V^{(i)}|\geq\lceil\frac{3\operatorname{R}_{2}(PA_{t,\omega})-2}{3}\rceil$,
otherwise
$|V^{(2)}|+|V^{(3)}|+|V^{(4)}|<3\operatorname{R}_{2}(PA_{t,\omega})-2\leq n$,
a contradiction. Without loss of generality, let
$|V^{(2)}|\geq\lceil\frac{3\operatorname{R}_{2}(PA_{t,\omega})-2}{3}\rceil\geq\operatorname{R}_{2}(PA_{t,\omega})$.
Then there is a monochromatic copy of $PA_{t,\omega}$ colored by $1$ or $2$.
Since $\operatorname{R}_{2}(PA_{t,\omega})\geq t$, it follows that
$3\operatorname{R}_{2}(PA_{t,\omega})-2>t+4$ for $\omega\geq 6$ and $t\geq 7$.
If $(b)$ or $(c)$ or $(e)$ is true, then there is a monochromatic copy of
$PA_{t,\omega}$. ∎

Sah [27] obtained the following result.

######  Theorem 4.6.

[27] There is an absolute constant $c>0$ such that for $k\geq 3$,

$\operatorname{R}_{2}(k+1)\leq{2k\choose k}e^{-c(\log k)^{2}}.$

By the upper bound in Theorem 4.5, we can derive the following result.

######  Theorem 4.7.

There is an absolute constant $c>0$ such that for $\omega\geq 4$,

$\operatorname{R}_{2}(PA_{t,\omega})\leq{2\omega-2\choose\omega-1}e^{-c\log^{2}(\omega-1)}+(t-2)(\omega-1).$

###### Proof.

Let $n={2\omega-2\choose\omega-1}e^{-c\log^{2}(\omega-1)}+(t-2)(\omega-1)$.
For any red/blue-edge-coloring of $K_{n}$, from Theorem 4.4, there is a
monochromatic copy of $K_{\omega}$, say $K_{\omega}^{1}$. Without loss of
generality, assume that $K_{\omega}^{1}$ is red. Choose one vertex in
$K_{\omega}^{1}$, say $v_{1}$. Let $X_{1}$ be the set of vertices with red
edges from $v_{1}$ to $K_{n}-K_{\omega}^{1}$. Then $|X_{1}|\leq t-\omega-1$.
By deleting the vertices of $K_{\omega}^{1}\cup X_{1}$,
$K_{n}-K_{\omega}^{1}-X_{1}$ contains a red clique of order $\omega$, say
$K_{\omega}^{2}$. Choose one vertex in $K_{\omega}^{2}$, say $v_{2}$. Let
$X_{2}$ be the set of vertices with red edges from $v_{2}$ to
$K_{n}-(K_{\omega}^{1}\cup K_{\omega}^{2}\cup X_{1})$. Then $|X_{2}|\leq
t-\omega-1$. By deleting the vertices of $K_{\omega}^{2}\cup X_{2}$, one can
see that $K_{n}-(K_{\omega}^{1}\cup K_{\omega}^{2}\cup X_{1}\cup X_{2})$
contains a red clique of order $\omega$, say $K_{\omega}^{3}$.

Continue this process,
$K_{n}-(\bigcup_{i=1}^{\omega-2}K_{\omega}^{i})-\bigcup_{i=1}^{\omega-2}X_{i}$
contains a red clique of $\omega$, say $K_{\omega}^{\omega-1}$. Choose one
vertex in $K_{\omega}^{\omega-1}$, say $v_{\omega-1}$. Let $X_{\omega-1}$ be
the set of vertices with red edges from $v_{\omega-1}$ to
$K_{n}-(\bigcup_{i=1}^{\omega-1}K_{\omega}^{i})-\bigcup_{i=1}^{\omega-2}X_{i}$.
Then $|X_{\omega-1}|\leq t-\omega-1$. Choose one vertex in
$K_{n}-(\bigcup_{i=1}^{\omega-1}K_{\omega}^{i})-\bigcup_{i=1}^{\omega-1}X_{i}$,
say $v_{\omega}$. Since the number of red edges from $v_{1}$ to
$K_{n}-K_{\omega}^{1}$ is at most $t-\omega-1$, it follows that the number of
blue edges from $v_{1}$ to $K_{n}-K_{\omega}^{1}$ is at least $n-t$, and hence
there is blue copy of $PA_{t,\omega}$. Note that the subgraph in $K_{n}$
induced by $\\{v_{1},v_{2},\ldots,v_{\omega}\\}$ is blue clique of order
$\omega$. Since the number of red edges from $v_{1}$ to $K_{n}-K_{\omega}^{1}$
is at most $t-\omega-1$, it follows that the number of blue edges from $v_{1}$
to $K_{n}-K_{\omega}^{1}$ is at least $n-t$, and hence there is blue copy of
$PA_{t,\omega}$. ∎

The following corollary is immediate.

######  Corollary 4.8.

Let $k,t,\omega$ be three integers with $k=4$ and $\omega\geq 6$. Then

$(\omega-1)(t-1)+1\leq\operatorname{gr}_{4}(P_{5}:PA_{t,\omega})\leq
3{2\omega-2\choose\omega-1}e^{-c\log^{2}(\omega-1)}+(t-2)(\omega-1)-2,$

where $c>0$ is an absolute constant.

From Lemma 2.1, Theorems 2.7 and 4.7, the following corollary is true.

######  Corollary 4.9.

Let $k,t,\omega$ be three integers with $5\leq k\leq\omega-1$ and $\omega\geq
6$. Then

$(\omega-1)(t-1)+1\leq\operatorname{gr}_{k}(P_{5}:PA_{t,\omega})\leq{2\omega-2\choose\omega-1}e^{-c\log^{2}(\omega-1)}+(t-2)(\omega-1).$

## References

  * [1] J.A. Bondy, P. Erdős, Ramsey numbers for cycles in graphs, J. Combin. Theory, Ser. B 14 (1973), 46–54.
  * [2] K. Cameron and J. Edmonds, Lambda composition, J. Graph Theory, 26(1):9–16, 1997.
  * [3] M. Chen, Y. Li, C. Pei, Gallai-Ramsey numbers of odd cycles and complete bipartite graphs, _Graphs Combin._ 34 (2018), 1185–1196.
  * [4] G. A. Dirac, Some theorems on abstract graphs, _Proc. London Math. Soc._ (3)2 (1993), 69–81.
  * [5] R. J. Faudree, R. H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313–329.
  * [6] J. Fox, B. Sudakov, Ramsey-type problem for an almost monochromatic $K_{4}$, _SIAM J. Discrete Math._ 23(1) (2008), 155–162.
  * [7] S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations of Ramsey theory–a dynamic survey.  Theo. Appl. Graphs, 0(1), 2014.
  * [8] S. Fujita, C. Magnant, Gallai-Ramsey numbers for cycles, _Discrete Math._ 311 (2011), 1247–1254.
  * [9] S. Fujita, C. Magnant, Extensions of Gallai-Ramsey results, J. Graph Theory, 70(4) (2012), 404–426.
  * [10] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar 18 (1967), 25–66.
  * [11] A. Gyárfás, G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46(3) (2004), 211–216.
  * [12] R.L. Graham, B.L. Rothschild, J.H. Spencer, _Ramsey Theory_ , JOHN WILEY & SONS, 1990.
  * [13] A. Gyárfás, G. Sárközy, A. Sebő, S. Selkow, Ramsey-type results for gallai colorings, J. Graph Theory 64(3) (2010), 233–243.
  * [14] A. Gyárfás, D. Pálvölgyi, B. Patkós, Distribution of colors in Gallai colorings, European J. Combin. 86 (2020), 103087.
  * [15] X. Li, L. Wang, Gallai-Ramsey numbers for a class of graphs with five vertices, _Graphs Comb._ 36 (2020), 1603–1618.
  * [16] X. Li, P. Besse, C. Magnant, L. Wang, N. Watts, Gallai-Ramsey numbers for rainbow paths, _Graphs Comb._ 36 (2020), 1603–1618.
  * [17] X. Li, L. Wang, Monochromatic stars in rainbow $K_{3}$-free and $S_{3}^{+}$-free colorings, _Discrete Math._ 343 (2020), 112131.
  * [18] X. Li, L. Wang, X. Liu, Complete graphs and complete bipartite graphs without rainbow path, _Discrete Math._ 342 (2019) 2116–2126.
  * [19] C. Magnant, P.S. Nowbandegani, _Topics in Gallai-Ramsey Theory_ , Springer, Switzerland, 2020.
  * [20] Y. Mao, Z. Wang, C. Maganant, I. Schiermeyer, Gallai-Ramsey number for the union of stars, accepted by Acta Mathematica Sinica, English Series.
  * [21] Y. Mao, Z. Wang, C. Maganant, I. Schiermeyer, Gallai-Ramsey number for stars with extra independent edges, Discrete Appl. Math. 285 (2020), 153–172.
  * [22] Y. Mao, Z. Wang, C. Maganant, I. Schiermeyer, Gallai-Ramsey number for wheels, accepted by Graphs Comb.
  * [23] S. P. Radziszowski, Small Ramsey numbers, _Electron. J. Combin._ , Dynamic Survey 1, 30 pp. (electronic), 1994.
  * [24] F.P. Ramsey, On a problem of formal logic, _Proc. London. Math. Soc._ (2)30 (1930), 264–286.
  * [25] F.S. Roberts, Applications of Ramsey theory, _Discrete Appl. Math._ 9(3) (1984), 251–261.
  * [26] V. Rosta, Ramsey theory applications, _Electron. J. Combin._ 11(1) (2004), 89.
  * [27] A. Sah, Diagonal Ramsey via effective quasirandomness, preprint, arXiv:2005.09251 [math.CO], 2020.
  * [28] J. Spencer, Asymptotic lower bounds for Ramsey functions, _Discrete Math._ 20 (1977), 69–76.
  * [29] A. Thomason, P. Wagner, Complete graphs with no rainbow path, J. Graph Theory 54(3) (2007), 261–266.
  * [30] Z. Wang, Y. Mao, J. Zou, C. Maganant, Ramsey and Gallai-Ramsey numbers for two classes of unicyclic graphs, Graphs Combin. 37(1) (2021), 337–354.
  * [31] Y. Yang, R. Peter, On the third Ramsey numbers of graphs with five edges, J. Combin. Math. Combin. Comput. 11 (1992), 213–222.
  * [32] Y. Yang, On the third Ramsey numbers of graphs with six edges, J. Combin. Math. Combin. Comput. 17 (1995), 199–208.
  * [33] Q. Zhang, B. Wei, Gallai-Ramsey numbers for graphs with chromatic number three, Discrete Appl. Math. 304 (2021), 110–118.


# Convex Geometry of Building Sets

Spencer Backman<EMAIL_ADDRESS>and  Rick Danner<EMAIL_ADDRESS>
###### Abstract.

Building sets were introduced in the study of wonderful compactifications of
hyperplane arrangement complements and were later generalized to finite meet-
semilattices. Convex geometries, the duals of antimatroids, offer a robust
combinatorial abstraction of convexity. Supersolvable convex geometries and
antimatroids appear in the study of poset closure operators, Coxeter groups,
and matroid activities. We prove that the building sets on a finite meet-
semilattice form a supersolvable convex geometry.

##  1\. Introduction

De Concini and Procesi’s celebrated wonderful compactifications of a
hyperplane arrangement complement proceed by blow ups of certain flats of the
arrangement [12]. There are choices for which flats are blown up, and each set
of choices is encoded by a _building set_. Feichtner and Kozlov [18] extended
the notion of a building set from the lattice of flats of a hyperplane
arrangement to arbitrary finite meet-semilattices111Henceforth, all posets in
this paper will be assumed to be finite., and observed that this
generalization admits connections to other topics such as stellar subdivisions
of fans.

The Bergman fan of a matroid was introduced by Ardila-Klivans [4] and
Feichtner-Sturmfels [19] as a matroidal generalization of the tropicalization
of a linear space, and it was shown in [19] that the nested set complex
associated to a building set for the lattice of flats gives a unimodular
triangulation of the Bergman fan. In seminal work of Adiprasito-Huh-Katz [1],
the Chow ring of a matroid, introduced earlier by Feichtner-Yuzvinsky [20],
was utilized for settling the Heron-Rota-Welsh conjecture on the log-concavity
of the coefficients of the characteristic polynomial of a matroid. Although
Feichtner-Yuzvinsky’s construction is defined for arbitrary building sets,
Adiprasito-Huh-Katz found that the maximum building set was sufficient for
their goals. Much of the subsequent work by researchers studying Chow rings of
matroids has been focused on the maximum building set with a few important
notable exceptions: the conormal fan of a matroid222An important consequence
of [2] is that the Kähler package holds for the Chow ring of a matroid with
respect to an arbitrary building set.333The biflats, viewed as a subset of
$\mathcal{L}(M)^{op}\times\mathcal{L}(M^{\perp})$, are closed under taking
joins and thus satisfy condition (2) of Proposition 2.2. While the biflats do
not satisfy condition (1) of Proposition 2.2, the image of the biflats in
$\Sigma_{M}\times\Sigma_{M^{\perp}}$ contains the image of the irreducibles.
As the biflats are closed under taking joins, the would-be nested set complex
associated to the biflats is the order complex, which agrees with the facial
structure of the conormal fan. [2, 3, 28], the augmented Bergman fan of a
matroid [8, 9, 16, 25], and the Bergman fan of a polymatroid [11, 17, 27, 29].

Perhaps surprisingly, there has been no work exploring the systematic
construction of building sets for the lattice of flats of a matroid – this
apparent gap in the literature was the genesis of this paper. Although our
primary motivation is the study of matroids, we have found that our results
hold for arbitrary meet-semilattices. Postnikov provided an elegant
description of building sets for the Boolean lattice [30]. We begin by
extending Postnikov’s characterization to a general meet-semilattice
$\mathcal{L}$. We apply this result to demonstrate that the building sets for
$\mathcal{L}$ form an intersection lattice and note that this observation may
already be new for the Boolean lattice. It follows that given an arbitrary
subset $X\subseteq\mathcal{L}$, there exists a smallest building set $B$ which
contains $X$, and there is a simple algorithm for computing $B$. Thus we are
led to the realization that the building sets for $\mathcal{L}$ determine a
special kind of closure operator called a _convex geometry_. These objects
were introduced independently by Edelman and Jamison [14, 15, 23], and provide
a combinatorial abstraction of convex hulls in finite point configurations and
upper ideals in posets. A fundamental result of Björner [6] states that convex
geometries are dual to antimatroids, which are an important class of
greedoids. Supersolvable antimatroids and convex geometries appear implicitly
in the work of Stanley [32], and were developed in earnest by Armstrong [5].
They arise naturally in the study of poset closure operators [22], Coxeter
groups [5], and matroid activities [21]. We demonstrate that the building sets
on a meet-semilattice form a supersolvable convex geometry.

##  2\. Semilattices and Building Sets

In this section we review the theory of posets, semilattices, and building
sets. The section concludes with Theorem 2.3 which states that the collection
of building sets on a meet-semilattice ordered by inclusion forms an
intersection lattice.

######  Definition 2.1.

A _partially ordered set_ , or _poset_ , is a set $\mathcal{P}$ with a
relation $\leq$ such that for all $x,y,z\in\mathcal{P}$

  1. (1)

$x\leq x$ _reflexive_

  2. (2)

$x\leq y$ and $y\leq x$ implies $x=y$ _antisymmetric_

  3. (3)

$x\leq y$ and $y\leq z$ imply $x\leq z$ _transitive_

We write $x<y$ if $x\leq y$ and $x\neq y$, and we define $x>y$ similarly. We
say that $y$ _covers_ $x$ if $x<y$ and there is no element $z\in\mathcal{P}$
such that $x<y<z$. We define the subset $\mathcal{P}_{\leq x}$ to be
$\\{z\in\mathcal{P}:z\leq x\\}$. For a subset $B$ of $\mathcal{P}$ with the
induced order, and $x\in\mathcal{P}$, we define $B_{\leq x}=\\{z\in B:z\leq
x\\}$. An interval $[x,y]\subseteq\mathcal{P}$ is the set of elements
$z\in\mathcal{P}$ such that $x\leq z\leq y$. Let $(\mathcal{P}_{1},\leq_{1})$
and $(P_{2},\leq_{2})$ be posets. A function
$f:\mathcal{P}_{1}\rightarrow\mathcal{P}_{2}$ is an _isomorphism_ if it is
bijective and for any $x,y\in\mathcal{P}_{1}$, $x\leq_{1}y$ implies
$f(x)\leq_{2}f(y)$. The _direct product_
$\mathcal{P}_{1}\times\mathcal{P}_{2}$ of two posets
$(\mathcal{P}_{1},\leq_{1})$ and $(\mathcal{P}_{2},\leq_{2})$, has order
$\leq$ defined by $(x,y)\leq(x^{\prime},y^{\prime})$ if and only if
$x\leq_{1}x^{\prime}$ and $y\leq_{2}y^{\prime}$. If a poset has a minimum
element, we may denote this element by $\hat{0}$, and if a poset has a maximum
element, we may denote this element by $\hat{1}$. A poset is called
_irreducible_ if it is not a direct product of two other posets, each
consisting of at least two elements. Let
$I(\mathcal{P})=\\{x\in\mathcal{P}\mid[\hat{0},x]\leavevmode\nobreak\ \text{is
irreducible}\\}$ be the _set of irreducibles of $\mathcal{P}$_. We call the
set $\text{max}\,I(\mathcal{P})_{\leq x}$ the _elementary divisors_ of $x$.

######  Lemma 2.1.

[18] Let $(\mathcal{P},\leq)$ be a partially ordered set with a minimum
element $\hat{0}$ and a maximum element $x$. Let
$\text{max}\,I(\mathcal{P})=\\{y_{1},...,y_{l}\\}$, then

$\mathcal{P}\cong\prod_{i=1}^{l}[\hat{0},y_{i}].$

###### Proof.

If $x$ is irreducible, then the statement is trivial. Otherwise $x$ is
reducible and, by induction, there exists some factorization
$[\hat{0},x]=\mathcal{P}\cong\prod_{i=1}^{k}\mathcal{P}_{i}$ with $k\geq 2$,
such that $\mathcal{P}_{i}$ is irreducible and $|\mathcal{P}_{i}|\geq 2$ for
each $i$. We claim that, after some potential reordering,
$\mathcal{P}_{i}\cong[\hat{0},y_{i}]$ and $k=l$. First we observe that each
$\mathcal{P}_{i}$ must have a minimum element, which we denote $\hat{0}$, and
a maximum element $z_{i}$, otherwise $\mathcal{P}$ would have more than one
minimal or maximal element. Let $\mathcal{P}_{i}=[\hat{0},z_{i}]$ and let
$\phi:\prod_{i=1}^{k}\mathcal{P}_{i}\rightarrow\mathcal{P}$ be an explicit
isomorphism. For any fixed $y_{j}$, there exists $w_{i}\in\mathcal{P}_{i}$ for
$1\leq i\leq k$ such that $\phi(\prod_{i=1}^{k}w_{i})=y_{j}$. It follows from
the definition of a poset isomorphism that
$[\hat{0},y_{j}]\cong\prod_{i=1}^{k}[\hat{0},w_{i}].$ Therefore, there is a
unique index $i$ for which $w_{i}\neq\hat{0}$. By assumption, each $z_{i}$ is
irreducible. Letting $\phi(z_{i})$ denote
$\phi(\hat{0},\ldots,z_{i},\ldots,\hat{0})$, we have $y_{j}\leq\phi(z_{i})$.
By the definition of $y_{j}$, it must be that $y_{j}=\phi(z_{i})$. Thus the
map $\phi$ induces a canonical bijection between $\\{z_{1},\ldots,z_{k}\\}$
and $\\{y_{1},\ldots,y_{l}\\}$, and the statement of the claim follows. ∎

We note that the factorization in the statement of Lemma 2.1 is the unique
finest factorization of $\mathcal{P}$.

######  Definition 2.2.

Let $\mathcal{P}$ be a poset and $x,y\in\mathcal{P}$. The greatest lower bound
of elements $x$ and $y$, if it exists, is the _meet_ of $x$ and $y$, denoted
$x\wedge y$. The least upper bound of $x$ and $y$, if it exists, is the _join_
of $x$ and $y$, denoted $x\vee y$. A poset $\mathcal{L}$ is called a _meet-
semilattice_ if the meet of any two of its elements exists in $\mathcal{L}$.
We define a _join-semilattice_ similarly. A poset $\mathcal{L}$ is called a
_lattice_ if it is a meet-semilattice and a join-semilattice. If $\mathcal{L}$
is a meet-semilattice, we define
$\mathcal{L}^{+}:=\mathcal{L}\backslash\\{\hat{0}\\}$.

######  Remark 1.

If $\mathcal{L}$ is a meet-semilattice and contains a maximum element
$\hat{1}$ then $\mathcal{L}$ is a lattice: for any $x,y\in\mathcal{L}$,

$x\vee y:=\bigwedge_{x,y\,\leq\,z}z.$

Thus if $\mathcal{L}$ is a meet-semilattice, or a join-semilattice, and
$x,y\in\mathcal{L}$ with $x\leq y$, the interval $[x,y]\subseteq\mathcal{L}$
is itself a lattice. Let $\mathcal{E}$ be a set and $\mathbb{S}$ a lattice of
subsets of $\mathcal{E}$ with meet given by intersection, then we refer to
$\mathbb{S}$ as an _intersection lattice_ 444We warn the reader that this
terminology, although natural, could be a source of confusion as the lattice
of flats of a hyperplane arrangement form an intersection lattice, but this is
the reverse of the intersection order of flats in an arrangement..

######  Definition 2.3.

A lattice $\mathcal{L}$ is _ranked_ if there exists a function
$r:\mathcal{L}\rightarrow\mathbb{Z}_{\geq 0}$ such that

  1. (1)

$x\leq y$ in $\mathcal{L}$ implies $r(x)\leq r(y)$.

  2. (2)

If $y$ covers $x$, then $r(y)=r(x)+1$.

A ranked lattice is said to be _supermodular_ if $r(x\wedge y)+r(x\vee y)\geq
r(x)+r(y)$.

A ranked lattice is said to be _submodular_ if $r(x\wedge y)+r(x\vee y)\leq
r(x)+r(y)$.

######  Definition 2.4.

[12, 18] Let $\mathcal{L}$ be a meet-semilattice, and
$B\subseteq\mathcal{L}^{+}$. The set $B$ is a _building set_ of $\mathcal{L}$
if for any $x\in\mathcal{L}^{+}$ and $\text{max}\,B_{\leq
x}=\\{x_{1},...,x_{k}\\}$ there is an isomorphism of posets

(1) $\phi_{x}:\prod_{j=1}^{k}[\hat{0},x_{j}]\rightarrow[\hat{0},x]$

with $\phi_{x}(y_{1},...,y_{k})=y_{1}\vee\cdots\vee y_{k}$ for
$y_{j}\in[\hat{0},x_{j}]$ with $1\leq j\leq k.$ We call $\text{max}\,B_{\leq
x}$ the _set of factors_ of $x$ in $B$.

######  Example 2.1.

The set of irreducible elements $I(\mathcal{L})$ form a building set by Lemma
2.1. We call $I(\mathcal{L})$ the _minimum building set._

######  Example 2.2.

The set $\mathcal{L}^{+}$ is a building set: for any $x\in\mathcal{L}^{+}$,
$\text{max}\,\mathcal{L}^{+}_{\leq x}=\\{x\\}$ and we have the trivial
isomorphism $\phi_{x}:[\hat{0},x]\rightarrow[\hat{0},x]$. We call
$\mathcal{L}^{+}$ the _maximum building set_.

We note that our terminology in Examples 2.1 and 2.2 differs from that of
others; the minimum and maximum building sets are typically referred to as the
minimal and maximal building sets, respectively. This revision of terminology
is justified by Proposition 2.3.

Associated to any building set one has a distinguished simplicial complex
$\mathcal{N}(B)$. Typically, when a building set $B$ is utilized for producing
a compactification ${\bf W}(B)$ of some space, $\mathcal{N}(B)$ encodes the
poset of strata of ${\bf W}(B)$. Although $\mathcal{N}(B)$ does not play a
significant role in the current version of our paper, we include its
definition for completeness.

######  Definition 2.5.

Let $\mathcal{L}$ be a meet-semilattice and $B\in\mathbb{B}(\mathcal{L})$. A
subset $N\subseteq B$ is a _nested set_ if for every $x_{1},...,x_{t}\in N$
with $t\geq 2$, which are incomparable elements,
$\bigvee_{i=1}^{t}x_{i}\in\mathcal{L}\backslash B$. The _nested set complex_
$\mathcal{N}(B)$ is the abstract simplicial complex consisting of all nested
sets of $B$.

Postnikov provided an impressively simple characterization of building sets
for the Boolean lattice [30]. Such objects have also appeared in the work of
Schmitt under the name Whitney systems [31]. Here we prove that Postnikov’s
characterization extends to arbitrary meet-semilattices. For recovering
Postnikov’s description from Proposition 2.2, note that for the Boolean
lattice, $I(\mathcal{L})=\\{\\{i\\}:i\in[n]\\}$, meets and joins are
intersections and unions, respectively, and joins always exist.

######  Proposition 2.2.

Let $\mathcal{L}$ be a meet-semilattice and $B\subseteq\mathcal{L}^{+}$. Then
$B$ is a building set if and only if

  1. (1)

$I(\mathcal{L})\subseteq B$

  2. (2)

if $x,y\in B$ such that $x\wedge y\neq\hat{0}$ and $x\vee y\in\mathcal{L}$,
then $x\vee y\in B$.

###### Proof.

($\Rightarrow$) Let $B$ be a building set of $\mathcal{L}$. It is clear that
from the definition of a building set that $I(\mathcal{L})\subseteq B$. Let
$x,y\in B$ such that $x\vee y\notin B$. If $x\vee y\notin\mathcal{L}$, there
is nothing to prove, so suppose that $x\vee y\in\mathcal{L}$, and let
$\text{max}\,B_{\leq x\vee y}=\\{z_{1},...,z_{k}\\}.$ Both $x$ and $y$ are
strictly less than $x\vee y$ as $x\vee y\not\in B$. Therefore
$x\in[\hat{0},z_{s}]$ and $y\in[\hat{0},z_{t}]$ where $s\neq t$. Since $B$ is
a building set there is an isomorphism $\phi_{x\vee
y}:\prod_{j=1}^{k}[\hat{0},z_{j}]\rightarrow[\hat{0},x\vee y]$. Because
$\phi_{x\vee y}$ is injective, the intersection of these intervals is
$\hat{0}$. It follows that $x\wedge y=\hat{0}$.
$(\Leftarrow)$ Let $B\subseteq\mathcal{L}^{+}$ which satisfies conditions (1)
and (2). Let $x\in\mathcal{L}$ and let $\text{max}\,B_{\leq
x}=\\{x_{1},...,x_{k}\\}$. We wish to show
$\prod_{j=1}^{k}[\hat{0},x_{j}]\cong[\hat{0},x]$. We begin with the
observation that for each $1\leq i,j\leq k$ with $i\neq j$,
$[\hat{0},x_{i}]\cap[\hat{0},x_{j}]=\hat{0}$. Suppose this is not the case and
let $z\in[\hat{0},x_{i}]\cap[\hat{0},x_{j}]$ with $\hat{0}\neq z$. Then
$x_{i}\wedge x_{j}\neq\hat{0}$ and $x_{i},x_{j}\leq x$, so $x_{i}\vee
x_{j}\in\mathcal{L}$, thus $x_{i}\vee x_{j}\in B$. But $x_{i}\vee x_{j}\leq x$
which contradicts the maximality of $x_{i}$ and $x_{j}$.

Let $\text{max}\,I(\mathcal{L})_{\leq x}=\\{y_{1},\ldots,y_{l}\\}$. For each
$1\leq t\leq k$ let $\pi_{t}=\\{y_{i}\in\text{max}\,I(\mathcal{L})_{\leq
x}:y_{i}\leq x_{t}\\}$. We claim that the set of $\pi_{t}$ forms a partition
of $\text{max}\,I(\mathcal{L})_{\leq x}$. By hypothesis $I(\mathcal{L})$ is a
subset of $B$, so for each $y_{i}$ there exists some $x_{t}$ such that
$y_{i}\leq x_{t}$, and we know by disjointness of the $[\hat{0},x_{i}]$, that
$x_{t}$ is unique in this regard – this establishes the partition.

We next claim that $\text{max}\,I(\mathcal{L})_{\leq x_{t}}=\pi_{t}$. Let
$y\in\text{max}\,I(\mathcal{L})_{\leq x_{t}}$, and let $y_{i}$ be such that
$y\leq y_{i}$. By our previous argument, there exists a unique $t$ such that
$y_{i}\leq x_{t}$, hence $y=y_{i}$. By Lemma 2.1 there are isomorphisms

$\phi_{x}:\prod_{j=1}^{l}[\hat{0},y_{j}]\xrightarrow{\cong}[\hat{0},x]\hskip
14.22636pt\text{and}\hskip
14.22636pt\phi_{x_{t}}:\prod_{y\in\pi_{t}}[\hat{0},y]\xrightarrow{\cong}[\hat{0},x_{t}]$

It follows that
$\phi_{x}\circ\prod_{t=1}^{k}(\phi_{x_{t}})^{-1}:\prod_{t=1}^{k}[\hat{0},x_{t}]\rightarrow[\hat{0},x]$
is an isomorphism.

∎

Manntovani-Padrol-Pilaud [26] have found a cryptomorphic characterization of
building sets for Las Vergnas’ face lattice of an oriented matroid. In the
future, we hope to compare Proposition 2.2 with their characterization555We
remark that the recent work of Brauner-Eur-Pratt-Raluca [10] has some overlap
with the work of Manntovani-Padrol-Pilaud [26], but not in this particular
aspect it seems..

Given a meet-semilattice $\mathcal{L}$, we denote
$\mathbb{B}(\mathcal{L})=\\{B\subseteq\mathcal{L}^{+}:B\leavevmode\nobreak\
\text{is a building set of}\leavevmode\nobreak\ \mathcal{L}\\}.$ We will now
investigate the poset $(\mathbb{B}(\mathcal{L}),\subseteq)$. When
$\mathcal{L}$ is clear from context we may simply refer to
$(\mathbb{B}(\mathcal{L}),\subseteq)$ as $\mathbb{B}$. To the best of our
knowledge, the following observation has not appeared previously, even in the
case of the Boolean lattice, although the literature is vast and it is
possible that we have overlooked some reference.

######  Theorem 2.3.

Let $\mathcal{L}$ be a meet-semilattice. The poset
$(\mathbb{B}(\mathcal{L}),\subseteq)$ is a lattice.

###### Proof.

We first utilize Proposition 2.2 for showing that the intersections of two
buildings sets is a building set. Let $B,B^{\prime}\in\mathbb{B}$. As
$I(\mathcal{L})\subseteq B,B^{\prime}$, we have that $I(\mathcal{L})\subseteq
B\cap B^{\prime}$. Let $x,y\in B\cap B^{\prime}$ such that $x\wedge
y\neq\hat{0}$. If $x\vee y\in\mathcal{L}$, then $x\vee y\in B$ and $x\vee y\in
B^{\prime}$ as $B$ and $B^{\prime}$ are building sets. Therefore $x\vee y\in
B\cap B^{\prime}$. Note that $\mathbb{B}$ has a maximum element
$\mathcal{L}^{+}$. Thus $\mathbb{B}$ is a meet-semilattice with a maximum
element and is therefore a lattice. ∎

##  3\. Convex Geometries

In this section we review the theory of convex geometries and prove Theorem
3.2, which states that the collection of building sets on a meet-semilattice
forms a supersolvable convex geometry. We provide a new characterization of
supersolvable convex geometries and conclude with a brief discussion of how
one can algorithmically produce building sets using the ideas of this article.

######  Definition 3.1.

A _set system_ is a pair $(\mathcal{E},\mathbb{S})$ where $\mathcal{E}$ is a
set and $\mathbb{S}\subseteq 2^{\mathcal{E}}$. We refer to $\mathcal{E}$ as
the _ground set_.

######  Definition 3.2.

A _closure operator_ on a ground set $\mathcal{E}$ is a map
$\sigma:2^{\mathcal{E}}\rightarrow 2^{\mathcal{E}}$ such that for each
$A,B\subseteq\mathcal{E}$,

  1. (1)

$A\subseteq\sigma(A)$

  2. (2)

$A\subseteq B\Rightarrow\sigma(A)\subseteq\sigma(B)$

  3. (3)

$\sigma(\sigma(A))=\sigma(A)$

We call the set $A$ _convex_ or _closed_ if $\sigma(A)=A$.

######  Definition 3.3.

Let $\sigma$ be a closure operator on ground set $\mathcal{E}$. Let
$\mathbb{S}=\\{A\in 2^{\mathcal{E}}:\sigma(A)=A\\}$ be the closed subsets of
$\mathcal{E}$. Then $(\mathcal{E},\mathbb{S},\sigma)$ is called a _closure
system_.

######  Lemma 3.1.

Let $(\mathcal{E},\mathbb{S},\sigma)$ be a closure system and
$A,B\in\mathcal{E}$, then $\sigma(A)\cap\sigma(B)\in\mathbb{S}$.

###### Proof.

It needs to be shown that
$\sigma(\sigma(A)\cap\sigma(B))=\sigma(A)\cap\sigma(B)$. By (2) of Definition
3.2, $\sigma(\sigma(A)\cap\sigma(B))\subseteq\sigma(\sigma(A))=\sigma(A)$ by
(3) and $\sigma(\sigma(A)\cap\sigma(B))\subseteq\sigma(\sigma(B))=\sigma(B)$
by (3), which implies
$\sigma(\sigma(A)\cap\sigma(B))\subseteq\sigma(A)\cap\sigma(B)$. The reverse
inclusion is a consequence of (1) of Definition 3.2. ∎

######  Remark 2.

Every closure system $(\mathcal{E},\mathbb{S},\sigma)$ comes with a natural
meet and join: for $A,B\in\mathbb{S}$, $A\wedge B=A\cap B$ and $A\vee
B=\sigma(A\cup B)$. Thus $\mathbb{S}$ is an intersection lattice. Conversely,
given an intersection lattice $\mathbb{S}$ with ground set $\mathcal{E}$, we
can define a closure operator $\sigma:2^{\mathcal{E}}\rightarrow
2^{\mathcal{E}}$ as follows: given $X\subseteq\mathcal{E}$, let

$\sigma(X)=\bigcap_{A\in\mathbb{S},X\subseteq A}A.$

This induces a canonical identification of intersection lattices and closure
operators. It follows, in particular, that a closure system
$(\mathcal{E},\mathbb{S},\sigma)$ is encoded by $(\mathcal{E},\mathbb{S})$
alone.

######  Definition 3.4.

[14, 23] Let $(\mathcal{E},\mathbb{S},\sigma)$ be a closure system and assume
in addition that $\sigma$ satisfies

$\bullet\,\,\text{for every}\leavevmode\nobreak\
A\in\mathbb{S}\leavevmode\nobreak\ \text{and any distinct}\leavevmode\nobreak\
x,y\not\in A,\text{if}\,\leavevmode\nobreak\
y\in\sigma(A\cup\\{x\\})\,\text{then}\,x\not\in\sigma(A\cup\\{y\\}.)$

Then $\sigma$ is an _anti-exchange closure operator_ and
$(E,\mathbb{S},\sigma)$ is a _convex geometry_. We may denote the convex
geometry by $\mathbb{S}$ when no confusion will arise.

Greedoids are a generalization of matroids which were originally introduced by
Korte and Lovász in the setting of greedy algorithms [24]. Antimatroids form
another important class of greedoids. They first apppeared in the work of
Dilworth [13] where they were described in the language of lattices. Greeoids,
antimatroids, and convex geometries, much like matroids, admit several
cryptomorphic definitions. We refer the reader to the excellent survey by
Björner and Ziegler for an introduction to greedoids and antimatroids [7]. The
following definition is one of the most well-known definitions of an
antimatroid.

######  Definition 3.5.

An _antimatroid_ is a set system $(\mathcal{E},\mathbb{S})$ such that

  1. (1)

$\emptyset\in\mathbb{S}$

  2. (2)

$\text{for every}\leavevmode\nobreak\ A,B\in\mathbb{S}\leavevmode\nobreak\
\text{such that}\leavevmode\nobreak\ B\nsubseteq A,\leavevmode\nobreak\
\text{there exists}\leavevmode\nobreak\ e\in B\backslash A\leavevmode\nobreak\
\text{such that}\leavevmode\nobreak\ A\cup\\{e\\}\in\mathbb{S}$

For any set system $(\mathcal{E},\mathbb{S})$ there is a complementary set
system on the same groundset: $(\mathcal{E},\mathbb{S}^{c})$ where by
$\mathbb{S}^{c}$ we mean $\\{\mathcal{E}\backslash F:F\in\mathbb{S}\\}$. A
fundamental result of Björner states that a set system
$(\mathcal{E},\mathbb{S})$ is a convex geometry if and only if the
complementary set system $(\mathcal{E},\mathbb{S}^{c})$ is an antimatroid [6].
Thus a convex geometry can alternately be defined as follows.

######  Definition 3.6.

A _convex geometry_ is a set system $(\mathcal{E},\mathbb{S})$ such that

  1. (1)

$\mathcal{E}\in\mathbb{S}$

  2. (2)

$\text{for every}A,B\in\mathbb{S}\leavevmode\nobreak\ \text{such
that}\leavevmode\nobreak\ B\nsupseteq A,\leavevmode\nobreak\ \text{there
exists}\leavevmode\nobreak\ e\in A\backslash B\leavevmode\nobreak\ \text{such
that}\leavevmode\nobreak\ A\backslash\\{e\\}\in\mathbb{S}$

Supersolvable lattices were first introduced by Stanley [32] motivated by the
study of supersolvable groups. In the same work, he defined supersolvable
join-distributive lattices. Edelman proved that join-distributive lattices are
cryptomorphic to antimatroids666More accurately, Edelman proved that meet-
distributive lattices are cryptomorphic to convex geometries.[14]. Hawrylycz
and Reiner demonstrated that the collection of all closure operators on a
poset defines a supersolvable join-distributive lattice [22]. Armstrong
provided a natural cryptomorphic description of supersolvable join-
distributive lattices in the context of antimatroids, and applied this notion
in the study of Coxeter groups [5].

######  Definition 3.7.

[5] Let $(\mathcal{E},\mathbb{S})$ be a closure system. Let $<$ be a total
order of $\mathcal{E}$. We say that $\mathbb{S}$ is a _supersolvable
antimatroid_ if

  1. (1)

$\emptyset\in\mathbb{S}$

  2. (2)

$\text{for every}\leavevmode\nobreak\ A,B\in\mathbb{S}\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\ B\nsubseteq A,\leavevmode\nobreak\
\text{for}\leavevmode\nobreak\ e=\text{min}_{<}(B\backslash
A)\leavevmode\nobreak\ \text{we have }\leavevmode\nobreak\
A\cup\\{e\\}\in\mathbb{S}.$

We say $\mathbb{S}$ is supersolvable with respect to $<$.

Thus one has the following dual definition of supersolvable convex geometries,
which was utilized by Gillespie in the study of matroid activities [21].

######  Definition 3.8.

[5, 21] 777Definition 3.8 and the phrase “supersolvable convex geometry” do
not appear in [5, 21], nonetheless we feel it is appropriate to attribute this
definition to those sources as it is implicit in their discussions. Let
$(\mathcal{E},\mathbb{S})$ be a closure system. Let $<$ be a total order of
$\mathcal{E}$. We say that $\mathbb{S}$ is a _supersolvable convex geometry_
if

  1. (1)

$\mathcal{E}\in\mathbb{S}$

  2. (2)

$\text{for every}\leavevmode\nobreak\ A,B\in\mathbb{S}\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\ B\nsupseteq A,\leavevmode\nobreak\
\text{for}\leavevmode\nobreak\ e=\text{min}_{<}(A\backslash
B)\leavevmode\nobreak\ \text{we have }\leavevmode\nobreak\
A\setminus\\{e\\}\in\mathbb{S}.$

We say $\mathbb{S}$ is supersolvable with respect to $<$.

The following is our main result.

######  Theorem 3.2.

Let $\mathcal{L}$ be a meet-semilattice, then
$(\mathcal{L}^{+},\mathbb{B}(\mathcal{L}))$ is a supersolvable convex geometry
which is supersolvable respect to any linear extension of $\mathcal{L}$.

###### Proof.

Let $<$ be a linear extension of $\mathcal{L}$. As was noted in example 2.2,
$\mathcal{L}^{+}\in\mathbb{B}$ thus condition (1) is satisfied. For verifying
condition (2), let $B,B^{\prime}\in\mathbb{B}$ with $B^{\prime}\not\subseteq
B$, and $x=\text{min}_{<}(B^{\prime}\backslash B)$. We claim that
$B^{\prime}\backslash\\{x\\}\in\mathbb{B}$, and we verify the conditions of
Proposition 2.2. Since $I(\mathcal{L})\subseteq B$ and $x\not\in B$, $x$ is
not irreducible so $B^{\prime}\backslash\\{x\\}$ contains $I(\mathcal{L})$.
Let $y,z\in B^{\prime}\backslash\\{x\\}$ such that $y\wedge z\neq\hat{0}$. If
$y\vee z\in\mathcal{L}$, by Proposition 2.2, $y\vee z\in B^{\prime}$. We wish
to show that $y\vee z\neq x$ for which we need only consider $y,z<x$. By the
minimality of $x$ as an element outside of $B$ we know $y,z\in B$. By
Proposition 2.2, $y\vee z\in B$ so certainly $y\vee z\neq x$. Thus $y\vee z\in
B^{\prime}\backslash{x}$. By Proposition 2.2, it follows that
$B^{\prime}\backslash\\{x\\}\in\mathbb{B}$. ∎

######  Corollary 3.3.

$\mathbb{B}(\mathcal{L})$ is a supermodular lattice.

###### Proof.

This a standard property of any convex geometry – we provide a proof here. For
$B\in\mathbb{B}(\mathcal{L})$, set $B^{\circ}:=B\backslash I(\mathcal{L})$.
Define the function $r:\mathbb{B}\rightarrow\mathbb{Z}_{\geq 0}$ by
$r(B)=|B^{\circ}|$, and note that $r(I(\mathcal{L}))=0$. Let
$B,B^{\prime}\in\mathbb{B}$ such that $B^{\prime}$ covers $B$. By Theorem 3.2,
if $x=min_{<}(B^{\prime}\setminus B)$, then
$B^{\prime}\backslash\\{x\\}\in\mathbb{B}$, thus $B^{\prime}=B\cup\\{x\\}$,
and $r(B^{\prime})=r(B)+1$. Therefore $\mathbb{B}(\mathcal{L})$ is ranked. To
see that $r$ is supermodular let $B,B^{\prime}\in\mathbb{B}$. Then $r(B\vee
B^{\prime})=|(B\vee B^{\prime})^{\circ}|\geq|B^{\circ}\cup B^{\prime\circ}|$
and $r(B\wedge B^{\prime})=|(B\wedge B^{\prime})^{\circ}|=|(B\cap
B^{\prime})^{\circ}|=|B^{\circ}\cap B^{\prime\circ}|$ together imply

$r(B\vee B^{\prime})+r(B\wedge B^{\prime})\geq|B^{\circ}\cup
B^{\prime\circ}|+|B^{\circ}\cap
B^{\prime\circ}|=|B^{\circ}|+|B^{\prime\circ}|=r(B)+r(B^{\prime}).$

∎

We now introduce a new characterization of supersolvable convex geometries,
which we feel is a bit closer to the definition of a building set, and
motivates Proposition 3.5.

######  Definition 3.9.

Let $\sigma:2^{\mathcal{E}}\rightarrow 2^{\mathcal{E}}$ be a closure operator
and $<$ be a total order on $\mathcal{E}$. We say that $\sigma$ is a
_supersolvable closure operator_ (with respect to $<$) if for each closed set
$A$ and $e\in\mathcal{E}\setminus A$, we have that

  * •

if $f\in\sigma(A\cup\\{e\\})\setminus(A\cup\\{e\\})$ then $e<f$.

######  Proposition 3.4.

Let $(\mathcal{E},\mathbb{S})$ be a set system, then $\mathbb{S}$ is a
supersolvable convex geometry if and only if $\mathbb{S}$ is the collection of
closed sets of a supersolvable closure operator.

###### Proof.

Suppose that $(\mathcal{E},\mathbb{S})$ is a supersolvable convex geometry
with associated closure operator $\sigma$. Suppose that $\sigma$ is not
supersolvable, then there exists a closed set $A$ and
$e,f\in\mathcal{E}\setminus A$ such that
$f\in\sigma(A\cup\\{e\\})\setminus(A\cup\\{e\\})$, and $f<e$. Take $f$ to be
the minimum such element. Applying condition 2 Definition 3.8 to the pair of
sets $A,\sigma(A\cup\\{e\\})$, we have that $\sigma(A\cup\\{e\\})\setminus
f\in\mathbb{S}$, but this contradicts the definition of
$\sigma(A\cup\\{e\\})$.

Conversely, suppose that $\sigma$ is a supersolvable closure operator on
$\mathcal{E}$ with $\mathbb{S}$ the associated closed sets. Let
$A,B\in\mathbb{S}$ and let $e=min_{<}(B\setminus A)$. Suppose for
contradiction that $B\setminus\\{e\\}$ is not a closed set. As $\sigma$ is a
closure operator, we know by Lemma 3.1 that $A\cap B$ is closed . Let
$e=e_{0}<\ldots<e_{k}$ be the elements of $B\setminus A$. Let $i$ be the
smallest index such that $e_{0}\in\sigma((A\cap
B)\cup\\{e_{1},\ldots,e_{i}\\})$. Let $X=(A\cap
B)\cup\\{e_{1},\ldots,e_{i-1}\\}$, then
$e_{0}\in\sigma(X\cup\\{e_{i}\\})\setminus(X\cup\\{e_{i}\\})$, but
$e_{0}<e_{i}$ contradicting supersolvability of $\sigma$. ∎

If follows from Theorem 3.2 and Proposition 3.4 that the closure operator for
building sets is supersolvable with respect to any linear extension of
$\mathcal{L}$. We will refine this observation with Proposition 3.5 by giving
an explicit description of $\sigma(B\cup\\{x\\})$. We digress briefly to
discuss algorithmic aspects of constructing building sets. Suppose that
$X\subseteq\mathcal{L}$. We apply Proposition 2.2 for computing $\sigma(X)$.
First, set $X_{0}:=X\cup I(\mathcal{L})$. Given $X_{i}$, set

$Y_{i}:=\\{a\vee b\in\mathcal{L}:a,b\in X_{i}\,,\,a\wedge
b\neq\hat{0}\\},\,\,\text{and}\,\,X_{i+1}:=X_{i}\cup Y_{i}.$

Because $\mathcal{L}$ is finite and $X_{i}\subseteq X_{i+1}$, there must be
some $k$ for which $X_{k+1}=X_{k}$. An inductive application of Proposition
2.2 implies that $X_{k}=\sigma(X)$. The following Proposition 3.5 provides a
more organized and incremental way of doing this. As noted above, this
proposition refines the statement that the closure operator for building sets
is supersolvable.

######  Proposition 3.5.

Let $\mathcal{L}$ be a meet-semilattice and $B$ a building set for
$\mathcal{L}$. Let $x\in\mathcal{L}\setminus B$, and

$B(x)=B\cup\\{x\vee y\in\mathcal{L}:y\in B,x\wedge
y\neq\hat{0}\\},\,\,\text{then}\,\,B(x)=\sigma(B\cup\\{x\\}).$

###### Proof.

Clearly $B(x)\subseteq\sigma(B\cup x)$. For demonstrating the reverse
inclusion, it suffices to show that $B(x)$ is a building set. We verify the
conditions of Propostion 2.2. Condition (1) is immediate as $B$ is a building
set, so we verify condition (2). Let $a,b\in B(x)$ such that $a\wedge
b\neq\hat{0}$ and $a\vee b\in\mathcal{L}$. We wish to prove that $a\vee b\in
B(x)$. If $a,b\in B$, then this is immediate as $B$ is a building set. Suppose
that $a\in B$ and $b\in B(x)\setminus B$. Let $b=b^{\prime}\vee x$ with
$b^{\prime}\in B$. Then $a\vee b=a\vee(b^{\prime}\vee x)=(a\vee
b^{\prime})\vee x$ by associativity of the join. As $b\in B(x)$, we know that
$b^{\prime}\wedge x\neq\hat{0}$, thus $(a\vee b^{\prime})\wedge x\neq\hat{0}$,
and $a\vee b\in B(x)$. Finally, assume that $a,b\in B(x)\setminus B$. Let
$a=a^{\prime}\vee x$ and $b=b^{\prime}\vee x$ with $a^{\prime},b^{\prime}\in
B$ and $a^{\prime}\wedge x\neq\hat{0}$, $b^{\prime}\wedge x\neq\hat{0}$. Then
$a\vee b=(a^{\prime}\vee x)\vee(b^{\prime}\vee x)=(a^{\prime}\vee
b^{\prime})\vee x$, by associativity, commutativity, and idempotency of
$\vee$. Because $a^{\prime}\wedge x\neq\hat{0}$, we know $(a^{\prime}\vee
b^{\prime})\wedge x\neq\hat{0}$ and thus $a\vee b\in B(x)$. ∎

Given $X\subseteq\mathcal{L}$, one may instead compute $\sigma(X)$ as follows:
start with $I(\mathcal{L})$. At each step, add an element of $X$ and calculate
the closure using of Proposition 3.5. Another method of producing building
sets is to first construct some building sets $B$ and $B^{\prime}$ such that
$B\nsubseteq B^{\prime}$, e.g. by the previous method. We can then apply
supersolvability to remove elements from $B$ one at a time – all of the
intermediate sets will be building sets.

##  4\. Future Work

In the future we plan to calculate the characteristic polynomial of
$\mathbb{B}(\mathcal{L})^{op}$, and to explore a convex geometric
characterization of building sets in the spirit of Gillespie’s work [21].

##  5\. Acknowledgements

The authors were supported by NSF Grant (DMS-2246967) and Simons Collaboration
Gift #854037. We thank Nate Bottman, Federico Castillo, Graham Denham, Alexei
Oblomkov, Arnau Padrol, Vincent Pilaud, Dasha Poliakova, and Raman Sanyal for
helpful discussions about building sets, and we thank Bryan Gillespie for
carefully explaining his work during the 2017 MSRI Semester on “Geometric and
Topological Combinatorics”. Some of our discussions took place at the Simons
Center for Geometry and Physics Workshop on “Combinatorics and Geometry of
Convex Polyhedra” in March 2023. S.B. thanks the MSRI (now SLMath) and the
Simons Center for their hospitality and excellent working conditions.

## References

  * [1] K. Adiprasito, J. Huh, and E. Katz.  Hodge theory for combinatorial geometries.  Annals of Mathematics, 188(2):381–452, 2018.
  * [2] F. Ardila, G. Denham, and J. Huh.  Lagrangian combinatorics of matroids.  arXiv preprint arXiv:2109.11565, 2021.
  * [3] F. Ardila, G. Denham, and J. Huh.  Lagrangian geometry of matroids.  Journal of the American Mathematical Society, 36(3):727–794, 2023.
  * [4] F. Ardila and C. J. Klivans.  The Bergman complex of a matroid and phylogenetic trees.  Journal of Combinatorial Theory, Series B, 96(1):38–49, 2006.
  * [5] D. Armstrong.  The sorting order on a Coxeter group.  Journal of Combinatorial Theory, Series A, 116(8):1285–1305, 2009.
  * [6] A. Björner.  On matroids, groups and exchange languages.  Department of Mathematics, University of Stockholm, Sweden, 1983.
  * [7] A. Björner and G. M. Ziegler.  Introduction to greedoids.  Matroid applications, 40:284–357, 1992.
  * [8] T. Braden, J. Huh, J. P. Matherne, N. Proudfoot, and B. Wang.  Singular hodge theory for combinatorial geometries.  arXiv preprint arXiv:2010.06088, 2020.
  * [9] T. Braden, J. Huh, J. P. Matherne, N. Proudfoot, and B. Wang.  A semi-small decomposition of the Chow ring of a matroid.  Advances in Mathematics, 409:108646, 2022.
  * [10] S. Brauner, C. Eur, E. Pratt, and R. Vlad.  Wondertopes.  arXiv preprint arXiv:2403.04610, 2024.
  * [11] C. Crowley, J. Huh, M. Larson, C. Simpson, and B. Wang.  The Bergman fan of a polymatroid.  arXiv preprint arXiv:2207.08764, 2022.
  * [12] C. De Concini and C. Procesi.  Wonderful models of subspace arrangements.  Selecta Mathematica, 1:459–494, 1995.
  * [13] R. Dilworth.  Lattices with unique irreducible decompositions.  Annals of Mathematics, pages 771–777, 1940.
  * [14] P. H. Edelman.  Meet-distributive lattices and the anti-exchange closure.  Algebra Universalis, 10:290–299, 1980.
  * [15] P. H. Edelman and R. E. Jamison.  The theory of convex geometries.  Geometriae dedicata, 19(3):247–270, 1985.
  * [16] C. Eur, J. Huh, and M. Larson.  Stellahedral geometry of matroids.  In Forum of Mathematics, Pi, volume 11, page e24. Cambridge University Press, 2023.
  * [17] C. Eur and M. Larson.  Intersection theory of polymatroids.  International Mathematics Research Notices, page rnad213, 2023.
  * [18] E.-M. Feichtner and D. N. Kozlov.  Incidence combinatorics of resolutions.  Selecta Mathematica, 10:37–60, 2004.
  * [19] E. M. Feichtner and B. Sturmfels.  Matroid polytopes, nested sets and Bergman fans.  Portugaliae Mathematica. Nova Série, 62(4):437–468, 2005.
  * [20] E. M. Feichtner and S. Yuzvinsky.  Chow rings of toric varieties defined by atomic lattices.  Inventiones mathematicae, 155(3):515–536, 2004.
  * [21] B. R. Gillespie.  Convexity in ordered matroids and the generalized external order.  The Electronic Journal of Combinatorics, pages P3–41, 2020.
  * [22] M. Hawrylycz and V. Reiner.  The lattice of closure relations on a poset.  Algebra Universalis, 30:301–310, 1993.
  * [23] R. E. Jamison-Waldner.  A perspective on abstract convexity: classifying alignments by varieties.  Convexity and Related Combinatorial Geometry, New York, 1982.
  * [24] B. Korte and L. Lovász.  Mathematical structures underlying greedy algorithms.  In International Conference on Fundamentals of Computation Theory, pages 205–209. Springer, 1981.
  * [25] H.-C. Liao.  Stembridge codes and Chow rings.  arXiv preprint arXiv:2212.05362, 2022.
  * [26] E. Mantovani, A. Padrol, and V. Pilaud.  Acyclonestohedra.  _in preparation_.
  * [27] M. Mastroeni and J. McCullough.  Chow rings of matroids are Koszul.  Mathematische Annalen, 387(3):1819–1851, 2023.
  * [28] A. Nathanson and E. Partida.  On the topology of conormal complexes and posets of matroids.  arXiv preprint arXiv:2310.12291, 2023.
  * [29] R. Pagaria and G. M. Pezzoli.  Hodge theory for polymatroids.  International Mathematics Research Notices, 2023(23):20118–20168, 2023.
  * [30] A. Postnikov.  Permutohedra, associahedra, and beyond.  International Mathematics Research Notices, 2009(6):1026–1106, 2009.
  * [31] W. R. Schmitt.  Hopf algebra methods in graph theory.  Journal of Pure and Applied Algebra, 101(1):77–90, 1995.
  * [32] R. P. Stanley.  Supersolvable lattices.  Algebra Universalis, 2(1):197–217, 1972.