# Rainbow Hamiltonicity in uniformly coloured perturbed graphs

Kyriakos Katsamaktsis  Department of Mathematics, University College London,
Gower Street, London WC1E 6BT, UK. Email<EMAIL_ADDRESS>Research supported by the Engineering and Physical Sciences Research Council
[grant number EP/W523835/1].  Shoham Letzter  Department of Mathematics,
University College London, Gower Street, London WC1E 6BT, UK. Email:
<EMAIL_ADDRESS>Research supported by the Royal Society.

###### Abstract

We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-
coloured randomly perturbed graph. We show that for every $\delta\in(0,1)$
there exists $C=C(\delta)>0$ such that the following holds. Let $G_{0}$ be an
$n$-vertex graph with minimum degree at least $\delta n$ and suppose that each
edge of the union of $G_{0}$, with the random graph $\mathbf{G}(n,C/n)$ on the
same vertex set, gets a colour in $[n]$ independently and uniformly at random.
Then, with high probability, $G_{0}\cup\mathbf{G}(n,C/n)$ has a rainbow
Hamilton cycle.

This improves a result of Aigner-Horev and Hefetz, who proved the same when
the edges are coloured uniformly in a set of $(1+\varepsilon)n$ colours.

##  1 Introduction

Given $\delta\in(0,1)$, let $\mathcal{G}_{\delta,n}$ be the collection of
graphs on vertex set $[n]$ with minimum degree at least $\delta n$.
Determining the minimum $\delta$ that guarantees that every member of
$\mathcal{G}_{\delta,n}$ contains a given spanning subgraph is a central theme
in extremal combinatorics. The prototypical example is Dirac’s theorem [12],
which says that the minimum $\delta$ such that every member of
$\mathcal{G}_{\delta,n}$ is Hamiltonian is $1/2$. On the other hand, one of
the main pursuits of probabilistic combinatorics is understanding the minimum
$p$ such that $\mathbf{G}(n,p)$, the binomial random graph on $[n]$ with edge
probability $p$, contains a given subgraph _with high probability_ 111 We say
that a sequence of events $(A_{n})_{n\in\mathbb{N}}$ holds _with high
probability_ if $\mathbf{P}\left[A_{n}\right]\rightarrow 1$ as
$n\rightarrow\infty$. . Following the breakthrough of Pósa [25], it was proven
in [20, 21] that $\mathbf{G}(n,p)$ is Hamiltonian with high probability, if it
has minimum degree at least $2$ with high probability, showing that the
threshold $p$ for Hamiltonicity is $(1+o(1))\log n/n$.

As an interpolation between the two models, Bohman, Frieze and Martin [8]
introduced the _perturbed graph_ model. Given a fixed $\delta>0$, this is
defined as $G_{0}\cup\mathbf{G}(n,p)$, where $G_{0}\in\mathcal{G}_{\delta,n}$,
i.e. this is the union of some graph on vertex set $[n]$ with minimum degree
at least $\delta n$, and the random graph $\mathbf{G}(n,p)$ on the same vertex
set. In [8] the authors showed that there exists $C$, depending only on
$\delta$, such that for all $G_{0}\in\mathcal{G}_{\delta,n}$, the perturbed
graph $G_{0}\cup\mathbf{G}(n,C/n)$ is with high probability Hamiltonian. That
is, for every graph with linear minimum degree, adding linearly many random
edges results in a graph that is with high probability Hamiltonian. This is
best possible for all $\delta\in(0,1/2)$ up to the value of $C$, since the
complete bipartite graph with parts of size $\delta n$ and $(1-\delta)n$
requires $\Omega(n)$ edges to be Hamiltonian. (When $\delta\geq 1/2$ no random
edges are needed, due to Dirac’s theorem.) By now there is a sizeable
literature on the perturbed model; see e.g. [4, 5, 22, 1, 2, 9, 10, 23].

In this paper we consider a rainbow variant of the above result. A subgraph
$H$ of an edge coloured graph $G$ is called _rainbow_ if no two edges of $H$
share a colour. For a finite set of colours $\mathcal{C}$, a graph $G$ is
_uniformly coloured_ in $\mathcal{C}$ if each edge of $G$ gets a colour in
$\mathcal{C}$ independently and uniformly at random. The problem of finding
rainbow subgraphs of uniformly coloured graphs is well studied, in particular
for $\mathbf{G}(n,p)$ [11, 14, 17, 13, 6]. The problem of finding rainbow
subgraphs in the uniformly coloured perturbed graph $G\sim
G_{0}\cup\mathbf{G}(n,p)$, where $G_{0}\in\mathcal{G}_{\delta,n}$, was first
considered more recently [2, 1, 4, 3, 5]. In particular, the problem of
containing a rainbow Hamilton cycle was first addressed by Anastos and Frieze
[5], who showed that if the number of colours is at least about $120n$, then
$G\sim G_{0}\cup\mathbf{G}(n,C/n)$ has with high probability a rainbow
Hamilton cycle, for $C$ depending only on $\delta$ and all
$G_{0}\in\mathcal{G}_{\delta,n}$. Aigner-Horev and Hefetz [3] improved this
result by showing that, at the same edge probability in the random graph,
$n+o(n)$ colours suffice. We prove that the optimal number of colours
suffices.

######  Theorem 1.1.

For any $\delta\in(0,1)$ there exists $C>0$ such that the following holds. For
$G_{0}\in\mathcal{G}_{\delta,n}$, let $G\sim G_{0}\cup\mathbf{G}(n,C/n)$ be
uniformly coloured in $[n]$. Then with high probability $G$ contains a rainbow
Hamilton cycle.

As explained above, our result has the optimal edge probability, up to the
dependence of $C$ on $\delta$, for $\delta\in(0,1/2)$.

The paper is structured as follows. In Section 2 we sketch the proof of
Theorem 1.1. In Section 3 we prove Theorem 1.1 assuming Lemma 3.1, the key
lemma of the paper. Next in Section 4 we state and prove some preliminary
results that we need. In Section 5 we prove the existence of ‘gadgets’ which
underpin Lemma 3.1. In Section 6 we prove Lemma 3.1.

Throughout the paper, we will assume that $n$ is sufficiently large.
Asymptotic notation hides absolute constants: if for some $x,\varepsilon,n>0$
we write $x=O(\varepsilon n)$, then there is an absolute constant $C>0$, which
does not depend on $x,\varepsilon,n$ or any other parameters, such that $x\leq
C\varepsilon n$. We write $x\ll y$ if $x<f(y)$ for an implicit positive
increasing function $f$. We denote the set of colours on the edges of a graph
$H$ by $\mathcal{C}(H)$, and say that a graph $H$ is _spanning_ in a colour
set $\mathcal{C}^{\prime}$ if $\mathcal{C}(H)=\mathcal{C}^{\prime}$. Finally,
we let ${G}_{\delta,n}$ be an arbitrary member of $\mathcal{G}_{\delta,n}$,
which is the family of $n$-vertex graphs with minimum degree at least $\delta
n$.

##  2 Proof sketch

Our proof uses the _absorption method_. This method is typically applicable
when one searches for a spanning subgraph, and involves two stages: finding an
almost spanning subgraph; and dealing with the remainder, by having a
‘special’ set of vertices, put aside at the beginning, that can cover any
sufficiently small set of vertices.

This is done in Lemma 3.1, which says the following: with high probability
there exists a rainbow path $P_{\text{abs}}$ such that, for any sets of
vertices $V^{\prime}$ and colours $\mathcal{C}^{\prime}$ with
$\left|V^{\prime}\right|=\left|\mathcal{C}^{\prime}\right|$, disjoint from the
vertices and colors of $P_{\text{abs}}$, there exists another rainbow path $Q$
with vertex set $V^{\prime}\cup V(P_{\text{abs}})$ and colours
$\mathcal{C}^{\prime}\cup\mathcal{C}(P_{\text{abs}})$, whose ends can be any
vertices in $V^{\prime}$.

We now sketch the proof of Lemma 3.1. We first put aside a subset of the
vertices and a subset of the colours, which are typically called the
‘reservoir’ (also called ‘flexible set’), that have the following property:
for any sets of vertices and colours $V^{\prime},\mathcal{C}^{\prime}$ of the
same small size (much smaller than the reservoir) which are disjoint from the
reservoir, we can find a rainbow path $P_{0}$ that uses $V^{\prime}$,
$\mathcal{C}^{\prime}$ and a $\Theta(\left|V^{\prime}\right|)$ subset of the
vertices and colours in the reservoir.

Then the question is how to cover the rest of the reservoir; to this end, we
build an ‘absorbing structure’ ($P_{\text{abs}}$ above) which has the
following property: it can ‘absorb’ any subset of vertices and colours of the
same size of the reservoir in a rainbow path $P_{\text{abs}}^{\prime}$. Then
combining $P_{\text{abs}}^{\prime}$ and $P_{0}$ gives $Q$.

The path $P_{\text{abs}}$ and the ‘absorbing structure’ in which it resides
are built by putting together several ‘absorbing gadgets’, graphs on
$\Theta(1)$ vertices with the following property: each gadget has two paths
with the same endpoints such that one avoids a designated pair of a vertex and
a colour in the reservoir, and the other one ‘absorbs’ the same pair; see
Figure 1. The construction of the gadgets is done in Section 5. This absorbing
structure was introduced by Gould, Kelly, Kühn and Osthus [18] for
constructing rainbow Hamilton paths in random optimal colourings of the
complete graph, and is based on ideas of Montgomery [24].

For finding an almost spanning rainbow path we use a rainbow version of depth
first search [14, 3], which was used for the same problem in [3].

##  3 Proof of Theorem 1.1

In this section we prove the main theorem, Theorem 1.1. We will use Lemma 3.1
below, which we prove in Section 6.

######  Lemma 3.1.

Let $\delta,\gamma,\eta\in(0,1)$ and $C>0$ be constants such that
$C^{-1}\ll\eta\ll\gamma\ll\delta.$ Let
$G\sim{G}_{\delta,n}\cup\mathbf{G}(n,C/n)$ be uniformly coloured in
$\mathcal{C}=[n]$. Then, with high probability, $G$ has a rainbow path
$P_{\text{abs}}$ of length at most $\gamma n$ with the following property. For
any $V^{\prime}\subseteq V\setminus V(P_{\text{abs}})$,
$\mathcal{C}^{\prime}\subseteq\mathcal{C}\setminus\mathcal{C}(P_{\text{abs}})$
with $2\leq\left|V^{\prime}\right|=\left|\mathcal{C}^{\prime}\right|\leq\eta
n$ and distinct $x,y\in V^{\prime}$, there exists a path $Q$ such that

  * •

$Q$ has ends $x,y$,

  * •

$V(Q)=V(P_{\text{abs}})\cup V^{\prime}$,

  * •

$\mathcal{C}(Q)=\mathcal{C}(P_{\text{abs}})\cup\mathcal{C}^{\prime}$.

The next lemma is a rainbow version of a commonly used consequence of the
depth first search algorithm [7], which we will use to find an almost spanning
rainbow path. This lemma was used in [3] for the same problem.

######  Lemma 3.2 (Prop. 2.1 [3]; Lem. 2.17 [14]).

Let $G$ be a graph with its edges coloured in a set $\mathcal{C}$. If for any
two disjoint sets of vertices $X,\,Y$ of size $k$ we have
$\left|\mathcal{C}{(E(X,Y))}\right|\geq\left|V(G)\right|,$ then $G$ has a
rainbow path of length at least $\left|V(G)\right|-2k+1$.

The next lemma can easily be proved using Chernoff’s bound (cf. Theorem 4.1).

######  Lemma 3.3.

Let $\alpha\in(0,1)$ and $C>0$ be constants with $C^{-1}\ll\alpha$. Let
$G\sim\mathbf{G}(n,C/n)$ be uniformly coloured in $\mathcal{C}=[n]$. Then,
with high probability, for any two disjoint sets of vertices $X,\,Y$ of size
$\alpha n$ we have $\left|\mathcal{C}{(E(X,Y))}\right|\geq(1-\alpha)n.$

Our main theorem now follows easilly.

###### Proof of Theorem 1.1.

Let $\eta,\gamma$ be constants such that $C^{-1}\ll\eta\ll\gamma\ll\delta.$ By
Lemmas 3.1 and 3.3 we may assume that there exists a path $P_{\text{abs}}$
with the properties in Lemma 3.1; and that for any disjoint $X,Y\subseteq V$
of size $k=\eta n/4$ we have $\left|\mathcal{C}(E(X,Y))\right|\geq n-k$. Let
$\mathcal{C}_{2}=\mathcal{C}\setminus\mathcal{C}(P_{\text{abs}})$, let
$V^{\prime}\subseteq V\setminus V(P_{\text{abs}})$ be an arbitrary set of size
$k$, and let $V_{2}=V\setminus\left(V^{\prime}\cup V(P_{\text{abs}})\right)$.
So $\left|\mathcal{C}_{2}\right|\geq n-\gamma n$ and
$\left|V_{2}\right|=\left|\mathcal{C}_{2}\right|-k-1$. Then, for every
disjoint $X,Y\subseteq V_{2}$ of size $k$,

$\left|\mathcal{C}(E(X,Y))\cap\mathcal{C}_{2}\right|\geq|\mathcal{C}_{2}|-k\geq\left|V_{2}\right|.$

Therefore, in the spanning subgraph of $G[V_{2}]$ whose edges are edges in $G$
coloured in $\mathcal{C}_{2}$, by Lemma 3.2 there exists a rainbow path
$P_{2}$ of length at least $\left|V_{2}\right|-2k+1$. Hence
$V_{2}^{\prime}=V(G)\setminus\left(V(P_{\text{abs}})\cup V(P_{2})\right)$ has
size between $k$ and $3k\leq\eta n-2$ and
$\mathcal{C}_{2}^{\prime}=\mathcal{C}\setminus\left(\mathcal{C}(P_{\text{abs}})\cup\mathcal{C}(P_{2})\right)$
has size $\left|V_{2}^{\prime}\right|+2$. Let $x,y$ be the endpoints of
$P_{2}$. Then by the property of $P_{\text{abs}}$ there exists a rainbow path
$Q$ spanning in $V(P_{\text{abs}})\cup V_{2}^{\prime}\cup\\{x,y\\}$ and
$\mathcal{C}(P_{\text{abs}})\cup\mathcal{C}_{2}^{\prime}$ with endpoints
$x,y$. Then $P_{2}\cup Q$ is a rainbow Hamilton cycle. ∎

##  4 Preliminaries

In this section we collect three preliminary results that we need: the
Chernoff bound, cf. Theorem 4.1; that random sparse subgraph of dense
hypergraphs have large matchings, cf. Lemma 4.2; and that in the perturbed
graph, between any two vertices, there is a large rainbow collection of paths
of length three, cf. Lemma 4.3.

######  Theorem 4.1 (Chernoff Bound, [19, eq. (2.8) and Theorem 2.8]).

For every $\varepsilon>0$ there exists $c_{\varepsilon}>0$ such that the
following holds. Let $X$ be the sum of mutually independent indicator random
variables and write $\mu=\mathbf{E}\left[X\right]$. Then

$\mathbf{P}\left[\left|X-\mu\right|\geq\varepsilon\mu\right]\leq 2{\rm
e}^{-c_{\varepsilon}\,\mu}.$

The next lemma, despite its technical appearance, proves the following
straightforward statement: quite _sparse_ random subgraphs of dense
hypergraphs contain, with high probability, a matching of linear size.

######  Lemma 4.2.

Let $\alpha,c,c^{\prime}>0$ and $r\geq 2$ be an integer such that
$c^{\prime}\ll\alpha,c,r$. Let $\mathcal{H}$ be an $r$-uniform hypergraph on
$n$ vertices with at least $\alpha n^{r}$ edges.

Let $\mathcal{H}_{m}$ be the random subgraph of $\mathcal{H}$ that consists of
$m=cn$ edges of $\mathcal{H}$, chosen with replacement and uniformly at
random. Then, with probability at least $1-{\rm e}^{-\frac{c\alpha n}{4}}$,
the hypergraph $\mathcal{H}_{m}$ has a matching of size at least
$c^{\prime}n$.

Let $\mathcal{H}_{p}$ be the random subgraph of $\mathcal{H}$, where we keep
each edge independently with probability $p=cn^{-r+1}$. Then with probability
at least $1-{\rm e}^{-\frac{c\alpha n}{2r}}$, the hypergraph $\mathcal{H}_{p}$
has a matching of size at least $c^{\prime}n$.

###### Proof.

Write $\beta(\mathcal{G})$ for the size of the largest matching of a
hypergraph $\mathcal{G}$.

It is not hard to see that $\mathcal{H}$ contains an induced subgraph of
minimum degree at least $\alpha n^{r-1}$. Hence, without loss of generality,
we may assume that $\mathcal{H}$ has minimum degree at least $\alpha n^{r-1}$.

We first prove the result for $\mathcal{H}_{m}$. Suppose
$\beta(\mathcal{H}_{m})<c^{\prime}n$, and let $M$ be a maximal matching. Then
$S=V(\mathcal{H})\setminus V(M)$ is an independent set in $\mathcal{H}_{m}$
and $\left|S\right|\geq(1-rc^{\prime})n$. By the minimum degree condition of
$\mathcal{H}$, the number of edges with all vertices in $S$ is at least
$\frac{1}{r}|S|(\alpha
n^{r-1}-rc^{\prime}n^{r-1})\geq\frac{1}{r}(1-rc^{\prime})\,(\alpha-c^{\prime})n^{r}.$
This gives

$\displaystyle\mathbf{P}\left[S\text{ is independent}\right]$
$\displaystyle=\left(1-\frac{e(\mathcal{H}[S])}{e(\mathcal{H})}\right)^{m}$
$\displaystyle\leq\exp\left(-cn\cdot\frac{\frac{1}{r}(1-rc^{\prime})\,(\alpha-
rc^{\prime})n^{r}}{\binom{n}{r}}\right)$
$\displaystyle\leq\,\exp\left(-\frac{1}{2}(r-1)!\,c\,(1-rc^{\prime})\,(\alpha-
rc^{\prime})n\right)$

Then, since $rc^{\prime}<1/2$, the number of $S\subseteq V$ with
$\left|S\right|\geq(1-rc^{\prime})n$ is at most

$n\binom{n}{(1-rc^{\prime})n}=n\binom{n}{rc^{\prime}n}\leq{\rm
e}^{2rc^{\prime}n}(rc^{\prime})^{-rc^{\prime}n}.$

Thus by the union bound
$\mathbf{P}\left[\beta(\mathcal{H}_{m})<c^{\prime}n\right]\leq\exp\left(f_{c,r,\alpha}(c^{\prime})n\right),$
where

$f_{c,r,\alpha}(c^{\prime})=2rc^{\prime}-rc^{\prime}\ln(rc^{\prime})-\frac{(r-1)!}{2}c(1-rc^{\prime})(\alpha-
rc^{\prime})$

Since $f_{c,r,\alpha}(c^{\prime})$ is continuous near $0$ and
$f_{c,r,\alpha}(c^{\prime})\rightarrow 0-0-\frac{(r-1)!}{2}\,c\,\alpha<0$ as
$c^{\prime}\rightarrow 0$, for $c^{\prime}=c^{\prime}(c,r,\alpha)$
sufficiently small
$f_{c,r,\alpha}(c^{\prime})\leq-\frac{(r-1)!}{4}\,c\,\alpha\leq-\frac{1}{4}c\alpha$,
which gives the first part of the lemma.

For the second part of the lemma observe that the same argument works: with
$S$ as above, in $\mathcal{H}_{p}$ we have

$\mathbf{P}\left[S\text{ is
independent}\right]=(1-p)^{e(\mathcal{H}[S])}\leq\exp\left(-cn^{-r+1}\cdot\frac{1}{r}(1-rc^{\prime})\,(\alpha-
rc^{\prime})n^{r}\right)$

and a similar calculation as above shows that the probability there is such an
$S$ is at most ${\rm e}^{-\frac{c\alpha n}{2r}}$. ∎

######  Lemma 4.3 (Triangles and Short Paths).

Let $0<\delta<1$, $q,C>0$ and $\rho,\lambda_{\text{con}}\ll\delta,q,C$. Let
$\mathcal{C}$ be a set of colours of size $qn$. Let
$G\sim{G}_{\delta,n}\cup\mathbf{G}(n,C/n)$ be uniformly coloured in
$\mathcal{C}$. Then, with probability at least $1-{\rm
e}^{-\lambda_{\text{con}}n}$, the following holds. For any $u,v\in V(G)$ there
is a matching $M$ of size at least $\rho n$ such that the colours of the edges
$ux,xy,vy$, for $xy\in M$, are all distinct.

###### Proof.

Fix $u,v\in V$. Let $\rho_{1}$ be a constant such that
$\rho,\lambda_{\text{con}}\ll\rho_{1}\ll C,\delta,q$.

By the minimum degree assumption, there exist disjoint subsets $N_{u}\subseteq
N_{{G}_{\delta,n}}(u)$, $N_{v}\subseteq N_{{G}_{\delta,n}}(v)$, of size
$\delta n/2$. Consider the bipartite graph with bipartition $(N_{u},N_{v})$
and edges

$\left\\{\,zw\in E(\mathbf{G}(n,C/n)):\>z\in N_{u},\ w\in N_{v}\right\\}.$

This is a random subgraph of the complete bipartite graph, with each part
having order $\delta n/2$, and edge probability $C/n.$ Hence, by Lemma 4.2,
with probability $1-{\rm e}^{-\Omega(C\delta n)}$, there is matching $M$ of
size $\rho_{1}n$.

For each $zw\in M$, reveal whether the path $uzwv$ is rainbow, without
exposing the colours. Then each $uzwv$ is rainbow independently with
probability $1-o(1)$. Hence by Chernoff’s bound (Theorem 4.1), with
probability $1-{\rm e}^{-\Omega(\rho_{1}n)}$, there is $M^{\prime}\subseteq M$
with $\left|M^{\prime}\right|\geq\rho_{1}n/2$ such that each $uzwv$ is
rainbow, for all $zw\in M^{\prime}$.

Let $\mathcal{P}=\\{uzwv:zw\in M^{\prime}\\}$. It remains to show we can find
a large $M^{\prime\prime}\subseteq M^{\prime}$ such that the collection
$\mathcal{P}^{\prime}=\\{uzwv:zw\in M^{\prime\prime}\\}$ is rainbow.

Now reveal the colours on the edges in $\mathcal{P}$. By symmetry, each triple
of distinct colours in $\mathcal{C}$ is equally likely to appear in
$\mathcal{P}$. Hence $\mathcal{P}$ corresponds to selecting uniformly at
random with replacement $\left|\mathcal{P}\right|\geq\rho_{1}n/2$ edges from
the complete 3-graph with vertex set $\mathcal{C}$. Thus, by Lemma 4.2, with
probability $1-{\rm e}^{-\Omega(\rho_{1}qn)}$, there exists
$M^{\prime\prime}\subseteq M^{\prime}$ of size $\rho n$ so that the colours of
$\mathcal{P}^{\prime}=\\{uxyv:xy\in M^{\prime\prime}\\}$ form a matching in
the complete 3-graph on $\mathcal{C}$ i.e. $\mathcal{P}^{\prime}$ is rainbow.

The probability this fails for some pair $u,v$ is, by the union bound, at most

$n^{2}\cdot\left({\rm e}^{-\Omega(C\delta n)}+{\rm
e}^{-\Omega(\rho_{1}n)}+e^{-\Omega(\rho_{1}qn)}\right)\leq{\rm
e}^{-\lambda_{\text{con}}n},$

proving the lemma. ∎

##  5 Finding absorbers

In this section we prove Lemma 5.2, which asserts that for any vertex $v$,
colour $c$ and any small (but linear in size) set of forbidden vertices and
colours, we can find an ‘absorber’ (cf. Definition 5.1) for $v,c$. These
absorbers are the building blocks for $P_{\text{abs}}$ in Lemma 3.1. To
construct these absorbers we will need to find a rainbow 4-cycle containing a
given colour $c$, and none of the forbidden vertices and colours. This is the
most technical part of our proof, and is done in Lemma 5.5.

######  Definition 5.1 (Absorber).

Let $v$ be a vertex and $c$ a colour. A _$(v,c)$ -absorber_ is a graph
$A_{v,c}$ with $v\in V(A_{v,c})$ and $c\in\mathcal{C}(A_{v,c})$ that has two
paths $P,P^{\prime}$ with the following properties.

  * •

They are rainbow.

  * •

They have the same endpoints.

  * •

$P$ is spanning in $V(A_{v,c})$ and
$V(P^{\prime})=V(P)\setminus\\{v\\}=V(A_{v,c})\setminus\\{v\\}$.

  * •

$P$ is spanning in $\mathcal{C}(A_{v,c})$ and
$\mathcal{C}(P^{\prime})=\mathcal{C}(P)\setminus\\{c\\}=\mathcal{C}(A_{v,c})\setminus\\{c\\}$.

We call $P$ the _$(v,c)$ -absorbing path_ and $P^{\prime}$ the _$(v,c)$
-avoiding path_. The _internal vertices_ of $A_{v,c}$ are
$V(A_{v,c})\setminus\\{v\\}$ and the _internal colours_ are
$\mathcal{C}(A_{v,c})\setminus\\{c\\}$.

For the sake of concreteness, we will refer to one of the endpoints of the
paths as the _first vertex_ of the absorber and the other one as the _last
vertex_.

######  Lemma 5.2.

Let $0<\delta<1$, $C>0$ and $C^{-1}\ll\nu\ll\delta$. Let
$G\sim{G}_{\delta,n}\cup\mathbf{G}(n,C/n)$ be uniformly coloured in
$\mathcal{C}=[n]$. Then with high probability the following holds. For any
$v\in V(G)$ and $c\in\mathcal{C}$ and for all $V^{\prime}\subseteq V(G)$ and
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$ that have size at least $(1-\nu)n$,
there exists a $(v,c)$-absorber on 11 vertices with internal vertices in
$V^{\prime}$ and internal colours in $\mathcal{C}^{\prime}$.

Our absorbers will consist of the union of a triangle, a 4-cycle and two paths
of length three between opposite vertices of the cycle and between a vertex in
the triangle and a vertex in the 4-cycle. We require the colours of the
triangle to match the internal colours of the square. See Figure 1.

Figure 1: At the top is a $(v,c)$-absorber. At the bottom the first figure
shows the $(v,c)$-absorbing path and the second figure the $(v,c)$-avoiding
path.

###  5.1 Finding squares

We will use the following theorem, due to Fox and Sudakov [15], that is based
on the dependent random choice method.

######  Theorem 5.3 (Theorem 3.1 [15]; see also Prop. 5.3 [16]).

Let $\alpha,\alpha^{\prime}>0$ be constants such that
$\alpha^{\prime}\ll\alpha$. Let $G$ be a bipartite graph of order $n$ with
bipartition $(A,B)$ and $e(A,B)\geq\alpha n^{2}$. Then there are
$A^{\prime}\subseteq A$, $B^{\prime}\subseteq B$ such that for all $a\in
A^{\prime},b\in B^{\prime}$, the number of paths of length three between $a$
and $b$ in $G[A^{\prime},B^{\prime}]$ is at least $\alpha^{\prime}n^{2}$.

######  Lemma 5.4.

Let $\alpha,\beta>0$ be constants such that $\beta\ll\alpha$. Let $G$ be a
bipartite graph on $n$ vertices with bipartition $(A,B)$ and $e(A,B)\geq\alpha
n^{2}$. Then there exist disjoint sets $A_{1},A_{2}\subseteq A$,
$B_{1},B_{2}\subseteq B$, such that for any $a\in A_{1},b\in B_{1}$, the
number of paths of length three between $a,b$ with internal vertices in
$A_{2},B_{2}$ is at least $\beta n^{2}$. Moreover, the minimum degree of
$G[A_{1},B_{1}]$ is at least $\beta n$.

###### Proof.

Let $\alpha^{\prime}$ satisfy $\beta\ll\alpha^{\prime}\ll\alpha$ and let
$A^{\prime},B^{\prime}$ be given by Theorem 5.3. Let $(A_{1},A_{2})$ be a
random partition of $A^{\prime}$, and $(B_{1},B_{2})$ be a random partition of
$B^{\prime}$, i.e. each $a\in A^{\prime}$ lies in $A_{1}$ independently with
probability $1/2$, and similarly for $B_{1}$.

Then, since $G[A^{\prime},B^{\prime}]$ has minimum degree at least
$\alpha^{\prime}n$, for each $a\in A^{\prime}$ the expected number of
neighbours of $a$ in $B_{1}$ is at least $\alpha^{\prime}n/2$; the same is
true for the number of neighbours of $b\in B^{\prime}$ in $A_{1}$. Hence from
Chernoff’s bound, for any $a\in A^{\prime},b\in B^{\prime}$,

$\mathbf{P}\left[\left|N(a)\cap
B_{1}\right|\geq\alpha^{\prime}n/3\right],\,\mathbf{P}\left[\left|N(b)\cap
A_{1}\right|\geq\alpha^{\prime}n/3\right]\geq 1-{\rm
e}^{-\Omega(\alpha^{\prime}n)}.$

Consider a pair $a\in A^{\prime},b\in B^{\prime}$. Notice that the number of
paths of length three between $a,b$ in $G[A^{\prime},B^{\prime}]$ is equal to
the number of edges between $G[N(a),N(b)]$. From Theorem 5.3, the number of
edges of $G[N(a)\cap B^{\prime},N(b)\cap A^{\prime}]$ is at least
$\alpha^{\prime}n^{2}$, hence there are $B_{a,b}\subseteq N(a)\cap
B^{\prime}$, $A_{a,b}\subseteq N(b)\cap A^{\prime}$ such that
$G[A_{a,b},B_{a,b}]$ has minimum degree at least $\alpha^{\prime}n$. Then the
expected number of neighbours of each $a^{\prime}\in A_{a,b}$ in $B_{a,b}\cap
B_{2}$ is at least $\alpha^{\prime}n/2$, so by Chernoff’s bound, for
$a^{\prime}\in A_{a,b}$,

$\mathbf{P}\left[\left|N(a^{\prime})\cap B_{a,b}\cap
B_{2}\right|\geq\alpha^{\prime}n/3\right]\geq 1-{\rm
e}^{-\Omega(\alpha^{\prime}n)}.$

Similarly, for $b^{\prime}\in B_{a,b}$,

$\mathbf{P}\left[\left|N(b^{\prime})\cap A_{a,b}\cap
A_{2}\right|\geq\alpha^{\prime}n/3\right]\geq 1-{\rm
e}^{-\Omega(\alpha^{\prime}n)}.$

Hence, for each $a\in A^{\prime},b\in B^{\prime}$, the probability that the
minimum degree of $G[A_{a,b}\cap A_{2},B_{a,b}\cap B_{2}]$ is less than
$\alpha^{\prime}n/3$ is, by the union bound, at most

$\left|A_{a,b}\right|{\rm
e}^{-\Omega(\alpha^{\prime}n)}+\left|B_{a,b}\right|{\rm
e}^{-\Omega(\alpha^{\prime}n)}\leq{\rm e}^{-\Omega(\alpha^{\prime}n)}.$

Moreover, the number of paths of length three between $a,b$ with internal
vertices in $A_{2},B_{2}$ is

$e(N(a)\cap B_{2},N(b)\cap A_{2})\geq e(N(a)\cap B_{2}\cap B_{a,b},N(b)\cap
A_{2}\cap A_{a,b}),$

which is at least the square of the minimum degree of $G[N(a)\cap B_{2}\cap
B_{a,b},N(b)\cap A_{2}\cap A_{a,b}]$. Hence, the probability that the number
of paths of length three between $a\in A^{\prime},b\in B^{\prime}$ with
internal vertices in $A_{2},B_{2}$ is less than $\alpha^{\prime 2}n^{2}/9$ is
at most ${\rm e}^{-\Omega(\alpha^{\prime}n)}$.

By the union bound over $a\in A^{\prime},b\in B^{\prime}$ and pairs $(a,b)\in
A^{\prime}\times B^{\prime}$ the probability that a random partition fails to
satisfy the lemma, with $\beta=\alpha^{\prime 2}/9$, is at most $n{\rm
e}^{-\Omega(\alpha^{\prime}n)}+n^{2}{\rm e}^{-\Omega(\alpha^{\prime}n)}<1$.
Thus there exists a partition as desired. ∎

######  Lemma 5.5.

Let $\delta,q_{1},q_{2},\lambda_{\text{sq}}$ be constants such that
$0<\delta<1$, $0<q_{2}<q_{1}$ and $0<\lambda_{\text{sq}}\ll\delta,q_{2}$. Let
$\mathcal{C}$ be a set of colors with $\left|\mathcal{C}\right|=q_{1}n$ and
$\mathcal{C}_{0}\subseteq\mathcal{C}^{3}$ be a collection of colour triples
that are pairwise disjoint, with $\left|\mathcal{C}_{0}\right|=q_{2}n$. Let
$G$ be a graph of order $n$ and minimum degree at least $\delta n$ which is
uniformly coloured in $\mathcal{C}$. Then, with probability at least $1-{\rm
e}^{-\lambda_{\text{sq}}n}$, the following holds. For any $c\in\mathcal{C}$
there exists a 4-cycle in $G$ coloured $(c_{1},c_{2},c_{3},c)$, for some
$(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}$.

###### Proof.

Let $\beta,\gamma_{1},\gamma_{3}$ be constants such that $\beta\ll\delta$ and
$\lambda_{\text{sq}}\ll\gamma_{3}\ll\gamma_{1}\ll\gamma\ll\beta,q_{1}^{-1}$.

Fix $c\in\mathcal{C}$. By passing to a bipartite subgraph of $G$ with at least
$e(G)/2$ edges, from Lemma 5.4 there exist disjoint
$A_{1},B_{1},A_{2},B_{2}\subseteq V(G)$ such that the bipartite graph
$G[A_{1},B_{1}]$ has minimum degree at least $\beta n$, and for all $a\in
A_{1},b\in B_{1}$, the number of edges in $G[N(a)\cap B_{2},N(b)\cap A_{2}]$
is at least $\beta n^{2}$. We will reveal the colours of the edges in
$G[A_{1}\cup A_{2},B_{1}\cup B_{2}]$ in the order
$E(A_{1},B_{1}),E(A_{1},B_{2}),E(A_{2},B_{1}),E(A_{2},B_{2})$.

Since each edge of $G[A_{1},B_{1}]$ is coloured $c$ independently with
probability $(q_{1}n)^{-1}$, by Lemma 4.2, with probability at least $1-{\rm
e}^{-\Omega(\lambda_{\text{sq}}n)}$, there exists a matching $M\subseteq
G[A_{1},B_{1}]$ of size at least $\gamma n$ with all edges coloured $c$.

For $(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}$ say an edge $e\in E(A_{2},B_{2})$
is _good_ for $(c_{1},c_{2},c_{3})$, if, when $\mathcal{C}(e)=c_{2}$, it
completes a 4-cycle coloured $(c_{1},c_{2},c_{3},c)$ with vertices in
$A_{1},B_{1},A_{2},B_{2}$ (in this order). Notice that, this definition does
not depend on the colours of the edges in $G[A_{2},B_{2}]$. Let

$F(c_{1},c_{2},c_{3}):=\\{e\in E(A_{2},B_{2}):e\text{ is good for
}(c_{1},c_{2},c_{3})\\}.$

######  Claim 5.6.

Fix $(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}$. With probability at least $1-{\rm
e}^{-\Omega(\lambda_{\text{sq}}n)}$,
$\left|F(c_{1},c_{2},c_{3})\right|\geq\gamma_{3}n.$

###### Proof.

Let $ab\in M$. Since $e(N(a)\cap B_{2},N(b)\cap A_{2})\geq\beta n^{2}$, there
exist $A_{ab}\subseteq N(b)\cap A_{2}$, $B_{ab}\subseteq N(a)\cap B_{2}$ such
that $G[A_{ab},B_{ab}]$ has minimum degree at least $\beta n$. Let
$G^{\prime}$ be the spanning subgraph of $G$ such that $xy\in E(G^{\prime})$
if and only if the following holds:

  * •

If $xy\in E_{G}(A_{1},B_{1})$ then $xy\in M$.

  * •

If $xy\in E_{G}(A_{1},B_{2})$ then $x\in V(M)\cap A_{1}$ and $y\in B_{xM(x)}$,
where $M(x)$ is the neighbour of $x$ in $M$.

  * •

If $xy\in E_{G}(A_{2},B_{1})$ then $y\in V(M)\cap B_{1}$ and $x\in A_{M(y)y}$.

  * •

If $xy\in E_{G}(A_{2},B_{2})$ then $xy\in E_{G}(A_{e},B_{e})$ for some $e\in
M$.

Since $G$ is 4-partite with parts $A_{1},B_{1},A_{2},B_{2}$, this exhausts all
possible edges of $G^{\prime}$.

Then the number of edges of $G^{\prime}[A_{1},B_{2}]$ is at least $\sum_{a\in
A_{1}\cap V(M)}\left|B_{ab}\right|\geq\gamma\beta n^{2}$. Moreover, each edge
is coloured $c_{1}$ independently with probability $(q_{1}n)^{-1}$. Therefore,
by Lemma 4.2, with probability at least $1-{\rm
e}^{-\Omega(\lambda_{\text{sq}}n)}$, there is a matching $M_{1}$ in
$G^{\prime}[A_{1},B_{2}]$ coloured $c_{1}$ that has size at least
$\gamma_{1}n$.

Finally, we will find a large matching $M_{3}$ coloured $c_{3}$ which, along
with $M_{1}$ and $M$ will give us a large number of good edges for
$(c_{1},c_{2},c_{3})$. To this end, let $G^{\prime\prime}$ be the spanning
subgraph of $G^{\prime}$ such that $xy\in E(G^{\prime\prime})$ if and only if
the following holds:

  * •

if $xy\in E_{G^{\prime}}(A_{1},B_{1})$ then $xy\in M$ and $x\in V(M)\cap
V(M_{1})$.

  * •

If $xy\in E_{G^{\prime}}(A_{1},B_{2})$ then $xy\in M_{1}$.

  * •

If $xy\in E_{G^{\prime}}(A_{2},B_{1})$ then $y\in V(M)\cap B_{1}$, $M(y)\in
V(M_{1})$, and $x\in A_{M(y)y}\cap N_{G^{\prime}}\left(M_{1}(M(y))\right)$.

  * •

If $xy\in E_{G^{\prime}}(A_{2},B_{2})$ then there exists $ab\in M$ such that
$y=M_{1}(a)$ and $x\in A_{ab}$.

Again, this exhausts all possibilities for the edges of $G^{\prime\prime}$.

Then the number of edges of $G^{\prime\prime}[A_{2},B_{1}]$ is at least

$\sum_{ab\in M:\,a\in V(M_{1})\cap A_{1}}\left|N_{G^{\prime}}(M_{1}(a))\cap
A_{ab}\right|\geq\gamma_{1}\beta n^{2},$

where we use that for all $ab\in M$ the minimum degree of
$G^{\prime\prime}[A_{ab},B_{ab}]$ is at least $\beta n$.

Moreover, each edge of $G^{\prime\prime}[A_{2},B_{1}]$ is coloured $c_{3}$
independently with probability $(q_{1}n)^{-1}$. Hence, by Lemma 4.2, with
probability at least $1-{\rm e}^{-\Omega(\lambda_{\text{sq}}n)}$, there exists
a matching $M_{3}$ in $G^{\prime\prime}[A_{2},B_{1}]$ coloured $c_{3}$ that
has size at least $\gamma_{3}n$.

Let

$F_{0}(c_{1},c_{2},c_{3}):=\\{xy\in E_{G^{\prime\prime}}(A_{2},B_{2}):x\in
V(M_{3})\cap A_{2}\ \\}.$

Notice from the definition of $G^{\prime\prime}$ that every $x\in A_{2}$ has a
neighbour in $B_{2}$, hence
$\left|F_{0}(c_{1},c_{2},c_{3})\right|\geq\left|M_{3}\right|$. Moreover, if
$xy\in F_{0}(c_{1},c_{2},c_{3})$, then, by the definition of
$G^{\prime\prime}$, there are $a\in A_{1},b\in B_{1}$ such that $ab\in M$,
$ay\in M_{1}$, $xb\in M_{3}$; i.e. $\mathcal{C}(ab)=c$,
$\mathcal{C}(ay)=c_{1}$, $\mathcal{C}(xb)=c_{3}$. Therefore, $xy$ is a good
edge for $(c_{1},c_{2},c_{3})$. Thus $F_{0}(c_{1},c_{2},c_{3})\subseteq
F(c_{1},c_{2},c_{3})$, so
$\left|F(c_{1},c_{2},c_{3})\right|\geq\left|F_{0}(c_{1},c_{2},c_{3})\right|\geq\left|M_{3}\right|\geq\gamma_{3}n$
and the claim follows. ∎

By the union bound over $(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}$, for which
there are $q_{2}n$ choices, 5.6 implies that with probability at least $1-{\rm
e}^{-\Omega(\lambda_{\text{sq}}n)}$, for each
$(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}$,
$\left|F(c_{1},c_{2},c_{3})\right|\geq\gamma_{3}n$. Let

$F^{\prime}(e):=\\{c_{2}\in\mathcal{C}:\text{there exist $c_{1},c_{3}$ such
that }(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}\text{ and }e\in
F(c_{1},c_{2},c_{3})\\}.$

Then, using that no two triples in $\mathcal{C}_{0}$ share a colour we have

$\sum_{e\in
E(A_{2},B_{2})}\left|F^{\prime}(e)\right|=\sum_{(c_{1},c_{2},c_{3})\in\mathcal{C}_{0}}\left|F(c_{1},c_{2},c_{3})\right|\geq\left|\mathcal{C}_{0}\right|\gamma_{3}n=q_{2}\gamma_{3}n^{2}.$

Now we reveal the colours of $E(A_{2},B_{2})$. For $e\in E(A_{2},B_{2})$ let
$A_{e}$ be the event that $e$ gets a good colour i.e. $\mathcal{C}(e)\in
F^{\prime}(e)$. Then
$\mathbf{P}\left[A_{e}\right]=\left|F^{\prime}(e)\right|/q_{1}n$. Each edge is
coloured independently, so the events $A_{e}$ are mutually independent. Hence,
the probability that no $e\in E(A_{2},B_{2})$ gets a good colour is

$\displaystyle\prod_{e\in
E(A_{2},B_{2})}\left(1-\mathbf{P}\left[A_{e}\right]\right)$
$\displaystyle\leq\exp\left(-\sum_{e\in
E(A_{2},B_{2})}\mathbf{P}\left[A_{e}\right]\right)$
$\displaystyle=\exp\left(-\sum_{e\in
E(A_{2},B_{2})}\frac{|F^{\prime}(e)|}{q_{1}n}\right)\leq\exp\left(-\frac{q_{2}\gamma_{3}n}{q_{1}}\right).$

Hence, with probability at least $1-{\rm
e}^{-\frac{q_{2}\gamma_{3}n}{q_{1}}}$, at least one edge gets a good colour,
i.e. there exists $e\in E(A_{2},B_{2})$ such that $\mathcal{C}(e)\in
F^{\prime}(e)$, as required for the lemma.

The above fails for some colour $c$ with probability at most

$q_{1}n{\rm e}^{-\Omega(\lambda_{\text{sq}}n)}\leq{\rm
e}^{\lambda_{\text{sq}}n},$

proving the lemma. ∎

###  5.2 Proof of Lemma 5.2

###### Proof of Lemma 5.2.

Let $\rho,\rho^{\prime}$ be constants satisfying
$C^{-1}\ll\nu\ll\lambda,\rho,\rho^{\prime}\ll\delta$. Fix $v\in
V(G),\,c\in\mathcal{C}$ and $V^{\prime}\subseteq
V(G),\,\mathcal{C}^{\prime}\subseteq\mathcal{C}$ of size at least $(1-\nu)n$.

For the next claim, it is useful to refer to Figure 1.

######  Claim 5.7.

With probability $1-{\rm e}^{-\Omega(\lambda n)}$, there exist a 4-cycle
$K=xyzw$ and a triangle $T=vuu^{\prime}$ in $G[V^{\prime}]$ such that
$\mathcal{C}(yz)=c$, $\mathcal{C}(xw)=\mathcal{C}(uu^{\prime})$,
$\mathcal{C}(xy)=\mathcal{C}(vu^{\prime})$, $\mathcal{C}(zw)=\mathcal{C}(vu)$.

###### Proof.

Let $(V_{\triangle},V_{\square})$ be a random partition of $V^{\prime}$. Then
from Chernoff’s bound, a union bound over $v\in V^{\prime}$, and $\nu\ll 1$,
with probability $1-{\rm e}^{-\Omega(\delta n)}$, the graphs
${G}_{\delta,n}[V_{\triangle}]$, ${G}_{\delta,n}[V_{\square}]$ have minimum
degree at least $\delta n/3$ and
$\left|V_{\triangle}\right|,\left|V_{\square}\right|\geq n/3$.

First reveal the random edges and colours of $G[V_{\triangle}]$. Then, by
Lemma 4.3, with probability $1-{\rm e}^{-\Omega(\lambda n)}$, there is a
collection $\Delta_{v}$ of $\rho n$ rainbow triangles that pairwise intersect
only on $v$; are pairwise colour-disjoint; and $V(\Delta_{v})\subseteq
V_{\triangle}\cup\\{v\\}$. Let $\mathcal{C}_{v}$ be the collection of colour
triples $(\mathcal{C}(vu),\mathcal{C}(uu^{\prime}),\mathcal{C}(vu^{\prime}))$
with $vuu^{\prime}\in\Delta_{v}$, whose three colours are in
$\mathcal{C}^{\prime}$. Then $\left|\mathcal{C}_{v}\right|\geq\rho n-3\nu
n\geq(\rho/2)n$.

Next reveal the colours of edges in $G[V_{\square}]$. By setting
$\mathcal{C}_{0}=\mathcal{C}_{v}$ in Lemma 5.5, it follows that with
probability $1-{\rm e}^{-\Omega(\lambda n)}$ there exists a 4-cycle $xyzw$ and
a triangle $vuu^{\prime}\in\Delta_{v}$ with colours in $\mathcal{C}_{v}$, such
that $\mathcal{C}(yz)=c$, $\mathcal{C}(xw)=\mathcal{C}(uu^{\prime})$,
$\mathcal{C}(xy)=\mathcal{C}(vu^{\prime})$, $\mathcal{C}(wz)=\mathcal{C}(vu)$.

We fail to find a triangle or square as required with probability at most
${\rm e}^{-\Omega(\lambda n)}$. ∎

By Lemma 4.3, with probability $1-{\rm e}^{-\Omega(\lambda n)}$, for every
$u,v\in V^{\prime}$ there are $\rho^{\prime}n$ rainbow paths of length three
between $u,v$ which are pairwise colour disjoint and internally vertex
disjoint. Hence, with probability $1-{\rm e}^{-\Omega(\lambda n)}$, this and
the conclusion of 5.7 hold simultaneously.

Then, using $\nu\ll\rho^{\prime}$, there exists two colour- and vertex-
disjoint rainbow paths $P_{1},P_{3}$ of length $3$ such that: $P_{1}$ has
endpoints $u_{2},w$; $P_{3}$ has endpoints $x,z$; the interiors of
$P_{1},P_{2}$ are in $V^{\prime}\setminus(V(K)\cup V(C))$; and the colours of
$P_{1},P_{2}$ are in
$\mathcal{C}^{\prime}\setminus(\mathcal{C}(K)\cup\mathcal{C}(T))$. Then the
graph $A_{v,c}$, defined as

$A_{v,c}=K\,\cup\,T\,\cup\,P_{1}\,\cup\,P_{2},$

is a $(v,c)$-absorber: the $(v,c)$-absorbing path is
$uvu^{\prime}P_{1}wxP_{2}zy$ and the $(v,c)$-avoiding path is
$uu^{\prime}P_{1}wzP_{2}xy$, and it is straightforward to check they satisfy
Definition 5.1. Clearly $A_{v,c}$ has 11 vertices.

The number of $V^{\prime}\subseteq V$ of size at least $(1-\nu)n$ is at most
$n\binom{n}{\nu n}={\rm e}^{O\left(\nu\log\nu\right)n}$, and the same bound
holds for the number of $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ of the same
size. Using $\nu\ll\lambda$, the probability we fail to find an absorber for
some $v,\,c,\,V^{\prime},\,\mathcal{C}^{\prime}$ is by the union bound at most

$n^{2}{\rm e}^{O\left(\nu\log\nu\right)n}\cdot{\rm e}^{-\Omega(\lambda n)}\leq
n^{-2}.\qed$

##  6 Proof of Lemma 3.1

To cover an arbitrary small subset of the vertices using $P_{\text{abs}}$ into
a rainbow path $Q$ we need the following lemma, which asserts that for any two
vertices and a color we can connect them with a short rainbow path through a
random subset of the vertices.

######  Lemma 6.1 (Flexible sets).

Let $\zeta,\mu,\delta\in(0,1)$ and $C>0$ be constants such that
$C^{-1}\ll\zeta\ll\mu\ll\delta$. Let
$G\sim{G}_{\delta,n}\cup\mathbf{G}(n,C/n)$. Then there exist
$V_{\text{flex}\,}\subseteq V$,
$\mathcal{C}_{\text{flex}}\subseteq\mathcal{C}$ of size $2\mu n$ such that
with high probability the following holds. For all $u,v\in V$,
$c\in\mathcal{C}$, and $V_{\text{flex}\,}^{\prime}\subseteq
V_{\text{flex}\,}$,
$\mathcal{C}_{\text{flex}}^{\prime}\subseteq\mathcal{C}_{\text{flex}}$ of size
at least $(2\mu-\zeta)n$, there exists a rainbow path of length seven with
endpoints $u,v$, internal vertices in $V_{\text{flex}\,}^{\prime}$ and colours
in $\mathcal{C}_{\text{flex}}^{\prime}\cup\\{c\\}$, that contains the colour
$c$.

###### Proof.

Let $\gamma$ be a constant satisfying
$C^{-1}\ll\zeta\ll\gamma\ll\mu\ll\nu\ll\delta$.

For a colour $c$, let $M_{c}$ be a largest matching of colour $c$ in $G$, and
for distinct vertices $u,v$, let $\mathcal{P}_{u,v}$ be a largest collection
of pairwise vertex- and colour-disjoint rainbow paths of length three with
endpoints $u,v$. By Lemmas 4.2 and 4.3, with probability $1-e^{-\gamma n}$, we
have $|M_{c}|\geq\gamma n$ and $|\mathcal{P}_{u,v}|\geq\gamma n$ for every
colour $c$ and distinct vertices $u,v$.

Let $V^{\prime}$ be a random subset of $V$, obtained by including each vertex
independently with probability $\mu$, and let $\mathcal{C}^{\prime}$ be a
random subset of $\mathcal{C}$, obtained by including each colour
independently with probability $\mu$.

Then, by Chernoff and union bounds, with high probability, the following
properties hold.

  * •

$|V^{\prime}|,|\mathcal{C}^{\prime}|\leq 2\mu n$,

  * •

at least $\frac{1}{2}\mu^{2}\gamma n$ edges in $M_{c}$ have both endpoints in
$V^{\prime}$, for every $c\in\mathcal{C}$,

  * •

at least $\frac{1}{2}\mu^{5}\gamma n$ paths in $\mathcal{P}_{u,v}$ have their
interior vertices in $V^{\prime}$ and all colours in $\mathcal{C}^{\prime}$,
for all distinct $u,v\in V$.

Suppose that all three properties hold, and let $V_{\text{flex}}$ be a subset
of $V$ that contains $V^{\prime}$ and has size $2\mu n$ and let
$\mathcal{C}_{\text{flex}}$ be a subset of $\mathcal{C}$ that contains
$\mathcal{C}^{\prime}$ and has size $2\mu n$.

We show that these sets satisfy the requirements of the lemma. Indeed, fix
$u,v,c$ and $V_{\text{flex}}^{\prime},\mathcal{C}_{\text{flex}}^{\prime}$ as
in the lemma. Then, as $\zeta\ll\mu,\gamma$, there is an edge $e=xy\in M_{c}$
with both ends in $V_{\text{flex}}^{\prime}$. Similarly, there are paths
$P_{1}\in\mathcal{P}_{u,x},P_{2}\in\mathcal{P}_{y,v}$ that are vertex- and
colour-disjoint, their interiors are in $V_{\text{flex}}^{\prime}$, and their
colours are in $\mathcal{C}_{\text{flex}}^{\prime}\setminus\\{c\\}$. Then
$P_{1}\cup e\cup P_{2}$ is a path that satisfies the requirements of the
lemma. ∎

We will put together several $(v,c)$-absorbers to construct the paths in Lemma
3.1, by having a $(v,c)$-absorber for each edge of a bipartite graph which has
the following property. This follows an idea introduced by Montgomery [24],
which was adapted to the rainbow setting by Gould, Kelly, Kühn and Osthus
[18].

######  Definition 6.2 (Def. 3.3, [18]).

Let $H$ be a balanced bipartite graph with bipartition $(A,B)$. We say $H$ is
_robustly matchable_ with respect to $A^{\prime},\,B^{\prime}$, for some
$A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$ of equal size, if for
every pair of sets $X\subseteq A^{\prime},Y\subseteq B^{\prime}$ with
$\left|X\right|=\left|Y\right|\leq\left|A^{\prime}\right|/2,$ there is a
perfect matching in $H[A\setminus X,B\setminus Y]$. We call
$A^{\prime},B^{\prime}$ the _flexible sets_ of $H$.

######  Proposition 6.3 (Lemma 4.5, [18]).

For every large enough $m\in\mathbb{N}$, there exists a $256$-regular
bipartite graph with bipartition $(A,B)$ and
$\left|A\right|=\left|B\right|=7m$, which is robustly matchable with respect
to some $A^{\prime}\subseteq A,B^{\prime}\subseteq B$ with
$\left|A^{\prime}\right|=\left|B^{\prime}\right|=2m$.

###### Proof of Lemma 3.1.

Let $\zeta,\mu,\nu\in(0,1)$ be constants such that

$C^{-1}\ll\eta\ll\zeta\ll\mu\ll\nu\ll\delta.$

Let $V_{\text{flex}\,},$ $\mathcal{C}_{\text{flex}}$ be the sets given by
Lemma 6.1 that have size $2\mu n$. By the union bound, the conclusions of
Lemmas 4.3, 6.1 and 5.2 hold simultaneously with high probability. Assume they
all hold.

Let $V_{\text{buf}\,},\,\mathcal{C}_{\text{buf}\,}$ be arbitrary subsets of
$V\setminus V_{\text{flex}\,},\,\mathcal{C}\setminus\mathcal{C}_{\text{flex}}$
of size $5\mu n$. Let $H$ be a bipartite graph on $(V_{\text{flex}\,}\cup
V_{\text{buf}\,},\,\mathcal{C}_{\text{flex}}\cup\mathcal{C}_{\text{buf}\,})$
that is isomorphic to a graph as in Proposition 6.3 such that
$V_{\text{flex}\,},\,\mathcal{C}_{\text{flex}}$ are the flexible sets.

######  Claim 6.4.

There is collection of absorbers $A_{v,c}$ on $11$ vertices and rainbow paths
$P_{v,c}$ of length three, for each edge $vc$ in $H$, with the following
properties: the internal vertices of $A_{v,c}$ and of $P_{v,c}$ are pairwise
disjoint and disjoint of $V_{\text{flex}\,}\cup V_{\text{buf}\,}$; the
internal colours of $A_{v,c}$ and the colours of $P_{v,c}$ are pairwise
disjoint and disjoint of
$\mathcal{C}_{\text{flex}}\cup\mathcal{C}_{\text{buf}\,}$; and for some
ordering of the edges of $H$, the path $P_{v,c}$ starts with the last vertex
of $A_{v^{\prime},c^{\prime}}$ and ends with the first vertex of $A_{v,c}$,
where $v^{\prime}c^{\prime}$ is the predecessor of $vc$ in the ordering (so we
can ignore $P_{vc}$ for the first edge $vc$).

###### Proof.

Let $H_{0}$ be a maximal subgraph of $H$ with some ordering of its edges, for
which we can find a collection of absorbers and paths as in the claim. Suppose
for contradiction $H_{0}\neq H$ and let $v_{1}c_{1}\in E(H\setminus H_{0})$
and $v_{0}c_{0}$ be the last edge of $H_{0}$ in the ordering, that has
absorber $A_{v_{0},c_{0}}$.

Let $V_{0},\mathcal{C}_{0}$ be the union of the vertices and colours spanned
by the absorbers for $E(H_{0})$, the paths connecting them, and
$V_{\text{flex}\,}\cup V_{\text{buf}\,}$,
$\mathcal{C}_{\text{flex}}\cup\mathcal{C}_{\text{buf}\,}$. Then, since each
absorber has $11$ vertices and each path connecting consecutive absorbers has
$4$ vertices, we have

$\left|V_{0}\right|,\left|\mathcal{C}_{0}\right|=O(e(H_{0}))=O(\mu n)<\nu
n/2,$

where for the inequality we used that $\mu\ll\nu$. Hence by Lemma 5.2 there
exists a $(v_{1},c_{1})$-absorber $A_{v_{1},c_{1}}$ on 11 vertices with
internal vertices and internal colours disjoint from $V_{0}$ and
$\mathcal{C}_{0}$. Moreover, by Lemma 4.3 there exists a rainbow path
$P_{v_{1},c_{1}}$ of length three between the last vertex of $A_{v_{0},c_{0}}$
and the first vertex of $A_{v_{1},c_{1}}$, with internal vertices disjoint
from $V_{0}\cup V(A_{v_{1},c_{1}})$ and colours disjoint from
$\mathcal{C}_{0}\cup\mathcal{C}(A_{c_{1},c_{1}})$. Then the subgraph of $H$
with edges $E(H_{0})\cup\\{v_{1}c_{1}\\}$ satisfies the conditions of the
claim and properly contains $H_{0}$, contradicting the maximality of $H_{0}$.
∎

We can now define $P_{\text{abs}}$. Since $H$ is regular bipartite, it has a
perfect matching $M$. For $vc\in E(H)$, let $P_{M}(vc)$ be the
$(v,c)$-absorbing path of $A_{v,c}$, if $vc\in E(M)$, and the avoiding path
otherwise. Let $P_{vc}=\emptyset$ if $vc$ is the first edge, and otherwise let
$P_{vc}$ be as in 6.4. Set

$P_{\text{abs}}=\bigcup_{vc\in E(H)}(P_{M}(vc)\cup P_{vc}).$

Then $P_{\text{abs}}$ uses each $v\in V_{\text{flex}\,}\cup V_{\text{buf}\,}$
and $c\in\mathcal{C}_{\text{flex}}\cup\mathcal{C}_{\text{buf}\,}$ precisely
once; any other vertex and colour in $P_{\text{abs}}$ is also used, by
construction, precisely once. Therefore $P_{\text{abs}}$ is a rainbow path
that is spanning in $\bigcup_{vc\in E(H)}(V(A_{vc})\cup V(P_{vc}))$ and
$\bigcup_{vc\in E(H)}(\mathcal{C}(A_{vc})\cup\mathcal{C}(P_{vc}))$ with
endpoints the first vertex $w$ of the first absorber and the last vertex
$w^{\prime}$ of the last absorber.

We will now show how to construct $Q$, given $V^{\prime}\subseteq V\setminus
V(P_{\text{abs}})$ and
$\mathcal{C}^{\prime}\subseteq\mathcal{C}\setminus\mathcal{C}(P_{\text{abs}})$
of size between $2$ and $\eta n$, with endpoints $x,y\in V^{\prime}$. Let
$c_{0}\in\mathcal{C}^{\prime}$. From Lemma 6.1, there exists a rainbow path
$Q_{1}$ with endpoints $w,x$, internal vertices in $V_{\text{flex}\,}$ and
colours in $\mathcal{C}_{\text{flex}}\cup\\{c_{0}\\}$, which includes the
colour $c_{0}$ and has length 7.

######  Claim 6.5.

There exists a rainbow path $Q_{2}$ between $w^{\prime},y$, with internal
vertices $V_{\text{flex}\,}^{\prime\prime}\cup(V^{\prime}\setminus x)$, and
colours
$\mathcal{C}_{\text{flex}}^{\prime\prime}\cup(\mathcal{C}^{\prime}\setminus
c_{0})$, for some $V_{\text{flex}\,}^{\prime\prime}\subseteq
V_{\text{flex}\,}\setminus V(Q_{1})$,
$\mathcal{C}_{\text{flex}}^{\prime\prime}\subseteq\mathcal{C}_{\text{flex}}\setminus\mathcal{C}(Q_{1})$
with
$\left|V_{\text{flex}\,}^{\prime\prime}\right|=\left|\mathcal{C}_{\text{flex}}^{\prime\prime}\right|\leq\mu
n-7$.

###### Proof.

The Claim will follow by applying greedily Lemma 6.1 to cover
$V^{\prime}\setminus x$, $\mathcal{C}^{\prime}\setminus c_{0}$ using
$V_{\text{flex}\,}\setminus V(Q_{1})$,
$\mathcal{C}_{\text{flex}}\setminus\mathcal{C}(Q_{1})$ in a rainbow path with
endpoints $w^{\prime}$ and $y$.

Fix a linear order of $V^{\prime}\setminus x$ with $y$ the last vertex. Let
$P_{0}$ be a longest path from $w^{\prime}$ to a vertex in
$V^{\prime}\setminus x$ among all rainbow paths that start at $w^{\prime}$ and
satisfy the following: if $u,v\in V(P_{0})\cap(V^{\prime}\setminus x)$ and
$u<v$, then $u$ appears before $v$ on $P_{0}$; every seventh vertex on $P_{0}$
lies in $V^{\prime}\setminus x$, and all other vertices are in
$\\{w^{\prime}\\}\cup V_{\text{flex}\,}\setminus V(Q_{1})$; between
consecutive vertices in $V^{\prime}\setminus x$, and between $w^{\prime}$ and
the first vertex in $V^{\prime}\setminus x$, there is exactly one edge with
colour in $\mathcal{C}^{\prime}\setminus c_{0}$, and all other edges have
colours in $\mathcal{C}_{\text{flex}}\setminus\mathcal{C}(Q_{1})$.

Let $z$ be the last vertex of $P_{0}$. If $z=y$ we are done so suppose
otherwise, and let $z^{\prime}\in V^{\prime}\setminus x$ be the vertex after
$z$ in the order. Since, by construction, $\left|V(P_{0})\cap
V^{\prime}\right|=\left|\mathcal{C}(P_{0})\cap\mathcal{C}^{\prime}\right|$,
there is also $c_{1}\in\mathcal{C}^{\prime}\setminus\mathcal{C}(P_{0})$.

Let $V_{\text{flex}\,}^{\prime}=V_{\text{flex}\,}\setminus(V(P_{0})\cup
V(Q_{1}))$,
$\mathcal{C}_{\text{flex}}^{\prime}=\mathcal{C}_{\text{flex}}\setminus(\mathcal{C}(P_{0})\cup\mathcal{C}(Q_{1}))$.
Since $\left|P_{0}\right|\leq 7\left|V^{\prime}\right|\leq 7\eta n,$ and
$Q_{1}$ has length 7, using $\eta\ll\zeta$, it follows that
$\left|V_{\text{flex}\,}^{\prime}\right|=\left|\mathcal{C}_{\text{flex}}^{\prime}\right|\geq(2\mu-\zeta)n.$
Hence by Lemma 6.1 there is a rainbow path $P_{1}$ between $z,z^{\prime}$ of
length 7, that contains an edge with colour $c_{1}$, and whose internal
vertices and other colours are in
$V_{\text{flex}\,}^{\prime},\mathcal{C}_{\text{flex}}^{\prime}$. Then
$P_{1}\cup P_{0}$ contradicts the maximality of $P_{0}$.

Let $V_{\text{flex}\,}^{\prime\prime}=V(P_{0})\cap V_{\text{flex}\,}$,
$\mathcal{C}_{\text{flex}}^{\prime\prime}=\mathcal{C}(P_{0})\cap\mathcal{C}_{\text{flex}}$.
Then
$\left|V_{\text{flex}\,}^{\prime\prime}\right|=\left|\mathcal{C}_{\text{flex}}^{\prime\prime}\right|<\left|P_{0}\right|\leq\zeta
n<\mu n-7,$ so we can take $Q_{2}=P_{0}$. ∎

Let $V_{\text{flex}\,}^{\prime\prime\prime}=(V(Q_{1})\cup V(Q_{2}))\cap
V_{\text{flex}\,}$ and
$\mathcal{C}_{\text{flex}}^{\prime\prime\prime}=(\mathcal{C}(Q_{1})\cup\mathcal{C}(Q_{2}))\cap\mathcal{C}_{\text{flex}}$.
Then we have
$\left|V_{\text{flex}\,}^{\prime\prime\prime}\right|=\left|\mathcal{C}_{\text{flex}}^{\prime\prime\prime}\right|\leq\mu
n$. Hence by choice of $H$ there is a matching $M^{\prime}$ between
$V_{\text{flex}\,}\setminus V_{\text{flex}\,}^{\prime\prime\prime}$ and
$\mathcal{C}_{\text{flex}}\setminus\mathcal{C}_{\text{flex}}^{\prime\prime\prime}$.

As before, for $vc\in E(H)$ let $P_{M^{\prime}}(vc)$ be the $(v,c)$-absorbing
path of $A_{v,c}$ if $vc\in E(M^{\prime})$ and the avoiding path otherwise.
Let

$P_{\text{abs}}^{\prime}=\bigcup_{vc\in E(H)}(P_{M^{\prime}}(vc)\ \cup
P_{vc}).$

Then $P_{\text{abs}}^{\prime}$ is a rainbow path that is spanning in
$V(P_{\text{abs}})\setminus V_{\text{flex}\,}^{\prime\prime\prime}$ and
$\mathcal{C}(P_{\text{abs}})\setminus\mathcal{C}_{\text{flex}}^{\prime\prime\prime}$
with endpoints $w,w^{\prime}$. Therefore $Q=Q_{1}\cup
P_{\text{abs}}^{\prime}\cup Q_{2}$ is a rainbow path, spanning in
$V(P_{\text{abs}})\cup V^{\prime}$ and
$\mathcal{C}(P_{\text{abs}})\cup\mathcal{C}^{\prime}$ and has endpoints $x,y$.
∎

## References

  * [1] E. Aigner-Horev, O. Danon, D. Hefetz, and S. Letzter, _Large rainbow cliques in randomly perturbed dense graphs_ , SIAM Journal on Discrete Mathematics 36 (2022), no. 4, 2975–2994.
  * [2] , _Small rainbow cliques in randomly perturbed dense graphs_ , European Journal of Combinatorics 101 (2022), 103452.
  * [3] E. Aigner-Horev and D. Hefetz, _Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs_ , SIAM Journal on Discrete Mathematics 35 (2021), no. 3, 1569–1577.
  * [4] E. Aigner-Horev, D. Hefetz, and A. Lahiri, _Rainbow trees in uniformly edge-coloured graphs_ , Random Structures & Algorithms 62 (2023), no. 2, 287–303.
  * [5] M. Anastos and A. Frieze, _How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?_ , Journal of Graph Theory 92 (2019), no. 4, 405–414.
  * [6] D. Bal and A. Frieze, _Rainbow matchings and Hamilton cycles in random graphs_ , Random Structures & Algorithms 48 (2016), no. 3, 503–523.
  * [7] I. Ben-Eliezer, M. Krivelevich, and B. Sudakov, _The size Ramsey number of a directed path_ , Journal of Combinatorial Theory, Series B 102 (2012), no. 3, 743–755.
  * [8] T. Bohman, A. Frieze, and R. Martin, _How many random edges make a dense graph Hamiltonian?_ , Random Structures & Algorithms 22 (2003), no. 1, 33–42.
  * [9] J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk, and Y. Person, _Universality for bounded degree spanning trees in randomly perturbed graphs_ , Random Structures & Algorithms 55 (2019), no. 4, 854–864.
  * [10] J. Böttcher, O. Parczyk, A. Sgueglia, and J. Skokan, _Triangles in randomly perturbed graphs_ , Combinatorics, Probability and Computing 32 (2023), no. 1, 91–121.
  * [11] C. Cooper and A. Frieze, _Multi-coloured Hamilton cycles in random edge-coloured graphs_ , Combinatorics, Probability and Computing 11 (2002), no. 2, 129–133.
  * [12] G. A. Dirac, _Some theorems on abstract graphs_ , Proceedings of the London Mathematical Society s3-2 (1952), no. 1, 69–81.
  * [13] A. Ferber, _Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs_ , Electronic Journal of Combinatorics 22 (2015), no. 1, Paper 1.61, 7 pp.
  * [14] A. Ferber and M. Krivelevich, _Rainbow Hamilton cycles in random graphs and hypergraphs_ , Recent Trends in Combinatorics, vol. 159, Springer, 2016, pp. 167–189.
  * [15] J. Fox and B. Sudakov, _On a problem of Duke–Erdős–Rödl on cycle-connected subgraphs_ , Journal of Combinatorial Theory, Series B 98 (2008), no. 5, 1056–1062.
  * [16] , _Dependent random choice_ , Random Structures & Algorithms 38 (2011), no. 1-2, 68–99.
  * [17] A. Frieze and P.-S. Loh, _Rainbow Hamilton cycles in random graphs_ , Random Structures & Algorithms 44 (2014), no. 3, 328–354.
  * [18] S. Gould, T. Kelly, D. Kühn, and D. Osthus, _Almost all optimally coloured complete graphs contain a rainbow Hamilton path_ , Journal of Combinatorial Theory, Series B 156 (2022), 57–100.
  * [19] S. Janson, A. Ruciński, and T. Łuczak, _Random Graphs_ , John Wiley & Sons, 2011.
  * [20] J. Komlós and E. Szemerédi, _Limit distribution for the existence of Hamiltonian cycles in a random graph_ , Discrete Mathematics 43 (1983), no. 1, 55–63.
  * [21] A.D. Korshunov, _A solution of a problem of P. Erdős and A. Rényi about Hamilton cycles in non-oriented graphs_ , Metody Diskr. Anal. Teoriy Upr. Syst., Sb. Trudov Novosibirsk 31 (1977), 17–56 (in Russian).
  * [22] M. Krivelevich, M. Kwan, and B. Sudakov, _Bounded-degree spanning trees in randomly perturbed graphs_ , SIAM Journal on Discrete Mathematics 31 (2017), no. 1, 155–171.
  * [23] M. Krivelevich, B. Sudakov, and P. Tetali, _On smoothed analysis in dense graphs and formulas_ , Random Structures & Algorithms 29 (2006), no. 2, 180–193.
  * [24] R. Montgomery, _Spanning trees in random graphs_ , Advances in Mathematics 356 (2019), 106793.
  * [25] L. Pósa, _Hamiltonian circuits in random graphs_ , Discrete Mathematics 14 (1976), no. 4, 359–364.


978-1-nnnn-nnnn-n/yy/mm nnnnnnn.nnnnnnn

Usama Khalid National University of Computer and Emerging Sciences (FAST-
NUCES<EMAIL_ADDRESS>
Mirza Omer Beg National University of Computer and Emerging Sciences (FAST-
NUCES<EMAIL_ADDRESS>
# Few Shot Learning for Information Verification

(20yy)

###### Abstract

Information verification is quite a challenging task, this is because many
times verifying a claim can require picking pieces of information from
multiple pieces of evidence which can have a hierarchy of complex semantic
relations. Previously a lot of researchers have mainly focused on simply
concatenating multiple evidence sentences to accept or reject claims. These
approaches are limited as evidence can contain hierarchical information and
dependencies. In this research, we aim to verify facts based on evidence
selected from a list of articles taken from Wikipedia. Pretrained language
models such as XLNET are used to generate meaningful representations and
graph-based attention and convolutions are used in such a way that the system
requires little additional training to learn to verify facts.

###### keywords:

Fact Checking, Language Models, XLNET, BERT, FEVER, Claim Verification

##  1 Problem statement

In the age of information individuals and organizations can easily share and
consume vasts amounts of data on any subject matter just with a tap of a
button. Many of the barriers required for verifying information have been
removed due to the advent of social media. Effectively allowing any piece of
created content to reach millions of readers instantly Allcott and Gentzkow
[2017].

This increased ability to reach people can be used to disseminate both true
and false information, which is a major concern since it is suspected to have
caused major disruptions in public decision making such as during elections as
shown by recent studies Vosoughi et al. [2018].

##  2 Introduction

Fact checking or Information verification is a very challenging task in NLP
and has recently attracted much attention from the research community. It is
important today more than ever as news and social media platforms are a huge
source of disseminating Fake news and misinformation. Huge pretrained models
with billions of parameters like GPT-2 Radford et al. [2019] and GPT-3 Brown
et al. [2020] are extremely good at generating fluent and coherent text which
lowers the bars for any malicious entity to generate deceptive content.

Initially information verification used to be a manual process. People visited
and still visit sites such as PolitiFact.com , FactCheck.org, and Snopes.com
where they could see latest or trending news currently circulating on the
Internet. However this type of fact checking is not at all scalable Sharma et
al. [2019] and as expected is susceptible to human bias Sathe et al. [2020].

Information verification or Fact-checking is the task of verifying if the
statements made in spoken or written language are valid. This task is normally
performed by qualified experts, who use past data and statistics or known
evidence to together with logic to reach a decision. This method can take from
less than an hour to a few days, depending on the complexity of the
information Hassan et al. [2015]. The information verification process
involves investigating and finding facts, knowing the knowledge background and
thinking for what can be derived from this facts. In judging the veracity of
an argument, the purpose of automatic fact testing is to reduce human
responsibility.

Information verification is quite a challenging task, this is because many a
times verifying a claim can require picking pieces of information from
multiple evidences and picking relevant evidences from corpora of information.
To correctly verify a claim it is also important to discern the semantic
structure and relation between the evidences present. Previously most research
focused primarily on aggregating evidence sentences simply by string
concatenation or either by using complex fusing of separate evidence
sentences.

Information verification is able to achieve a lot progress due to the
introduction of large datasets such as SNLI Bowman et al. [2015] and the FEVER
Thorne et al. [2018] task. A major shortcoming of these datasets is that they
are synthetic in nature i.e. they are produced by crowd-sourcing annotators
and evidence writers thus they differ significantly from actual claims and
evidences that are present on the internet.

To address and overcome theses shortcomings datasets like WIKIFACTCHECK Sathe
et al. [2020] have been proposed. The dataset contains ore the 124k triples.
These triples consist of context, claim and evidence sentences. The data is
extracted from documents of the English Wikipedia and consists of citations
and articles. The dataset also consists of more than 34k handwritten claims
which are negated by the gathered evidences. The advantage of this dataset
compared to others is that it is based on real world facts taken from
Wikipedia which will enable the training of systems that are better suited to
model the real world claims. The research also shows that an attention based
model trained on this dataset significantly outperforms the one trained on the
SNLI task.

##  3 Related work

Previously fact checking used to be done by segregating sentences into
subject-predicate-object tuples Nacem et al. [2020]; Beg et al. [2006] and
matching the claim with the evidence Nakashole and Mitchell [2014]. More
modern approaches that use the FEVER dataset Thorne et al. [2018] divide their
methodology into three steps, document selection, evidence sentence selection,
and claim verification.

In the document selection phase, named entities are extracted from a claim and
a query is formulated to search using the Wikipedia API. In the evidence
selection phase similar sentences are picked using either an Enhanced LSTM
Chen et al. [2017] or using sentence similarity functions like TF-IDF without
trainable parameters Padia et al. [2018]. For the claim verification phase,
evidence sentences are concatenated into a single string Nie et al. [2019],
each evidence-claim pair is classified separately and the results are merged.

A lot of work for Fact checking previously was done using natural language
inference models Dagan et al. [2013]; Angeli and Manning [2014] as this
requires forming reason for the claim to be accepted by the evidence sentences
Arshad et al. [2019]. Previous approaches either concatenated evidence
sentences to a single string as done in top performing systems for the FEVER
task Thorne et al. [2018]. Many approaches also extract features from multiple
evidence sentences and aggregate them to verify a claim Zhou et al. [2019].
However, these methods lack the ability to extract semantic structure and
information present in multiple evidence sentences. Due to these shortcomings
more deeper architectures cannot be applied to these approaches for claim
verification.

For the extraction of evidence sentences Thorne et al. [2018] employs Term
Freuency Inverse Document Frequency (TF-IDF). A similar approach is also
applied to retrieve relevant documents from the original list of documents.
Yoneda et al. [2018] uses logistic regression to train a model on heuristic
based features [Zafar et al., 2020]. Another technique named Enhanced
Sequential Inference Model (ESIM) which uses BiLSTMs Beg and Beek [2013] and a
premise based hypothesis mechanism to classify claims has been used in
Hanselowski et al. [2018].

Verifying information at a larger scale is also a difficult task as the number
of websites containing Facts or spreading information is constantly
increasing. The problem of gathering data from crowd sourcing is that data
voluntarily produced, despite the good intentions, may many a times prone to
errors. Fan et al. [2020] investigates methods to improve the efficiency and
accuracy of fact checking systems by providing additional information about a
claim before verifying it. The additional information was in forms such as
passage based briefs which contained a list of relevant passages from
Wikipedia, entity oriented passages which consisted of pages from Wikipedia
Javed et al. [2020b] which revolved around the mentioned entities. Information
verification is an inefficient and cumbersome task when performed manually by
fact checkers and experts. A lot of research has been put into finding ways to
automate this task and achieve near human accuracy.

A research work aims to solve this by using sentence embeddings and
hierarchical attention networks Ma et al. [2019]; Javed et al. [2019]. The
work focuses on learning to find evidences such that their pattern is coherent
as well as they are semantically related with the claim. Their proposed
architecture consists of three main parts. The first is a coherence based
attention layer Naeem et al. [2020] which produces coherent evidences from
relevant articles when considering the claim. The second component is another
attention layer Zafar et al. [2019b] which is entailment based, this means the
layer can attend more to sentences that have an inference of the claim Rani et
al. [2015]. The final output layer Farooq et al. [2019b] predicts whether a
claim is accepted or refuted based on the evidence embeddings from the
previous layers. They have shown their technique has outperformed on three
public benchmarks.

##  4 Proposed approach

The information verification system is divided into three stages. The Document
Retrieval and sentence selection Beg et al. [2019] stage have been used from
Hanselowski et al. [2018] as they have the current best method which performs
well on the FEVER task Zafar et al. [2018]. The claim verification stage will
be improved upon.

For the first step of the document retrieval phase, potential entities are
extracted from the claim using a constituency parser by Gardner et al. [2018].
Relevant Wikipedia documents [Baig et al., b] are then obtained using the
MediaWiki API 111https://www.mediawiki.org/wiki/API:Main_page

The sentence selection component scores each sentence based on the relevance
score between evidence and claim Hanselowski et al. [2018]. In the claim
verification section an XLNET is used to generate embeddings Beg [2006] for
sentences which are then propagated through a Graph Convolutional network Beg
[2008] and finally Graph Attention is applied to get classification of the
claim Zafar et al. [2019a].

###  4.1 Evidence Sentence Selection

For verifying a claim it is essential to pick the most relevant sentences
which will in turn enable the claim to be more accurately refuted or accepted
Alvi et al. [2017]. To select a good evidence sentence we use the work of top
performing approaches Nie et al. [2019] for retrieving evidence sentences from
the FEVER task. The system is divided into two phases Khawaja et al. [2018].
Initially a list of relevant documents are shortlisted from Wikipedia articles
Farooq et al. [2019a] and in the second step candidate evidence sentences are
generated from the selected documents Beg [2009]. These sentences are then
further shortlisted based on a threshold to produce sentences that can be used
to verify claims.

To filter relevant documents from the Wikipedia, keyword matching is used
initially. To handle ambiguity in document titles NSMN Nie et al. [2019]
technique is used. These ambiguous documents amount to about 10% of all
documents for a particular claim Sahar et al. [2019]. Documents with
unambiguous titles are therefore allotted higher scores. The Sentence
selection system takes input the claim and all the candidate documents
produced bu keyword matching. In the big picture the NSMN system Majeed et al.
[2020] creates encodings Uzair et al. [2019], performs alignment and matching
to produce scores of documents from which a list of top ten documents are
selected for the next stage.

The evidence selection stage takes in the top ten selected documents from the
previous stage and outputs the list of relevant sentences Thaver and Beg
[2016]. The evidence selection task is considered as a semantics matching
problem which can considerably benefit from the deep contextualized
representations produced by large pretrained models like RoBERTa Liu et al.
[2019] and XLNet Yang et al. [2019]. To calculate the relevance of each
evidence sentence to a claim sentence they are passed into XLNET as follows:
[CLS CLAIM SEP EVIDENCE SEP]. Here the CLAIM and EVIDENCE are the tokenized
form of claim and evidence sentences respectively Seth and Beg [2006]. The CLS
token directs the network to produce embeddings for classification and the SEP
tokens are used to separate between the claim and evidence sentences. The
output embeddings of this phase are scored and top five most relevant evidence
sentences are selected Awan and Beg [2021].

###  4.2 SRL Graph

To utilise the intrinsic semantic and hierarchical structure Bangash et al.
[2017] of the input sentences a graph is the most suitable structure likely to
be built using the extracted information. There are many methods of
constructing graphs, one such method involves recognizing named entities
Etzioni et al. [2008]. This can also be combined with sequence to sequence
generation and relation classification which can be trained to produce
structured tuples Goodrich et al. [2019]. For constructing graphs in this work
we use the work of Carreras and Màrquez [2005] which involves using Semantic
Role Labeling (SRL) to construct graphs.

The procedure to build graphs using SRL Asad et al. [2020] involves the
following steps. Each sentence is segmented into a list of tuples using the
BERT based method proposed by Shi and Lin [2019]. The elements of each tuple
is divided into certain categories of nodes present in SRL graphs Tariq et al.
[2019], which are location, verb, temporal and argument. The graph creation
technique can also be extended to include more categories Beg and Van Beek
[2010]. Edges are created between two tuples linked by a verb. Multiple
evidence sentences are connected by an edge if they contain some common
information Zahid et al. [2020]. To establish the structural information for
claim sentences the same pipeline is used to create the SRL based claim graph.

Threshold | Recall | Precision | F1 | FEVER Score | Label Accuracy
---|---|---|---|---|---
0 | 23.76 | 82.68 | 36.80 | 91.10 | 74.84
$10^{-4}$ | 31.68 | 86.59 | 45.53 | 91.04 | 74.86
$10^{-3}$ | 40.63 | 86.37 | 55.23 | 90.86 | 74.91
$10^{-2}$ | 52.42 | 85.28 | 65.52 | 90.27 | 74.89
$10^{-1}$ | 71.68 | 81.18 | 75.72 | 87.70 | 74.81
Table 1:  The Recall, Precision, F1, FEVER score and Label accuracy achieved
for different thresholds on the FEVER dataset.

###  4.3 Word Representations

The produced SRL graphs of tuples containing words have to be transformed into
some mathematical representations which contain the semantics of the original
word. The main purpose of this step is to map words in such a space that two
semantically similar words are close together in that space. This step is best
performed with large attention Vaswani et al. [2017] based models such as BERT
and XLNET. Consider five evidence sentences ${s_{1},s_{2},s_{3},...,s_{5}}$,
concatenating these sentences will fail to capture essential semantic
structure needed for verifying the claim. A different technique to solve this
problem would be to construct an $NxM$ matrix containing the distances of
words. $N$ is the total number of words in the evidence. This however is an
inefficient technique as it would require a quadratic amount of memory space,
as shown by previous works Shaw et al. [2018].

Therefore for this research we use pretrained XLNET Yang et al. [2019] to
calculate distances and relations between words. This is also essential to
reason on sentence basis Beg [2007] which is essential for this task as there
are multiple evidence sentences. To enable the capturing of more meaningful
relations between sentences using XLNET we perform topology sorting such that
sentences that have greater number of connections in the SRL graph appear
close together.

###  4.4 Graph Convolution and Attention

When meaningful representations for words are obtained these can be passed
through a multi layer graph convolutional network (GCN) Kipf and Welling
[2017]; Qamar et al. . The representation of a single node is calculated by
averaging the representations of each of the tuples contained within that
node. After that a multi layer graph based convolutional network is used to
process the aggregated node representations of all the nodes and their
neighbours.

The graph based learning is performed for both the evidence and the claim
sentences. After propagating these graphs through GCNs Baig et al. [a] we
compute attention between the obtained representations of the evidence graph
and the claim graph. These attention computations are based on Graph Attention
Networks (GANs) Velickovic et al. [2018]. These graph attention computations
are passed into a multi-layer perceptron to obtain a three-way classification
of a claim belonging to one on the categories ”ACCEPTED”, ”REFUTED” or ”NOT
ENOUGH INFO”.

##  5 Evaluation and Experiments

In this section the results of various performed experiments are discussed.
The components evaluated consist of the sentence selection, document retrieval
and graph construction using semantic role labelling. The overall claim
verification framework is also evaluated from multiple aspects. A case study
Koleilat et al. [2006] is also done to demonstrate the effectiveness of the
framework Dilawar et al. [2018].

###  5.1 Datasets

Information verification systems are usually evaluated using the FEVER task,
Thorne et al. [2018] short for Fact Extraction and Verification, a benchmark
dataset for fact checking. A three way classification score is calculated
corresponding to the classes ”SUPPORTED”, ”REFUTED” or ”NOT ENOUGH INFO
(NEI)”. Another score called the FEVER score further measures the accuracy of
correct retrieved evidence of “SUPPORTED” and “REFUTED” classes.

To test the performance of our system we evaluate on the tasks present in the
Fact Extraction and VERification (FEVER) Thorne et al. [2018] benchmark. The
dataset is built by collecting evidence sentences and their corresponding
claims from the English Wikipedia which consists about 5 million documents.
Each ground truth label of the claim sentence is divided into one of the three
labels which are ”ACCEPTED”, ”REFUTED” or ”NOT ENOUGH INFO (NEI)” Javed et al.
[2020a]. The FEVER score is computed for each prediction which calculates how
good is the claim classified. In addition to this another F1 score is computed
which calculates if the correct set of evidences is selected for a particular
claim.

###  5.2 Baselines

The performance of our system is compared with top performing systems of the
FEVER task which involve a recent work GEAR Zhou et al. [2019], a work that
employs semantic neural network based matching Nie et al. [2019] both for
verifying a claim and picking out evidence sentences from a list of documents.
Yoneda et al. [2018] performs claim verification by first calculating the
veracity of each claim and evidence pair separately and then making a
prediction and finally aggregating the score of each prediction. Hanselowski
et al. [2018] uses pooling for aggregating the prediction of each evidence and
claim pair.

###  5.3 Model Evaluation

The proposed framework is evaluated using multiple different ways. The
accuracy scores of our proposed framework are compared with other baseline
systems. The sentence filters applied using thresholds on documents are also
evaluated. The effect of sentence embeddings are also explored. Many claims
also require reasoning over multiple evidence sentences to verify a claim. To
verify the effectiveness of the framework a more harder subset of tasks is
used as the dev set.

The accuracy of labels assigned to a claim are used to judge the effectiveness
of the models present in the claim verification system. The experiments also
reveal that further fine-tuning of the XLNET model used results in a
considerable increase in performance of the model on similar tasks. This also
reveals that such large pretrained models have a lot of representational
capacity to learn meaningful semantic relations between words Karsten et al.
[2007]. There is also a slight improvement when concatenating all evidence
embeddings obtained from XLNET as compared to pairing each sentence with the
corresponding claim. This also provides better aggregation of evidence and
better reasoning over multiple sentences as it is better suited to aggregate
and analyze multiple features.

###  5.4 Document Retrieval

The document retrieval component of the system is evaluated using the FEVER
score. Table 1 shows a list of FEVER scores corresponding to different
threshold values. The FEVER scores obtained using our system are slightly
lower as compared to previous works like Hanselowski et al. [2018], this may
be due to randomness of data and other factors. The sentence selection
component which selects sentences from shortlisted documents is also evaluated
with the same thresholds as shown in Table 1. The best results are achieved
when the threshold is close to zero. As the threshold increases the recall and
the FEVER score decrease constantly while the F1 score and precision score
increases. The results also make sense intuitively because if filter criteria
for evidence sentences is relaxed then the probability of verifying claims
would naturally increase. However as the threshold is increased lesser
evidence sentences are selected which have a stronger evidence for the claim,
this leads to a better F1 and precision score.

##  6 Ablation Studies

In this section the system is evaluated by removing different components and
testing how that effects the performance of the system. This also reveals how
important each component is in the whole system. The dev subset containing
multiple evidence sentences that aggregate the ground truth labels of claims
are used for this evaluation task. The main performance degradation occurs
when initial or higher level components like document selection are removed.
This is because a small initial error propagating through subsequent
components results in a larger impact. When the document retrieval component
is removed, all available documents are then passed on for claim verification
and it will be difficult to select relevant sentences to verify the claim.

Linking claim entities to entities in evidence is also an important piece in
rightly verifying a claim based on its content. To verify the selection of
correct entities we test our models using a dev set enhanced with evidence
sentences. These sentences contain the ground truth evidences with the score
signifying the relevance of each sentence. This ensures that each claim in the
enhanced dataset is paired with a ground truth sentence and the retrieved
sentence. The study performed on the enhanced dataset leads to a 1.4% increase
in the scores as compared to the original dev set used for evaluation.

##  7 Conclusion

In this research we propose a novel framework for verifying claims which is
based of Graph evidence reasoning and aggregation. The claim verification task
is mainy trained on the popular FEVER dataset. The proposed framework uses
XLNET to encode evidence sentences so that Graph convolution and attention can
be applied to those meaningful embeddings. The document retrieval and evidence
sentence selection components are used out-of-the-box from previous studies
and the framework is able to achieve significant improvements on the FEVER
task. For future research a multi-step pipeline for extracting evidence
sentences from documents can be performed that also integrate information from
external sources to verify a claim.

## References

  * Allcott and Gentzkow [2017] H. Allcott and M. Gentzkow.  Social media and fake news in the 2016 election.  _Journal of economic perspectives_ , 31(2):211–36, 2017.
  * Alvi et al. [2017] H. M. Alvi, H. Sahar, A. A. Bangash, and M. O. Beg.  Ensights: A tool for energy aware software development.  In _2017 13th International Conference on Emerging Technologies (ICET)_ , pages 1–6. IEEE, 2017.
  * Angeli and Manning [2014] G. Angeli and C. D. Manning.  Naturalli: Natural logic inference for common sense reasoning.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 534–545, 2014.
  * Arshad et al. [2019] M. U. Arshad, M. F. Bashir, A. Majeed, W. Shahzad, and M. O. Beg.  Corpus for emotion detection on roman urdu.  In _2019 22nd International Multitopic Conference (INMIC)_ , pages 1–6. IEEE, 2019.
  * Asad et al. [2020] M. Asad, M. Asim, T. Javed, M. O. Beg, H. Mujtaba, and S. Abbas.  Deepdetect: detection of distributed denial of service attacks using deep learning.  _The Computer Journal_ , 63(7):983–994, 2020\.
  * Awan and Beg [2021] M. N. Awan and M. O. Beg.  Top-rank: a topicalpostionrank for extraction and classification of keyphrases in text.  _Computer Speech & Language_, 65:101116, 2021.
  * Baig et al. [a] T. I. Baig, N. Banaras, E. Banissi, R. Bashir, M. O. Beg, J. Bilal, A. H. Butt, W. Chishti, C. Chrysoulas, A. Dastgir, et al.  Awan, shahid mahmood 245 ayubi, salah-u-din 192.  a.
  * Baig et al. [b] Z. Baig, M. O. Beg, B. M. Bhatti, F. A. Bhuiyan, T. F. Bissyandé, S. Chen, M. B. Chhetri, M. Couto, J. de Macedo, R. de Vries, et al.  Ahmed, sanam 124 aleti, aldeida 105 aloísio, joão 151 arachchilage, nalin asanka gamagedara 7.  b.
  * Bangash et al. [2017] A. A. Bangash, H. Sahar, and M. O. Beg.  A methodology for relating software structure with energy consumption.  In _2017 IEEE 17th International Working Conference on Source Code Analysis and Manipulation (SCAM)_ , pages 111–120. IEEE, 2017.
  * Beg [2008] M. Beg.  Critical path heuristic for automatic parallelization.  2008\.
  * Beg [2009] M. Beg.  Flecs: A framework for rapidly implementing forwarding protocols.  In _International Conference on Complex Sciences_ , pages 1761–1773. Springer, 2009.
  * Beg and Beek [2013] M. Beg and P. v. Beek.  A constraint programming approach for integrated spatial and temporal scheduling for clustered architectures.  _ACM Transactions on Embedded Computing Systems (TECS)_ , 13(1):1–23, 2013.
  * Beg and Van Beek [2010] M. Beg and P. Van Beek.  A graph theoretic approach to cache-conscious placement of data for direct mapped caches.  In _Proceedings of the 2010 international symposium on Memory management_ , pages 113–120, 2010.
  * Beg et al. [2006] M. Beg, L. Charlin, and J. So.  Maxsm: A multi-heuristic approach to xml schema matching.  2006\.
  * Beg [2006] M. O. Beg.  Performance analysis of packet forwarding on ixp2400 network processor.  2006\.
  * Beg [2007] M. O. Beg.  Flecs: A data-driven framework for rapid protocol prototyping.  Master’s thesis, University of Waterloo, 2007.
  * Beg et al. [2019] M. O. Beg, M. N. Awan, and S. S. Ali.  Algorithmic machine learning for prediction of stock prices.  In _FinTech as a Disruptive Technology for Financial Institutions_ , pages 142–169. IGI Global, 2019.
  * Bowman et al. [2015] S. Bowman, G. Angeli, C. Potts, and C. D. Manning.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 632–642, 2015.
  * Brown et al. [2020] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Carreras and Màrquez [2005] X. Carreras and L. Màrquez.  Introduction to the conll-2005 shared task: Semantic role labeling.  In _Proceedings of the ninth conference on computational natural language learning (CoNLL-2005)_ , pages 152–164, 2005.
  * Chen et al. [2017] Q. Chen, X. Zhu, Z.-H. Ling, S. Wei, H. Jiang, and D. Inkpen.  Enhanced lstm for natural language inference.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1657–1668, 2017\.
  * Dagan et al. [2013] I. Dagan, D. Roth, M. Sammons, and F. M. Zanzotto.  Recognizing textual entailment: Models and applications.  _Synthesis Lectures on Human Language Technologies_ , 6(4):1–220, 2013.
  * Dilawar et al. [2018] N. Dilawar, H. Majeed, M. O. Beg, N. Ejaz, K. Muhammad, I. Mehmood, and Y. Nam.  Understanding citizen issues through reviews: A step towards data informed planning in smart cities.  _Applied Sciences_ , 8(9):1589, 2018.
  * Etzioni et al. [2008] O. Etzioni, M. Banko, S. Soderland, and D. S. Weld.  Open information extraction from the web.  _Communications of the ACM_ , 51(12):68–74, 2008\.
  * Fan et al. [2020] A. Fan, A. Piktus, F. Petroni, G. Wenzek, M. Saeidi, A. Vlachos, A. Bordes, and S. Riedel.  Generating fact checking briefs.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7147–7161, 2020.
  * Farooq et al. [2019a] M. U. Farooq, M. O. Beg, et al.  Bigdata analysis of stack overflow for energy consumption of android framework.  In _2019 International Conference on Innovative Computing (ICIC)_ , pages 1–9. IEEE, 2019a.
  * Farooq et al. [2019b] M. U. Farooq, S. U. R. Khan, and M. O. Beg.  Melta: A method level energy estimation technique for android development.  In _2019 International Conference on Innovative Computing (ICIC)_ , pages 1–10. IEEE, 2019b.
  * Gardner et al. [2018] M. Gardner, J. Grus, M. Neumann, O. Tafjord, P. Dasigi, N. F. Liu, M. Peters, M. Schmitz, and L. Zettlemoyer.  Allennlp: A deep semantic natural language processing platform.  _ACL 2018_ , page 1, 2018.
  * Goodrich et al. [2019] B. Goodrich, V. Rao, P. J. Liu, and M. Saleh.  Assessing the factual accuracy of generated text.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 166–175, 2019.
  * Hanselowski et al. [2018] A. Hanselowski, H. Zhang, Z. Li, D. Sorokin, B. Schiller, C. Schulz, and I. Gurevych.  Ukp-athene: Multi-sentence textual entailment for claim verification.  _EMNLP 2018_ , page 103, 2018.
  * Hassan et al. [2015] N. Hassan, B. Adair, J. T. Hamilton, C. Li, M. Tremayne, J. Yang, and C. Yu.  The quest to automate fact-checking.  In _Proceedings of the 2015 Computation+ Journalism Symposium_ , 2015\.
  * Javed et al. [2020a] A. R. Javed, M. O. Beg, M. Asim, T. Baker, and A. H. Al-Bayatti.  Alphalogger: Detecting motion-based side-channel attack using smartphone keystrokes.  _Journal of Ambient Intelligence and Humanized Computing_ , pages 1–14, 2020a.
  * Javed et al. [2020b] A. R. Javed, M. U. Sarwar, M. O. Beg, M. Asim, T. Baker, and H. Tawfik.  A collaborative healthcare framework for shared healthcare plan with ambient intelligence.  _Human-centric Computing and Information Sciences_ , 10(1):1–21, 2020b.
  * Javed et al. [2019] H. T. Javed, M. O. Beg, H. Mujtaba, H. Majeed, and M. Asim.  Fairness in real-time energy pricing for smart grid using unsupervised learning.  _The Computer Journal_ , 62(3):414–429, 2019\.
  * Karsten et al. [2007] M. Karsten, S. Keshav, S. Prasad, and M. Beg.  An axiomatic basis for communication.  _ACM SIGCOMM Computer Communication Review_ , 37(4):217–228, 2007.
  * Khawaja et al. [2018] H. S. Khawaja, M. O. Beg, and S. Qamar.  Domain specific emotion lexicon expansion.  In _2018 14th International Conference on Emerging Technologies (ICET)_ , pages 1–5. IEEE, 2018.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net, 2017.  URL https://openreview.net/forum?id=SJU4ayYgl.
  * Koleilat et al. [2006] W. Koleilat, J. So, and M. Beg.  Watagent: A fresh look at tac-scm agent design.  2006\.
  * Liu et al. [2019] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov.  Roberta: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692, 2019.  URL http://arxiv.org/abs/1907.11692.
  * Ma et al. [2019] J. Ma, W. Gao, S. Joty, and K.-F. Wong.  Sentence-level evidence embedding for claim verification with hierarchical attention networks.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2561–2571, 2019.
  * Majeed et al. [2020] A. Majeed, H. Mujtaba, and M. O. Beg.  Emotion detection in roman urdu text using machine learning.  In _Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering Workshops_ , pages 125–130, 2020.
  * Nacem et al. [2020] S. Nacem, M. Iqbal, M. Saqib, M. Saad, M. S. Raza, Z. Ali, N. Akhtar, M. O. Beg, W. Shahzad, and M. U. Arshad.  Subspace gaussian mixture model for continuous urdu speech recognition using kaldi.  In _2020 14th International Conference on Open Source Systems and Technologies (ICOSST)_ , pages 1–7. IEEE, 2020.
  * Naeem et al. [2020] B. Naeem, A. Khan, M. O. Beg, and H. Mujtaba.  A deep learning framework for clickbait detection on social area network using natural language cues.  _Journal of Computational Social Science_ , pages 1–13, 2020.
  * Nakashole and Mitchell [2014] N. Nakashole and T. Mitchell.  Language-aware truth assessment of fact candidates.  In _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1009–1019, 2014\.
  * Nie et al. [2019] Y. Nie, H. Chen, and M. Bansal.  Combining fact extraction and verification with neural semantic matching networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 6859–6866, 2019.
  * Padia et al. [2018] A. Padia, F. Ferraro, and T. Finin.  Team umbc-fever: Claim verification using semantic lexical resources.  _Team UMBC-FEVER: Claim verification using Semantic Lexical Resources_ , 2018.
  * [47] S. Qamar, H. Mujtaba, H. Majeed, and M. O. Beg.  Relationship identification between conversational agents using emotion analysis.  _Cognitive Computation_ , pages 1–15.
  * Radford et al. [2019] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Rani et al. [2015] U. Rani, A. Imdad, and M. Beg.  Case 2: Recurrent anemia in a 10-year-old girl.  _Pediatrics in review_ , 36(12):548–550, 2015\.
  * Sahar et al. [2019] H. Sahar, A. A. Bangash, and M. O. Beg.  Towards energy aware object-oriented development of android applications.  _Sustainable Computing: Informatics and Systems_ , 21:28–46, 2019.
  * Sathe et al. [2020] A. Sathe, S. Ather, T. M. Le, N. Perry, and J. Park.  Automated fact-checking of claims from wikipedia.  In _Proceedings of The 12th Language Resources and Evaluation Conference_ , pages 6874–6882, 2020.
  * Seth and Beg [2006] A. Seth and M. Beg.  Achieving privacy and security in radio frequency identification.  In _Proceedings of the 2006 International Conference on Privacy, Security and Trust: Bridge the Gap Between PST Technologies and Business Services_ , pages 1–1, 2006.
  * Sharma et al. [2019] K. Sharma, F. Qian, H. Jiang, N. Ruchansky, M. Zhang, and Y. Liu.  Combating fake news: A survey on identification and mitigation techniques.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 10(3):1–42, 2019.
  * Shaw et al. [2018] P. Shaw, J. Uszkoreit, and A. Vaswani.  Self-attention with relative position representations.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 464–468, 2018.
  * Shi and Lin [2019] P. Shi and J. Lin.  Simple BERT models for relation extraction and semantic role labeling.  _CoRR_ , abs/1904.05255, 2019.  URL http://arxiv.org/abs/1904.05255.
  * Tariq et al. [2019] M. Tariq, H. Majeed, M. O. Beg, F. A. Khan, and A. Derhab.  Accurate detection of sitting posture activities in a secure iot based assisted living environment.  _Future Generation Computer Systems_ , 92:745–757, 2019\.
  * Thaver and Beg [2016] D. Thaver and M. Beg.  Pulmonary crohn’s disease in down syndrome: A link or linkage problem.  _Case reports in gastroenterology_ , 10(2):206–211, 2016.
  * Thorne et al. [2018] J. Thorne, A. Vlachos, C. Christodoulopoulos, and A. Mittal.  Fever: a large-scale dataset for fact extraction and verification.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 809–819, 2018.
  * Uzair et al. [2019] A. Uzair, M. O. Beg, H. Mujtaba, and H. Majeed.  Weec: Web energy efficient computing: A machine learning approach.  _Sustainable Computing: Informatics and Systems_ , 22:230–243, 2019.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  In _Advances in neural information processing systems_ , pages 5998–6008, 2017.
  * Velickovic et al. [2018] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph attention networks.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.  URL https://openreview.net/forum?id=rJXMpikCZ.
  * Vosoughi et al. [2018] S. Vosoughi, D. Roy, and S. Aral.  The spread of true and false news online.  _Science_ , 359(6380):1146–1151, 2018.
  * Yang et al. [2019] Z. Yang, Z. Dai, Y. Yang, J. Carbonell, R. R. Salakhutdinov, and Q. V. Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  In _Advances in neural information processing systems_ , pages 5753–5763, 2019.
  * Yoneda et al. [2018] T. Yoneda, J. Mitchell, J. Welbl, P. Stenetorp, and S. Riedel.  Ucl machine reading group: Four factor framework for fact finding (hexaf).  In _Proceedings of the First Workshop on Fact Extraction and VERification (FEVER)_ , pages 97–102, 2018.
  * Zafar et al. [2018] A. Zafar, H. Mujtaba, M. O. Beg, and S. Ali.  Deceptive level generator.  2018\.
  * Zafar et al. [2019a] A. Zafar, H. Mujtaba, S. Ashiq, and M. O. Beg.  A constructive approach for general video game level generation.  In _2019 11th Computer Science and Electronic Engineering (CEEC)_ , pages 102–107. IEEE, 2019a.
  * Zafar et al. [2019b] A. Zafar, H. Mujtaba, M. T. Baig, and M. O. Beg.  Using patterns as objectives for general video game level generation.  _ICGA Journal_ , 41(2):66–77, 2019b.
  * Zafar et al. [2020] A. Zafar, H. Mujtaba, and M. O. Beg.  Search-based procedural content generation for gvg-lg.  _Applied Soft Computing_ , 86:105909, 2020.
  * Zahid et al. [2020] R. Zahid, M. O. Idrees, H. Mujtaba, and M. O. Beg.  Roman urdu reviews dataset for aspect based opinion mining.  In _2020 35th IEEE/ACM International Conference on Automated Software Engineering Workshops (ASEW)_ , pages 138–143. IEEE, 2020.
  * Zhou et al. [2019] J. Zhou, X. Han, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun.  Gear: Graph-based evidence aggregating and reasoning for fact verification.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 892–901, 2019.