# Ramsey numbers upon vertex deletion

Yuval Wigderson Institute for Theoretical Studies, ETH Zürich, 8092 Zürich,
Switzerland. Email address<EMAIL_ADDRESS>Supported in part
by NSF GRFP Grant DGE-1656518, ERC Consolidator Grants 863438 and 101044123,
and NSF-BSF Grant 20196.

###### Abstract

Given a graph $G$, its Ramsey number $r(G)$ is the minimum $N$ so that every
two-coloring of $E(K_{N})$ contains a monochromatic copy of $G$. It was
conjectured by Conlon, Fox, and Sudakov that if one deletes a single vertex
from $G$, the Ramsey number can change by at most a constant factor. We
disprove this conjecture, exhibiting an infinite family of graphs such that
deleting a single vertex from each decreases the Ramsey number by a super-
constant factor.

One consequence of this result is the following. There exists a family of
graphs $\\{G_{n}\\}$ so that in any Ramsey coloring for $G_{n}$ (that is, a
coloring of a clique on $r(G_{n})-1$ vertices with no monochromatic copy of
$G_{n}$), one of the color classes has density $o(1)$.

##  1 Introduction

The Ramsey number of a graph $G$ is the minimum $N$ so that every two-coloring
of the edges of the complete graph $K_{N}$ contains a monochromatic copy of
$G$. Motivated by understanding the concentration of the Ramsey number of the
Erdős–Rényi random graph $G(n,p)$, Conlon, Fox, and Sudakov [3] made the
following natural conjecture.

######  Conjecture 1.1 ([3, Conjecture 5.1]).

There exists a universal constant $C>0$ so that the following holds. Let $G$
be a graph, and let $H$ be obtained from $G$ by deleting a single vertex. Then

$r(G)\leq C\cdot r(H).$

Conlon, Fox, and Sudakov proved two natural weakenings of this conjecture.
First, they showed that Conjecture 1.1 holds when $G$ is a dense graph, i.e.
when it has $n$ vertices and at least $p\binom{n}{2}$ edges, and $C$ is
allowed to depend on $p$. They also proved a slightly weaker inequality,
namely that for any $(n+1)$-vertex graph $G$ and any graph $H$ obtained by
deleting a single vertex from $G$, one has

$r(G)\leq 2n\cdot r(H).$ (1)

Our goal in this paper is to disprove Conjecture 1.1. We find an explicit
family of graphs such that deleting a single vertex decreases the Ramsey
number by a super-constant factor. Here, and in the rest of the paper, all
logarithms have base $2$.

######  Theorem 1.2.

For any $n\geq 16$, there exists an $(n+1)$-vertex graph $G$ with Ramsey
number $r(G)>\frac{1}{3}n\log n$. However, there is a vertex of $G$ whose
deletion yields a graph $H$ with Ramsey number $r(H)=n$. In particular,
$r(G)=\omega(r(H))$.

In the other direction, we prove the following strengthening of (1).

######  Theorem 1.3.

Let $G$ be an $(n+1)$-vertex graph, and suppose that $H$ is obtained from $G$
by deleting one vertex. Then

$r(G)\leq C\sqrt{n\log n}\cdot r(H)$

for some absolute constant $C>0$.

Recall that the edge density of an $N$-vertex graph is its number of edges
divided by $\binom{N}{2}$. For $\varepsilon\in(0,\frac{1}{2}]$, let us say
that a two-coloring of $E(K_{N})$ is _$\varepsilon$ -balanced_ if both color
classes have edge density at least $\varepsilon$. Ramsey properties of
$\varepsilon$-balanced colorings have been well studied, see e.g. [6, 7, 4, 1,
9]. A _Ramsey coloring_ for a graph $G$ is a two-coloring of $E(K_{N})$, where
$N=r(G)-1$, which contains no monochromatic copy of $G$. In general, there may
be multiple non-isomorphic Ramsey colorings for $G$. For
$\varepsilon\in(0,\frac{1}{2}]$, let us say that $G$ is _$\varepsilon$
-Ramsey-balanced_ if there exists a Ramsey coloring for $G$ which is
$\varepsilon$-balanced.

Our next result shows that for Ramsey-balanced graphs $G$, Conjecture 1.1 is
true.

######  Proposition 1.4.

Let $\varepsilon\in(0,\frac{1}{2}]$, let $G$ be an $\varepsilon$-Ramsey-
balanced graph, and let $H$ be obtained from $G$ by deleting one vertex. Then

$r(G)\leq\frac{4}{\varepsilon}\cdot r(H).$

Proposition 1.4 shows that Conjecture 1.1 is true for any graph $G$ which is
$\Omega(1)$-Ramsey-balanced. Combined with Theorem 1.2, we conclude that for
any fixed $\varepsilon>0$, there exist graphs which are _not_
$\varepsilon$-Ramsey-balanced. This is somewhat surprising, as one might
naively expect all graphs to be Ramsey-balanced: since we are searching for
the same graph in both the red and blue colors, it seems plausible that any
extremal coloring should have roughly equal red and blue densities, or at
least that these densities would be within a constant factor of one another.

The rest of this paper is organized as follows. In Section 2, we exhibit
explicit graphs in which the removal of one vertex changes the Ramsey number
by a super-constant factor, proving Theorem 1.2. In Section 3, we prove
Theorem 1.3, establishing a stronger upper bound than (1). In Section 4, we
prove Proposition 1.4, showing that Conjecture 1.1 is true for Ramsey-balanced
graphs. In Section 5, we make some comments on the multicolor version of these
problems. We end with some concluding remarks and open problems in Section 6.
For clarity of presentation, we systematically omit floor and ceiling signs
whenever they are not crucial.

##  2 Proof of Theorem 1.2

Let $k$ and $n\geq 4^{k}$ be positive integers. Let $H_{k,n}$ be the
$n$-vertex graph consisting of the clique $K_{k}$, plus $n-k$ isolated
vertices. Additionally, let $G_{k,n}$ be obtained from $H_{k,n}$ by adding an
apex vertex, i.e. a vertex adjacent to all vertices of $H_{k,n}$. We note for
future reference that $G_{k,n}$ is connected and has chromatic number $k+1$.
Theorem 1.2 follows from the following two lemmas, both of which have simple
proofs using standard techniques, which we give after stating the lemmas.

######  Lemma 2.1.

$r(H_{k,n})=n$ if $n\geq 4^{k}$.

######  Lemma 2.2.

$r(G_{k,n})>nk$.

In particular, given $n\geq 16$, let $k=\lfloor\frac{1}{2}\log n\rfloor$, so
that $4^{k}\leq n<4^{k+1}$. Then $r(G_{k,n})>nk\geq\frac{1}{3}n\log n$ since
$n\geq 16$. This shows that Theorem 1.2 follows from Lemmas 2.1 and 2.2.

###### Proof of Lemma 2.1.

The lower bound $r(H_{k,n})\geq n$ is immediate since every $n$-vertex graph
has Ramsey number at least $n$. For the upper bound, fix a two-coloring of
$E(K_{n})$. Erdős and Szekeres [5] proved that $r(K_{k})\leq 4^{k}\leq n$, so
this coloring contains a monochromatic $K_{k}$. Together with the remaining
$n-k$ vertices, we obtain a monochromatic copy of $H_{k,n}$. ∎

###### Proof of Lemma 2.2.

Let $N=nk$, and consider the _Turán coloring_ of $E(K_{N})$. Namely, we
equitably partition $V(K_{N})$ into sets $S_{1},\dots,S_{k}$, each of order
$n$. We color all edges inside some $S_{i}$ red, and all edges between $S_{i}$
and $S_{j}$ blue, for all $i\neq j$. Since $G_{k,n}$ is connected and has
$n+1$ vertices, there can be no monochromatic red copy of $G_{k,n}$, as the
connected components of the red graph in this coloring each have $n$ vertices.
The blue graph, on the other hand, has chromatic number $k$, and $G_{k,n}$ has
chromatic number $k+1$, so there can be no monochromatic blue copy of
$G_{k,n}$ either. This shows that $r(G_{k,n})>nk$, as claimed. ∎

##  3 Upper bounds

A graph $H$ is called _$d$ -degenerate_ if every subgraph of $H$ has a vertex
of degree at most $d$. Equivalently, $H$ is $d$-degenerate if one can order
its vertices so that every vertex has at most $d$ neighbors which precede it
in the ordering. The _degeneracy_ of $H$ is defined as the minimum $d$ so that
$H$ is $d$-degenerate.

Theorem 1.3 follows from the following result, which gives two bounds on
$r(G)/r(H)$ when $H$ is obtained from $G$ by deleting a vertex; the first is
strong when $H$ is sparse (i.e. has low degeneracy), while the second is
stronger when $H$ is dense (i.e. has high degeneracy). Balancing the two
bounds, we obtain Theorem 1.3.

######  Proposition 3.1.

Let $H$ be obtained from $G$ by deleting a vertex. If $H$ has $n$ vertices and
degeneracy $d\geq 1$, then

$r(G)\leq 4dr(H),$ (2)

and

$r(G)\leq\left(A\frac{n}{d}\log\frac{n}{d}\right)r(H)$ (3)

where $A>0$ is an absolute constant.

We remark that the graph $H_{k,n}$ constructed in Section 2 has degeneracy
$k=\Theta(\log n)$. Since $r(G_{k,n})/r(H_{k,n})=\Omega(\log n)$, this shows
that (2) is tight up to the constant factor for the graphs $G_{k,n}$ and
$H_{k,n}$. This implies that if one were to search for stronger
counterexamples to Conjecture 1.1, they would need to have somewhat higher
degeneracy (i.e. $d=\omega(\log n)$).

Assuming Proposition 3.1, Theorem 1.3 follows.

###### Proof of Theorem 1.3.

Note that for $d\geq 1$, we have

$\min\left\\{4d,A\frac{n}{d}\log\frac{n}{d}\right\\}\leq\sqrt{4d\cdot
A\frac{n}{d}\log\frac{n}{d}}=\sqrt{4An\log\frac{n}{d}}\leq\left(2\sqrt{A}\right)\sqrt{n\log
n}.$

Setting $C=2\sqrt{A}$ and applying Proposition 3.1 yields Theorem 1.3. ∎

To prove Proposition 3.1, we need the following simple and well-known lemma,
which shows that one can embed a graph of bounded degeneracy in a very dense
graph.

######  Lemma 3.2.

Let $H$ be an $n$-vertex $d$-degenerate graph, and let $R$ be an $N$-vertex
graph in which every vertex has at most $(N-n)/d$ non-neighbors. Then $H$ is a
subgraph of $R$.

###### Proof.

Let the vertices of $H$ be $v_{1},\dots,v_{n}$, sorted so that each $v_{i}$
has at most $d$ neighbors $v_{j}$ with $j<i$. We inductively pick an embedding
$\varphi:V(H)\to V(R)$, maintaining the property that
$\varphi(v_{1}),\dots,\varphi(v_{i})$ span a copy of $H[v_{1},\dots,v_{i}]$.
First, we let $\varphi(v_{1})$ be an arbitrary vertex of $R$. Suppose we’ve
defined $\varphi(v_{1}),\dots,\varphi(v_{i-1})$, and we wish to define
$\varphi(v_{i})$. Let $J$ be the set of $j<i$ with $v_{j}v_{i}\in E(H)$, so
that $\lvert J\rvert\leq d$. For every $j\in J$, there are at most $(N-n)/d$
non-neighbors of $\varphi(v_{j})$ in $R$, and thus at most $N-n$ vertices of
$R$ are non-adjacent to $\varphi(v_{j})$ for some $j\in J$. Thus, there are at
least $n$ vertices of $R$ that are adjacent to all $\\{\varphi(v_{j})\\}_{j\in
J}$, and fewer than $n$ of these vertices have been used in embedding
$v_{1},\dots,v_{i-1}$. So we pick any of the remaining candidate vertices as
$\varphi(v_{i})$, which maintains our inductive hypothesis. Continuing in this
manner until $i=n$, we find a copy of $H$ in $R$. ∎

We will use the following result of Erdős and Szemerédi [6]. It shows that
colorings which are not $\varepsilon$-balanced contain larger cliques than
what is implied by the Ramsey number alone.

######  Lemma 3.3 ([6, Theorem 2]).

There exists an absolute constant $a>0$ such that the following holds for all
$\varepsilon\in(0,\frac{1}{2}]$ and every positive integer $N$. Any two-
coloring of $E(K_{N})$ which is not $\varepsilon$-balanced contains a
monochromatic clique of order
$\frac{a}{\varepsilon\log\frac{1}{\varepsilon}}\log N$.

Finally, we will need the following well-known lower bound on the Ramsey
number of a graph of high degeneracy (see e.g. [8, Section 11, Remark 2]). We
provide the proof for completeness.

######  Lemma 3.4.

If $G$ is a graph with degeneracy $d\geq 1$, then $r(G)\geq{2^{d/2}}$.

###### Proof.

By the definition of degeneracy, there exists a subgraph $G_{0}\subseteq G$
with minimum degree at least $d$. Let $G_{0}$ have $k$ vertices, so that it
has at least $dk/2$ edges, and note that $k\geq 2$ since $d\geq 1$. Let
$N={2^{d/2}}$, and consider a uniformly random two-coloring of $E(K_{N})$. The
expected number of monochromatic copies of $G_{0}$ is at most

$k!\binom{N}{k}2^{1-dk/2}<N^{k}2^{1-dk/2}=2\left(\frac{N}{2^{d/2}}\right)^{k}=2.$

Thus, there exists a two-coloring of $E(K_{N})$ with fewer than $2$
monochromatic copies of $G_{0}$. By deleting one vertex, we obtain a coloring
on $N-1$ vertices with no monochromatic copies of $G_{0}$, and thus, no
monochromatic copies of $G$. This shows that $r(G)\geq(N-1)+1=N$, as claimed.
∎

We are now ready to prove Proposition 3.1.

###### Proof of Proposition 3.1.

Let $N=r(G)-1$, and fix a two-coloring of $E(K_{N})$ with no monochromatic
copy of $G$. Let $v$ be a vertex of $K_{N}$. Assume without loss of generality
that $v$ has at least $(N-1)/2$ red neighbors, and let $S$ be this red
neighborhood. Now consider the induced coloring on $S$. Let $w$ be a vertex of
maximum blue degree in this induced coloring, and let $T$ be the blue
neighborhood of $w$ in $S$. Then every vertex in $T$ is adjacent to $v$ in red
and to $w$ in blue, and thus $T$ cannot contain a monochromatic copy of $H$.
Therefore, $\lvert T\rvert\leq r(H)-1$. We now lower-bound $\lvert T\rvert$ in
two different ways.

First, we claim that $\lvert T\rvert>(\lvert S\rvert-n)/d$. Since $w$ is a
vertex of maximum blue degree, we see that if this is not the case, then every
vertex in $S$ has fewer than $(\lvert S\rvert-n)/d$ blue neighbors in $S$.
Applying Lemma 3.2 with $R$ being the red graph on $S$, we find that there is
a red copy of $H$ in $S$. Together with $v$, this yields a red copy of $G$, a
contradiction. This proves the claim, which implies that

$r(H)-1\geq\lvert T\rvert>\frac{\lvert
S\rvert-n}{d}\geq\frac{N-1}{2d}-\frac{n}{d}$

and thus

$N<2dr(H)-2d+2n+1\leq 2dr(H)+2n-1\leq 4dr(H)$

since $d\geq 1$ and since $n\leq r(H)$. Recalling that $N=r(G)-1$ yields (2).

Note that (3) follows from (1) if $d\leq 9$ by choosing $A$ sufficiently
large, so we henceforth assume $d\geq 10$. We now claim that $\lvert
T\rvert\geq\varepsilon(\lvert S\rvert-1)$, where
$\varepsilon=cd/(n\log\frac{n}{d})$, for some sufficiently small constant
$c>0$. If this is not the case, then every vertex in $S$ has blue degree less
than $\varepsilon(\lvert S\rvert-1)$, and thus the blue edge density in $S$ is
less than $\varepsilon$. So the induced coloring on $S$ is not
$\varepsilon$-balanced, and by Lemma 3.3, we may find in $S$ a monochromatic
clique of order $\frac{a}{\varepsilon\log\frac{1}{\varepsilon}}\log{\lvert
S\rvert}$. Note that, as $H\subseteq G$, the degeneracy of $G$ is at least
$d$, and therefore Lemma 3.4 implies that

$\lvert S\rvert\geq\frac{N-1}{2}=\frac{r(G)-2}{2}\geq\frac{2^{d/2}-2}{2}\geq
2^{d/3},$

by our assumption that $d\geq 10$. Note too that by choosing $c$ sufficiently
small, we can ensure that

$\varepsilon\log\frac{1}{\varepsilon}=\frac{cd}{n\log\frac{n}{d}}\cdot\left(\log\frac{n}{d}+\log\frac{1}{c}+\log\log\frac{n}{d}\right)\leq\frac{ad}{6n}.$

Therefore,

$\frac{a}{\varepsilon\log\frac{1}{\varepsilon}}\log{\lvert S\rvert}\geq
a\cdot\frac{6n}{ad}\cdot\frac{d}{3}=2n.$

This shows that $S$ contains a monochromatic clique of order $2n$, and thus a
copy of $G$, a contradiction. This proves the claim that $\lvert
T\rvert\geq\varepsilon(\lvert S\rvert-1)$, which implies that

$r(H)-1\geq\lvert T\rvert\geq\varepsilon(\lvert
S\rvert-1)\geq\frac{\varepsilon N}{4}$

and thus

$r(G)=N+1\leq\frac{4}{\varepsilon}r(H)=\left(A\frac{n}{d}\log\frac{n}{d}\right)r(H)$

for a constant $A=4/c>0$. ∎

##  4 Ramsey-balanced graphs

In this section we discuss Ramsey-balanced graphs and prove Proposition 1.4,
which says that Conjecture 1.1 is true for Ramsey-balanced graphs. As
discussed in the Introduction, this shows that there exists a sequence of
graphs $G_{n}$ such that in any Ramsey coloring for $G_{n}$, one of the color
classes has density $o(1)$.

For a vertex $v$ in a two-colored complete graph, we denote by
$N_{R}(v),N_{B}(v)$ the red and blue neighborhoods of $v$, respectively. The
only property we need of $\varepsilon$-balanced colorings is that in any
$\varepsilon$-balanced coloring, we can find vertices $v,w$ such that
${N_{R}(v)\cap N_{B}(w)}$ is large. Such a statement can be easily deduced
from [7, Lemma 2.1]; however, the following result, due to Kamčev and
Müyesser111This result is mentioned without proof in [9]. The proof given here
is due to Kamčev and Müyesser, and is included with their kind permission.,
gives a stronger quantitative bound.

######  Lemma 4.1 (Kamčev–Müyesser).

Let $0<\varepsilon\leq\frac{1}{2}$, and fix an $\varepsilon$-balanced coloring
of $E(K_{N})$ with colors red and blue. Then there exist $v,w\in V(K_{N})$
such that $\lvert N_{R}(v)\cap N_{B}(w)\rvert\geq\frac{\varepsilon}{4}(N-1)$.

In the course of the proof of Lemma 4.1, we will need the following simple
fact about convex functions, which can be viewed as a “reversed” form of
Jensen’s inequality. Although this result appears to be well-known, we were
not able to find a concise statement in the literature, and include the short
proof for a completeness.

######  Lemma 4.2 (Reverse Jensen inequality).

Let $f:[0,s]\to\mathbb{R}$ be a convex function. Let
$x_{1},\dots,x_{N}\in[0,s]$ be real numbers, and let $x=\sum_{i}x_{i}$. Then

$\sum_{i=1}^{N}f(x_{i})\leq\frac{Ns-x}{s}f(0)+\frac{x}{s}f(s).$

###### Proof.

The definition of convexity implies that

$f(x_{i})\leq\frac{s-x_{i}}{s}f(0)+\frac{x_{i}}{s}f(s)$

for every $1\leq i\leq N$. Summing this up over all $i$ gives the claimed
result. ∎

We are now ready to prove Lemma 4.1.

###### Proof of Lemma 4.1.

By swapping the roles of the colors if necessary, we may assume without loss
of generality that at least half the edges are colored blue. We may also
assume that exactly $\varepsilon\binom{N}{2}$ edges are red, and the remainder
are blue; if this is not the case, then we simply replace $\varepsilon$ by a
larger value, and obtain a stronger conclusion. Thus, the average red degree
is $\varepsilon(N-1)$, and the average blue degree is $(1-\varepsilon)(N-1)$.

Suppose first that there is some vertex $v$ with $\lvert
N_{R}(v)\rvert\geq\frac{3}{2}\varepsilon(N-1)$. Let $w$ be a vertex of maximum
blue degree, so that $\lvert N_{B}(w)\rvert\geq(1-\varepsilon)(N-1)$. Then by
the pigeonhole principle, we have that

$\lvert N_{R}(v)\cap N_{B}(w)\rvert\geq\frac{\varepsilon}{2}(N-1).$

Therefore we may assume that every vertex of $K_{N}$ has red degree at most
$\frac{3}{2}\varepsilon(N-1)$. Applying Lemma 4.2 with $f(y)=y^{2}$ and
$s=\frac{3}{2}\varepsilon(N-1)$, this implies that

$\sum_{u\in V(K_{N})}\lvert N_{R}(u)\rvert^{2}\leq\frac{\sum_{u}\lvert
N_{R}(u)\rvert}{\frac{3}{2}\varepsilon(N-1)}\left(\frac{3}{2}\varepsilon(N-1)\right)^{2}=\frac{2N}{3}\left(\frac{3}{2}\varepsilon(N-1)\right)^{2}\leq\frac{3}{4}\varepsilon
N(N-1)^{2},$

where the final inequality uses that $\varepsilon\leq\frac{1}{2}$. Let $X$
denote the number of copies of $K_{1,2}$ with one red and one blue edge. We
have that

$\displaystyle X$ $\displaystyle=\sum_{u\in V(K_{N})}\lvert
N_{R}(u)\rvert(N-1-\lvert N_{R}(u)\rvert)$ $\displaystyle=(N-1)\sum_{u\in
V(K_{N})}\lvert N_{R}(u)\rvert-\sum_{u\in V(K_{N})}\lvert N_{R}(u)\rvert^{2}$
$\displaystyle\geq(N-1)\cdot\varepsilon N(N-1)-\frac{3}{4}\varepsilon
N(N-1)^{2}$ $\displaystyle=\frac{\varepsilon}{4}N(N-1)^{2}.$

On the other hand, we have that

$X=\sum_{v,w\in V(K_{N})}\lvert N_{R}(v)\cap
N_{B}(w)\rvert=\sum_{\begin{subarray}{c}v,w\in V(K_{N})\\\ v\neq
w\end{subarray}}\lvert N_{R}(v)\cap N_{B}(w)\rvert,$

where the second equality is because $N_{R}(v)\cap N_{B}(v)=\varnothing$. This
implies that there exist $v,w$ such that

$\lvert N_{R}(v)\cap
N_{B}(w)\rvert\geq\frac{X}{N(N-1)}\geq\frac{\varepsilon}{4}(N-1).\qed$

With these preliminaries, Proposition 1.4 is an easy consequence.

###### Proof of Proposition 1.4.

Let $N=r(G)-1$, and fix an $\varepsilon$-balanced coloring of $E(K_{N})$ with
no monochromatic copy of $G$. Lemma 4.1 yields two vertices $v,w\in V(K_{N})$
with $\lvert N_{R}(v)\cap N_{B}(w)\rvert\geq\frac{\varepsilon}{4}(N-1)$. Let
$S=N_{R}(v)\cap N_{B}(w)$. We claim that $S$ contains no monochromatic copy of
$H$. Indeed, if there were some red copy of $H$ in $S$, then by adding $v$ to
it we would find a red copy of $G$; similarly, a blue copy of $H$ in $S$
yields a blue copy of $G$ by adding $w$. So we conclude that $\lvert
S\rvert\leq r(H)-1$, which implies that

$r(G)=N+1\leq\frac{4}{\varepsilon}\lvert
S\rvert+2\leq\frac{4}{\varepsilon}(r(H)-1)+2\leq\frac{4}{\varepsilon}r(H).\qed$

To conclude this section, we remark that the results of Section 3 can be more
or less equivalently phrased in terms of Ramsey-balanced graphs. Namely, the
proof of Proposition 3.1 can be used to show that if $H$ is an $n$-vertex
graph of degeneracy $d\geq 1$, then $H$ is both $\Omega(\frac{1}{d})$-Ramsey-
balanced and $\Omega(d/(n\log\frac{n}{d}))$-Ramsey-balanced. Balancing these
two bounds and plugging them into Proposition 1.4 yields Theorem 1.3.

##  5 More colors

For an integer $q\geq 2$, let $r(H;q)$ denote the $q$-color Ramsey number of
$H$, that is, the least $N$ so that every $q$-coloring of $E(K_{N})$ contains
a monochromatic copy of $H$. When the number of colors is greater than $2$, we
can prove a stronger version of Theorem 1.2, showing a polynomial gap between
$r(G)$ and $r(H)$.

######  Theorem 5.1.

Fix an integer $q\geq 3$. For all sufficiently large $n$, there exists an
$(n+1)$-vertex graph $G$ with Ramsey number $r(G;q)>n^{1+\frac{3q-5}{8q\log
q}-o(1)}$. However, there is a vertex of $G$ whose deletion yields a graph $H$
with Ramsey number $r(H;q)=n$. In particular, for sufficiently large $n$,

$r(G;q)\geq(r(H;q))^{1+\alpha}$

for some fixed $\alpha>0$ depending only on $q$.

###### Proof.

Fix positive integers $k$ and $n\geq q^{qk}$, and let $H_{k,n}$ and $G_{k,n}$
be the graphs defined in Section 2. As in the proof of Lemma 2.1, it is easy
to check that $r(H_{k,n};q)=n$, by using the well-known upper bound
$r(K_{k};q)\leq q^{qk}$.

For the lower bound on $r(G_{k,n};q)$, let $m=r(K_{k+1};q-1)-1$ and $N=mn$. By
the definition of $r(K_{k+1};q-1)$, there exists a coloring
$\chi:E(K_{m})\to[q-1]$ with no monochromatic copy of $K_{k+1}$. We partition
$V(K_{N})$ into $m$ blocks $S_{1},\dots,S_{m}$, each comprising $n$ vertices.
For all $i\neq j$, we color all edges between $S_{i}$ and $S_{j}$ by the color
$\chi(i,j)\in[q-1]$, and we color all edges inside some part with color $q$.
There is no copy of $K_{k+1}$ in any of the first $q-1$ colors, and thus no
copy of $G_{k,n}$ in any of these colors. Additionally, $G_{k,n}$ is connected
and has $n+1$ vertices, so there is no copy of $G_{k,n}$ in the $q$th color
either. This shows that $r(G_{k,n};q)>N$.

To conclude, we need a lower bound on $r(K_{k+1};q-1)$ that grows
exponentially in $q$. Such a bound was first proved by Lefmann [10], with
recent improvements by Conlon–Ferber [2], the author [12], and Sawin [11]. For
concreteness, we quote the bound from [12], which says that for fixed $q\geq
3$ and $k\to\infty$,

$r(K_{k+1};q-1)>2^{\frac{3q-5}{8}k-o(k)}.$

Letting $k=\lfloor\log n/(q\log q)\rfloor$, we conclude that

$r(G_{k,n};q)>(r(K_{k+1};q-1)-1)n\geq n^{1+\frac{3q-5}{8q\log q}-o(1)}.\qed$

We remark that one can get a slightly stronger bound on $\alpha$ for $q\geq 4$
by using the main result from [11], which says that

$r(K_{k+1};q-1)>2^{(0.38796(q-3)+\frac{1}{2})k-o(k)}.$

However, as the value of $\alpha$ we obtain is likely far from optimal in any
case, we chose to use the somewhat simpler expression from [12].

One strange feature of Theorem 5.1 is that the bound on $\alpha$ actually
deteriorates as $q$ gets larger, since the expression $(3q-5)/(8q\log q)$
tends to $0$ as $q\to\infty$. However, this is really a consequence of our
poor understanding of multicolor Ramsey numbers. Indeed, the best known bounds
on $r(K_{k};q)$ are

${cqk}\leq\log r(K_{k};q)\leq{qk}\log q$

for some constant $c>0$. The logarithmic gap between the lower and upper
bounds here appears as the factor of $\log q$ in the denominator of $\alpha$.
As such, we expect that a better understanding of the asymptotics of
$r(K_{k};q)$ would lead to a bound on $\alpha$ which does not deteriorate as
$q\to\infty$.

While the lower bound of Theorem 5.1 is noticeably stronger than that of
Theorem 1.2—we obtain a polynomial rather than barely super-linear bound when
$q\geq 3$—unfortunately, the upper bounds in the multicolor case are much
worse. Indeed, mimicking the proof222The key observation is that, in a
$q$-coloring of $K_{N}$, we may assume that the density of every color is at
least $1/r(G;q-1)$, as otherwise we may apply Turán’s theorem to find a set of
$r(G;q-1)$ vertices colored by only $q-1$ colors, which then contains a
monochromatic copy of $G$. Applying this observation $q$ times in nested
common neighborhoods, we can find a set of $N/r(G;q-1)^{q}$ vertices, which is
complete in each of the $q$ colors to some other vertex. Hence
$r(G;q)/r(G;q-1)^{q}<r(H;q)$, which implies the claimed bound since
$r(G;q-1)^{q}\leq 2^{c_{q}n}$. of (1), one obtains that if $G$ is an
$n$-vertex graph and $H$ is obtained from $G$ by deleting a single vertex,
then

$r(G;q)\leq 2^{c_{q}n}r(H;q)$

for an absolute constant $c_{q}>0$ depending only on $q$, for any fixed $q\geq
3$. In other words, in contrast to the $O(n)$ bound on $r(G)/r(H)$ in (1), in
the case of $q\geq 3$, the bound on $r(G;q)/r(H;q)$ is exponential in $n$.
Given that $r(G;q)$ is itself at most exponential in $n$, this bound is
extremely weak, and it is not clear how to meaningfully improve it.

##  6 Concluding remarks

Although Theorem 1.2 disproves the original conjecture of Conlon, Fox, and
Sudakov, there remain a number of other interesting open problems.

The most natural question is to close the gap between Theorems 1.2 and 1.3.
Formally, we can define

$f(n)\coloneqq\max\left\\{\frac{r(G)}{r(G\setminus\\{v\\})}:G\text{ is an
}(n+1)\text{-vertex graph and }v\in V(G)\right\\},$

which measures how much the deletion of a single vertex can affect the Ramsey
number of an $(n+1)$-vertex graph. Then Theorems 1.2 and 1.3 imply that
$\Omega(\log n)\leq f(n)\leq O(\sqrt{n\log n})$. It would be interesting to
improve either bound; concretely, we make the following conjecture.

######  Conjecture 6.1.

There is some $c>0$ so that $f(n)\geq n^{c}$ for all sufficiently large $n$.

It would also be very interesting to improve the corresponding gap for
multicolor Ramsey numbers; as discussed in Section 5, the bounds for $q\geq 3$
are very far apart.

Additionally, the structure of the counterexamples to Conjecture 1.1 is
somewhat dissatisfying, since $H_{k,n}$ consists of a small clique and an
enormous number of isolated vertices. One can avoid using isolated vertices
(for example, essentially the same proof333The only material difference is
that now, one needs to replace Lemma 2.1 by the weaker bound
$r(H_{n,k}^{\prime})\leq 3n$ (assuming $n\geq 4^{k}$). This bound is proved by
repeatedly applying the Erdős–Szekeres bound to find disjoint monochromatic
$K_{k}$, continuing as long as at least $n$ vertices remain. One can thus find
$2n/k$ disjoint monochromatic $K_{k}$, half of which must have the same color,
yielding a monochromatic $H_{n,k}^{\prime}$. goes through if one lets
$H_{k,n}^{\prime}$ be the disjoint union of $n/k$ copies of $K_{k}$), but
there is a limit to how far one can push this using the techniques of this
paper. Namely, we do not know how to prove a result like Theorem 1.2 unless
the graph $H$ consists of a large number of small connected components. In
particular, it seems that the following conjecture would require new ideas.

######  Conjecture 6.2.

There exists a graph $G$ and a vertex $v\in V(G)$ such that
$H=G\setminus\\{v\\}$ is connected, and $r(G)=\omega(r(H))$.

It would also be interesting to study an “average-case” version of this
question, rather than the “worst-case” version considered in Conjectures 1.1,
1.2 and 1.3. For a graph $G$, its _deck_ $D(G)$ consists of all vertex-deleted
induced subgraphs of $G$ (counted with multiplicity). Conjecture 1.1 asks
whether $r(H)=\Omega(r(G))$ for all $H\in D(G)$, and Theorem 1.2 says that
this is false. However, rather than _all_ , one can ask for _most_.

######  Conjecture 6.3.

There exists an absolute constant $c>0$ so that for all graphs $G$, at least
$\frac{1}{2}\lvert D(G)\rvert$ of the graphs $H\in D(G)$ satisfy $r(H)\geq
c\cdot r(G)$.

In fact, it seems possible that $r(H)\geq c\cdot r(G)$ holds for all but
$o(\lvert D(G)\rvert)$ of the graphs in $D(G)$. If this holds with appropriate
control on the little-$o$, then it suffices for the original application of
Conlon, Fox, and Sudakov; namely, such a result would show that $\log
r(G(n,p))$ is concentrated in an interval of length $O(\sqrt{n})$, by
mimicking the proof of [3, Theorem 5.6].

Another open problem concerns unbalanced colorings. Recall that the
Erdős–Szemerédi theorem, Lemma 3.3, says that unbalanced colorings contain
much larger monochromatic cliques than what is implied by the Ramsey number
$r(K_{k})$ alone. We used this in the proof of (3) in Proposition 3.1, where
we found a monochromatic copy of $G$ by finding a sufficiently large
monochromatic clique. This suggests a technique for strengthening Proposition
1.4, which is interesting in its own right: for graphs other than cliques, can
one use the assumption of an unbalanced coloring to prove stronger Ramsey
bounds?

Finally, rather than asking about vertex deletion, one could ask about edge
deletion: if $H$ is obtained from $G$ by deleting a single edge, how large can
$r(G)/r(H)$ be? It does not seem as though the techniques of Section 2 can be
used to construct examples where $r(G)/r(H)$ is super-constant, simply because
the deletion of a single edge cannot split a connected graph into more than
two connected components. In fact, we conjecture that there is no case where
this ratio is super-constant.

######  Conjecture 6.4.

Let $G$ be a graph, and let $H$ be obtained from $G$ by deleting a single
edge. Then

$r(H)\geq c\cdot r(G)$

for some absolute constant $c>0$.

### Acknowledgments.

I am indebted to Jacob Fox for many valuable discussions about this paper, and
especially for his help with the proof of Theorem 1.3. I would also like to
thank David Conlon and the anonymous referees for many helpful comments on
earlier drafts of this paper. Finally, I would like to thank Mehtaab Sawhney
for suggesting the particularly short proof of Lemma 4.2, and am grateful to
Nina Kamčev and Alp Müyesser for their permission to include their proof of
Lemma 4.1.

## References

  * [1] Y. Caro, A. Hansberg, and A. Montejano, Unavoidable chromatic patterns in 2-colorings of the complete graph, _J. Graph Theory_ 97 (2021), 123–147.
  * [2] D. Conlon and A. Ferber, Lower bounds for multicolor Ramsey numbers, _Adv. Math._ 378 (2021), Paper No. 107528, 5pp.
  * [3] D. Conlon, J. Fox, and B. Sudakov, Short proofs of some extremal results III, _Random Structures Algorithms_ 57 (2020), 958–982.
  * [4] J. Cutler and B. Montágh, Unavoidable subgraphs of colored graphs, _Discrete Math._ 308 (2008), 4396–4413.
  * [5] P. Erdős and G. Szekeres, A combinatorial problem in geometry, _Compositio Math._ 2 (1935), 463–470.
  * [6] P. Erdős and A. Szemerédi, On a Ramsey type theorem, _Period. Math. Hungar._ 2 (1972), 295–299.
  * [7] J. Fox and B. Sudakov, Unavoidable patterns, _J. Combin. Theory Ser. A_ 115 (2008), 1561–1569.
  * [8] J. Fox and B. Sudakov, Density theorems for bipartite graphs and related Ramsey-type results, _Combinatorica_ 29 (2009), 153–196.
  * [9] N. Kamčev and A. Müyesser, Unavoidable patterns in locally balanced colourings, _Combin. Probab. Comput._ 32 (2023), 796–808.
  * [10] H. Lefmann, A note on Ramsey numbers, _Studia Sci. Math. Hungar._ 22 (1987), 445–446.
  * [11] W. Sawin, An improved lower bound for multicolor Ramsey numbers and a problem of Erdős, _J. Combin. Theory Ser. A_ 188 (2022), Paper No. 105579, 11pp.
  * [12] Y. Wigderson, An improved lower bound on multicolor Ramsey numbers, _Proc. Amer. Math. Soc._ 149 (2021), 2371–2374.


$\omega=\mathrm{St}(\bar{\Delta}_{1})\times D_{\bar{\Delta}_{1}}(\pi)$. Let
$\bar{\Delta}_{1}=\nu^{-1/2}\Delta_{1}$.

By Theorem 8.3 and Definition 8.1, we have

$\mathfrak{mx}(\pi^{\prime},\Delta_{1})=\emptyset,\mbox{ and
}\mathfrak{mx}^{L}(\pi,\Delta_{2})=\emptyset.$

We first check that

(10.9) $\displaystyle m(\omega,\pi^{\prime})=1.$

To this end, we use the filtration on $\mathrm{St}(\bar{\Delta}_{1})\times
D_{\bar{\Delta}_{1}}(\pi)$ in [Ch22, Proposition 5.13]: (set
$p=n(D_{\bar{\Delta_{1}}}(\pi))$)

$\mathrm{St}(\bar{\Delta}_{1})^{[0]}\times(D_{\bar{\Delta}_{1}}(\pi)|_{G_{p-1}}),$
$\mathrm{St}(\bar{\Delta}_{1})^{[1]}\times(D_{\bar{\Delta}_{1}}(\pi)\otimes\zeta_{F}),$
$\mathrm{St}(\bar{\Delta}_{1})^{[k]}\times\mathrm{RS}_{k-2}(D_{\bar{\Delta}_{1}}(\pi))\quad\mbox{for
$k\geq 2$}.$

Then a direct computation on geometric lemma gives that the only layer the can
contribute a non-zero Hom is the bottom one. This gives that

$m(D_{\bar{\Delta}_{1}}(\pi),\pi^{\prime})\geq m(\pi,\pi^{\prime})$

On the other hand, a similar argument (see also proof of [Ch22, Lemma 4.4])
gives that

$m(\sigma\times
D_{\bar{\Delta}_{1}}(\pi),\pi^{\prime})=m(D_{\bar{\Delta}_{1}}(\pi),\pi^{\prime})$

for some cuspidal representation $\sigma$ good to $\pi$ and $\nu^{-1/2}\tau$.
Let $\lambda=\sigma\times D_{\bar{\Delta}_{1}}(\pi)$. The former one has at
most one by [AGRS10] (also see [Ch23]). In order to show that the multiplicity
is precisely one, by Lemmas 10.2 and 10.3,

$\mathrm{Ext}^{j}_{G_{n-i}}(\omega^{[i]},{}^{(i-1)}\pi^{\prime})=0$

for all $j$ and $i<i^{*}$. Thus, a standard long exact sequence argument gives
that

(10.10)
$\displaystyle\mathrm{Hom}_{G_{n}}(\omega_{i-1},\pi^{\prime})\cong\mathrm{Hom}_{G_{n}}(\omega,\pi^{\prime}),$

where
$0=\omega_{n+1}\subset\omega_{n}\subset\ldots\subset\omega_{1}\subset\omega_{0}=\omega$
is the Bernstein-Zelevinsky filtration of $\omega$. Now,

$\mathrm{Hom}_{G_{n}}(\omega_{i-1}/\omega_{i},\pi^{\prime})\cong\mathrm{Hom}_{G_{n+1-i}}(\omega^{[i]},{}^{(i-1)}\pi^{\prime})\cong\mathrm{Hom}_{G_{n+1-i}}(D_{\bar{\Delta}_{1}}(\pi),{}^{(i-1)}\pi^{\prime}),$

where the last isomorphism follows from using comparison of cuspidal support
to pick the indecomposable component in $\omega^{[i]}$ for contributing the
Hom. Since ${}^{(i-1)}\pi^{\prime}$ has $D^{L}_{\Delta_{2}}(\pi^{\prime})\cong
D_{\Delta_{1}}^{R}(\nu^{1/2}\pi)$ as the submodule, the Hom space is non-zero
as desired. Thus we have (10.9).

We secondly check that

(10.11) $\displaystyle m(\pi,\tau)=1.$

We shall turn into the first case and then one can apply similar argument on
that. By taking a dual restriction (see [Ch22, Proposition 4.1]), we have:

$m(\pi,\tau)=m(\sigma^{\prime}\times\tau^{\vee},\pi{}^{\vee})$

for some $\sigma^{\prime}\in\mathrm{Irr}(G_{2})$ good to
$\nu^{1/2}\pi{}^{\vee}$ and $\tau^{\vee}$. Similar argument using Bernstein-
Zelevinsky filtration gives (10.11).

We finally check that:

(10.12) $\displaystyle m(\omega,\tau)=1.$

By above two cases, it suffices to show that

$m(\omega,\tau)\leq 1.$

One again has a filtration on $\omega|_{G_{n}}$ as in showing (10.9). Again
using geometric lemma with the given hypothesis for the segments in the
proposition, we have that the only bottom layer can contribute the branching
law. Thus we again have

$m(\omega,\tau)\leq m(D_{\Delta_{1}}(\pi),\tau).$

Using a duality as in (10.11) then gives that:

$m(D_{\Delta_{1}}(\pi),D^{L}_{\Delta_{2}}(\pi^{\prime}))\geq
m(D_{\Delta_{1}}(\pi),\tau).$

The former one is at most one by [AGRS10], and combining above equations, we
have:

$m(\omega,\tau)\leq 1$

as desired.

We now apply Lemma 10.1 and (10.9), (10.11), (10.12) to obtain the
proposition. ∎

######  Proposition 10.5.

Proposition 10.4 holds without the assumption that
$\mathfrak{mx}(\nu^{1/2}\pi,\Delta_{1})=\Delta_{1}$.

###### Proof.

We only give a sketch of the proof (since general case will be proved in
[Ch22+c] in more detail). Let $i^{*}=l_{a}(\Delta_{1})$. When $i^{*}=1$, it
follows more easily from the Bernstein-Zelevinsky filtration (because the
layer contributing the branching laws comes from the first layer and one does
not have to consider homological problems). Let
$\bar{\Delta}_{1}=\nu^{-1/2}\Delta_{1}$. Let
$\bar{\mathfrak{p}}_{1}=\mathfrak{mx}(\pi,\bar{\Delta}_{1})$ and let
$\mathfrak{p}_{1}=\nu^{1/2}\bar{\mathfrak{p}}_{1}$. Let
$\omega=\mathrm{St}(\bar{\mathfrak{p}}_{1})\times
D_{\bar{\mathfrak{p}}_{1}}(\pi)$. Let $\pi^{\prime}=I_{\Delta_{2}}\circ
D_{\Delta_{1}}(\nu^{1/2}\cdot\pi)$ and let $\tau=\mathrm{St}(\Delta_{2})\times
D^{L}_{\Delta_{2}}(\pi^{\prime})$. Then we let $\widetilde{\omega}$ (resp.
$\widetilde{\pi}$) be the quotient of $\omega$ (resp. $\pi$) modulo out the
$k$-th Bernstein-Zelevinsky layers greater than for all $k>i^{*}$. By
analysing the BZ layers and using the Frobenius reciprocity, the conditions
that $\mathfrak{mx}^{L}(D_{\Delta_{1}}(\nu^{1/2}\pi),\Delta_{2})=\emptyset$
and

$\mathfrak{mx}(D^{L}_{\Delta_{2}}(\pi^{\prime}),\Delta_{1})=\mathfrak{mx}(D_{\Delta_{1}}(\pi),\Delta_{1})=\mathfrak{p}_{1}-\Delta_{1}$

implies that

$m(\widetilde{\omega},\tau)\leq 1$

(and so $m(\widetilde{\pi},\tau)\leq 1$). To prove the inequality is an
equality, we consider the quotient of $\widetilde{\omega}$ from

$\mathrm{St}(\mathfrak{p}_{1}-\Delta_{1})\times(D_{\mathfrak{p}_{1}-\Delta_{1}}(\pi)|_{G_{m-1}})$

(see [Ch22, Proposition 5.13]), where
$m=n(D_{\mathfrak{p}_{1}-\Delta_{1}}(\pi))$. Then, Proposition 10.4 implies
that such quotient contributes a quotient
$\mathrm{St}(\mathfrak{p}_{1}-\Delta_{1})\times I_{\Delta_{2}}\circ
D_{\mathfrak{p}_{1}}(\nu^{1/2}\pi)$ and so contributes a quotient
$I_{\mathfrak{p}_{1}-\Delta}\circ I_{\Delta_{2}}\circ
D_{\mathfrak{p}_{1}}(\nu^{1/2}\cdot\pi)$, which is isomorphic to
$\pi^{\prime}$ by using Corollary 8.4 and Proposition 5.1 (multiple times).
Such quotient also comes from the $i^{*}$-BZ layer. This proves the equality,
and indeed also proves that

$m(\widetilde{\omega},\pi^{\prime})=1.$

It remains to prove that

$\mathrm{dim}~{}\mathrm{Hom}_{G_{n}}(\widetilde{\pi},\tau)\neq 0.$

Now one proceeds as in checking (10.9) in Proposition 10.4 (while the current
one is in a certain dual form), and shows that the $i^{*}$-th BZ layer of
$\pi$ contributes the branching law for $\mathrm{Hom}_{G_{n}}(\pi,\tau)$ (by a
higher Ext-vanishing argument using Lemma 10.2 and the condition that
$\mathfrak{mx}^{L}(\Delta_{2},\nu^{1/2}\cdot\pi)=\emptyset$). Hence, a non-
zero element in $\mathrm{Hom}_{G_{n}}(\pi,\tau)$ descends to a non-zero
element in $\mathrm{Hom}_{G_{n}}(\widetilde{\pi},\tau)$.

∎

######  Remark 10.6.

Removing the conditions (1)-(2) in Proposition 10.4 is technical, which is
used in showing (10.12). This can be resolved by switching to the ’left’
Bernstein-Zelevinsky filtration, but for that, we need to consider sequences
of derivatives developed in [Ch22+] and their integral version.

######  Remark 10.7.

The dual restriction in [Ch22, Proposition 4.1] asserts that:

$\mathrm{Hom}_{G_{n+1}}(\sigma\times\pi^{\prime},\pi)\neq 0$

for some cuspidal representation $\sigma$ of $G_{2}$ good to $\nu^{1/2}\pi$
and $\pi^{\prime}$, and this should match with the duality in Section 6, also
see next section.

###  10.4. Generalized Gan-Gross-Prasad relevant pairs

Gan-Gross-Prasad [GGP20] introduces a notion of relevant pairs for Arthur type
representations, governing their branching law for general linear groups
[Ch22]. Such notion can be reformulated in terms of the Bernstein-Zelevinsky
derivatives, see [Ch22]. This hints some connections with derivatives (also
see [Ch22+]).

We first extend the notion of strongly commutative triples from segments to
multisegments. For two segments $\Delta$ and $\Delta^{\prime}$, we write
$\Delta>\Delta^{\prime}$ if $\Delta$ and $\Delta^{\prime}$ are linked and
$a(\Delta)\cong\nu^{c}\cdot a(\Delta^{\prime})$ for some $c>0$.

######  Definition 10.8.

(c.f. Propositions 5.5 and 5.6) Let $\mathfrak{m},\mathfrak{n}$ be
multisegments. We impose an ordering on
$\mathfrak{m}=\left\\{\Delta_{1},\ldots,\Delta_{r}\right\\}$ (resp.
$\mathfrak{n}=\left\\{\Delta_{1}^{\prime},\ldots,\Delta_{s}^{\prime}\right\\}$)
given by (c.f. [Ze80, Theorem 6.1]): for any $i<j$,

$\Delta_{i}\not>\Delta_{j}\quad(\mbox{resp.}\Delta_{i}^{\prime}\not>\Delta_{j}^{\prime}).$

Let $\mathfrak{m}_{i}=\left\\{\Delta_{1},\ldots,\Delta_{i}\right\\}$ and let
$\mathfrak{n}_{j}=\left\\{\Delta_{1}^{\prime},\ldots,\Delta_{j}^{\prime}\right\\}$.
Let $\mathfrak{m},\mathfrak{n}\in\mathrm{Mult}$. Let $\pi\in\mathrm{Irr}$. We
say that $(\mathfrak{m},\mathfrak{n},\pi)$ is a strongly RdLi-commutative
triple if for any $1\leq i\leq r$ and $1\leq j\leq s$,
$(\mathrm{St}(\Delta_{i}),\mathrm{St}(\Delta_{j}),I_{\mathfrak{n}_{j-1}}\circ
D_{\mathfrak{m}_{i-1}}(\pi))$ is strongly RdLi-commutative in the sense of
Definition 1.1. Here
$D_{\mathfrak{m}_{i}}(\lambda)=D_{\Delta_{i}}\circ\ldots\circ
D_{\Delta_{1}}(\lambda)$ and
$I_{\mathfrak{n}_{j}}(\lambda)=I_{\Delta^{\prime}_{j}}\circ\ldots\circ
I_{\Delta_{1}^{\prime}}(\lambda)$.

We can now define a notion of generalized relevant pairs.

######  Definition 10.9.

For $\pi\in\mathrm{Irr}$ and $\pi^{\prime}\in\mathrm{Irr}$, we say that
$(\pi,\pi^{\prime})$ is (generalized) relevant if there exists multisegments
$\mathfrak{m},\mathfrak{n}$ such that
$(\mathfrak{m},\mathfrak{n},\nu^{1/2}\pi)$ is a strongly RdLi-commutative
triple and

$D^{R}_{\mathfrak{m}}(\nu^{1/2}\cdot\pi)\cong
D^{L}_{\mathfrak{n}}(\pi^{\prime}).$

Such notion is expected to govern the quotient branching law, dealt with in
[Ch22+c]. Proposition 10.5 gives a baby example.

## References

  * [AL22] A. Aizenbud, E. Lapid, A binary operation on irreducible components of Lusztig’s nilpotent varieties II: Definition and properties, to appear in Pure and Applied Mathematics Quarterly.
  * [AGRS10] A. Aizenbud, D. Gourevitch, S. Rallis and G. Schiffmann, Multiplicity one theorems, Ann. of Math. (2) 172 (2010), no. 2, 1407-1434.
  * [Ar96] S. Ariki, On the decomposition numbers of the Hecke algebra of type $G(m,1,n)$, J. Math. Kyoto Univ. 36 (1996), 789-808. 1992\. Lectures by Joseph Bernstein. Written by Karl E. Rumelhart.
  * [BZ76] I. N. Bernstein and A. V. Zelevinsky, Representations of the group $\mathrm{GL}(n,F)$, where $F$ is a non-archimedean local field, Russian Math. Surveys 31:3 (1976), 1-68.
  * [BZ77] I. N. Bernstein and A. V. Zelevinsky, Induced representations of reductive p-adic groups, I, Ann. Sci. Ecole Norm. Sup. 10 (1977), 441-472.
  * [Bo91] A. Borel, Linear Algebraic Groups (2nd ed.), New York: Springer-Verlag, GTM 1991.
  * [Ch21] K.Y. Chan, Homological branching law for $(\mathrm{GL}_{n+1}(F),\mathrm{GL}_{n}(F))$: projectivity and indecomposability, Invent. math. (2021), doi.org/10.1007/s00222-021-01033-5
  * [Ch22] K.Y. Chan, Restriction for general linear groups: The local non-tempered Gan-Gross-Prasad conjecture (non-Archimedean case), Journal für die reine und angewandte Mathematik (Crelles Journal), vol. 2022, no. 783, doi.org/10.1515/crelle-2021-0066
  * [Ch23] K.Y. Chan, Ext-multiplicity theorem for standard representations of $(\mathrm{GL}_{n+1},\mathrm{GL}_{n})$, arXiv:2104.11528, Math. Z. 303, 45 (2023). https://doi.org/10.1007/s00209-022-03198-y
  * [Ch22+] K.Y. Chan, Construction of simple quotients of Bernstein-Zelevinsky derivatives and highest derivative multisegments, arXiv:2111.13286
  * [Ch22+b] K.Y. Chan, On the product functor on the inner forms of general linear group over a non-Archimedean local field, arXiv:2206.10928
  * [Ch22+c] K.Y. Chan, Quotient branching law for $p$-adic $(\mathrm{GL}_{n+1},\mathrm{GL}_{n})$ I: generalized Gan-Gross-Prasad relevant pairs, arXivï¼š2212.05919 (2022)
  * [CS21] K.Y. Chan and G. Savin, A vanishing Ext-branching theorem for $(\mathrm{GL}_{n+1}(F),\mathrm{GL}_{n}(F))$, Duke Math Journal, 2021, 170 (10), 2237-2261. https://doi.org/10.1215/00127094-2021-0028
  * [CP96] V. Chari and A. Pressley, Quantum affine algebras and affine Hecke algebras, Pacific J. Math. 174 (1996), no. 2, 295-326.
  * [CR08] J. Chuang, R. Rouquier, Derived Equivalences for Symmetric Groups and $sl_{2}$-Categorification, Annals of Mathematics, 245-298 from Volume 167 (2008), 10.4007/annals.2008.167.245
  * [De77] Deodhar, V.V. Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function. Invent Math 39, 187-198 (1977). https://doi.org/10.1007/BF01390109
  * [Fa06] M. Fayers, Weights of multipartitions and representations of Ariki-Koike algebras, Advances in Mathematics, Volume 206, Issue 1, 2006, Pages 112-144, doi.org/10.1016/j.aim.2005.07.017.
  * [GGP12] W.T. Gan, B.H. Gross, and D. Prasad, Symplectic local root numbers, central critical L values, and restriction problems in the representation theory of classical groups. Sur les conjectures de Gross et Prasad. I., Asterisque No. 346 (2012), 1-109.
  * [GGP20] W.T. Gan, B.H. Gross, and D. Prasad, Branching laws for classical groups: the non-tempered case, Compositio Mathematica, 156(11) (2020), 2298-2367. doi:10.1112/S0010437X20007496
  * [GS05] Christof Geiss and Jan Schröer, Extension-orthogonal components of preprojective varieties, Trans. Amer. Math. Soc. 357 (2005), no. 5, 1953-1962.
  * [Ja07] C. Jantzen, Jacquet modules of $p$-adic general linear groups, Represent. Theory 11 (2007), 45-83 https://doi.org/10/1090/S1088-4165-0700316-0
  * [KKKO15] Seok-Jin Kang, Masaki Kashiwara, Myungho Kim and Se-jin Oh, Simplicity of heads and socles of tensor products, Compos. Math. 151 (2015), no. 2, 377-396.
  * [KL09] M. Khovanov and A. D. Lauda; A diagrammatic approach to categorification of quantum groups, I, Represent. Theory, 13 (2009), 309-347.
  * [LM14] E. Lapid and A. Mínguez. On a determinantal formula of Tadić. Amer. J. Math. 136 (2014): 111-142.
  * [LM16] E. Lapid, A. Mínguez, On parabolic induction on inner forms of the general linear group over a non-Archimedean local field, Sel. Math. New Ser. (2016) 22, 2347-2400. Doi.org/10.1007/s00029-016-0281-7
  * [LM19] E. Lapid, A. Mínguez, Geometric conditions for $\square$-irreducibility of certain representations of the general linear group over a non-archimedean local field, Advances in Mathematics Volume 339 (2018), 113-190, 10.1016/j.aim.2018.09.027
  * [LM22] E. Lapid, A. Mínguez, A binary operation on irreducible components of Lusztig’s nilpotent varieties II: applications and conjectures for representations of GLn over a non-archimedean local field, to appear in Pure and Applied Mathematics Quarterly.
  * [Le03] B. Leclerc, Imaginary vectors in the dual canonical basis of $U_{q}(n)$. Transformation Groups 8, 95-104 (2003). https://doi.org/10.1007/BF03326301
  * [LLT96] Lascoux, A., Leclerc, B. and Thibon, JY. Hecke algebras at roots of unity and crystal bases of quantum affine algebras. Commun.Math. Phys. 181, 205-263 (1996), doi.org/10.1007/BF02101678
  * [MW86] C. Mœglin, J.-L. Waldspurger, Sur l’involution de Zelevinski. J. Reine Angew. Math. 372, 136-177 (1986)
  * [Mi09] A. Mínguez, Surl’irréducitibilité d’une induite parabolique, 2009, no. 629, Crelle’s Journal, https://doi.org/10.1515/CRELLE.2009.028
  * [MS14] Alberto Mínguez, Vincent Sécherre, Représentations lisses modulo $l$ de GLm(D), Duke Mathematical Journal, Duke Math. J. 163(4), 795-887, DOI: 10.1215/00127094-2430025
  * [MW12] C. Mœglin and J.-L. Waldspurger, La conjecture locale de Gross-Prasad pour les groupes speciaux orthogonaux: le cas general, Sur les conjectures de Gross et Prasad. II, Astersque. No. 247 (2012), 167-216.
  * [Sc00] O. Schiffmann, The Hall algebra of a cyclic quiver and canonical bases of Fock spaces, Internat. Math. Res. Notices 8 (2000), 413-440.
  * [Ta90] M. Tadić, Induced representations of GL (n, A) for p-adic division algebras A. Journal für die reine und angewandte Mathematik (Crelles Journal), vol. 1990, no. 405, 1990, pp. 48-77. https://doi.org/10.1515/crll.1990.405.48
  * [VV99] M. Varagnolo, E. Vasserot, On the decomposition matrices of the quantized Schur algeba, Duke Math. J., 100(2), 267-297, doi.org/10.1215/S0012-7094-99-10010-X
  * [Ze80] A. Zelevinsky, Induced representations of reductive p-adic groups II, Ann. Sci. Ecole Norm. Sup. 13 (1980), 154-210.