# The $(t-1)$-chromatic Ramsey number for paths

Matija Bucić Amir Khamseh

###### Abstract

The following relaxation of the classical problem of determining Ramsey number
of a fixed graph has first been proposed by Erdős, Hajnal and Rado over 50
years ago. Given a graph $G$ and an integer $t\geq 2$ determine the minimum
number $N$ such that in any $t$-coloured complete graph on $N$ vertices there
is a copy of $G$ using only edges of some $t-1$ colours. We determine the
answer precisely when $G$ is a path.1112010 Mathematics Subject
Classification: 05C55; 05D10. Keywords. Ramsey numbers, $(t-1)$-chromatic
Ramsey numbers, edge colouring.

##  1 Introduction

Ramsey theory refers to a large body of results which all roughly speaking say
that any sufficiently large structure must contain a well-organised
substructure. For example, the classical theorem of Ramsey from 1929 [35]
states that for any fixed graph $H$ in any $t$-edge colouring of a
sufficiently large complete graph we can find a monochromatic copy of $H$. The
$t$-colour Ramsey number of $H$, denoted $R^{t}(H)$, is defined as the
smallest order of a complete graph satisfying this property.

Despite a large amount of attention over the years, there are still very few
families of graphs for which the Ramsey numbers are known precisely. An early
example of an exact Ramsey result, due to Gerencser and Gyarfas from 1967
[16], determines $R^{2}(P_{n})=\lfloor 3n/2-1\rfloor,$ where $P_{n}$ denotes
the path with $n$ vertices. Already the $3$-colour case was already
substantially more difficult, Łuczak [32] determined $R^{3}(P_{n})$
asymptotically, which was subsequently strengthened to an exact result for
long enough paths by Gyárfás, Ruszinkó, Sárközy and Szemerédi [19]. For four
and more colours even the asymptotic result is still open, with best lower and
upper bounds being due to Yongqi, Yuansheng, Feng and Bingxi [36], and Knierim
and Su [30], respectively.

Over the years, many generalisations of Ramsey numbers have been considered
(the survey [11] contains many examples); In particular, determining the
generalised Ramsey number of a path in a variety of these more general
settings has often turned out to be a very interesting problem [1, 4, 5, 6, 7,
12, 22, 23, 31]. A particularly natural generalisation first considered by
Erdős, Hajnal and Rado in 1965 [13] asks the following. Given a graph $H$ and
integers $t\geq k\geq 1$ determine the minimum number $N$ such that in any
$t$-coloured complete graph on $N$ vertices there is a copy of $H$ whose edges
are coloured using at most $k$ different colours. Let us denote the answer to
this question by $R^{t}_{k}(H)$. Observe that the case $k=1$ recovers the
classical Ramsey problem and represents the most difficult instance of the
problem. On the other hand, the case $k=t-1$ is the first non-trivial one and
turns out to already be interesting. In particular, $R^{t}_{t-1}$ is referred
to as the $t-1$-chromatic Ramsey number and represents a natural first step
towards understanding the classical Ramsey numbers.

Erdős, Hajnal and Rado only considered the $(t-1)$-chromatic Ramsey numbers
for complete graphs. In this direction Erdős and Szemeredi [14] showed the
answer for the complete graph $K_{n}$ is exponential in $n$ and the main open
problem is to determine how the exponent behaves depending on the number of
colours. The best known general bounds here are due to Alon, Erdős, Gunderson
and Molloy [2].

First to explicitly ask the question of determining the $(t-1)$-chromatic
Ramsey number for non-complete graphs were Chung and Liu in 1978. This
question has been considered for a number of families of graphs over the years
[3, 8, 9, 10, 17, 18, 21, 24, 25, 26, 27, 28, 29]. In this paper we are
interested in the $(t-1)$-chromatic Ramsey number of a path. Since the case of
$t=2$ corresponds to the classical $2$-colour Ramsey problem, it is solved
completely by the result of Gerencser and Gyarfas [16]. For $3\leq t\leq 5$
the value of $R^{t}_{t-1}(P_{\ell})$ was determined in [33, 27, 26]. In this
paper we determine the answer precisely for any number of colours, answering a
question raised in [27].

###### Theorem 1.1

For $\ell,t\geq 2$ we have:

$R_{t-1}^{t}(P_{\ell})=\ell+\left\lfloor\frac{\ell-2}{2^{t}-2}\right\rfloor.$

An interesting aspect of this result is that the $(t-1)$-chromatic Ramsey
number of an even path matches that of the matching of the same order,
determined by Gyárfás, Sárközy and Selkow [20], so in particular it also
recovers this result.

We also determine the correct value in the so called “asymmetric” variant of
the problem where we seek paths of different lengths depending on which colour
they omit. This more general result plays a key role in our proof of Theorem
1.1.

##  2 Preliminaries

Let us first agree on some convention and terminology. If $G$ is a graph, $V$
will denote its vertex set and $E$ its edge set. The number of vertices of $G$
is denoted by $|G|$. $C_{i}$ denotes the cycle with $i$ vertices. A
$t$-colouring will always refer to a colouring of the edges of $G$ using $t$
colours, or in other words a partition of $E$ into $t$ classes. Typically we
use $[t]=\\{1,2,\ldots,t\\}$ as the set of colours.

Let us now extend the definition of $(t-1)$-chromatic Ramsey numbers, to the
asymmetric case. The $(t-1)$-chromatic Ramsey number, denoted by
$R_{t-1}^{t}(G_{1},G_{2},\ldots,G_{t})$, is defined to be the least number $n$
such that in any $t$-colouring of the complete graph $K_{n}$, for some $i$ we
can find a copy of $G_{i}$ whose edges do not use colour $i$. Since we will
focus on the case when each $G_{i}$ is a path let us also define
$p(\ell_{1}\ldots,\ell_{t})=R_{t-1}^{t}(P_{\ell_{1}},\ldots,P_{\ell_{t}}).$

Since in $2$-colours this precisely recovers the classical Ramsey numbers the
following is an immediate corollary of the result of Gerencser and Gyárfás
[16].

###### Theorem 2.1

If $2\leq\ell_{1}\leq\ell_{2}$, then
$p({\ell_{1}},{\ell_{2}})=\ell_{2}+\lfloor\ell_{1}/2\rfloor-1$.

The following proposition gives us, mostly trivial bounds which relate the
$t-1$-chromatic Ramsey numbers of graphs with respect to different number of
colours. It is a generalization of results from Chung and Liu [10].

###### Lemma 2.2

Let $2\leq\ell_{1},\ldots,\ell_{t}$. Then we have
$p(\ell_{1},\ldots,\ell_{t})\leq p(\ell_{1},\ldots,\ell_{t-1})$ and equality
holds if $\ell_{t}\geq p(\ell_{1},\ldots,\ell_{t-1})$.

Proof. Let $n=p(\ell_{1},\ldots,\ell_{t-1})$ and $c:E(K_{n})\rightarrow[t]$ be
a $t$-colouring of the edges of $K_{n}$. Define a new $(t-1)$-colouring
$c^{\prime}$ obtained by merging the colours $t-1$ and $t$. I.e.
$c^{\prime}(e)=i$ if $c(e)=i$, when $1\leq i\leq t-2$, and
$c^{\prime}(e)={t-1}$ if $c(e)=t-1$ or $c(e)=t$. By definition of $n$, in
$K_{n}$ coloured according to $c^{\prime}$ we can find a copy of
$P_{\ell_{i}}$ avoiding colour $i$ for some $i\leq t-1$. This $P_{i}$ also
avoids colour $i$ in colouring $c$. Hence $p(\ell_{1},\ldots,\ell_{t})\leq n$,
as required.

Now suppose that $\ell_{t}\geq p(\ell_{1},\ldots,\ell_{t-1})=n$. By
definition, there exists a colouring of $K_{n-1}$ with $t-1$ colours
$\\{1,\dots,t-1\\}$ such that $K_{n-1}$ does not contain $P_{\ell_{i}}$
avoiding colour $i$, for all $i:1\leq i\leq t-1$. One can view this as a
$t$-colouring (not using colour $t$) of $K_{n-1}$ and since $n-1<\ell_{t}$ we
are guaranteed there is no path of order $\ell_{t}$ so this colouring also
shows

$n\leq p(\ell_{1},\ldots,\ell_{t})\leq p(\ell_{1},\ldots,\ell_{t-1})=n,$

completing the proof.$\hfill\square$

We note that the above lemma does not require the sequence $\ell_{i}$ to be
sorted.

##  3 Proof of the main result

In this section we will prove the following result.

###### Theorem 3.1

Let $t\geq 3$ and
$2\leq\ell_{1}\leq\ell_{2}\leq\ldots\leq\ell_{t-1}\leq\ell_{t}$, then

$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})=\begin{cases}\left\lfloor\frac{\ell_{1}+2\ell_{2}+\ldots+2^{t-1}\ell_{t}-2}{2^{t}-2}\right\rfloor&\text{if
}\quad\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})\\\
p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})&\text{else.}\end{cases}$

Given this result Theorem 1.1 follows immediately by choosing each
$\ell_{j}=\ell$.

Before proceeding to the proof, we introduce some convention and notation.
Until further notice we suppose that
$2\leq\ell_{1}\leq\ell_{2}\leq\ldots\leq\ell_{t-1}\leq\ell_{t}$. For $2\leq
k\leq t$, we define

$s(\ell_{1},\ldots,\ell_{k}):=\left\lfloor\frac{\ell_{1}+2\ell_{2}+\ldots+2^{k-1}\ell_{k}-2}{2^{k}-2}\right\rfloor.$

Observe first that if $\ell_{t}\geq
p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$ Lemma 2.2 implies
$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})=p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$
so we only need to prove the first case of Theorem 3.1. Namely provided that
$\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$ we need to show
$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})=s(\ell_{1},\ldots,\ell_{t})$.

We begin with the lower bound in order to give an illustration on how the
optimal examples behave, this will also serve to provide some motivation for
the upper bound argument.

###  3.1 The lower bound

The following proposition contains the remaining case for the lower bound.

###### Proposition 3.2

If $\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$, then
$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})\geq s(\ell_{1},\ldots,\ell_{t})$.

Proof. Let $s=s(\ell_{1},\ldots,\ell_{t})$. We shall show
$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})>s-1$ by exhibiting a $t$-colouring
of $K_{s-1}$ which does not contain a colour $j$-avoiding path of order
$\ell_{j}$ for all $1\leq j\leq t$.

Let us first observe that if $s<\ell_{t}$ then $K_{s-1}$ can not contain
$P_{\ell_{t}}$ regardless of the colouring so we can choose to only use the
first $t-1$ colours. In particular, since
$s<\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$ we can, by
definition of $p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$ find a desired
colouring of $K_{s-1}.$ From now on we assume $s\geq\ell_{t}$.

As we will see the structure of our colouring is very natural, although
choosing the parameters correctly turns out to be a bit more technical.

We split the vertices of our $K_{s-1}$ into $t$ parts $A_{1},\ldots,A_{t}$
with sizes $|A_{j}|=a_{j}.$ We colour in colour $j$ all edges contained within
a part $A_{j}$. For edges between parts $A_{i}$ and $A_{j}$ with $i<j$ we
colour the edges in colour $j$. See Figure 2 for an illustration.

The partitioning condition requires us to choose the sizes $a_{j}$ so as to
satisfy $a_{1}+a_{2}+\ldots+a_{t}=s-1$. Let us now establish requirements on
the sizes $a_{j}$ which guarantee there is no path avoiding colour $j$ of
order $\ell_{j}$. Consider first the subgraph of $K_{s-1}$ consisting of edges
coloured with colours in $[t]\setminus\\{j\\}$. We can split it into three
parts $A=A_{1}\cup\ldots\cup A_{j-1};B=A_{j};C=A_{j+1}\cup\ldots\cup A_{t}$
and we know $A\cup C$ spans a clique, all edges between $B$ and $C$ exist, $B$
spans an independent set and there are no edges between $A$ and $B$ (see
Figure 2 for an illustration). Let us consider the longest path in this graph.
If the path uses no vertex from $A$ its order is at most $2|C|+1.$ Otherwise
by removing any vertex belonging to $A$ we split the path into pieces all of
which have at least one endpoint in $C$, so in total have order at most
$2|C|$. In total in this case the order is at most $|A|+2|C|.$ Putting the
cases together the longest path we can find has order $\max(1,|A|)+2|C|$.

$A_{1}$$A_{2}$$A_{3}$ Figure 1: The $3$ colour example.

$A$$B$$C$ Figure 2: Edges allowed in a colour $2$-avoiding path.

Using this observation the claim will follow provided we can find $a_{j}$’s
satisfying the following collection of equalities and inequalities, in
addition to $a_{1}>0$ and $a_{j}\geq 0$ for all $j$.

$\displaystyle 2a_{2}+2a_{3}+2a_{4}+\ldots+2a_{t-1}+2a_{t}+1$
$\displaystyle\leq\ell_{1}-1,$ $\displaystyle
a_{1}+2a_{3}+2a_{4}+\ldots+2a_{t-1}+2a_{t}$ $\displaystyle\leq\ell_{2}-1,$
$\displaystyle a_{1}+a_{2}+2a_{4}+\ldots+2a_{t-1}+2a_{t}$
$\displaystyle=\ell_{3}-1,$ $\displaystyle\vdots$ $\displaystyle
a_{1}+a_{2}+\ldots+a_{t-3}+2a_{t-1}+2a_{t}$ $\displaystyle=\ell_{t-2}-1,$
$\displaystyle a_{1}+a_{2}+a_{3}+\ldots+a_{t-2}+2a_{t}$
$\displaystyle=\ell_{t-1}-1,$ $\displaystyle
a_{1}+a_{2}+a_{3}+\ldots+a_{t-2}+a_{t-1}$ $\displaystyle=\ell_{t}-1.$
$\displaystyle a_{1}+a_{2}+a_{3}+\ldots+a_{t-2}+a_{t-1}+a_{t}$
$\displaystyle=s-1,$

We will choose $a_{t}=s-\ell_{t}\geq 0$ and define recursively
$a_{i}=2a_{i+1}+\ell_{i+1}-\ell_{i}$ for $3\leq i\leq t-1$ the remaining two
sizes $a_{1},a_{2}$ we will choose later to satisfy the first two and the last
of the above expressions. Note that $a_{i}\geq 0$ for these $i$ also follows
since $\ell_{i+1}\geq\ell_{i}$.

Note now that by repeatedly substituting $a_{i}=2a_{i+1}+\ell_{i+1}-\ell_{i}$
and using $a_{t}=s-\ell_{t}$ in the last equality we get:

$\displaystyle S:=a_{3}+a_{4}+\ldots+a_{t}$
$\displaystyle=-\ell_{3}+\ell_{4}+3a_{4}+a_{5}+\ldots+a_{t}$
$\displaystyle=-\ell_{3}-2\ell_{4}+3\ell_{5}+7a_{5}+a_{6}+\ldots+a_{t}$
$\displaystyle\>\>\vdots$
$\displaystyle=-\ell_{3}-2\ell_{4}-2^{2}\ell_{5}-\ldots-2^{t-4}\ell_{t-1}+(2^{t-3}-1)\ell_{t}+(2^{t-2}-1)a_{t}$
$\displaystyle=-\ell_{3}-2\ell_{4}-2^{2}\ell_{5}-\ldots-2^{t-3}\ell_{t}+(2^{t-2}-1)s$

So we now have to choose $a_{1},a_{2}$ so as to satisfy
$2a_{2}+2S+1\leq\ell_{1}-1$, $a_{1}+2S\leq\ell_{2}-1$ and $a_{1}+a_{2}+S=s-1$.
We choose:

$a_{1}=\left\lceil\frac{2s-2S+\ell_{2}-\ell_{1}-1}{3}\right\rceil\quad\quad\quad\quad\quad\quad\quad
a_{2}=\left\lfloor\frac{s-S+\ell_{1}-\ell_{2}-2}{3}\right\rfloor$

Observe that removing the ceil sign in $a_{1}$ and floor in $a_{2}$ their sum
is precisely $s-S-1$ which is an integer. This in turn implies the same holds
for $a_{1}$ and $a_{2}$ since one comes with floor and one with ceil signs,
namely $a_{1}+a_{2}+S=s-1$.

Observe now that by definition of $s$ we know

$(2^{t}-2)s\leq-2+\ell_{1}+2\ell_{2}+\ldots+2^{t-1}\ell_{t}=-2+\ell_{1}+2\ell_{2}+(2^{t}-4)s-4S,$

which after rearranging implies $4S+2s+2\leq\ell_{1}+2\ell_{2}.$

We now use this inequality to verify the remaining required inequalities.
First let us verify that $a_{2}\geq 0$ (which then immediately implies also
$a_{1}\geq 1$ since $\ell_{2}\geq\ell_{1}$). This follows from the above
inequality since it gives

$\displaystyle 4(s-S)$ $\displaystyle\geq 6s-\ell_{1}-2\ell_{2}+2\geq
4(\ell_{2}-\ell_{1}+2),$

where the final inequality is equivalent to $6s+3\ell_{1}\geq 6\ell_{2}+6,$
which holds since $s\geq\ell_{t}\geq\ell_{2}$ and $\ell_{1}\geq 2$.

Once again rearranging our inequality gives us

$\ell_{2}-1\geq\frac{2s-2S-1-\ell_{1}+\ell_{2}}{3}+2S.$

Since the LHS is an integer we may take the ceil of the RHS which implies
$\ell_{2}-1\geq a_{1}+2S,$ as desired. We obtain the final inequality after
yet another rearrangement gives

$\ell_{1}-1\geq 2\cdot\frac{s-S+\ell_{1}-\ell_{2}-2}{3}+1+2S\geq 2a_{2}+2S+1.$

$\Box$

###  3.2 The upper bound

Our proof of Theorem 3.1 is going to proceed by induction on
$\ell_{1}+\ldots+\ell_{t}$. The following lemma will serve as the basis.
Throughout the section we write
$s=s({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}}).$

###### Lemma 3.3

If $\ell_{1}\leq 3$, then $p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})\leq s$.

Proof. By repeated use of Lemma 2.2 and an application of Theorem 2.1 we get

$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})\leq
p({\ell_{1}},{\ell_{2}})=\ell_{2}+\lfloor\ell_{1}/2\rfloor-1=\ell_{2}\leq s,$

where the last equality follows since $2\leq\ell_{1}\leq 3$ and the final
inequality follows from definition of $s$ and
$2^{t-1}\ell_{2}+\ldots+2^{2}\ell_{2}+2\ell_{2}\leq
2^{t-1}\ell_{t}+\ldots+2^{2}\ell_{3}+2\ell_{2}+\ell_{1}-2$.$\hfill\Box$

We are now ready to prove the remaining case of the upper bound of Theorem 3.1
and hence complete its proof.

###### Theorem 3.4

If $t\geq 3$ and $\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$, then
$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t}})\leq s$.

Proof. The proof is by induction on both $t$ and $\ell_{1}+\ldots+\ell_{t}$
with base cases being taken care of by Theorem 2.1 and Lemma 3.3. Let us
suppose now that $t\geq 3$ and $\ell_{i}\geq 4$. We assume that Theorem 3.1
holds for $t-1$ paths of any lengths and for $t$ paths of lengths
$2\leq\ell_{1}^{\prime}\leq\ldots,\ell_{t}^{\prime}$ provided
$\ell_{1}^{\prime}+\ldots+\ell_{t}^{\prime}<\ell_{1}+\ldots+\ell_{t}$. In
particular, we are going to use the following immediate corollary of the
inductive assumption.

$p(\ell_{1}^{\prime},\ldots,\ell_{t}^{\prime})\leq\max\\{s(\ell_{1}^{\prime},\ldots,\ell_{t}^{\prime}),\ell_{t}^{\prime}\\}.$
(1)

Suppose that the edges of $G=K_{s}$ are coloured by $1,\ldots,t$. We split the
proof in a sequence of claims.

###### Claim 3.5

$\ell_{t}\leq s$.

Proof of Claim 3.5. Let us first show that
$p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})\leq
s({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}}).$

If $t\geq 4$ then using Lemma 2.2,
$\ell_{t-1}\leq\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})\leq
p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-2}})$ so the inductive assumption
implies $p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})\leq
s({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}}).$ Note that the same holds if
$t=3$ as well, by Theorem 2.1.

Since $\ell_{t}<p({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})\leq
s({\ell_{1}},{\ell_{2}},\ldots,{\ell_{t-1}})$, we have
$\ell_{t}(2^{t-1}-2)\leq\ell_{1}+2\ell_{2}+\ldots+2^{t-2}\ell_{t-1}-2$. Adding
$2^{t-1}\ell_{t}$ to both sides and dividing by $2^{t}-2$ shows

$\ell_{t}\leq\frac{\ell_{1}+2\ell_{2}+\ldots+2^{t-2}\ell_{t-1}-2}{2^{t}-2}.$

Since $\ell_{t}$ is an integer we may take the floor of the RHS, which gives
our desired conclusion. $\hfill\dashv$

The following claim will be a useful estimate when applying induction.

###### Claim 3.6

Let $k\geq 1$ be an integer and let $\ell_{i}^{\prime}$ be such that for some
$j$ we have $\ell_{j}^{\prime}=\ell_{j}$ and for all $i\neq j$ we have
$\ell_{i}^{\prime}=\ell_{i}-2k\geq 2$. Then
$p(\ell_{1}^{\prime},\ldots,\ell_{t}^{\prime})\leq\max\\{\ell_{1}^{\prime},\ldots,\ell_{t}^{\prime},s-k\\}.$

Proof of Claim 3.6. We note that we are not assuming that the sequence
$\ell_{i}^{\prime}$ is sorted. Indeed let
$2\leq\ell_{1}^{\prime\prime}\leq\ldots\leq\ell_{t}^{\prime\prime}$ be the
sorted permutation of $\ell_{1}^{\prime},\ldots,\ell_{t}^{\prime}$. The
induction hypothesis, in the form of (1), implies
$p(\ell_{1}^{\prime},\ldots,\ell_{t}^{\prime})\leq\max\\{\ell_{t}^{\prime\prime},s(\ell_{1}^{\prime\prime},\ldots,\ell_{t}^{\prime\prime})\\}.$
To complete the claim observe that

$\displaystyle s(\ell_{1}^{\prime\prime},\ldots,\ell_{t}^{\prime\prime})$
$\displaystyle=\left\lfloor\frac{\ell_{1}^{\prime\prime}+2\ell_{2}^{\prime\prime}+\ldots+2^{t-1}\ell_{t}^{\prime\prime}-2}{2^{t}-2}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{\ell_{1}-2k+2(\ell_{2}-2k)+\ldots+2^{t-2}(\ell_{t-1}-2k)+2^{t-1}\ell_{t}-2}{2^{t}-2}\right\rfloor$
$\displaystyle=\left\lfloor\frac{\ell_{1}+2\ell_{2}+\ldots+2^{t-1}\ell_{t}-2}{2^{t}-2}\right\rfloor-k=s-k.$

In the inequality above we first took out the $t-1$ terms $-2k$, note that
their contribution is maximal if they are matched with the smallest possible
powers of $2$. The remaining terms are products of $1,2,\ldots,2^{t-1}$ with
respectively with corresponding term of a certain permutation of
$\ell_{1},\ldots,\ell_{t}$. Since by the rearrangement inequality such a
product is maximised when both sequences are ordered in the same way we know
the contribution is indeed $\ell_{1}+2\ell_{2}+\ldots+2^{t-1}\ell_{t}.$
$\hfill\dashv$

The following claim provides us with a slightly stronger estimate which will
be useful in certain regimes.

###### Claim 3.7

Let $2q+2\leq\ell_{1}\leq\ldots\leq\ell_{t}$ and assume $s=q+\ell_{j}-1$ then

$p(\ell_{1}-2q,\ldots,\ell_{j-1}-2q,\ell_{j+1}-2q,\ldots,\ell_{t}-2q)\leq\max(\ell_{t}-2q,\ell_{j}-1).$

Proof of Claim 3.7. As in the previous claim we know that the desired
expression is either at most $\ell_{t}-2q$ or at most the floor of

$\displaystyle\frac{\ell_{1}-2q+\ldots+2^{j-2}(\ell_{j-1}-2q)+2^{j-1}(\ell_{j+1}-2q)+\ldots+2^{t-2}(\ell_{t}-2q)-2}{2^{t-1}-2}=$
$\displaystyle\frac{\ell_{1}+\ldots+2^{j-2}\ell_{j-1}+2^{j-1}\ell_{j+1}+\ldots+2^{t-2}\ell_{t}-(2^{t}-2)q-2}{2^{t-1}-2}\leq$
$\displaystyle\frac{\ell_{1}+\ldots+2^{j-2}\ell_{j-1}+2^{j-1}\ell_{j}+2^{j}\ell_{j+1}+\ldots+2^{t-1}\ell_{t}-2^{t-1}\ell_{j}-(2^{t}-2)q-2}{2^{t-1}-2}<$
$\displaystyle\frac{(s+1)(2^{t}-2)-2^{t-1}\ell_{j}-(2^{t}-2)q}{2^{t-1}-2}=\frac{(2^{t}-2)\ell_{j}-2^{t-1}\ell_{j}}{2^{t-1}-2}=\ell_{j}$

where in the first inequality we added $2^{i-2}(\ell_{i}-\ell_{j})\geq 0$ for
all $i>j$ and added and subtracted $2^{j-1}\ell_{j}$ this contributed the term
of $(2^{j-1}+2^{j-1}+2^{j}+\ldots+2^{t-2})\ell_{j}=2^{t-1}\ell_{j}$. In the
second inequality we used the definition of $s$ and in the penultimate
equality we used $s=q+\ell_{j}-1$. Since for our bound we take the floor of
the first expression and the inequality is strict the expression is at most
$\ell_{j}-1,$ as claimed. $\hfill\dashv$

The following two claims contain the main part of our argument.

###### Claim 3.8

If $G$ contains a cycle of length $\ell_{j}-1$ avoiding colour $j$ then $G$
contains $P_{\ell_{j^{\prime}}}$ avoiding colour $j^{\prime}$ for some
$j^{\prime}\in[t]$.

Proof of Claim 3.8. Let $C$ be the cycle of length $\ell_{j}-1$ given by the
lemma and let $Q$ be the graph induced by the $q=s-(\ell_{j}-1)$ vertices of
$G$ not in $C$. If there is any edge not of colour $j$ between $C$ and $Q$
then we can use it to extend $C$ into a $P_{\ell_{j}}$ avoiding colour $j$ and
are done. Otherwise, all of the edges joining the $\ell_{j}-1$ vertices of $C$
and the $q$ vertices of $Q$ have colour $j$. We can always use these edges to
build a path in colour $j$ of order $2\min(\ell_{j}-1,q)$ and actually by one
longer if $\ell_{j}-1\neq q.$ Observe first that if $\ell_{j}-1=q$ then we can
find a Hamilton path of colour $j$, so of order at least $s\geq\ell_{t}$ which
provides the desired $j^{\prime}$ avoiding path for any $j^{\prime}\neq j$. So
we may assume $\ell_{j}-1\neq q$ and that we have a colour $j$ path of order
$2\min(\ell_{j}-1,q)+1$.

Case 1. $\ell_{j}-1<q.$

The colour $j$ path has order $2\ell_{j}-1\geq\ell_{1}$ so it serves as the
desired path, avoiding colour $1$, unless $j=1$. In this case it would also
serve as the desired path avoiding colour $2$ unless
$\ell_{2}>2(\ell_{1}-1)+1$. This implies $\ell_{2}\geq 2(\ell_{1}-1)+2$ and
allows us to use Claim 3.6 to show

$p({\ell_{1}},{\ell_{2}-2(\ell_{1}-1)},{\ell_{3}-2(\ell_{1}-1)},\ldots,{\ell_{t}-2(\ell_{1}-1)})\leq\max(\ell_{1},\ell_{t}-2(\ell_{1}-1),s-(\ell_{1}-1))\leq
q,$

where the final inequality holds since by the case assumption we have
$\ell_{1}\leq q$ and since $\ell_{t}-2(\ell_{1}-1)\leq
s-2(\ell_{1}-1)=q-(\ell_{1}-1)$.

This means that we can either find the desired colour $1$ avoiding path of
order $\ell_{1}$ inside $Q$ or we can find a path of order
$\ell_{i}-2(\ell_{1}-1)$ avoiding some colour $i>1$ inside $Q$. Since
$\ell_{i}-2(\ell_{1}-1)\leq s-2(\ell_{1}-1)=q-(\ell_{1}-1)$ there are
$\ell_{1}-1$ vertices in $Q$ not on this path. This means that we can extend
the path by going to $C$ and then alternating between these $\ell_{1}-1$
vertices of $Q$ not on the path and $C$ (see Figure 3 for an illustration).
This produces a path of order $\ell_{i}-2(\ell_{1}-1)+2(\ell_{1}-1)=\ell_{i}$
which avoids colour $i$ (recall that all edges between $C$ and $Q$ are in
colour $j=1$) as desired.

$C$$Q$$\ell_{1}-1$$\ell_{1}-1$$\ell_{i}-2(\ell_{1}-1)$ Figure 3: Illustration
on how we construct the desired path. The path of length
$\ell_{i}-2(\ell_{1}-1)$ avoiding some colour $i\neq 1$ is found by induction
inside $Q$. We extend it using as depicted using the fact that all edges
between $C$ and $Q$ have colour $1$.

Case $2$. $\ell_{j}-1>q.$

This means that in between $Q$ and $C$ we can find a colour $j$ path of order
$2q+1$. This means that we are done unless $\ell_{i}\geq 2q+2$ for all $i\neq
j$. This allows us to use Claim 3.7 which gives

$p(\ell_{1}-2q,\ldots,\ell_{j-1}-2q,\ell_{j+1}-2q,\ldots,\ell_{t}-2q)\leq\max(\ell_{t}-2q,\ell_{j}-1)=\ell_{j}-1,$

since $\ell_{t}-2q\leq s-2q\leq(\ell_{j}-1)-q$. This means that among vertices
of $C$ we can find a colour $i$ avoiding path of order $\ell_{i}-2q$ for some
$i\neq j$ (note that technically we merge two colours in order to obtain a
$t-1$ colouring).

Observe that there are at least $s-q-(\ell_{i}-2q)\geq q$ unused vertices left
in $C$ so once again we can extend our path by alternating between $q$
vertices in $Q$ and these $q$ vertices of $C$. Since all the edges between $Q$
and $C$ are in colour $j\neq i$ the new path is still colour $i$ avoiding and
has order $\ell_{i}$ as desired.

Let us take a vertex $x$ and colour $i$ such that the degree of $x$ in the
colour $i$ is maximum among all choices of $x$ and $i$.

###### Claim 3.9

Suppose there is a path in $G-x$ of order $\ell_{j}-2$ avoiding some colour
$j\neq i$. Then there is a colour $j^{\prime}$ avoiding path of order
$\ell_{j^{\prime}}$ for some $j^{\prime}$.

Proof of Claim 3.9. Let $P$ be the colour $j$ avoiding path of order
$\ell_{j}-2$ contained in $G-x$. Suppose $y,z$ are the endpoints of $P$. If
both $xy,xz$ are not of colour $j$ then we can use $x$ to extend $P$ into a
colour $j$ avoiding cycle of length $\ell_{j}-1$ and we are done by Claim 3.8.
We are left with the following two cases.

Case $1$. Exactly one of the edges $xy,xz$ are of colour $j$, say w.l.o.g.
$xz$.

If $x$ had any neighbours of colour $i$ outside $P$ then we can extend
$zPyx$222Here by $aPb$ we denote the part of $P$ between two of its vertices
$a$ and $b$. to this vertex to find a colour $j$ avoiding path of order
$\ell_{j}$ (since $i\neq j$). So we are done unless all colour $i$ neighbours
of $x$ are on $P$. Let $w\neq y$ be such a neighbour. We claim that the
neighbour $w^{+}$ of $w$ on $P$ closer to $y$ needs to be joined to $z$ by an
edge of colour $j$. Indeed otherwise $xyPw^{+}zPwx$ is a colour $j$ avoiding
cycle of length $\ell_{j}-1$ and we are done by Claim 3.8. This means that for
any neighbour in colour $i$ of $x$ we know $z$ has a corresponding neighbour
in colour $j$. In particular, within $P$ we know $z$ has at most one neighbour
in colour $j$ less than $x$ has in colour $i$ (since $xy$ might be of colour
$i$). In addition $x$ is a neighbour of $z$ in colour $j$ so within
$P\cup\\{x\\}$ the colour $j$ degree of $z$ is at least as big as that of $x$
in colour $i$. Finally, take a vertex $a$ outside $P\cup\\{x\\}$ (note that it
exists since $s\geq\ell_{t}>\ell_{j}-1=|P\cup\\{x\\}|$). If $za$ is not of
colour $j$ then $xyPza$ is the desired path of order $\ell_{j}$ avoiding
colour $j$ and we are done. Otherwise $z$ has more neighbours in colour $j$
than $x$ in colour $i$ (recall that $x$ has no colour $i$ neighbours outside
$P\cup\\{x\\}$), which is a contradiction to the maximality of our choice of
$x$ and $i$.

Case $2$. Both edges $xy$ and $xz$ are of colour $j$.

Suppose $w$ is a neighbour of colour $i$ of $x$ on $P$. Note that $w\neq y$
since $xy$ is of colour $j\neq i$. As in the previous case consider the
neighbour $w^{+}$ of $w$ on $P$ closer to $y$. If $zw^{+}$ is not of colour
$j$ then we can rotate and find a path $yPw^{+}zPw$ of same length as $P$,
which still avoids colour $j$ but of its endpoints $y,w$, exactly one is
adjacent to $x$ in colour $j$ (since $xw$ is of colour $i\neq j$). So we can
reduce to the first case and are done. This means that $zw^{+}$ is of colour
$j$. This means that $z$ has at least as many neighbours of colour $j$ on $P$
as $x$ has neighbours of colour $i$.

Note also that for any vertex $a$ outside of $P\cup\\{x\\}$ if $xa$ is of
colour $i$ then $za$ must be of colour $j$, as otherwise $yPzax$ is the
desired path avoiding colour $j$. So $z$ has at least as many neighbours of
colour $j$ outside $P\cup\\{x\\}$ as $x$ has neighbours of colour $i$.
Finally, since $x$ itself is a neighbour of $z$ in colour $j$ once again $z$
has more neighbours in colour $j$ than $x$ has in colour $i$, contradicting
maximality of $x$ and $i$. $\hfill\dashv$

We are now in a position to finish the proof. By Lemma 3.3, we may assume
$\ell_{i}\geq 4$ for all $i$.

First by Claim 3.6 we have

$p({\ell_{1}-2},\ldots,{\ell_{i-1}-2},{\ell_{i}},{\ell_{i+1}-2},\ldots,{\ell_{t}-2})\leq\max\\{\ell_{i},\ell_{t}-2,s-1\\}$

In case this is at most $s-1$ we can find either a colour $i$ avoiding path of
order $\ell_{i}$ and are done or a colour $j$ avoiding path of order
$\ell_{j}-2$ in $G-x$ and are done by Claim 3.9. Otherwise, since
$\ell_{i}\leq\ell_{t}\leq s,$ we must have $\ell_{i}=\ell_{t}=s$. This implies
$s=(\ell_{i}-1)+1$ and we may apply Claim 3.7 with $j=i$ and $q=1$ to show

$p({\ell_{1}-2},\ldots,{\ell_{i-1}-2},{\ell_{i+1}-2},\ldots{\ell_{t}-2})\leq\max\\{\ell_{t-1}-2,s-1\\}\leq
s-1.$

Once again this allows us to find a colour $j$ avoiding path of order
$\ell_{j}-2$ for some $j\neq i$ inside $G-x$ and we are done by Claim 3.9.
This completes the proof. $\hfill\Box$

##  4 Concluding remarks and open problems

In this paper, we determine the $(t-1)$-chromatic Ramsey number of a path of
any length exactly, in other words we determine the minimum number of vertices
$n$ needed for a $t$-edge coloured $K_{n}$ to contain a path of length $\ell$
using only $t-1$ of the colours.

A natural further question could be to determine how the answer behaves if we
want our path to use $s$ colours.

###### Question 4.1

Let $t>s\geq 1$ be integers. What is the smallest $n$ such that in any
$t$-edge colouring of $K_{n}$ we can find a path of order $\ell$ using at most
$s$ colours?

When $s=1$ this recovers the classical Ramsey problem and the answer is known,
up to lower order terms, to be between $(t-1)\ell$ and $(t-1/2)\ell$ and
closing this gap is a major open problem in the area. We settle the opposite
extreme, namely when $s=t-1$ and the answer is much smaller at
$\ell+\left\lfloor\frac{\ell-2}{2^{t}-2}\right\rfloor$. It seems like a nice
question to determine how the answer transitions as $s$ varies from one
extreme to another.

A natural first step in attacking this question would be to try to resolve it
if we seek a matching of size $\ell$ instead of $P_{2\ell}$. This question was
raised by Gyárfás, Sárközy and Selkow [20].

A particularly nice instance of our result is that if $n\leq 2^{t}$ then in
any $t$ colouring of $K_{n}$ we can find a Hamilton path avoiding some colour.
A nice question in this direction is whether the same holds for a Hamilton
cycle?

In general it could be interesting to determine what happens in the
$(t-1)$-chromatic case for cycles.

###### Question 4.2

What is the smallest $n$ such that in any $t$-edge colouring of $K_{n}$ we can
find a cycle of length $\ell$ using at most $t-1$ colours?

Understanding the answer for other sparse structures, such as general trees
might also be interesting.

## References

  * [1] N. Alon, M. Bucić, T. Kalvari, E. Kuperwasser and T. Szabó, List Ramsey numbers, J. Graph Theory 96 (2021), no. 1, 109-128.
  * [2] N. Alon, P. Erdős, D. S. Gunderson and M. Molloy, A Ramsey–type problem and the Turán numbers, J. Graph Theory 40 (2002), no. 2, 120-129.
  * [3] G. Beam, and M. Budden, Weakened Gallai-Ramsey numbers, Surv. Math. Appl. 13 (2018), 131-145.
  * [4] M. Bucić, S. Letzter, and B. Sudakov, 3-colour bipartite Ramsey number of cycles and paths, J. Graph Theory 92 (2019), no. 4, 445-459.
  * [5] M. Bucić, S. Letzter, and B. Sudakov, Directed Ramsey number for trees, J. Combin. Theory Ser. B 137 (2019), 145-177.
  * [6] M. Bucić, S. Letzter, and B. Sudakov, Monochromatic paths in random tournaments, Random Structures Algorithms 54 (2019), no. 1, 69-81.
  * [7] M. Bucić, S. Letzter, and B. Sudakov, Multicolour bipartite Ramsey number of paths, Electron. J. Combin. 26 (2019), no. 3, Paper No. 3.60, 15 pp.
  * [8] M. Budden, M. Stender and Y. Zhang, Weakened Ramsey numbers and their hypergraph analogues, Integers 17 (2017), 1-8.
  * [9] K.M. Chung, M.L. Chung and C.L. Liu, A generalization of Ramsey theory for graphs-with stars and complete graphs as forbidden subgraphs, Congr. Numer. 19 (1977) 155-161.
  * [10] K.M. Chung and C.L. Liu, A generalization of Ramsey theory for graphs, Discrete Math. 2 (1978) 117-127.
  * [11] D. Conlon, J. Fox, and B. Sudakov, _Recent developments in graph Ramsey theory_ , Surveys in combinatorics 424 (2015), 49–118.
  * [12] L. DeBiasio, A. Gyárfás, R.A. Krueger, M. Ruszinkó and G.N. Sárközy, Monochromatic balanced components, matchings, and paths in multicoloured complete bipartite graphs, J. Comb. 11 (2020), no. 1, 35-45.
  * [13] P. Erdős, A. Hajnal, and R. Rado, _Partition relations for cardinal numbers_ , Acta Mathematica Academiae Scientiarum Hungarica 16 (1965), 93–196.
  * [14] P. Erdős and A. Szemerédi _On a Ramsey type theorem_ , Periodica Mathematica Hungarica 2 (1972), 295–299.
  * [15] R.J. Faudree and R.H. Schelp, Path Ramsey Numbers in Multicolourings, Journal of Combinatorial Theory, Series B 19 (1975) 150-160.
  * [16] L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest Eötvös. 10 (1967) 167-170.
  * [17] A. Gyárfás, Large sets of $t$-designs and a Ramsey-type problem, Integers 18 (2018), Paper No. A53, 3 pp.
  * [18] A. Gyárfás, and G.N. Sárközy, Matchings with few colours in coloured complete graphs and hypergraphs, Discrete Math. 343 (2020), no. 5, 111831, 8 pp.
  * [19] A. Gyárfás, M. Ruszinkó, G.N. Sárközy and E. Szemerédi, Three-colour Ramsey Numbers for Paths, Combinatorica 27 (2007) 35-69. Corrigendum in 28 (2008) 499-502.
  * [20] A. Gyárfás, G.N. Sárközy and S. Selkow, Coverings by few monochromatic pieces: a transition between two Ramsey problems, Graphs Combin. 31(1) (2015) 131-140.
  * [21] H. Harborth and M. Möller, Weakened Ramsey numbers, Discrete Applied Math. 95 (1999) 279-284.
  * [22] J. Hook, Critical graphs for $r(P_{n},P_{m})$ and the star-critical ramsey number for paths, Discuss. Math. Graph Theory 35 (2015) 689-701.
  * [23] J. Hook and G. Isaak, Star-critical Ramsey numbers, Discrete Appl. Math. 159 (2011) 328-334.
  * [24] M.S. Jacobson, On a generalization of Ramsey theory, Discrete Math. 38 (1982) 191-195.
  * [25] A. Khamseh, A note on $(t-1)$-chromatic Ramsey number of linear forests, Int. J. Comput. Math. Comput. Syst. Theory 5 (2) (2020) 92-97.
  * [26] A. Khamseh, On $(t-1)$-coloured paths in $t$-coloured complete graphs, Bull. Belg. Math. Soc. Simon Stevin 25 (2) (2018) 197-207.
  * [27] A. Khamseh and G.R. Omidi, A generalization of Ramsey theory for linear forests, Int. J. Comput. Math. 89 (10) (2012) 1303-1310.
  * [28] A. Khamseh and G.R. Omidi, A generalization of Ramsey theory for stars and one matching, Math. Reports 19(69), 1 (2017) 85-92.
  * [29] A. Khamseh and G.R. Omidi, Large stars with few colours, Math. Reports, to appear.
  * [30] C. Knierim, and P. Su, _Improved bounds on the multicolour Ramsey numbers of paths and even cycles_ , Electron. J. Combin. 1.26 (2019).
  * [31] S. Letzter, and B. Sudakov, The oriented size Ramsey number of directed paths, European J. Combin. 88 (2020), 103103, 5 pp.
  * [32] T. Łuczak, _$R(C_{n},C_{n},C_{n})\leq(4+o(1))n$_ , J. Combin. Theory Ser. B 75 (1999), no. 2, 174–187.
  * [33] R. Meenakshi and P.S. Sundararaghavan, Generalized Ramsey numbers for paths in $2$-chromatic graphs, Internat. J. Math. Sci. 9 (1986) 273-276.
  * [34] S.P. Radziszowski, Small Ramsey numbers, Electronic J. Combin. 1 (1994) Dynamic Surveys, DS1.15 (March 3, 2017).
  * [35] F. P. Ramsey, _On a Problem of Formal Logic_ , Proc. London Math. Soc. S2-30 (1929), no. 1, 264.
  * [36] S. Yongqi, Y. Yuansheng, F. Xu, and L. Bingxi, _New lower bounds on the multicolour Ramsey numbers $R_{r}(C_{2m})$_, Graphs Combin. 22 (2006), no. 2, 283–288.

Matija Bucić

Department of Mathematics, ETH, Z̈urich, Switzerland

<EMAIL_ADDRESS>
Amir Khamseh

Department of Mathematics, Kharazmi University, 15719-14911 Tehran Iran

<EMAIL_ADDRESS>


tcb@breakable

# A Note on Rounding Matchings in General Graphs

Aditi Dudeja<EMAIL_ADDRESS>This work is supported by Austrian
Science Fund (FWF): P 32863-N. This project has received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No 947702). Department of
Computer Science, University of Salzburg

###### Abstract

In this note, we revisit the rounding algorithm of Wajc [Waj20]. Wajc gave a
fully-adaptive randomized algorithm that rounds a dynamic fractional matching
in an _unweighted bipartite graph_ to an integral matching of nearly the same
value in $O(\mbox{\rm poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$ update
time. We give show that the guarantees of this algorithm hold for _general
graphs_ as well. Additionally, we show useful properties of this subroutine
which have applications in rounding weighted fractional matchings.

In the dynamic matching problem, the graph undergoes edge insertions and
deletions, and the algorithm is required to maintain a good approximation to
the maximum matching. The goal is to optimize the update time which is the
time required to cope with a single edge insertion or deletion. Several
dynamic algorithms for approximate maximum matching proceed by computing a
fractional matching [BHI15, BHN16, BCH20, BHN17, BK23] and then rounding it
[ACC+18, Waj20, BK21, Kis22, BKSW23]. Fractional matchings have several
interesting advantages. They are not only computationally easier to compute,
but also certain types of fractional matchings are robust to adversarial edge
insertions and deletions [BGS20, ABD22, CST23, JJST22]. Thus, there has been a
lot of focus on designing efficient rounding algorithms.

##  1 Background on Dynamic Rounding of Fractional Matching

Arar, Chechik, Cohen, Stein, and Wajc [ACC+18] gave a rounding procedure based
on independent sampling: given a dynamic unweighted fractional matching
$\vec{x}$, sample every edge with a probability proportional to $x(e)$ and
include it in the subgraph $S$. The resulting subgraph $S$ has the property
that $\mu(S)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}x(e)$, and is sparse.
However, it is only robust to an oblivious adversary. Subsequently, [Waj20]
gave a dependent version of the above sampling scheme, and showed that the
resulting sparsifier was now robust to an adaptive adversary. This rounding
procedure, combined with existing fractional matching results, then gave a
slew of fully-adaptive dynamic matching algorithms, with varying approximation
ratios and update times. However, his analysis only demonstrated that
_arbitrary_ fractional matchings in bipartite graphs can be rounded to
integral matchings of nearly the same value. In another work, Bhattacharya and
Kiss [BK21] gave a deterministic rounding procedure for fractional matchings
in bipartite graphs.

Subsequently, Bhattacharya, Kiss, Sidford, and Wajc [BKSW23] showed that the
sampling approach of [ACC+18] can be made robust to output-adaptive
adversaries. They also gave deterministic rounding algorithms for bipartite
graphs, and for certain types of structured matchings in general graphs. Very
recently, Chen, Sidford, and Tu [CST23] showed that the deterministic rounding
procedures of [BKSW23] and [ACC+18] also work for general graphs. Curiously,
the randomized sparsifier of [ACC+18] also has some additional nice
properties, which have applications for rounding weighted matchings. The
deterministic sparsifier doesn’t seem to share these additional nice
properties. In particular, [ACC+18] show the following theorem for dense
weighted graphs:

######  Result 1 (Informal [CST23]).

There is an output-adaptive randomized algorithm that maintains
$(1-\varepsilon)$-approximate maximum weight matching in decremental dense
weighted graphs with an update time of $O(\mbox{\rm poly}(\log
n,\frac{1}{\varepsilon}))$.

Prior to this, all known weighted matching algorithms either had a dependence
of $(\nicefrac{{1}}{{\varepsilon}})^{O(\nicefrac{{1}}{{\varepsilon}})}$, or
had a significantly worse approximation ratio than their unweighted
counterparts. A crucial step in obtaining 1, is the rounding algorithm of
[ACC+18] and [BKSW23]. This is also the reason why this algorithm is not
fully-adaptive.

In their paper, [CST23] left open the question of analysing Wajc’s algorithm,
since it is a dependent and consequently, easier to sample from version of
[ACC+18]. We show that Wajc’s algorithm also works for general graphs, and
additionally show the fully adaptive version of 1. In particular, we show the
following two results:

######  Result 2 (Informal).

There is a fully-adaptive randomized dynamic rounding algorithm for fractional
matchings in general graphs with amortized update time $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$ update time.

######  Result 3 (Informal).

There is a fully adaptive randomized algorithm that maintains
$(1-\varepsilon)$-approximate maximum weight matching in decremental dense
weighted graphs with an update time of $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$.

##  2 General Graph Rounding

We start by defining some notation, then we state Wajc’s algorithm. We
emphasis that the algorithm remains the same. We merely show that the analysis
extends to the case of general (possibly non-bipartite) graphs as well.

#### Notation

Given a graph $G$, we will use $\mu(G)$ to denote the size of the maximum
matching in $G$. Sometimes, we will consider weighted graphs, and in this
case, we use $\textsf{mwm}(G)$ to denote the weight of the maximum weight
matching. We will use $\vec{x}$ to denote a fractional matching. Given
$\vec{x}$, we define

$\displaystyle E_{i}$ $\displaystyle=\left\\{e\mid
x(e)\in\left[(1+\varepsilon)^{-i},(1+\varepsilon)^{-i+1}\right)\right\\}$ (1)
$\displaystyle G_{i}$ $\displaystyle=(V,E_{i})$ (2)

For a vertex $v$, we define $E_{v}$ to be the set of edges incident on the
vertex $v$. Additionally, given a graph $G$ we have the following notation,
which we borrow from [CST23]:

$\displaystyle\mathcal{O}$ $\displaystyle=\left\\{B\subseteq V\ \big{|}\
|B|\text{ is odd}\right\\}$ $\displaystyle\mathcal{O}_{\varepsilon}$
$\displaystyle=\left\\{B\subseteq V\ \big{|}\ |B|\text{ is odd and
}|B|\leqslant\nicefrac{{1}}{{\varepsilon}}\right\\}$
$\displaystyle\mathcal{P}_{G}$
$\displaystyle=\left\\{\vec{x}\in\mathbb{R}^{E}_{\geqslant 0}\ \big{|}\
\sum_{e\in E_{v}}x(e)\leqslant 1\right\\}$ $\displaystyle\mathcal{M}_{G}$
$\displaystyle=\left\\{\vec{x}\in\mathcal{P}_{G}\ \big{|}\ \sum_{e\in
G[B]}x(e)\leqslant\frac{|B|-1}{2},\forall B\in\mathcal{O}\right\\}$
$\displaystyle\mathcal{M}_{G,\varepsilon}$
$\displaystyle=\left\\{\vec{x}\in\mathcal{P}_{G}\ \big{|}\ \sum_{e\in
G[B]}x(e)\leqslant\frac{|B|-1}{2},\forall
B\in\mathcal{O}_{\varepsilon}\right\\}$

We will also often use the following fact about matchings.

######  Fact 4 ([ABD22]).

Suppose $\vec{x}\in\mathcal{M}_{G,\varepsilon}$, then
$\frac{\vec{x}}{(1+\varepsilon)}\in\mathcal{M}_{G}$.

######  Observation 5.

Ignoring the set of edges $E_{\text{low}}=\left\\{e\in E\mid
x(e)\leqslant\frac{\varepsilon^{2}}{n^{2}}\right\\}$ does not affect $\vec{x}$
by more than a value $\varepsilon$. Consequently, in the notation in (1), we
can assume that $i\in\left[2\cdot\log\frac{n}{\varepsilon}\right]$.

Algorithm 1 Sparsification($G,\vec{x},\varepsilon$)

1:for $i=1,\cdots,\lceil 2\cdot\log\frac{n}{\varepsilon}\rceil$ do

2: Edge color the graph $G_{i}$ using $2\cdot\lceil(1+\varepsilon)^{i}\rceil$
many colors. $\triangleright$ Coloring Phase

3: Sample $\min\left\\{2\cdot\lceil
d\cdot(1+\varepsilon)\rceil,2\cdot\lceil(1+\varepsilon)^{i}\rceil\right\\}$
colors from $G_{i}$. Denote sampled edges by $S_{i}$. $\triangleright$
Sampling Phase

4:end for

5:Output $S=\cup_{i}S_{i}$.

The sparsification procedure is stated in Algorithm 1. We first start by
giving the following property of this random process, which is a paraphrasing
of Lemma 3.2 from [Waj20].

######  Observation 6.

[Waj20] Suppose $d\geqslant\frac{\log n}{\varepsilon^{2}}$, for an edge $e$,
we have,

$\displaystyle\frac{\min\left\\{1,x(e)\cdot
d\right\\}}{(1+\varepsilon)^{2}}\leqslant\operatorname*{\textnormal{Pr}}\left(e\in
S\right)\leqslant\min\left\\{1,x(e)\cdot d\right\\}\cdot(1+\varepsilon).$

Additionally, if $x(e)>\nicefrac{{1}}{{d}}$, then
$\operatorname*{\textnormal{Pr}}\left(e\in S\right)=1$.

######  Definition 7.

For an edge $e$, we denote $\mathbb{1}_{e}$ to be the indicator random
variable for the event $e\in S$.

######  Definition 8.

Observe that the Coloring Phase splits up the graphs $G_{i}$, and consequently
$G$ into monochromatic matchings. Let $M_{1},\cdots,M_{l}$ be these matchings,
where $l\leqslant 2\cdot\lceil d\cdot(1+\varepsilon)\rceil\cdot\lceil
2\cdot\log\frac{n}{\varepsilon}\rceil$. For each of these matchings we
associate an indicator random variable $\mathbb{1}_{M_{i}}$ which takes value
$1$ if $M_{i}\in S$ and $0$ otherwise.

######  Lemma 9.

([DP09]) Suppose $b_{1},b_{2},\cdots,b_{r}$ be any set of $r$ elements.
Consider the random process of sampling $k\leqslant r$ objects without
replacement from these $r$ elements. Let $X_{i}$ denote the indicator variable
of $b_{i}$ being included in the sample. Then,
$\left\\{X_{i}\right\\}_{i\in[r]}$ are negatively associated random variables.

######  Observation 10.

Consider a vertex $v$, then the random variables
$\left\\{\mathbb{1}_{e}\right\\}_{e\in E_{v}}$ are negatively associated
random variables.

We also have the following observation, which

######  Observation 11.

Consider any odd set $B$, note that the Coloring Phase splits up $G_{i}[B]$
and consequently, $G[B]$ into monochromatic matchings of size at most
$\frac{|B|-1}{2}$. Moreover, all edges on a given matching $M$ are roughly the
same weight. Let $M^{\prime}$ be any such matching in $G_{i}$ for
$i\in\left\\{1,2,\cdots,\lceil
2\cdot\log\frac{n}{\varepsilon}\rceil\right\\}$, and $\mathbb{1}_{M^{\prime}}$
is an indicator random variable which takes value $1$ if $M^{\prime}\in S$ in
the Sampling Phase.

######  Lemma 12.

Consider any odd set $B$, and let $M^{\prime}_{1},\cdots,M^{\prime}_{j}$ be
the matchings $G[B]$ has been split up into after the Coloring Phase. Then,
$\left\\{\mathbb{1}_{M^{\prime}_{j}}\right\\}_{M^{\prime}_{j}\in G[B]}$ are
negatively associated random variables.

###### Proof.

Consider $G_{l}$ and recall 9. The set of colors, and consequently the
matchings correspond to the set of elements we are sampling from in 9. Let
$M_{1},\cdots,M_{k}$ be the matchings associated with each color (these
matchings can be potentially empty, if the colors are not used). In the
Coloring Phase, we are sampling a subset of these matchings without
replacement. Thus, the random variables,
$\left\\{\mathbb{1}_{M_{i}}\right\\}_{i\in[k]}$ are negatively associated by
9. Since subsets of negatively associated random variables are also negatively
associated, we have that $\left\\{\mathbb{1}_{M_{i}}\mid
M_{i}\neq\emptyset\right\\}_{i\in[k]}$ are also negatively associated. Next,
the independent union of negatively associated random variables are also
negatively associated. Thus, we have, $\mathcal{R}=\left\\{\mathbb{1}_{M}\mid
M\neq\emptyset\right\\}_{M\in G}$ are negatively associated as well.

Finally, consider an odd set $B$, and let
$M^{\prime}_{1},\cdots,M^{\prime}_{p}$ be the matchings $G[B]$ is split up
into. Note that the indicator random associated with these matchings are
identical to distinct random variables in $\mathcal{R}$. Consequently, we
have, $\left\\{\mathbb{1}_{M^{\prime}_{i}}\right\\}_{M^{\prime}_{i}\in G[B]}$
are negatively associated as well. ∎

Next, we have the following lemma, which is an analog of 6 for the case of
matchings, and in fact directly follows from 6.

######  Observation 13.

Suppose $M\in G_{i}[B]$, and let $e\in M$, then we have,

$\displaystyle\frac{d\cdot
x(M)}{(1+\varepsilon)\cdot|M|}\leqslant\operatorname*{\textnormal{Pr}}\left(M\in
S\right)\leqslant(1+\varepsilon)^{2}\cdot\frac{d\cdot x(M)}{|M|},$

if $d<(1+\varepsilon)^{i-1}$, and $\operatorname*{\textnormal{Pr}}\left(M\in
S\right)=1$ otherwise.

######  Lemma 14 (Chernoff Bounds [DP09]).

Suppose $X_{1},\ldots,X_{m}$ are $m$ negatively associated random variables
with range $[0,b]$ each for some $b\geqslant 1$. Let $X:=\sum_{i=1}^{m}X_{i}$
and $\mu_{L}\leqslant\mathbb{E}[X]\leqslant\mu_{H}$. Then, for any $\delta>0$,

$\operatorname{Pr}\left(X>(1+\delta)\cdot\mu_{H}\right)\leqslant\exp\left(-\frac{\delta^{2}\cdot\mu_{H}}{(3+\delta)\cdot
b}\right)\quad\text{ and
}\quad\operatorname{Pr}\left(X<(1-\delta)\cdot\mu_{L}\right)\leqslant\exp\left(-\frac{\delta^{2}\cdot\mu_{L}}{(2+\delta)\cdot
b}\right)$

######  Lemma 15.

Suppose $\vec{x}\in\mathcal{M}_{G}$ is input to Sparsification(), and
$d\geqslant\frac{\log n}{\varepsilon^{4}}$, then, with high probability, there
is a vector $\vec{y}\subseteq\text{supp}(S)$ such that:

  1. _a_)

For all vertices $v\in V$, $(1-\varepsilon)\cdot\sum_{e\in
E_{v}}x(e)-\varepsilon\leqslant\sum_{e\in
E_{v}}y(e)\leqslant(1-\varepsilon)\cdot\sum_{e\in E_{v}}x(e)+\varepsilon$.

  2. _b_)

For all odd sets $B$ with $|B|\leqslant\nicefrac{{1}}{{\varepsilon}}$,

$\displaystyle(1-\varepsilon)\cdot\sum_{e\in
G[B]}x(e)-\frac{\varepsilon\cdot(|B|-1)}{2}\leqslant\sum_{e\in
G[B]}y(e)\leqslant(1-\varepsilon)\cdot\sum_{e\in
G[B]}x(e)+\frac{\varepsilon\cdot|B|}{2}.$

Moreover, if $\sum_{e\in E}x(e)\geqslant(1-\varepsilon)\cdot\mu(G)$, then with
a constant probability, we have, that $\vec{y}$ satisfies:

$\displaystyle\sum_{e\in E}y(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in
E}x(e).$ (3)

The above lemma essentially states that with a constant probability there is a
fractional matching $\vec{y}\subseteq\text{supp}(S)$ with $\sum_{e\in
E}y(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}x(e)$ satisfying small odd set
constraints.

###### Proof.

We first define a flow $\vec{y}$ on the support of $S$. Then, we show _a_) and
_b_) are satisfied for $\vec{y}$ with high probability. Finally, we
conditioned on _a_) and _b_), we show that $\sum_{e\in
E}y(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}x(e)$ with a constant
probability. Let $S_{v}=\left\\{e\ni v\mid x(e)<\frac{1}{d}\right\\}$. We now
define the flow as follows, for all $v\in V$, $e\in S_{v}$,

$\displaystyle y(e)=\frac{1}{d}\cdot\mathbb{1}_{e}\cdot(1-4\varepsilon)$

On the other hand, for $e\notin S_{v}$, we let $y(e)=x(e)$. We first show
_a_). Consider an edge $e\in S_{v}$, from 6, we have,

$\displaystyle
x(e)\cdot(1-3\varepsilon)\leqslant\operatorname*{{\mathbb{E}}}\left[y(e)\right]\leqslant
x(e)\cdot(1-2\varepsilon)$

Consequently, for a vertex $v$, we have,

$\displaystyle(1-3\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)\leqslant\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
S_{v}}y(e)\right]\leqslant(1-2\varepsilon)\cdot\sum_{e\in S_{v}}x(e)$

Note that to show concentration, it is sufficient to consider the set of edges
$S_{v}$. This is because of 6. Next, observe that for $e\in S_{v}$,
$y(e)\leqslant\frac{1}{d}$. Finally, by 10, we have, that
$\left\\{y(e)\right\\}_{e\in S_{v}}$ are negatively associated. Thus, by
Chernoff bound (14), we have, the following upper tail bound by picking
$\mu_{H}=(1-2\varepsilon)\cdot\sum_{e\in S_{v}}x(e)$, and
$\delta=\frac{\varepsilon}{(1-2\varepsilon)\cdot\sum_{e\in S_{v}}x(e)}$,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\sum_{e\in
S_{v}}y(e)\geqslant(1-2\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)+\varepsilon\right)$
$\displaystyle\leqslant\exp\left(-\frac{\left(\frac{\varepsilon}{(1-2\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)}\right)^{2}\cdot\left((1-2\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)\right)}{\left(3+\frac{\varepsilon}{(1-2\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)}\right)\cdot\frac{\varepsilon^{4}}{\log n}}\right)$
$\displaystyle=O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon}}}}\right)$

Similarly, substituting $\mu_{L}=(1-3\varepsilon)\cdot\sum_{e\in S_{v}}x(e)$
and $\delta=\frac{\varepsilon}{(1-3\varepsilon)\cdot\sum_{e\in S_{v}}x(e)}$,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\sum_{e\in
S_{v}}y(e)\leqslant(1-3\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)-\varepsilon\right)$
$\displaystyle\leqslant\exp\left(-\frac{\left(\frac{\varepsilon}{(1-3\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)}\right)^{2}\cdot\left((1-3\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)\right)}{\left(2+\frac{\varepsilon}{(1-3\varepsilon)\cdot\sum_{e\in
S_{v}}x(e)}\right)\cdot\frac{\varepsilon^{4}}{\log n}}\right)$
$\displaystyle=O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon}}}}\right)$

Finally, since $\sum_{e\in E_{v}\setminus
S_{v}}y(e)=(1-4\varepsilon)\cdot\sum_{e\in E_{v}\setminus S_{v}}x(e)$ for all
$v\in V$, we can conclude that with high probability,

$\displaystyle(1-4\varepsilon)\cdot\sum_{e\in
E_{v}}x(e)-\varepsilon\leqslant\sum_{e\in
E_{v}}y(e)\leqslant(1-3\varepsilon)\cdot\sum_{e\in E_{v}}x(e)-\varepsilon$

We now show _b_). Consider an odd set $B$, and let
$M^{\prime}_{1},\cdots,M^{\prime}_{k}$ denote the set of matchings $G[B]$ is
split up into. As before, we can consider only matchings in $G_{i}$, where
$d<(1+\varepsilon)^{i-1}$ due to 13.

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
G[B]}y(e)\right]=\operatorname*{{\mathbb{E}}}\left[\sum_{i=1}^{k}y(M^{\prime}_{i})\right]\leqslant\sum_{i=1}^{k}x(M^{\prime}_{i})\cdot(1-4\varepsilon)\leqslant\sum_{e\in
G[B]}x(e)\cdot(1-4\varepsilon)$

Similarly, we have,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
G[B]}y(e)\right]=\operatorname*{{\mathbb{E}}}\left[\sum_{i=1}^{k}y(M^{\prime}_{i})\right]\geqslant\sum_{e\in
G[B]}x(e)\cdot(1-5\varepsilon)$

Additionally, observe that $y(M^{\prime}_{i})$ can take value at most
$\frac{|M^{\prime}_{i}|}{d}\leqslant\frac{|B|-1}{2\cdot d}$. Thus, using
$\mu_{H}=\sum_{e\in G[B]}x(e)\cdot(1-4\varepsilon)$,
$\delta=\frac{\varepsilon\cdot(|B|-1)}{\sum_{e\in
G[B]}x(e)\cdot(1-4\varepsilon)}$, we have,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\sum_{e\in
G[B]}y(e)\geqslant\sum_{e\in
G[B]}x(e)\cdot(1-4\varepsilon)+\frac{\varepsilon\cdot(|B|-1)}{2}\right)$
$\displaystyle\leqslant\exp\left(-\frac{\left(\frac{-\varepsilon^{2}\cdot(|B|-1)^{2}}{4\cdot\left(\sum_{e\in
G[B]}x(e)\cdot(1-4\varepsilon)\right)^{2}}\right)\cdot(1-4\varepsilon)\cdot\sum\limits_{e\in
G[B]}x(e)}{\left(3+\frac{\varepsilon}{\sum_{e\in
G[B]}x(e)\cdot(1-3\varepsilon)}\right)\cdot\frac{|B|-1}{2\cdot d}}\right)$
$\displaystyle=O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon^{2}}}}}\right).$

Using the fact that $\sum_{e\in G[B]}x(e)\leqslant\frac{|B|-1}{2}$ and
$d\geqslant\nicefrac{{\log n}}{{\varepsilon^{4}}}$, we have the second
equality. Finally, we union bounding over all odd sets of size at most
$\frac{1}{\varepsilon}$, we have the upper bound. For the lower bound,
consider $\mu_{L}=(1-5\varepsilon)\cdot\sum_{e\in G[B]}x(e)$, and
$\delta=\frac{\varepsilon\cdot(|B|-1)}{(1-4\varepsilon)\sum_{e\in G[B]}x(e)}$,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\sum_{e\in
G[B]}y(e)\geqslant\sum_{e\in
G[B]}x(e)\cdot(1-4\varepsilon)-\frac{\varepsilon\cdot(|B|-1)}{2}\right)$
$\displaystyle\leqslant\exp\left(-\frac{\left(\frac{-\varepsilon^{2}\cdot(|B|-1)^{2}}{4\cdot\left(\sum_{e\in
G[B]}x(e)\cdot(1-4\varepsilon)\right)^{2}}\right)\cdot(1-4\varepsilon)\cdot\sum\limits_{e\in
G[B]}x(e)}{\left(3+\frac{\varepsilon}{\sum_{e\in
G[B]}x(e)\cdot(1-3\varepsilon)}\right)\cdot\frac{|B|-1}{2\cdot d}}\right)$
$\displaystyle\leqslant
O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon}}^{2}}}\right).$

Taking a union bound over all odd sets of size at most
$\frac{1}{\varepsilon}$, we have _b_). We now move on to proving Equation 3.
First, let $\mathcal{E}_{b,c}$ denote the event that _a_) and _b_) occur. We
have,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\mathcal{E}_{b,c}\right)\geqslant
1-O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon^{2}}}}}\right).$

Additionally, we have,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
E}y(e)\right]\geqslant(1-4\varepsilon)\cdot\sum_{e\in E}x(e).$

By law of total probability, we have,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
E}y(e)\Bigm{|}\mathcal{E}_{b,c}\right]\cdot\operatorname*{\textnormal{Pr}}\left(\mathcal{E}_{b,c}\right)+\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
E}y(e)\Bigm{|}\lnot\mathcal{E}_{b,c}\right]\cdot\operatorname*{\textnormal{Pr}}\left(\lnot\mathcal{E}_{b,c}\right)$
$\displaystyle\geqslant(1-4\varepsilon)\cdot\sum_{e\in E}x(e)$
$\displaystyle\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
E}y(e)\Bigm{|}\mathcal{E}_{b,c}\right]+n^{2}\cdot
O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon}}}}\right)$
$\displaystyle\geqslant(1-4\varepsilon)\cdot\sum_{e\in E}x(e)$

Thus, we have, $\operatorname*{{\mathbb{E}}}\left[\sum_{e\in
E}y(e)\Bigm{|}\mathcal{E}_{b,c}\right]\geqslant(1-5\varepsilon)\cdot\sum_{e\in
E}x(e)$. Let $\vec{x}^{*}\in\mathcal{M}_{G}$ be any optimum fractional
matching. Conditioned on $\mathcal{E}_{b,c}$, we have
$\vec{y}\in\mathcal{M}_{G,\varepsilon}$. Thus, from 4, we have, $\sum_{e\in
E}y(e)\leqslant(1+\varepsilon)\cdot\sum_{e\in E}x^{*}(e)$. Therefore, the
random variable $(1+\varepsilon)\cdot\sum_{e\in E}x^{*}(e)-y(e)$ is non-
negative, and moreover, by our assumption that $\sum_{e\in
E}x(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}x^{*}(e)$, we have,

$\displaystyle\operatorname*{{\mathbb{E}}}\left[(1+\varepsilon)\cdot\sum_{e\in
E}x^{*}(e)-y(e)\Bigm{|}\mathcal{E}_{b,c}\right]\leqslant
4\varepsilon\cdot\sum_{e\in E}x^{*}(e)$

Thus, by Markov inequality, we have,

$\displaystyle\operatorname*{\textnormal{Pr}}\left((1+\varepsilon)\cdot\sum_{e\in
E}x^{*}(e)-y(e)\geqslant 8\varepsilon\cdot\sum_{e\in
E}x^{*}(e)\Bigm{|}\mathcal{E}_{b,c}\right)\leqslant\frac{1}{2}$

This implies,

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\sum_{e\in
E}y(e)\leqslant(1-8\varepsilon)\cdot\sum_{e\in
E}x^{*}(e)\Bigm{|}\mathcal{E}_{b,c}\right)\leqslant\frac{1}{2}$

Thus, the total probability of either _a_),_b_), or Equation 3 not happening
is upper bounded as follows:

$\displaystyle\operatorname*{\textnormal{Pr}}\left(\lnot\mathcal{E}_{b,c}\right)+\operatorname*{\textnormal{Pr}}\left(\sum_{e\in
E}y(e)\leqslant(1-8\varepsilon)\cdot\sum_{e\in E}x^{*}(e)\ \Bigm{|}\
\mathcal{E}_{b,c}\right)\leqslant\frac{1}{2}+O\left(\frac{1}{n^{\nicefrac{{1}}{{\varepsilon}}^{2}}}\right).$

This proves our lemma. ∎

######  Corollary 16.

Let $\vec{x}\in\mathcal{M}_{G}$ be such that $\sum_{e\in
E}x(e)\geqslant(1-\varepsilon)\cdot\mu(G)$. Let $S$ be the output of
Sparsification($G,\vec{x},\varepsilon$). Then,
$\mu(S)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}x(e)$.

###### Proof.

Note that by Equation 3, we know that there is
$\vec{y}\subseteq\text{supp}(S)$ such that $\sum_{e\in
E}y(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in e}x(e)$. Additionally, from 15
_a_) we know that for every vertex $v$,

$\displaystyle\sum_{e\in E_{v}}y(e)\leqslant(1-\varepsilon)\cdot\sum_{e\in
E_{v}}x(e)+\varepsilon\leqslant 1$

Finally, we know that for any odd set $B$ with
$|B|\leqslant\nicefrac{{1}}{{\varepsilon}}$,

$\displaystyle\sum_{e\in G[B]}y(e)\leqslant(1-2\varepsilon)\cdot\sum_{e\in
G[B]}x(e)+\frac{\varepsilon\cdot|B|}{2}\leqslant(1-2\varepsilon)\cdot\frac{|B|-1}{2}+\frac{\varepsilon\cdot(|B|-1)}{2}\leqslant(1-\varepsilon)\cdot\frac{|B|-1}{2}$

Thus, we have, $\frac{\vec{y}}{1+\varepsilon}\in\mathcal{M}_{G}$. ∎

Next, we show two properties of the Algorithm 1 that [Waj20] gives in his
paper.

######  Observation 17.

[Waj20] Let $\vec{x}\in\mathcal{M}_{G}$ be a fractional matching of $G$, and
let $S$ be the output of Sparsification($G,\vec{x},\varepsilon$). Then,
$|E(H)|=O(d\cdot\mu(G)\cdot\log\frac{n}{\varepsilon})$.

######  Observation 18.

[Waj20] Given a dynamic fractional matching $\vec{x}$, Algorithm 1 maintains a
sparsifier $S$ of $\vec{x}$ satisfying 15 with update time $O(\mbox{\rm
poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$. Moreover, the guarantees of
Algorithm 1 hold against an adaptive adversary.

######  Lemma 19.

[DP14] There is a static algorithm, Static-Match() that computes a
$(1-\varepsilon)$-approximation to the maximum weight matching in
$O(m\cdot\nicefrac{{1}}{{\varepsilon}}\cdot\log\nicefrac{{1}}{{\varepsilon}})$
time.

######  Theorem 20.

There is a randomized dynamic rounding algorithm for general graphs with
amortized update time $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$. The algorithm is robust to adaptive
adversaries.

###### Proof.

Suppose $\vec{x}$ is the initial fractional matching with $\sum_{e\in
E}x(e)\geqslant(1-\varepsilon)\cdot\textsf{mwm}(G)$, then Algorithm 1
initializes the sparsifier in $O(m\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}})$ total time, and outputs the graph $S$. From
17, we know that $|E(S)|=O(d\cdot\mu(G)\cdot\log\frac{n}{\varepsilon})$. Thus,
we can run a static matching algorithm (say, [DP14]) to get a matching $M$
with $|M|\geqslant(1-\varepsilon)\cdot\mu(S)$. By 15 and 4, we have,

$\displaystyle\mu(S)\geqslant(1-\varepsilon)^{2}\sum_{e\in
E}x(e)\geqslant(1-\varepsilon)^{2}\cdot\mu(G)$

Now, we have to argue how the rounding algorithm deals with updates to the
input, that is, the fractional matching. Suppose the input fractional matching
$\vec{x}$ is modified. Then, note that by 18, in $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$ time, we can update the sparsifier $S$ to
reflect the change in the fractional matching. As for the integral matching
$M$, if the deleted edge $e$ is in $M$, then we remove it from $M$. If at any
point, $|M|\leqslant(1-2\cdot\varepsilon)\cdot\sum_{e\in E}x(e)$, then we
recompute $M$ by running [DP14] on $S$. The amortized time now, will be
$O(\mbox{\rm poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$, since we waited
for at least $\varepsilon\cdot\mu(G)$ updates before recomputing the matching.
The runtime of [DP14] is $O(d\cdot\mu(G)\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$ by 17. Finally, Algorithm 1 is robust to
adaptive adversaries, and [DP14] is a deterministic algorithm. Consequently,
the rounding algorithm is robust to adaptive adversaries. ∎

##  3 Application

In this section, our goal will be to show the following theorem.

######  Theorem 21.

There is a randomized fully adaptive algorithm maintaining a
$(1-\varepsilon)$-approximate integral weighted matching in a decremental
graph with amortized update time
$\tilde{O}(\varepsilon^{-41}+\frac{n^{2}}{m}\cdot\varepsilon^{-6})$.

In their work, [CST23] proved the same theorem, but with guarantees against an
output-adaptive adversary. In this section, we will strengthen this to a fully
adaptive adversary. Our main tool will be as in the case of [CST23], to use
the _entropy regularized matching_. Their proof strategy was as follows:

  1. 1.

They first consider the sparsification algorithm $\mathcal{A}$ of [ACC+18],
which is used to round unweighted fractional matchings. They showed that
$\mathcal{A}$ output a sparsifier $S$ which was also a degree sparsifier. A
degree sparsifier is a subgraph, which satisfies a stronger version of 22.
This algorithm is robust against output-adaptive adversaries.

  2. 2.

Next, they considered the _modified entropy regularized matching_ $\vec{x}$
(see 34) and showed the following:

    1. (a)

We have, $\sum_{e\in E}x(e)\cdot
w(e)\geqslant(1-\varepsilon)\cdot\textsf{mwm}(G)$.

    2. (b)

When $\vec{x}$ is fed into $\mathcal{A}$, then the sparsifier $S$ output by
the algorithm not only preserves most of its weight.

    3. (c)

The fractional matching $\vec{x}$ can be computed in $O(m\cdot\mbox{\rm
poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$ time.

They combine all of these facts to show the output adaptive version of 21.

We follow a similar strategy: we show the sparsifier output by Algorithm 1 is
a weak-degree sparsifier. We consider _entropy regularized matching_ problem,
and show that when $\vec{x}$ is fed into Sparsification(), then most of its
weight is preserved. Now, since Sparsification() is fully-adaptive, we are
able to prove a stronger version of the corresponding theorem of [CST23]. In
the subsequent section, we will start by giving the definition of a weak
degree sparsifier and show Sparsification() outputs a graph satisfying these
properties.

###  3.1 Weak $\varepsilon$-degree Sparsifier

We consider the modified definition of a degree sparsifier from [CST23].

######  Definition 22.

[Weak $\varepsilon$-degree sparsifier] Suppose $\vec{x}$ is a fractional
matching of $G$, then $H$ is an $s$-sparse, weak $\varepsilon$-degree
sparsifier of $G$ if $|H|\leqslant s\cdot\sum_{e\in E}x(e)$, and moreover,
there exists a fractional matching $x^{(H)}\in\mathcal{M}_{G}$ supported on
$H$, such that:

  1. 1.

For all $v\in V$, we have, $x^{H}(v)\geqslant x(v)-\varepsilon$,

  2. 2.

For all odd sets $B\in\mathcal{O}^{\varepsilon}_{G}$, we have, $\sum_{e\in
G[B]}x^{H}(e)\geqslant\sum_{e\in G[B]}x(e)-\varepsilon\cdot\frac{|B|-1}{2}$,
and

  3. 3.

If $\sum_{e\in E}x(e)\geqslant(1-\varepsilon)\cdot\mu(G)$, then $\sum_{e\in
E}x^{H}(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}x(e)$,

######  Corollary 23.

From 15, we can deduce that if $\vec{x}$ is input to Sparsification() with
parameter $\varepsilon$ and $d\geqslant\frac{\log n}{\varepsilon^{4}}$, then
the output $S$ is a $O(\log n)$-sparse, weak $\varepsilon$-degree sparsifier
of $G$ with probability at least $0.5$.

In the subsequent section we define the fractional matching problem we will be
solving.

###  3.2 Entropy Regularized Matching

The next part is, to show the properties of entropy regularized matching
problem. Note that [CST23] considered the modified entropy regularized
matching problem, given in 34. We consider a different version due to the fact
that our sparsifier is now weaker, so to prove the required guarantees, we
need to solve a slightly different version of the problem than [CST23].

######  Definition 24.

The _entropy regularized matching_ problem is the problem of finding a
fractional matching $\vec{x}\in\mathcal{M}_{G,\varepsilon}$, maximizing the
following objective function:

$\displaystyle g(\vec{x})=\sum_{e\in E}x(e)\cdot w(e)+\delta\cdot\sum_{e\in
E}w(e)\cdot x(e)\cdot\log\frac{\gamma}{w(e)\cdot x(e)}$

######  Remark 25.

Note that [CST23] solve the same objective function as in 24, but over the
polytope $\mathcal{M}_{G}$.

The next observation is a modified version of Lemma 4.8 in [CST23].

######  Observation 26.

If $\delta\leqslant\nicefrac{{\varepsilon}}{{8\cdot\log nW}}$ and
$\textsf{mwm}(G)\leqslant\gamma\leqslant\textsf{mwm}(G)\cdot n\cdot W$, then
and suppose $\vec{x}^{*}\in\mathcal{M}_{G,\varepsilon}$ is the optimal
solution to $g$, then
$g(\vec{x^{*}})\leqslant(1+\varepsilon)\cdot\textsf{mwm}(G)$.

Let $Z^{\delta}_{E,\gamma}$ denote the optimal value of the entropy
regularized matching over $\mathcal{M}_{G,\varepsilon}$. Moreover, let
$\vec{x}^{*}\in\mathcal{M}_{G,\varepsilon}$ be the unique matching realizing
this value. Let $w^{*}=\sum_{e\in E}w(e)\cdot x^{*}(e)$. We have the following
lemma, which is an adaptation of Lemma 6.23 of [CST23].

######  Lemma 27.

For an edge $e=(u,v)$ let
$\mathcal{O}_{\varepsilon}^{e}=\left\\{B\in\mathcal{O}_{\varepsilon}\bigm{|}e\in
G[B]\right\\}$. There exist a pair of vertex duals $\vec{y}$ and odd set duals
$\vec{z}$ such that for every edge $e$, we have,

$\displaystyle x^{*}(e)=2^{\frac{1}{\delta}-1-\frac{s_{e}}{\delta\cdot
w(e)}+\log\frac{\gamma}{w(e)}},$

where $s_{e}=y_{u}+y_{v}+\sum_{B\in\mathcal{O}^{e}_{\varepsilon}}z_{B}$ for
$e=(u,v)$. Additionally, the optimal objective value $Z^{\delta}_{E,\gamma}$
satisfies

$\displaystyle Z^{\delta}_{E,\gamma}=\delta\cdot\sum_{e\in E}w(e)\cdot
x^{*}(e)+\sum_{v\in
V}y_{v}+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\frac{|B|-1}{2}.$

###### Proof.

We consider the Lagrangian of the problem defined in 24:

$\displaystyle L(\vec{x},\vec{y},\vec{z},\vec{r})=g(\vec{x})+\sum_{v\in
V}y_{v}\cdot(1-\sum_{e\ni
v}x(e))+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\left(\left\lfloor\frac{|B|}{2}\right\rfloor-\sum_{e\in
G[B]}x(e)\right)+\sum_{e\in E}x(e)\cdot r_{e}.$

Suppose $(\vec{y},\vec{z},\vec{r})$ is the optimal solution of the dual of the
problem defined in 24. Then by the KKT Stationarity Condition, we have, that
the optimal primal solution is:

$\displaystyle x^{*}(e)=2^{\frac{1}{\delta}-1-\frac{s_{e}}{\delta\cdot
w(e)}+\frac{r_{e}}{\delta\cdot w(e)}+\log\frac{\gamma}{w(e)}}$

Since $x^{*}(e)>0$ for all $e$, using complementary slackness, we have
$r_{e}=0$ for all $e$. This proves the first part of the claim. Additionally,
the _entropy regularized matching problem_ satisfies Slater’s condition, and
consequently has strong duality. Therefore,
$Z_{E,\gamma}^{\delta}=L(\vec{x}^{*},\vec{y},\vec{z},\vec{r})$. By
substituting $(\vec{x}^{*},\vec{y},\vec{z},\vec{r})$ into $L$, we have,

$\displaystyle Z^{\delta}_{E,\gamma}=\delta\cdot\sum_{e\in E}w(e)\cdot
x^{*}(e)+\sum_{v\in
V}y_{v}+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\frac{|B|-1}{2}$

∎

Similarly, we have the following corollary, again adapted from [CST23].

######  Corollary 28.

It holds that $Z^{\delta}_{E,\gamma}\geqslant\sum_{v\in
V}y_{v}+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\frac{|B|-1}{2}$.

The next observation of [CST23] states that the optimal dual solution
$(\vec{y},\vec{z})$ corresponding to entropy regularized matching over
$\mathcal{M}_{G,\varepsilon}$ is also a fractional cover for all edges. Given
a fractional matching $\vec{x}$, we define $E_{\varepsilon}(x)=\left\\{e\in
E\mid x(e)\geqslant\frac{\varepsilon}{3\cdot n}\right\\}$.

######  Lemma 29.

Let $\varepsilon>0$, let $w^{*}\leqslant\gamma\leqslant m\cdot w^{*}$, and
suppose $\delta\leqslant\frac{\varepsilon}{8\cdot\log\left(\frac{n^{4}\cdot
W}{\varepsilon}\right)}$. Let $\vec{y},\vec{z}$ be the optimal dual solution
to the entropy regularized matching problem over
$\mathcal{M}_{G,\varepsilon}$. Then, for every edge $e\in E$,
$s_{e}\geqslant(1-\varepsilon)\cdot w(e)$. Moreover, for every edge $e\in
E_{\varepsilon}(x^{*})$, $s_{e}\leqslant(1+\varepsilon)\cdot w(e)$.

###### Proof.

To prove the first part, we invoke 27, and the fact that $x^{*}(e)\leqslant
1$, we have,

$\displaystyle\frac{1}{\delta}-1-\frac{s_{e}}{\delta\cdot
w(e)}+\log\frac{\gamma}{w(e)}$ $\displaystyle\leqslant 0$ $\displaystyle
w(e)-\delta\cdot w(e)+\delta\cdot w(e)\cdot\log\frac{\gamma}{w(e)}$
$\displaystyle\leqslant s_{e}$ $\displaystyle
w(e)\cdot(1-\varepsilon)\leqslant s_{e}$

The last inequality follows from the fact that $\gamma\geqslant w(e)$. For
$e\in E_{\varepsilon}(x^{*})$, we have:

$\displaystyle\log\frac{\varepsilon}{3n}$
$\displaystyle\leqslant\frac{1}{\delta}-1-\frac{s_{e}}{\delta\cdot
w(e)}+\log\frac{\gamma}{w(e)}$ $\displaystyle s_{e}$ $\displaystyle\leqslant
w(e)\cdot(1-\delta)+\delta\cdot w(e)\log\frac{\gamma}{w(e)}-\delta\cdot
w(e)\cdot\log\frac{\varepsilon}{n}$
$\displaystyle\leqslant(1+\varepsilon)\cdot w(e)$

This proves our claim. ∎

Similar to [CST23] did for modified entropy regularization problem, we prove
the following lemma for the unmodified version.

######  Lemma 30.

Let $\varepsilon>0$. Consider any fractional matching
$\vec{x}\in\mathcal{M}_{G,\varepsilon}$, $w^{*}\leqslant\gamma\leqslant m\cdot
w^{*}$, and $\delta\leqslant\frac{\varepsilon}{8\log\left(\frac{n^{4}\cdot
W}{\varepsilon}\right)}$, we have,

$\displaystyle\sum_{e\in E_{\varepsilon}(x)}x(e)\cdot w(e)\geqslant\sum_{e\in
E}x(e)\cdot w(e)-\varepsilon\cdot Z^{\delta}_{E,\gamma}.$

###### Proof.

For edges in $E\setminus E_{\varepsilon}(x)$, we have,

$\displaystyle(1-\varepsilon)\sum_{e\in E\setminus
E_{\varepsilon}(x)}w(e)\cdot x(e)$ $\displaystyle\leqslant\sum_{e\in
E\setminus E_{\varepsilon}(x)}s_{e}\cdot x(e)$ (From 29)
$\displaystyle=\sum_{v\in V}y_{v}\cdot\sum_{e\in E_{v}\setminus
E_{\varepsilon}(x)}x(e)+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\sum_{e\in
G[B]\setminus E_{\varepsilon}(x)}x(e)$
$\displaystyle\leqslant\varepsilon\cdot\sum_{v\in
V}y_{v}+\varepsilon\cdot\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\frac{|B|-1}{2}$
$\displaystyle\leqslant\varepsilon\cdot Z^{\delta}_{E,\gamma}$ (From 28)

The second last inequality follows from the following line of reasoning:

$\displaystyle\sum_{e\in E_{v}\setminus E_{\varepsilon}(x)}x(e)$
$\displaystyle\leqslant\sum_{e\in E_{v}\setminus
E_{\varepsilon}(x)}\frac{\varepsilon}{n}\leqslant\varepsilon,\text{ and}$
$\displaystyle\sum_{e\in G[B]\setminus E_{\varepsilon}(x)}x(e)$
$\displaystyle\leqslant\frac{\varepsilon}{n}\cdot|B|\cdot\frac{|B|-1}{2}\leqslant\varepsilon\cdot\frac{|B|-1}{2}$

This shows our claim. ∎

######  Lemma 31.

Suppose $\varepsilon>0$, $w^{*}\leqslant\gamma\leqslant m\cdot\gamma$, and
$\delta\leqslant\frac{\varepsilon}{\log\left(\frac{n^{4}\cdot
W}{\varepsilon}\right)}$, suppose $\vec{x}\in\mathcal{M}_{G,\varepsilon}$
with,

$\displaystyle\sum_{e\in E}w(e)\cdot|x(e)-x^{*}(e)|\leqslant\varepsilon\cdot
Z^{\mu}_{E,\gamma},$

for any subset $E^{\prime}\subset E$ such that,

$\displaystyle\sum_{e\in E^{\prime}}w(e)\cdot
x(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in E}w(e)\cdot x(e),$

then suppose $\vec{f}$ is $\vec{x}$ restricted to $E_{\varepsilon}(x)$ and let
$S$ be the output of Sparsification($\vec{f},\varepsilon,d$). Then, $S$
satisfies,

$\displaystyle\textsf{mwm}(S)\geqslant(1-\varepsilon)\cdot\sum_{e\in
E^{\prime}}w(e)\cdot x(e).$

###### Proof.

Let $S$ denote the output of $\textsc{Sparsification}(\vec{y},\varepsilon,d)$.
Then, by 23, we know that $\vec{x}^{S}$ is a $O(\log n)$-sparse, weak
$\varepsilon$-degree sparsifier. Then, we want to show the following:

$\displaystyle\sum_{e\in E^{\prime}\cap E_{\varepsilon}(x)}w(e)\cdot
x^{S}(e)\geqslant(1-\varepsilon)\cdot\sum_{e\in E^{\prime}}w(e)\cdot x(e)$

Let $\vec{x}^{*}\in\mathcal{M}_{G,\varepsilon}$ be the optimal for the problem
defined in 24. Then, we have the following two observations from 30:

$\displaystyle\sum_{e\in E^{\prime}\setminus E_{\varepsilon}(x)}w(e)\cdot
x(e)$ $\displaystyle\leqslant\varepsilon\cdot
Z^{\delta}_{E^{\prime},\gamma}\leqslant 2\cdot\varepsilon\cdot
Z^{\delta}_{E,\gamma}$ $\displaystyle\sum_{e\in E^{\prime}\setminus
E_{\varepsilon}(x^{*})}w(e)\cdot x^{*}(e)$
$\displaystyle\leqslant\varepsilon\cdot
Z^{\delta}_{E^{\prime},\gamma}\leqslant 2\cdot\varepsilon\cdot
Z^{\delta}_{E,\gamma}$

Using the premise of the lemma, we have,

$\displaystyle\sum_{e\in E^{\prime}\setminus E_{\varepsilon}(x^{*})}w(e)\cdot
x(e)$ $\displaystyle\leqslant\sum_{e\in E^{\prime}\setminus
E_{\varepsilon}(x^{*})}w(e)\cdot x^{*}(e)+\sum_{e\in E^{\prime}\setminus
E_{\varepsilon}(x^{*})}w(e)\cdot|x(e)-x^{*}(e)|$ $\displaystyle\leqslant
3\cdot\varepsilon\cdot Z^{\delta}_{E^{\prime},\gamma}$

Consequently, we have,

$\displaystyle\sum_{e\in E^{\prime}\setminus E_{\varepsilon}(\vec{x}^{*})\cap
E_{\varepsilon}(\vec{x})}w(e)\cdot x(e)\leqslant 4\cdot\varepsilon\cdot
Z^{\delta}_{E^{\prime},\gamma}.$ (4)

We now focus on proving the main statement mentioned above. We define
$E^{\prime}_{\varepsilon}(\vec{x}^{*})\coloneqq
E_{\varepsilon}(\vec{x}^{*})\cap E^{\prime}$, and similarly we define
$E^{\prime}_{\varepsilon}(\vec{x})$. Additionally, define
$E^{\prime}_{\varepsilon}(v)=E_{v}\cap E^{\prime}_{\varepsilon}(\vec{x})\cap
E^{\prime}_{\varepsilon}(\vec{x}^{*})$, and
$G^{\prime}_{\varepsilon}[B]=G[B]\cap E^{\prime}_{\varepsilon}(\vec{x})\cap
E^{\prime}_{\varepsilon}(\vec{x}^{*})$.

$\displaystyle\sum_{e\in E^{\prime}}w(e)\cdot x^{S}(e)$
$\displaystyle\geqslant\sum_{e\in E^{\prime}_{\varepsilon}(\vec{x})\cap
E^{\prime}_{\varepsilon}(\vec{x}^{*})}w(e)\cdot x^{S}(e)$
$\displaystyle\geqslant(1-\varepsilon)\cdot\sum_{e\in
E^{\prime}_{\varepsilon}(\vec{x})\cap
E^{\prime}_{\varepsilon}(\vec{x}^{*})}s_{e}\cdot x^{S}(e)$ (From 29)
$\displaystyle\geqslant(1-\varepsilon)\cdot\sum_{v\in V}y_{v}\cdot\sum_{e\in
E^{\prime}_{\varepsilon}(v)}x^{S}(e)+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\sum_{e\in
G^{\prime}_{\varepsilon}[B]}x^{S}(e)$
$\displaystyle\geqslant(1-\varepsilon)\cdot\left(\sum_{v\in V}y_{v}\sum_{e\in
E^{\prime}_{\varepsilon}(v)}x(e)+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\sum_{e\in
G^{\prime}_{\varepsilon}[B]}x(e)\right)-\varepsilon\cdot\left(\sum_{v\in
V}y_{v}+\sum_{B\in\mathcal{O}_{\varepsilon}}z_{B}\cdot\frac{|B|-1}{2}\right)$
(From 23 and 22) $\displaystyle\geqslant(1-\varepsilon)\cdot\sum_{e\in
E^{\prime}_{\varepsilon}(\vec{x})\cap
E^{\prime}_{\varepsilon}(\vec{x}^{*})}w(e)\cdot x(e)-\varepsilon\cdot
Z^{\delta}_{E,\gamma}$ (From 28)
$\displaystyle\geqslant(1-\varepsilon)\cdot\sum_{e\in E^{\prime}}w(e)\cdot
x(e)-3\cdot\varepsilon\cdot Z^{\delta}_{E,\gamma}$ (From Equation 4)
$\displaystyle\geqslant(1-3\varepsilon)\cdot\sum_{e\in E^{\prime}}w(e)\cdot
x(e)$

∎

######  Fact 32.

Suppose $\vec{z}\in\mathcal{M}_{G,\varepsilon}$, and $\vec{x}^{*}$ be the
optimal solution to the _entropy regularized matching problem_ Then,

$\displaystyle g(\vec{z})\leqslant
g(\vec{x}^{*})-\frac{\delta}{\textsf{mwm}(G)}\cdot\left(\sum_{e\in
E}w(e)\cdot|z(e)-x^{*}(e)|\right)^{2}.$

######  Lemma 33.

Suppose $\vec{y}\in\mathcal{M}_{G,\varepsilon}$ is a
$(1-\varepsilon)$-approximate solution to the entropy regularization problem,
and $\vec{x}^{*}\in\mathcal{M}_{G,\varepsilon}$ is the optimal solution to the
entropy regularization problem. Then,

$\displaystyle\sum_{e\in E}w(e)\cdot|y(e)-x^{*}(e)|\leqslant\varepsilon\cdot
Z^{\delta}_{E,\gamma}$

###### Proof.

Observe that we have, $g(\vec{y})\geqslant(1-\varepsilon)\cdot
g(\vec{x}^{*})$. Consequently, we have,
$g(\vec{x}^{*})-g(\vec{y})\leqslant\varepsilon\cdot Z^{\delta}_{E,\gamma}$.
Then, combining the fact that $Z^{\delta}_{E,\gamma}\geqslant\textsf{mwm}(G)$
and 32, we have,

$\displaystyle\varepsilon\cdot Z^{\delta}_{E,\gamma}$
$\displaystyle\geqslant\frac{\delta}{\textsf{mwm}(G)}\cdot\left(\sum_{e\in
E}w(e)\cdot|z(e)-x^{*}(e)|\right)^{2}$ $\displaystyle\varepsilon\cdot
Z^{\delta}_{E,\gamma}$ $\displaystyle\geqslant\sum_{e\in
E}w(e)\cdot|z(e)-x^{*}(e)|$

∎

Thus, from 33 and 30, we have concluded the proof that the entropy regularized
fractional matching when fed into Sparsification() outputs a sparsifier $S$
that preserves most of its weight.

###  3.3 From Approximate Entropy Regularized Matching to Decremental Matching

In this section, show how to get decremental matching algorithms from
approximate entropy regularized matching. The proof is almost identical to
that given by [CST23]. We just state it here for completeness. We start with
the following definition, used by [CST23]:

######  Definition 34.

The modified entropy regularized matching problem is the problem of finding a
fractional matching $\vec{x}\in\mathcal{M}_{G}$, maximizing the following
objective function:

$\displaystyle g(\vec{x})=\sum_{e\in E}x(e)\cdot w(e)+\delta\cdot\sum_{e\in
E}w(e)\cdot x(e)\cdot\log\frac{\gamma}{w(e)\cdot x(e)}$

Let $Y^{\delta}_{E,\gamma}$ denote the optimal solution to this problem.

######  Observation 35.

We have, $Y^{\delta}_{E,\gamma}\geqslant
Z^{\delta}_{E,\gamma}\cdot(1-\varepsilon)$.

###### Proof.

Suppose $\vec{x}^{*}\in\mathcal{M}_{G,\varepsilon}$ realizes
$Z^{\delta}_{E,\gamma}$. From 4, we have,
$\vec{z}=\frac{\vec{x}^{*}}{1+\varepsilon}\in\mathcal{M}_{G}$. Thus, we have,

$\displaystyle Y^{\delta}_{E,\gamma}\geqslant
g(\vec{z})\geqslant(1-\varepsilon)\cdot g(\vec{x}^{*})\geqslant
Z^{\delta}_{E,\gamma}\cdot(1-\varepsilon).$

This proves the observation. ∎

The next lemma shows that we can compute an approximate solution to the
modified entropy maximization problem in $O(m\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$ time.

######  Lemma 36.

[CST23] For any $\varepsilon=\Omega(\nicefrac{{1}}{{\sqrt{n}}})$, there is a
randomized algorithm EntRegMatching() that give a
$(1-\varepsilon)$-approximation to the modified entropy regularized matching
problem in $O(m\cdot\varepsilon^{-6}+n\cdot\varepsilon^{-13})$ time.

Using the above lemma, we will show the following theorem:

See 21

We also need the following lemma, which states that the solution to the
_modified entropy regularized matching_ is a $(1-\varepsilon)$-approximation
to $\textsf{mwm}(G)$.

######  Lemma 37 ([CST23]).

For $\mu\leqslant\frac{\varepsilon}{\log n\cdot W}$ and
$\textsf{mwm}(G)\leqslant\gamma\leqslant n\cdot W\cdot\textsf{mwm}(G)$, let
$\vec{x}^{*}$ be the optimal solution to the _modified entropy regularized
matching_ problem, then we have,

$\displaystyle\sum_{e\in E}w(e)\cdot
x^{*}(e)\geqslant(1-\varepsilon)\cdot\textsf{mwm}(G).$

Similarly, suppose $\vec{x}$ is a $(1-\varepsilon)$-approximate solution to
the _modified entropy regularized matching_ problem, then we have,

$\displaystyle\sum_{e\in E}w(e)\cdot
x(e)+\varepsilon\cdot\textsf{mwm}(G)\geqslant(1-\varepsilon)\cdot
g(\vec{x}^{*})\geqslant(1-\varepsilon)\cdot\sum_{e\in E}w(e)\cdot
x^{*}(e)\geqslant(1-\varepsilon)^{2}\cdot\textsf{mwm}(G)$

In order to prove 21, we state the main algorithm, and then show its
correctness and runtime.

Algorithm 2 Decremental Matching

Input: $G$, weights $w$, and a precision parameter $\varepsilon>0$

1:procedure Initialize($G,E$)

2: Initialize $G\leftarrow G_{0}$ $\triangleright$ $G$ refers to the current
graph, and $G_{0}$ is the initial graph.

3: Initialize $E\leftarrow E_{0}$ $\triangleright$ $E$ refers to the current
edge set, and $E_{0}=E(G_{0})$.

4: CounterM$\leftarrow 0$$\triangleright$ Counts the total weight deleted from
$M$

5: CounterX$\leftarrow 0$$\triangleright$ Counts the total weight deleted from
$\vec{x}$

6:end procedure

7:procedure Rebuild

8: $\vec{y}\leftarrow$EntRegMatch($G,\varepsilon$)

9: Let $\vec{x}$ be $\vec{y}$ restricted to $E_{\varepsilon}(\vec{y})$.

10: $\mu^{*}\leftarrow\sum_{e\in E}w(e)\cdot x(e)$ $\triangleright$
$\mu^{*}\geqslant(1-\varepsilon)\cdot\textsf{mwm}(G)$

11:end procedure

12:procedure Round

13: $S\leftarrow\textsc{Sparsification}(\vec{x},\varepsilon)$

14: $M\leftarrow\textsc{Static-Match}(S,\varepsilon)$

15:end procedure

16:procedure Deletion($e$)

17: $E\leftarrow E\setminus e$

18: if $e\in\text{supp}(\vec{x})$ then

19: Delete $e$ from supp($\vec{x}$)

20: $\textsc{CounterX}\leftarrow\textsc{CounterX}+w(e)\cdot x(e)$

21: end if

22: if $\textsc{CounterX}\geqslant\varepsilon\cdot\mu^{*}$ then

23: Rebuild()

24: end if

25: if $e\in M$ then

26: $M\leftarrow M\setminus\left\\{e\right\\}$

27: $\textsc{CounterM}\leftarrow\textsc{CounterM}+1$

28: end if

29: if $\textsc{CounterM}\geqslant\varepsilon\cdot\mu^{*}$ then

30: $\textsc{CounterM}\leftarrow 0$

31: Round()

32: end if

33:end procedure

######  Lemma 38.

Algorithm 2 maintains an integral matching $M$ at all times such that
$w(M)\geqslant(1-\varepsilon)\cdot\textsf{mwm}(G)$.

###### Proof.

Note that from 36, we can conclude that the fractional matching $\vec{y}$
output by EntRegMatch($G,\varepsilon$) has the property that:

$\displaystyle g(\vec{y})\geqslant(1-\varepsilon)\cdot g(\vec{y}^{*}),$

where $\vec{y}^{*}\in\mathcal{M}_{G}$ is the optimal solution to the modified
entropy regularization problem. This satisfies the premise of 37.
Consequently, from that we can deduce:

$\displaystyle\sum_{e\in E}w(e)\cdot
y(e)\geqslant(1-\varepsilon)^{2}\cdot\textsf{mwm}(G).$

Note that $\vec{x}$ is $\vec{y}$ restricted to $E_{\varepsilon}(\vec{y})$.
Therefore, from 30 and 26, we can then conclude the following:

$\displaystyle\sum_{e\in E}w(e)\cdot x(e)\geqslant\sum_{e\in E}w(e)\cdot
y(e)-\varepsilon\cdot
Z^{\delta}_{E,\gamma}\geqslant(1-3\varepsilon)\cdot\textsf{mwm}(G)$

Additionally, note that the algorithm processes deletions, and rebuilds when
$\sum_{e\in E}w(e)\cdot x(e)$ has dropped by a $(1-\varepsilon)$ factor. Thus,
each time the algorithm is maintaining a fractional matching $\vec{x}$ such
that $\sum_{e\in E}w(e)\cdot
x(e)\geqslant(1-\varepsilon)^{3}\cdot\textsf{mwm}(G)$. Next, the algorithm
runs Sparsification($\vec{x},\varepsilon$) to compute a sparsifier $S$.
Observe $\vec{y}$ satisfies the premise of 33. Consequently, we have, 35,

$\displaystyle\sum_{e\in E}w(e)\cdot|y(e)-x^{*}(e)|\leqslant\varepsilon\cdot
Z^{\delta}_{E,\gamma}$

Note that we feed $\vec{x}$, which is $\vec{y}$ restricted to
$E_{\varepsilon}(\vec{y})$ into Sparsification(). Thus, from 31, we have,

$\displaystyle\textsf{mwm}(S)\geqslant(1-\varepsilon)\cdot\sum_{e\in
E}w(e)\cdot y(e)$

Therefore, from 19 we can conclude that the matching $M$ output by
$\textsc{Static-Match}(S,\varepsilon)$ has
$w(M)\geqslant\geqslant(1-\varepsilon)\cdot\textsf{mwm}(S)\geqslant(1-\varepsilon)^{2}\cdot\sum_{e\in
E}w(e)\cdot y(e)\geqslant(1-\varepsilon)^{3}\cdot\textsf{mwm}(G)$. Here, 37
gives us the last inequality. This shows the lemma. ∎

Now, we show the runtime, and for that we need the following lemma.

######  Lemma 39.

([CST23]) If EntRegMatch() returns a $(1-\varepsilon)$ approximate solution to
$g(\vec{x})$, then the Rebuild() will be called at most $O(\mbox{\rm
poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$ times before mwm($G$) drops from
at least $\mu^{*}$ to atmost $\mu^{*}\cdot(1-\varepsilon)$.

######  Lemma 40.

Algorithm 2 has an amortized updated time of $\tilde{O}\left(\mbox{\rm
poly}(\nicefrac{{1}}{{\varepsilon}})+\frac{n^{2}}{m}\cdot\mbox{\rm
poly}(\nicefrac{{1}}{{\varepsilon}})\right)$.

###### Proof.

First, observe the runtime of each of the procedures and each time they are
invoked:

  1. 1.

For the procedure Rebuild(), we can conclude from 36 that each time it is run
it takes time $\tilde{O}(m\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$. This procedure is called each time
CounterX increases to $\varepsilon\cdot\mu^{*}$ or $\sum_{e\in E^{*}}w(e)\cdot
x(e)$ has dropped by $(1-\varepsilon)$ amount. From 39, we can conclude
Rebuild($\vec{x},\varepsilon$) is called at most $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$ times. Thus, the total runtime of this
procedure over $m$ deletions is at most $O(m\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$. That is, till the matching weight drops
from $\mu^{*}$ to $1$.

  2. 2.

Next we consider the procedure Round(). Note that from 17 we can conclude that
$|E(S)|=O(n\cdot\mbox{\rm poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$.
Moreover, the time taken to maintain it is $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$. Thus, from 19 we can conclude that Static-
Match($S,\varepsilon$) and consequently, the procedure $\textsc{Round}()$ take
time $O(n\cdot\mbox{\rm poly}(\log n,\nicefrac{{1}}{{\varepsilon}}))$ each
time they are invoked. This is invoked each time CounterM drops by
$\varepsilon\cdot\mu^{*}$ amount. Since
$x(e)\geqslant\nicefrac{{\varepsilon}}{{n}}$ for all $e\in E$, this also
translates into the adversary deleting a weight of at least
$\nicefrac{{\varepsilon^{2}\cdot\mu^{*}}}{{n}}$ from the fractional matching
$\vec{x}$. Consequently, till before the next time Rebuild() is invoked,
Round() is invoked $O(\nicefrac{{n}}{{\varepsilon^{2}}})$ times. Since the
total number of times Rebuild() is called is at most $O(\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$, this implies that the total number of
times $\textsc{Round}()$ is called is at most $O(n\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$, and therefore, the total runtime
contributed by this procedure is $O(n^{2}\cdot\mbox{\rm poly}(\log
n,\nicefrac{{1}}{{\varepsilon}}))$.

  3. 3.

The other steps in the Deletion() procedure take $O(1)$ time per edge to
implement. So the total time over all updates is at most $O(m)$.

This concludes the proof. ∎

##  4 Acknowledgements

Thank you to David Wajc for numerous helpful email exchanges. Thank you to
Rishabh Dudeja, Madhusudhan Raman and Aditya Potukuchi for encouragement.

## References

  * [ABD22] Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja.  Decremental matching in general graphs.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 11:1–11:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [ACC+18] Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc.  Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 7:1–7:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [BCH20] Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger.  Deterministic dynamic matching in O(1) update time.  Algorithmica, 82(4):1057–1080, 2020.
  * [BGS20] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak.  Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1123–1134. IEEE, 2020.
  * [BHI15] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano.  Deterministic fully dynamic data structures for vertex cover and matching.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, page 785–804, USA, 2015. Society for Industrial and Applied Mathematics.
  * [BHN16] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  New deterministic approximation algorithms for fully dynamic matching.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 398–411, New York, NY, USA, 2016. Association for Computing Machinery.
  * [BHN17] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  Fully dynamic approximate maximum matching and minimum vertex cover in _O_(log${}^{\mbox{3}}$ _n_) worst case update time.  In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 470–489. SIAM, 2017.
  * [BK21] Sayan Bhattacharya and Peter Kiss.  Deterministic rounding of dynamic fractional matchings.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 27:1–27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [BK23] Joakim Blikstad and Peter Kiss.  Incremental (1-$\epsilon$)-approximate dynamic matching in o(poly(1/$\epsilon$)) update time.  In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 22:1–22:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [BKSW23] Sayan Bhattacharya, Peter Kiss, Aaron Sidford, and David Wajc.  Near-optimal dynamic rounding of fractional matchings in bipartite graphs.  CoRR, abs/2306.11828, 2023.
  * [CST23] Jiale Chen, Aaron Sidford, and Ta-Wei Tu.  Entropy regularization and faster decremental matching in general graphs.  CoRR, abs/2312.09077, 2023.
  * [DP09] Devdatt P. Dubhashi and Alessandro Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, 2009.
  * [DP14] Ran Duan and Seth Pettie.  Linear-time approximation for maximum weight matching.  Journal of the ACM (JACM), 61(1):1–23, 2014.
  * [JJST22] Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian.  Regularized box-simplex games and dynamic decremental bipartite matching.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 77:1–77:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [Kis22] Peter Kiss.  Deterministic dynamic matching in worst-case update time.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 94:1–94:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [Waj20] David Wajc.  Rounding dynamic matchings against an adaptive adversary.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 194–207, 2020.