# Asymmetric list sizes in bipartite graphs

Noga Alon Department of Mathematics, Princeton University, Princeton, NJ
08544, USA and Schools of Mathematics and Computer Science, Tel Aviv
University, Tel Aviv 6997801, Israel. Email<EMAIL_ADDRESS>Supported in
part by NSF grant DMS-1855464, BSF grant 2018267 and the Simons Foundation.
Stijn Cambie Department of Mathematics, Radboud University, Postbus 9010, 6500
GL Nijmegen, Netherlands. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Supported by a Vidi grant (639.032.614) of the
Netherlands Organisation for Scientific Research (NWO). Ross J. Kang
22footnotemark: 2

###### Abstract

Given a bipartite graph with parts $A$ and $B$ having maximum degrees at most
$\Delta_{A}$ and $\Delta_{B}$, respectively, consider a list assignment such
that every vertex in $A$ or $B$ is given a list of colours of size $k_{A}$ or
$k_{B}$, respectively.

We prove some general sufficient conditions in terms of $\Delta_{A}$,
$\Delta_{B}$, $k_{A}$, $k_{B}$ to be guaranteed a proper colouring such that
each vertex is coloured using only a colour from its list. These are
asymptotically nearly sharp in the very asymmetric cases. We establish one
sufficient condition in particular, where $\Delta_{A}=\Delta_{B}=\Delta$,
$k_{A}=\log\Delta$ and $k_{B}=(1+o(1))\Delta/\log\Delta$ as $\Delta\to\infty$.
This amounts to partial progress towards a conjecture from 1998 of Krivelevich
and the first author.

We also derive some necessary conditions through an intriguing connection
between the complete case and the extremal size of approximate Steiner
systems. We show that for complete bipartite graphs these conditions are
asymptotically nearly sharp in a large part of the parameter space. This has
provoked the following.

In the setup above, we conjecture that a proper list colouring is always
guaranteed

  * •

if $k_{A}\geq\Delta_{A}^{\varepsilon}$ and $k_{B}\geq\Delta_{B}^{\varepsilon}$
for any $\varepsilon>0$ provided $\Delta_{A}$ and $\Delta_{B}$ are large
enough;

  * •

if $k_{A}\geq C\log\Delta_{B}$ and $k_{B}\geq C\log\Delta_{A}$ for some
absolute constant $C>1$; or

  * •

if $\Delta_{A}=\Delta_{B}=\Delta$ and $k_{B}\geq
C(\Delta/\log\Delta)^{1/k_{A}}\log\Delta$ for some absolute constant $C>0$.

These are asymmetric generalisations of the above-mentioned conjecture of
Krivelevich and the first author, and if true are close to best possible. Our
general sufficient conditions provide partial progress towards these
conjectures.

##  1 Introduction

List colouring of graphs, whereby arbitrary restrictions on the possible
colours used per vertex are imposed, was introduced independently by Erdős,
Rubin and Taylor [10] and by Vizing [16]. Let $G=(V,E)$ be a simple,
undirected graph. For a positive integer $k$, a mapping
$L:V\to\binom{{\mathbb{Z}}^{+}}{k}$ is called a $k$-list-assignment of $G$; a
colouring $c:V\to{\mathbb{Z}}^{+}$ is called an $L$-colouring if $c(v)\in
L(v)$ for any $v\in V$. We say $G$ is $k$-choosable if for any $k$-list-
assignment $L$ of $G$ there is a proper $L$-colouring of $G$. The choosability
$\operatorname{ch}(G)$ (or choice number or list chromatic number) of $G$ is
the least $k$ such that $G$ is $k$-choosable.

Note that if $G$ is $k$-choosable then it is properly $k$-colourable. On the
other hand, Erdős, Rubin and Taylor [10] exhibited bipartite graphs with
arbitrarily large choosability. Let $K_{n_{1},n_{2}}$ denote a complete
bipartite graph with part sizes $n_{1}$ and $n_{2}$.

######  Theorem 1 ([10]).

For some function $M(k)$ with $M(k)=2^{k+o(k)}$ as $k\to\infty$,

  1. $(i)$

$K_{n,n}$ is not $k$-choosable if $n\geq M(k)$, and

  2. $(ii)$

$K_{n_{1},n_{2}}$ is $k$-choosable if $n_{1}+n_{2}<M(k)$.

More succinctly Theorem 1 says that $\operatorname{ch}(K_{n,n})\sim\log_{2}n$
as $n\to\infty$.

There are two contrasting ways to try to strengthen this last statement. First
does the lower bound hold more generally; that is, does a bipartite graph with
minimum degree $\delta$ have choosability $\Omega(\log\delta)$ as
$\delta\to\infty$? Indeed this was shown by the first author [1] using a
probabilistic argument; later Saxton and Thomason [15] proved the
asymptotically optimal lower bound of $(1+o(1))\log_{2}\delta$. Second does
the upper bound hold more generally; that is, does a bipartite graph with
maximum degree $\Delta$ always have choosability $O(\log\Delta)$ as
$\Delta\to\infty$? Krivelevich and the first author conjectured this in 1998.

######  Conjecture 2 ([2]).

There is some absolute constant $C>0$ such that any bipartite graph of maximum
degree at most $\Delta$ is $k$-choosable if $k\geq C\log\Delta$.

Johansson’s result for triangle-free graphs [12] gives the conclusion with
$k\geq C\Delta/\log\Delta$, which is far from the conjectured bound.
Conjecture 2 is an elegant problem in a well-studied area, but apart from
constant factors111In a recent advance, Molloy [14] considerably improved on
the constant in Johansson’s, cf. also [5]. there has been no progress until
now.

Despite the apparent difficulty of Conjecture 2, we propose an asymmetric
refinement. Given a bipartite graph $G=(V{=}A\cup B,E)$ with parts $A$, $B$
and positive integers $k_{A}$, $k_{B}$, a mapping
$L:A\to\binom{{\mathbb{Z}}^{+}}{k_{A}},B\to\binom{{\mathbb{Z}}^{+}}{k_{B}}$ is
called a $(k_{A},k_{B})$-list-assignment of $G$. We say $G$ is
$(k_{A},k_{B})$-choosable if there is guaranteed a proper $L$-colouring of $G$
for any such $L$.

######  Problem 3.

Given $\Delta_{A}$ and $\Delta_{B}$, what are optimal choices of
$k_{A}\leq\Delta_{A}$ and $k_{B}\leq\Delta_{B}$ for which any bipartite graph
$G=(V{=}A\cup B,E)$ with parts $A$ and $B$ having maximum degrees at most
$\Delta_{A}$ and $\Delta_{B}$, respectively, is $(k_{A},k_{B})$-choosable?

We have the upper bounds on $k_{A}$, $k_{B}$, since the problem is trivial if
$k_{A}>\Delta_{A}$ or $k_{B}>\Delta_{B}$.

Note that Problem 3, since it has a higher-dimensional parameter space, has
wider scope than Conjecture 2 and is necessarily more difficult. However, the
extra generality in Problem 3 has permitted a glimpse at an unexpected and
basic connection between list colouring and combinatorial design theory
(Theorem 6). This has prompted us to explore specific areas of the parameter
space in Problem 3, motivating concrete versions of Problem 3 in the spirit of
Conjecture 2 (Conjecture 7). One hope of ours is that further study of these
problems may yield insights into Conjecture 2. But in fact, already in the
present work, we have obtained asymmetric progress towards Conjecture 2
(Corollary 10).

Our first main result provides general progress towards Problem 3.

######  Theorem 4.

Let the positive integers $\Delta_{A}$, $\Delta_{B}$, $k_{A}$, $k_{B}$ satisfy
one of the following conditions, as stated or with roles exchanged between
$\Delta_{A}$ and $\Delta_{B}$ and between $k_{A}$ and $k_{B}$.

  1. $(i)$

$k_{B}\geq(ek_{A}\Delta_{B})^{1/k_{A}}\Delta_{A}$.

  2. $(ii)$

$\displaystyle
e(\Delta_{A}(\Delta_{B}-1)+1)\left(1-(1-1/k_{B})^{\Delta_{A}\min\left\\{1,k_{B}/k_{A}\right\\}}\right)^{k_{A}}\leq
1.$

Then any bipartite graph $G=(V{=}A\cup B,E)$ with parts $A$ and $B$ having
maximum degrees at most $\Delta_{A}$ and $\Delta_{B}$, respectively, is
$(k_{A},k_{B})$-choosable.

Theorem 4 under condition $(i)$ follows from a simple application of the
Lovász Local Lemma, as we show in Section 2. This sufficient condition for
Problem 3 is related to independent transversals in hypergraphs, cf. [8, 11],
and to least conflict choosability [7]. In the most asymmetric settings,
condition $(i)$ is sharp up to a constant factor. We prove Theorem 4 under
condition $(ii)$ in Section 3 with the Lovász Local Lemma and a link to the
coupon collector problem. In an attempt to clear up the ‘parameter soup’
arising from Problem 3 and the above sufficient conditions, we will discuss
specific natural context for these after presenting some further results.

We complement our sufficient conditions for $(k_{A},k_{B})$-choosability with
necessary ones, given mainly by the complete bipartite graphs. An easy
boundary case is provided as follows, for warmup. This generalises a classic
non-$k$-choosable construction.

######  Proposition 5.

For any $\delta,k\geq 2$, the complete bipartite graph $G=(V{=}A\cup B,E)$
with $|A|=\delta^{k}$ and $|B|=k$ is not $(k,\delta)$-choosable.

###### Proof.

Let the vertices of $B$ be assigned $k$ disjoint lists of length $\delta$, and
let the vertices of $A$ be assigned all possible $k$-tuples drawn from these
$k$ disjoint lists. ∎

This is best possible in the sense that the conclusion does not hold if
$|A|<\delta^{k}$ or $|B|<k$; however, in Section 8 we exhibit a non-complete
graph that is a slightly more efficient non-$(k,\delta)$-choosable
construction. On the other hand, Proposition 5 shows that condition $(i)$ in
Theorem 4 cannot be relaxed much in general. This follows for instance by
considering the most asymmetric case, namely $k=k_{A}=\Delta_{A}$ and
$\delta=\Delta_{B}^{1/k}$, with $k$ fixed and $\Delta_{B}\to\infty$. Thus for
fixed $k_{A}$ and $\Delta_{A}$ Problem 3 is settled up to a constant factor.

Our second main result is a related but much broader necessary condition for
Problem 3, also via the complete case. Let us write
$\overline{M}(k_{1},k_{2},\ell)$ for the hypergraph Turán number defined as
the minimum number of edges in a $k_{2}$-uniform hypergraph on $\ell$ vertices
with no independent set of size $\ell-k_{1}.$ This parameter is equivalent to
the extremal size of approximate Steiner systems; in particular,
$\overline{M}(k_{1},k_{2},\ell)$ is equal to the cardinality of a smallest
$k_{1}$-$(\ell,\ell-k_{2},\mathbb{Z}^{+})$ design, cf. [9, Ch. 13] and [13].
We can draw a link between this classical extremal parameter and Problem 3. We
show the following result in Section 4.

######  Theorem 6.

Let $k_{A},k_{B},\ell,k_{1},k_{2}$ be integers such that $k_{A},k_{B}\geq 2$
and $\ell=k_{1}+k_{2}+1$. The complete bipartite graph $G=(V{=}A\cup B,E)$
with $|A|=\overline{M}(k_{1},k_{A},\ell)$ and
$|B|=\overline{M}(k_{2},k_{B},\ell)$ is not $(k_{A},k_{B})$-choosable.

This link allows us, using known results for $\overline{M}$, to read off
decent necessary conditions for specific parameterisations of Problem 3. As
one example, a lower bound on $\operatorname{ch}(K_{n,n})$ of the form
$\operatorname{ch}(K_{n,n})\gtrsim\frac{1}{2}\log_{2}n$ follows from Theorem 6
with the choice $k_{1}=k_{2}=k-1$, $k_{A}=k_{B}=k$, and $\ell=2k-1$ for some
$k$. As another example, a slightly weaker form of the necessary condition of
Proposition 5 follows with the choice $k_{1}=k_{A}(k_{B}-1)$, $k_{2}=k_{A}-1$,
and $\ell=k_{A}k_{B}$. We detail both of these easy examples in Section 4.

Note though that these last two examples show that Theorem 6 provides
suboptimal necessary conditions for $(k_{A},k_{B})$-choosability even in the
complete case. Furthermore, in Section 8 we give a construction to show that
the complete case cannot, in general, be precisely extremal for Problem 3.
Nevertheless, we surmise that Theorem 6 provides some good rough borders for
Problem 3. More specifically, in Section 5 we give some basic sufficient
conditions for $(k_{A},k_{B})$-choosability specific to the complete case and
show in Section 6, through some routine asymptotic calculus, how these roughly
match with Theorem 6 over a broad family of parameterisations for Problem 3.
Then, just as Conjecture 2 was informed by Theorem 1, the asymptotic behaviour
of $(k_{A},k_{B})$-choosability in the complete case leads us to conjecture
the following concrete versions of Problem 3.

######  Conjecture 7.

Let the positive integers $\Delta_{A}$, $\Delta_{B}$, $k_{A}$, $k_{B}$ satisfy
one of the following.

  1. $(i)$

Given $\varepsilon>0$, we have $\Delta_{A},\Delta_{B}\geq\Delta_{0}$ for some
$\Delta=\Delta_{0}(\varepsilon)$, and

$\displaystyle k_{A}\geq\Delta_{A}^{\varepsilon}\quad\text{and}\quad
k_{B}\geq\Delta_{B}^{\varepsilon}.$

  2. $(ii)$

For some absolute constant $C>1$,

$\displaystyle k_{A}\geq C\log\Delta_{B}\quad\text{and}\quad k_{B}\geq
C\log\Delta_{A}.$

  3. $(iii)$

$\Delta_{A}=\Delta_{B}=\Delta$, and, for some absolute constant $C>0$,

$\displaystyle k_{B}\geq
C(\Delta/\log\Delta)^{1/k_{A}}\log\Delta\quad\text{or}\quad k_{A}\geq
C(\Delta/\log\Delta)^{1/k_{B}}\log\Delta.$

Then any bipartite graph $G=(V{=}A\cup B,E)$ with parts $A$ and $B$ having
maximum degrees at most $\Delta_{A}$ and $\Delta_{B}$, respectively, is
$(k_{A},k_{B})$-choosable.

Conjecture 7 constitutes three natural asymmetric analogues of Conjecture 2.
The first is weaker than Conjecture 2; the latter two are stronger. We discuss
these separately in turn.

Behind condition $(i)$, Conjecture 7 concerns the question, for what positive
functions $f$ does $k_{A}\geq f(\Delta_{A})$ and $k_{B}\geq f(\Delta_{B})$
suffice for $(k_{A},k_{B})$-choosability, no matter how far apart $\Delta_{A}$
and $\Delta_{B}$ are? Essentially we posit that some $f$ with $f(x)=x^{o(1)}$
as $x\to\infty$ will work, and this would be best possible due to the complete
case (Theorem 16$(i)$). In particular, $f(x)=O(\log x)$ is impossible, in
contrast to Conjecture 2. But in fact, Theorem 4 shows that Conjecture 7 under
condition $(i)$ reduces to its most symmetric form.

######  Corollary 8.

Given $0<\varepsilon<1$ and integers $\Delta_{A}$, $\Delta_{B}$ satisfying
$\Delta_{B}>\Delta_{A}^{2/\varepsilon}$ and
$\Delta_{A}>(4/\varepsilon)^{1/\varepsilon}$, any bipartite graph
$G=(V{=}A\cup B,E)$ with parts $A$ and $B$ having maximum degrees at most
$\Delta_{A}$ and $\Delta_{B}$, respectively, is
$(\Delta_{A}^{\varepsilon},\Delta_{B}^{\varepsilon})$-choosable.

As a consequence, Conjecture 7 under condition $(i)$ follows from the same
assertion under the further assumption that $\Delta_{A}=\Delta_{B}=\Delta$.

###### Proof.

It suffices to check condition $(i)$ of Theorem 4 with
$k_{A}=\Delta_{A}^{\varepsilon}$ and $k_{B}=\Delta_{B}^{\varepsilon}$. Indeed,
as $\Delta_{B}^{2}>e\Delta_{A}^{\varepsilon}\Delta_{B}$,
$\varepsilon/4>1/\Delta_{A}^{\varepsilon}$ and
$\Delta_{B}^{\varepsilon/2}>\Delta_{A}$, we have
$\Delta_{B}^{\varepsilon}>\left(e\Delta_{A}^{\varepsilon}\Delta_{B}\right)^{1/\Delta_{A}^{\varepsilon}}\Delta_{A}$.

Assume condition $(i)$ of Conjecture 7, and moreover assume the truth of the
conjecture only for its most asymmetric form $\Delta_{A}=\Delta_{B}=\Delta$.
We may assume that $\Delta_{0}>(4/\varepsilon)^{1/\varepsilon}$, and so,
without loss of generality, we may also assume by the first part that
$\Delta_{A}\leq\Delta_{B}\leq\Delta_{A}^{2/\varepsilon}$. For any bipartite
graph $G=(V{=}A\cup B,E)$ with parts $A$ and $B$ having maximum degrees at
most $\Delta_{A}$ and $\Delta_{B}$, we have from the assumption that $G$ is
$k$-choosable for, say,
$k=\Delta_{B}^{\varepsilon^{3}}\leq\Delta_{A}^{2\varepsilon^{2}}$, provided
$\Delta_{B}$, and thus $\Delta_{A}$, is large enough as a function of
$\varepsilon$. This is smaller than $\Delta_{A}^{\varepsilon}$ for
$\Delta_{A}$ sufficiently large as a function of $\varepsilon$, as required. ∎

Thus Conjecture 7 under condition $(i)$ would follow from a weaker form of
Conjecture 2. By an earlier work due to Davies, de Joannis de Verclos, Pirot
and the third author [5], we so far know that $f(x)=(1+o(1))x/\log x$ works.

Under condition $(ii)$, Conjecture 7 concerns a ‘crossed’ version of the
previous question, so for what positive functions $g$ does $k_{A}\geq
g(\Delta_{B})$ and $k_{B}\geq g(\Delta_{A})$ suffice for
$(k_{A},k_{B})$-choosability? In this case, we conjecture that $g(x)=O(\log
x)$ will work, which coincides with Conjecture 2 in the symmetric case
$\Delta_{A}=\Delta_{B}=\Delta$. The complete graphs demonstrate the
hypothetical sharpness of this assertion up to a constant factor for nearly
the entire range of possibilities for $\Delta_{A}$ and $\Delta_{B}$ (Theorem
16$(ii)$). Some modest partial progress towards Conjecture 7 under condition
$(ii)$ follows from Theorem 4.

######  Corollary 9.

Given $\varepsilon>0$, there exists $\delta$ such that for $\Delta_{B}$ large
enough, any bipartite graph $G=(V{=}A\cup B,E)$ with parts $A$ and $B$ having
maximum degrees at most $\Delta_{A}$ and $\Delta_{B}$, respectively, is
$(\delta\log\Delta_{B},(1+\varepsilon)\Delta_{A})$\- and
$(\log\Delta_{B},(e+\varepsilon)\Delta_{A})$-choosable.

###### Proof.

This follows for $\Delta_{B}$ large enough from condition $(i)$ of Theorem 4
with either $k_{A}=\delta\log\Delta_{B}$ and $k_{B}=(1+\varepsilon)\Delta_{A}$
or with $k_{A}=\log\Delta_{B}$ and $k_{B}=(e+\varepsilon)\Delta_{A}$. ∎

Under condition $(iii)$, Conjecture 7 concerns the setting most closely
related to Conjecture 2. It suggests how Problem 3 might behave for the
symmetric case $\Delta_{A}=\Delta_{B}=\Delta$. The complete graphs demonstrate
its hypothetical sharpness up to a constant factor for the entire range of
possibilities for $k_{A}$, and thus symmetrically $k_{B}$ (Theorem 16$(iii)$).
Theorem 4 provides the following partial progress towards Conjecture 7 under
condition $(iii)$. In fact, this constitutes significant (asymmetric) progress
towards Conjecture 2, and is the first substantial advance in this
longstanding problem.

######  Corollary 10.

Given $\varepsilon>0$, any bipartite graph $G=(A\cup B,E)$ with parts $A$ and
$B$ having maximum degree at most $\Delta$ is
$((1+\varepsilon)\Delta/\log_{4}\Delta,2)$\- and
$((1+\varepsilon)\Delta/\log\Delta,\log\Delta)$-choosable for all $\Delta$
large enough.

###### Proof.

This follows for $\Delta$ large enough from condition $(ii)$ in Theorem 4 with
$\Delta_{A}=\Delta_{B}=\Delta$ and either
$k_{A}=(1+\varepsilon)\Delta/\log_{4}\Delta$ and $k_{B}=2$ or
$k_{A}=(1+\varepsilon)\Delta/\log\Delta$ and $k_{B}=\log\Delta$. ∎

In Section 7 we are able to nearly completely characterise
$(k_{A},k_{B})$-choosability for complete bipartite graphs if
$k_{A}\geq\Delta_{A}-1$. In Section 9, we give a connection between minimum
degree and $(k_{A},k_{B})$-choosability along the lines of [1].

### Probabilistic preliminaries

We will use the following standard probabilistic tools, cf. [3].

######  A Chernoff Bound.

For $X\sim\operatorname{Bin}(n,p)$ and $\varepsilon\in[0,1]$,
$\,\mathbb{P}(X<(1-\varepsilon)np)\leq\exp(-\frac{\varepsilon^{2}}{2}np)$.

######  The Lovász Local Lemma.

Consider a set $\cal E$ of (bad) events such that for each $A\in\cal E$

  1. $(i)$

$\,\mathbb{P}(A)\leq p<1$, and

  2. $(ii)$

$A$ is mutually independent of a set of all but at most $d$ of the other
events.

If $ep(d+1)\leq 1$, then with positive probability none of the events in $\cal
E$ occur.

##  2 A sufficient condition via transversals

In this section, we prove Theorem 4 under condition $(i)$. We prefer to state
and prove a slightly stronger form. To do so, we need some notational setup.
Let $H=(V,E)$ be a hypergraph. The degree of a vertex in $H$ is the number of
edges containing it. Given some partition of $V$, a transversal of $H$ is a
subset of $V$ that intersects each part in exactly one vertex. A transversal
of $H$ is called independent if it contains no edge, cf. [8].

######  Lemma 11.

Fix $k\geq 2$. Let $H$ be a $k$-uniform vertex-partitioned hypergraph, each
part being of size $\ell$, such that every part has degree sum at most
$\Delta$. If $\ell^{k}\geq e(k(\Delta-1)+1)$, then $H$ has an independent
transversal.

Let us first show Lemma 11 implies Theorem 4 under condition $(i)$.

###### Proof of Theorem 4 under condition $(i)$.

Let $k_{A},k_{B},\Delta_{A},\Delta_{B}$ satisfy condition $(i)$. Let $L$ be a
$(k_{A},k_{B})$-list-assignment of $G$. We would like to show that there is a
proper $L$-colouring of $G$. We do so by defining a suitable hypergraph
$H=(V_{H},E_{H})$.

Let $(w,c)$ be a vertex of $V_{H}$ if $w\in B$ and $c\in L(w)$.

Let $((w_{1},c_{1}),\dots,(w_{k_{A}},c_{k_{A}}))$ be an edge of $E_{H}$
whenever there is some $v\in A$ such that
$N(v)\supseteq\\{w_{1},\dots,w_{k_{A}}\\}$ and
$L(v)=\\{c_{1},\dots,c_{k_{A}}\\}$.

Note that $H$ is a $k_{A}$-uniform vertex-partitioned hypergraph, where the
parts are naturally induced by each list in $B$ and so are each of size
$k_{B}$. We have defined $H$ and its partition so that any independent
transversal corresponds to a special partial $L$-colouring of $G$. In
particular, it is an $L$-colouring of the vertices in $B$ for which there is
guaranteed to be a colour in $L(v)$ available for every $v\in A$, and so it
can be extended to a proper $L$-colouring of all $G$.

Every part in $H$ has degree sum at most
$\Delta_{B}\binom{\Delta_{A}-1}{k_{A}-1}k_{A}!\leq\Delta_{B}\Delta_{A}^{k_{A}},$
so the result follows from Lemma 11 with $\ell=k_{B}$ and
$\Delta=\Delta_{B}\Delta_{A}^{k_{A}}$. ∎

###### Proof of Lemma 11.

Write $H=(V,E)$ and suppose $\ell^{k}\geq e(k(\Delta-1)+1)$. Consider the
random transversal $\mathbf{T}$ formed by choosing one vertex from each part
independently and uniformly. For each edge $f\in E$, let $A_{f}$ denote the
event that $\mathbf{T}\supseteq f$. Note that $\,\mathbb{P}(A_{f})\leq
1/\ell^{k}$. Moreover $A_{f}$ is mutually independent of a set of all but at
most $k(\Delta-1)$ of the other events $A_{f^{\prime}}$. The transversal
$\mathbf{T}$ is independent if none of the events $A_{f}$ occur. Since by
assumption $e(1/\ell^{k})(k(\Delta-1)+1)\leq 1$, there is a positive
probability that $\mathbf{T}$ is independent by the Lovász Local Lemma. ∎

##  3 A sufficient condition via coupon collection

###### Proof of Theorem 4 under condition $(ii)$.

Let $k_{A},k_{B},\Delta_{A},\Delta_{B}$ satisfy condition $(ii)$. Let $L$ be a
$(k_{A},k_{B})$-list-assignment of $G$. We would like to show that there is a
proper $L$-colouring of $G$. To this end, colour each vertex $w\in B$,
randomly and independently, by a colour chosen uniformly from its list $L(w)$.
Let $T_{v,c}$ be the event that $v\in A$ has a neighbour coloured with colour
$c$. Let $T_{v}$ be the event that $T_{v,c}$ happens for all $c\in L(v)$. The
proof hinges on the following claim, which is related to the coupon collector
problem, cf. e.g. [6].

######  Claim.

The events $T_{v,c}$, for fixed $v$ as $c$ ranges over all colours in $L(v)$,
are negatively correlated. In particular, $\,\mathbb{P}(T_{v})\leq\prod_{c\in
L(v)}\,\mathbb{P}(T_{v,c})$.

###### Proof.

We have to prove, for every $I\subset L(v)$, that $\,\mathbb{P}(\forall c\in
I\colon T_{v,c})\leq\prod_{c\in I}\,\mathbb{P}(T_{v,c}).$ If some colour $c\in
L(v)$ is not in the list of any neighbour of $v$, both sides equal zero and so
the inequality holds. So assume this is not the case. We prove the statement
by induction on $\lvert I\rvert.$ When $\lvert I\rvert\leq 1$ the statement is
trivially true. Let $I\subset L(v)$ be a subset for which the statement is
true and let $c^{\prime}\in L(v)\setminus I.$ We now prove the statement for
$I^{\prime}=I\cup\\{c^{\prime}\\}.$ We have $\,\mathbb{P}(\forall c\in I\colon
T_{v,c})\leq\,\mathbb{P}(\forall c\in I\colon T_{v,c}\mid\lnot
T_{v,c^{\prime}})$ as the probability to use a colour in $I$ is larger if in
all neighbouring lists the colour $c^{\prime}$ is removed. This is equivalent
to

$\displaystyle\,\mathbb{P}(\forall c\in I\colon T_{v,c})$
$\displaystyle\geq\,\mathbb{P}(\forall c\in I\colon T_{v,c}\mid
T_{v,c^{\prime}})$ $\displaystyle\iff\,\mathbb{P}(\forall c\in
I^{\prime}\colon T_{v,c})$ $\displaystyle\leq\,\mathbb{P}(\forall c\in I\colon
T_{v,c})\,\mathbb{P}(T_{v,c^{\prime}})$

This last expression is at most $\prod_{c\in I^{\prime}}\,\mathbb{P}(T_{v,c})$
by the induction hypothesis, as desired. ∎

For the $i^{\text{th}}$ colour $c_{i}$ in $L(v)$, let the number of
occurrences of $c_{i}$ in the neighbouring lists of $v$ be $x_{i}$. Note that
$\,\mathbb{P}(T_{v,c_{i}})=1-(1-1/k_{B})^{x_{i}}.$ Using $x_{i}\leq\Delta_{A}$
for every $1\leq i\leq k_{A}$ and the claim, we have

$\,\mathbb{P}(T_{v})\leq\left(1-\left(1-\frac{1}{k_{B}}\right)^{\Delta_{A}}\right)^{k_{A}}.$

Noting that $\sum_{i=1}^{k_{A}}x_{i}\leq k_{B}\Delta_{A}$ and that the
function $\log(1-(1-1/k_{B})^{x})$ is concave and increasing, Jensen’s
Inequality applied with the claim implies that

$\,\mathbb{P}(T_{v})\leq\left(1-\left(1-\frac{1}{k_{B}}\right)^{k_{B}\Delta_{A}/k_{A}}\right)^{k_{A}}.$

Each event $T_{v}$ is mutually independent of all other events $T_{u}$ apart
from those corresponding to vertices $u\in A$ that have a common neighbour
with $v$ in $G$. As there are at most $\Delta_{A}(\Delta_{B}-1)$ such vertices
besides $v$, the Lovász Local Lemma guarantees with positive probability that
none of the events $T_{v}$ occur, i.e. there is a proper $L$-colouring, as
desired. ∎

##  4 The complete case and Steiner systems

In this section, we investigate general necessary conditions for
$(k_{A},k_{B})$-choosability via the complete bipartite graphs. Inspired in
part by Theorem 1 and related work of Bonamy and the third author [4], this
leads naturally to the study of an extremal set theoretic parameter. For
positive integers $k_{1},k_{2},\ell$, we say that a family ${\mathcal{F}}$ of
$k_{2}$-element subsets of $[\ell]$ has Property A$(k_{1},k_{2},\ell)$ (A is
for asymmetric) if there is a $k_{1}$-element subset of $[\ell]$ that
intersects every set in ${\mathcal{F}}$. We then define
$\overline{M}(k_{1},k_{2},\ell)$ to be the cardinality of a smallest family of
$k_{2}$-element subsets of $[\ell]$ that does not have Property
A$(k_{1},k_{2},\ell)$. Note that this definition of $\overline{M}$ coincides
with the definition given before the statement of Theorem 6.

###### Proof of Theorem 6.

We define a $(k_{A},k_{B})$-list-assignment $L$ as follows. Let
${\mathcal{F}}_{1}$ be a family of $\overline{M}(k_{1},k_{A},\ell)$
$k_{A}$-element subsets of $[\ell]$ without Property A$(k_{1},k_{A},\ell)$.
Let ${\mathcal{F}}_{2}$ be a family of $\overline{M}(k_{2},k_{B},\ell)$
$k_{B}$-element subsets of $[\ell]$ without Property A$(k_{2},k_{B},\ell)$.
Assign the sets of ${\mathcal{F}}_{1}$ as lists to the vertices in $A$ and the
sets of ${\mathcal{F}}_{2}$ as lists to the vertices in $B$. Suppose that $c$
is an $L$-colouring. Then $C_{1}=\\{c(a)\mid a\in A\\}$ intersects every set
in ${\mathcal{F}_{1}}$ and so $|C_{1}|\geq k_{1}+1$ by assumption and
similarly $C_{2}=\\{c(b)\mid b\in B\\}$ has cardinality $|C_{2}|\geq k_{2}+1$.
So $|C_{1}|+|C_{2}|\geq k_{1}+k_{2}+2>\ell$, implying that $c$ cannot be a
proper colouring.∎

Since $\overline{M}(\ell-k_{A},k_{A},\ell)=\binom{\ell}{k_{A}}$, we have the
following corollary of Theorem 6.

######  Corollary 12.

Let $k_{A},k_{B},\ell$ be integers such that $k_{A},k_{B}\geq 2$ and $\ell\geq
k_{A}+k_{B}-1$. The complete bipartite graph $G=(V{=}A\cup B,E)$ with
$|A|=\binom{\ell}{k_{A}}$ and $|B|=\overline{M}(k_{A}-1,k_{B},\ell)$ is not
$(k_{A},k_{B})$-choosable.

Although they are trivial, the following observations already show that
Theorem 6 and Corollary 12 cannot be improved much in general.

  * •

If $k_{A}=k_{B}=k$ and $\ell=2k-1$, then
$\overline{M}(k_{A}-1,k_{B},\ell)=\binom{2k-1}{k}=2^{2k+o(k)}$ and Corollary
12 implies that $K_{\binom{2k-1}{k},\binom{2k-1}{k}}$ is not $k$-choosable.
This implies $\operatorname{ch}(K_{n,n})\gtrsim\frac{1}{2}\log_{2}n$, which
one can compare to the bounds of Theorem 1.

  * •

If $\ell=k_{A}\cdot k_{B}$, then $\overline{M}(k_{A}-1,k_{B},\ell)=k_{A}$ and
so Corollary 12 implies that $K_{\binom{k_{A}\cdot k_{B}}{k_{A}},k_{A}}$ is
not $(k_{A},k_{B})$-choosable. This produces a necessary condition on $k_{B}$
for $(k_{A},k_{B})$-choosability only slightly weaker than Proposition 5.

We present several more instances where Theorem 6 and Corollary 12 are nearly
sharp in Section 6. For this, we will have use for the following estimates for
the parameter $\overline{M}$. A version of this result can be found in [9, Ch.
13], but for completeness, we present a standard derivation in the appendix.

######  Theorem 13.

Let $k_{1},k_{2},\ell$ be integers such that $k_{1},k_{2}\geq 2$ and $\ell\geq
k_{1}+k_{2}$. Then

$\displaystyle\frac{\ell!(\ell-k_{1}-k_{2})!}{(\ell-k_{2})!(\ell-
k_{1})!}\leq\overline{M}(k_{1},k_{2},\ell)<\frac{\ell!(\ell-
k_{1}-k_{2})!}{(\ell-k_{2})!(\ell-k_{1})!}\log\binom{\ell}{k_{1}}.$

##  5 Sufficient conditions in the complete case

In this section, we give general sufficient conditions for
$(k_{A},k_{B})$-choosability of complete bipartite graphs $K_{a,b}.$ Our
strategy for establishing $(k_{A},k_{B})$-choosability in this setting is to
take a random bipartition of the set of all colours and try to use one part
for colouring $A$ and the other part for colouring $B$. This yields the
following lemma.

######  Lemma 14.

Let the reals $0<\varepsilon,p<1$ and positive integers $a$, $b$, $k_{A}$,
$k_{B}$ satisfy either

$\displaystyle ap^{k_{A}}+b(1-p)^{k_{B}}<1$ or (1)
$\displaystyle\frac{ap^{k_{A}-1}}{(1-\varepsilon)k_{B}}+b\exp{(-\varepsilon^{2}k_{B}p/2)}<1$
. (2)

Then the complete bipartite graph $G=(V{=}A\cup B,E)$ with $|A|=a$ and $|B|=b$
is $(k_{A},k_{B})$-choosable.

###### Proof.

Let $L$ be $(k_{A},k_{B})$-list-assignment of $G$. Let $U=\cup_{v\in V}L(v)$,
i.e. $U$ is the union of all colour lists. Define a random partition of $U$
into parts $L_{A}$ and $L_{B}$ as follows. For each colour in $U$, randomly
and independently assign it to $L_{B}$ with probability $p$ and otherwise
assign it to $L_{A}$.

First assume (1). For a given vertex $v\in A$, the probability that $L(v)\cap
L_{A}=\emptyset$ is $p^{k_{A}}$. For a given vertex $v\in B$, the probability
that $L(v)\cap L_{B}=\emptyset$ is $(1-p)^{k_{B}}$. So the expected number of
vertices $v$ which cannot be coloured with the corresponding list $L_{A}$ or
$L_{B}$ is equal to $ap^{k_{A}}+b(1-p)^{k_{B}}.$ So the probabilistic method
then guarantees a fixed choice of the parts $L_{A}$ and $L_{B}$ such that
every vertex in $A$ can be coloured with a colour from $L_{A}$ and every
vertex in $B$ with a colour from $L_{B}.$

Otherwise assume (2). For a given vertex $w\in B$, the random variable
$|L(w)\cap L_{B}|$ has a binomial distribution of parameters $k_{B}$ and $p$.
So by a Chernoff bound the probability that $|L(w)\cap L_{B}|$ is smaller than
$(1-\varepsilon)k_{B}p$ is smaller than $\exp{(-\varepsilon^{2}k_{B}p/2)}$.
Thus, with probability greater than $1-b\exp{(-\varepsilon^{2}k_{B}p/2)}$, we
have $|L(w)\cap L_{B}|\geq(1-\varepsilon)k_{B}p$ for all $w\in B$.

For a given vertex $v\in A$, the probability that $L(v)\cap L_{A}=\emptyset$
is $p^{k_{A}}$. So the expected number of vertices $v$ for which this holds is
$p^{k_{A}}|A|$. Thus by Markov’s inequality, the probability that there are at
least $(1-\varepsilon)k_{B}p$ such vertices $v$ is smaller than
$\frac{p^{k_{A}-1}a}{(1-\varepsilon)k_{B}}$.

Due to (2), the probabilistic method guarantees a fixed choice of partition of
$U$ into parts $L_{A}$ and $L_{B}$ such that $|L(w)\cap
L_{B}|\geq(1-\varepsilon)k_{B}p$ for every $w\in B$ and the number of vertices
$v\in A$ such that $L(v)\cap L_{A}=\emptyset$ is smaller than
$(1-\varepsilon)k_{B}p$. Colour any vertex $v\in A$ having $L(v)\cap
L_{A}=\emptyset$ with an arbitrary colour from $L(v)$. Colour any other vertex
$v^{\prime}\in A$ with a colour from $L(v^{\prime})\cap L_{A}$. Finally colour
any vertex $w\in B$ with some colour in $L(w)\cap L_{B}$ unused by any vertex
of $A$ — this is possible as there were fewer than $(1-\varepsilon)k_{B}p$
colours of $L_{B}$ used to colour vertices in $A$ and the lists in $B$ all
have at least $(1-\varepsilon)k_{B}p$ colours from $L_{B}$.

In either case, we are guaranteed a proper $L$-colouring of $G$, as promised.
∎

##  6 Asymptotic sharpness in the complete case

We next use the results of Sections 4 and 5 to roughly settle the behaviour of
complete bipartite graphs with respect to Problem 3 in several regimes. The
conditions in Theorems 15 and 16 naturally correspond to the conditions in
Conjecture 7.

######  Theorem 15.

Let the positive integers $a$, $b$, $k_{A}$, $k_{B}$ satisfy one of the
following.

  1. $(i)$

For any $\varepsilon>0$, $a,b\geq\Delta_{0}$ for some
$\Delta_{0}=\Delta_{0}(\varepsilon)$, $k_{A}>b^{\varepsilon}$ and
$k_{B}>a^{\varepsilon}$.

  2. $(ii)$

For any $t>0$, $k_{A}\geq\frac{1}{t}\log_{2}(2a)$ and $k_{B}>2^{t}\log(2b)$.

  3. $(iii)$

We have that $a=b=\Delta$ and either
$k_{B}>8(\Delta/(2\log(2\Delta)))^{1/k_{A}}\log(2\Delta)$ or
$k_{A}>8(\Delta/(2\log(2\Delta)))^{1/k_{B}}\log(2\Delta)$.

Then the complete bipartite graph $G=(V{=}A\cup B,E)$ with $|A|=a$ and $|B|=b$
is $(k_{A},k_{B})$-choosable.

###### Proof.

Assume condition $(i)$ and assume without loss of generality that $a\geq b$.
Fix $\varepsilon>0$ and take $\Delta_{0}>2$ large enough such that
$\varepsilon\Delta_{0}^{\varepsilon}>3$ and $x^{\varepsilon/3}>\log(2x)$ for
every $x\geq\Delta_{0}.$ Now $k_{B}\geq
a^{\varepsilon}>a^{2/b^{\varepsilon}}a^{\varepsilon/3}>(2a)^{1/b^{\varepsilon}}\log(2b)$.
By taking $p=(2a)^{-1/b^{\varepsilon}}$, we have that (1) is satisfied and the
result follows from Lemma 14.

Assume condition $(ii)$. Take $p=1/2^{t}$. Then $ap^{k_{A}}\leq 1/2$ and
$b(1-p)^{k_{B}}\leq b\exp(-pk_{B})<1/2$, so that (1) is satisfied and the
result follows from Lemma 14.

Assume condition $(iii)$ and by symmetry assume
$k_{B}>8(\Delta/(2\log(2\Delta)))^{1/k_{A}}\log(2\Delta)$. Take
$p=8\log(2\Delta)/k_{B}$ and $\varepsilon=1/2$. Then
$p<(2\log(2\Delta)/\Delta)^{1/k_{A}}$ and
$b\exp{(-\varepsilon^{2}k_{B}p/2)}<1/2$. Also

$\displaystyle\frac{ap^{k_{A}}}{(1-\varepsilon)pk_{B}}=\frac{\Delta
p^{k_{A}}}{4\log(2\Delta)}<\frac{1}{2}.$

Thus (2) is satisfied and the result follows from Lemma 14. ∎

The conditions are also sharp in some sense.

######  Theorem 16.

For each of the following four conditions, there are infinitely many choices
of the positive integers $a$, $b$, $k_{A}$, $k_{B}$ satisfying it such that
the complete bipartite graph $G=(V{=}A\cup B,E)$ with $|A|=a$ and $|B|=b$ is
not $(k_{A},k_{B})$-choosable.

  1. $(i)$

Given a monotone real function $g$ satisfying $g(1)\geq 1$ and
$g(x)=\omega(1)$ as $x\to\infty$,

$\displaystyle k_{A}>b^{1/g(b)}\text{ and }k_{B}=a.$

  2. $(ii)$

For any integer $t\geq 4$, either

$\displaystyle k_{A}\leq\frac{\log_{2}a}{t}\text{ and
}k_{B}\leq\frac{2^{t-1}}{e}(\log{b}-\log{\log{a}})\leq\frac{\log_{2}a}{t},$

or

$\displaystyle k_{A}\leq 2^{t}\log_{2}a\text{ and
}k_{B}\leq\frac{\log_{2}{b}-\log_{2}{\log{a}}}{t+\log_{2}t+3},$

where $4\leq b\leq a$.

  3. $(iii)$

For any fixed integer $k>1$ and $\Delta$ sufficiently large,
$\Delta_{A}=\Delta_{B}=\Delta$, $k_{A}=k$ and
$k_{B}=c(\Delta/\log\Delta)^{1/k}\log\Delta$ for some constant $c=c(k)$.

###### Proof.

Consider condition $(i)$. Take $\delta$ large enough so that
$g(\delta^{a})>a$. Let $k_{A}=\delta$ and $b=\delta^{a}$ and note that
$b^{1/g(b)}=\delta^{a/g(b)}<\delta=k_{A}$, i.e. $k_{A}^{g(b)}>b$. The result
then follows from Proposition 5.

Consider condition $(ii)$. For the former case, let

$\displaystyle\ell=\frac{2^{t}}{et}\log_{2}a\quad\text{and}\quad
k_{A}=\frac{\log_{2}a}{t}\geq k_{B}=\frac{2^{t-1}}{e}(\log{b}-\log{\log{a}}).$

Then $\binom{\ell}{k_{A}}\leq(e\ell/k_{A})^{k_{A}}=a.$ Also

$\displaystyle\binom{\ell}{k_{B}}\left/\binom{\ell-k_{A}+1}{k_{B}}\right.$
$\displaystyle\leq\left(\frac{\ell-k_{B}}{\ell-
k_{A}-k_{B}}\right)^{k_{B}}\leq\left(\frac{2^{t}-e}{2^{t}-2e}\right)^{k_{B}}\leq\exp\left(\frac{2e}{2^{t}}k_{B}\right)=\frac{b}{\log
a}.$

Here we used the estimation $(x-e)/(x-2e)\leq\exp(2e/x)$ for $x\geq 16.$

For the latter case, choose

$\ell=\left(2^{t}+\frac{1}{t+\log_{2}t+3}\right)\log_{2}a,\quad
k_{A}=2^{t}\log_{2}a\quad\text{and}\quad
k_{B}=\frac{\log_{2}{b}-\log_{2}{\log{a}}}{t+\log_{2}t+3}.$

Then $\binom{\ell}{k_{A}}=\binom{\ell}{\ell-k_{A}}\leq(e\ell/(\ell-
k_{A}))^{\ell-k_{A}}\leq a$ since

$\displaystyle e\ell/(\ell-k_{A})$ $\displaystyle\leq
e(2^{t}(t+\log_{2}t+3)+1)\leq 8t2^{t}=2^{t+\log_{2}t+3}.$

Also

$\displaystyle\binom{\ell}{k_{B}}\left/\binom{\ell-k_{A}+1}{k_{B}}\right.$
$\displaystyle\leq\left(\frac{e\ell}{\ell-
k_{A}}\right)^{k_{B}}\leq\frac{b}{\log a}.$

In either case, the result follows from Corollary 12 and Theorem 13.

Consider condition $(iii)$. First we make a computation verifying
$\overline{M}((\log m)/2,m/2,m)<m$ when $m$ is sufficiently large. By Theorem
13, for $m$ sufficiently large, we have that

$\displaystyle\overline{M}((\log m)/2,m/2,m)$
$\displaystyle\leq\left(\frac{m}{m/2-(\log m)/2}\right)^{(\log
m)/2}\log\binom{m}{(\log m)/2}<\sqrt{m}(\log m)^{2}<m.$

We choose $m=c(\Delta/\log\Delta)^{1/k}\log\Delta$, where $c=1/(4k(k-1))$. By
the above computation, this choice satisfies $\overline{M}((\log
m)/2,m/2,m)\leq\Delta$ for $\Delta$ large enough. Let $b$ be such that
$(k-1)b\log\Delta=(\log m)/2$, and note that $b\sim 2c$ as $\Delta\to\infty$.

Let $G=(A\cup B,E)$ be a complete bipartite graph with

$\lvert A\rvert=\overline{M}((\log m)/2,m/2,m)\quad\text{and}\quad\lvert
B\rvert=b\log\Delta\binom{\lceil m/(b\log\Delta)\rceil}{k}.$

Note that as $\Delta\to\infty$

$\lvert B\rvert\leq b\log\Delta\frac{\lceil
m/(b\log\Delta)\rceil^{k}}{k!}\sim\frac{1}{k!}\left(\frac{c}{b}\right)^{k}b\Delta\leq\Delta$

and thus $\Delta_{A},\Delta_{B}\leq\Delta$ for all $\Delta$ large enough.

We define a $(k_{A},k_{B})$-list-assignment $L$ as follows. Let $\mathcal{F}$
be a family of $\lvert A\rvert$ $(m/2)$-element subsets of $[m]$ without
Property A$((\log m)/2,m/2,m)$ and assign the sets of $\mathcal{F}$ as lists
to the vertices in $A$. So there is no $((\log m)/2)$-element subset of $[m]$
that intersects every list in $A$. For $B$, arbitrarily partition $[m]$ into
$b\log\Delta$ segments of nearly equal size, and assign as lists to the
vertices in $B$ all possible $k$-element subsets chosen from within a single
segment.

Note that for any $L$-colouring, $\cup_{w\in B}L(w)$ intersects at least one
colour from each $k$-element subset of a segment, and so $\cup_{w\in B}L(w)$
avoids at most $(k-1)b\log\Delta=(\log m)/2$ colours of $[m]$. However, as
noted above, $\cup_{v\in A}L(v)$ must have more than $(\log m)/2$ colours of
$[m]$, and this precludes a proper $L$-colouring. ∎

##  7 Sharpness in a boundary complete case

In this section, we precisely solve Problem 3 for complete bipartite graphs
when $k_{A}\geq\Delta_{A}-1.$ When $k_{A}\geq\Delta_{A}+1$, we know that any
bipartite $G=(A\cup B,E)$ must be $(k_{A},k_{B})$-choosable. The case
$k_{A}=\Delta_{A}$ is handled by Proposition 5 and the fact that its
conclusion fails if $|A|<\delta^{k}$ or $|B|<k$. The remainder of this section
is devoted to the case $k_{A}=\Delta_{A}-1$.

######  Proposition 17.

Let $b\geq 5$ and $\delta=q(b-1)+r$ with $0\leq r\leq b-2$ and $q$ being
integers such that $\delta\gg b.$ Then the complete bipartite graph
$G=(V{=}A\cup B,E)$ with $|A|=a$ and $|B|=b$ is $(b-1,\delta)$-choosable if
and only if

$a<\delta^{b-1}-((b-2)q+r)^{b-1-r}((b-2)q+r-1)^{r}.$

Note that for $1\ll b\ll\delta$, this bound on $a$ is approximately
$(1-1/e)\delta^{b-1}.$

###### Proof.

We write $B=\\{v_{1},v_{2},\ldots,v_{b}\\}.$ Let $L$ be a $(b-1,\delta)$-list-
assignment of $G$. If some colour appears in the list of at least three
different vertices of $B$, or two colours appear in common to the lists of two
disjoint pairs of vertices of $B$, then we can certainly $L$-colour $G$. Let
$L_{12}=L(v_{1})\cap L(v_{2})$ and analogously define $L_{ij}$ for each $1\leq
i<j\leq b$ and let $\ell_{ij}=\lvert L_{ij}\rvert$. We know the index set of
the non-empty $L_{ij}$ form an intersecting family, so there are two cases
depending on this family being trivial or non-trivial. We consider these cases
in turn.

  1. $(i)$

(non-trivial family) Without loss of generality, we may assume that only
$L_{12},L_{13}$ and $L_{23}$ are non-empty among all $L_{ij}$. If there are
$b-1$ colours which do not appear in the list of a vertex of $A$, such that
the vertices of $B$ can coloured with these $b-1$ colours, then $G$ is
$L$-colourable. So if $G$ is not $L$-colourable, every such collection of
$b-1$ colours has to appear as a list of a vertex in $A$. As there are
$(\delta-\ell_{12}-\ell_{13})(\delta-\ell_{12}-\ell_{23})(\delta-\ell_{13}-\ell_{23})\delta^{b-3}$
combinations of $b$ colours appearing only once among the lists of the
vertices in $B$, every $(b-1)$-list can forbid at most $\delta$ of these. This
implies that $G$ is $L$-colourable if

$\displaystyle a$
$\displaystyle<(\ell_{12}+\ell_{13}+\ell_{23})\delta^{b-2}-(\ell_{12}\ell_{13}+\ell_{12}\ell_{23}+\ell_{13}\ell_{23})\delta^{b-3}$
$\displaystyle\quad+(\delta-\ell_{12}-\ell_{13})(\delta-\ell_{12}-\ell_{23})(\delta-\ell_{13}-\ell_{23})\delta^{b-4}$
$\displaystyle=\delta^{b-1}-(\ell_{12}+\ell_{13}+\ell_{23})\delta^{b-2}+(\ell_{12}+\ell_{13}+\ell_{23})^{2}\delta^{b-3}$
$\displaystyle\quad-(\ell_{12}+\ell_{13})(\ell_{12}+\ell_{23})(\ell_{13}+\ell_{23})\delta^{b-4}.$

The minimum occurs for $\ell_{12}=\ell_{23}=\ell_{13}=\delta/4,$ leading to a
bound of $\frac{11}{16}\delta^{b-1}.$

  2. $(ii)$

(trivial family) Without loss of generality, we assume only some of the
$L_{1j}$ are non-empty and $\ell_{1b}=\min\\{\ell_{1j}\mid 2\leq j\leq b\\}.$
The number of choices of a set $S$ of $b-1$ colours such that any vertex has
at least one colour of $S$ in its list equals

$\delta^{b-1}-\prod_{j=2}^{b}(\delta-\ell_{1j}).$

We also need to forbid colouring the vertices of $B$ with all colours that
appear only once in a list in $B$. For this we need to forbid at least an
additional

$\left(\delta-\sum_{j=2}^{b}\ell_{1j}\right)\prod_{j=2}^{b-1}(\delta-\ell_{1j})$

sets $S$ with $b-1$ elements. The total number of sets to forbid equals

$\delta^{b-1}-\left(\sum_{j=2}^{b-1}\ell_{1j}\right)\prod_{j=2}^{b-1}(\delta-\ell_{1j}).$

This expression is minimised when $\delta-\sum_{j=2}^{b-1}\ell_{1j}$ and every
$\ell_{1j}$ for $2\leq j\leq b-1$ are equal to a number of the form
$\lfloor\frac{\delta}{b-1}\rceil.$ When $b\ll\delta$ and $b\geq 5$, we have
that this is approximately $(1-(1-1/(b-1))^{b-1})\delta^{b-1}$, which is
smaller than the value $\frac{11}{16}\delta^{b-1}$ obtained in the previous
case. Equality can be attained, i.e. $G$ is not $(b-1,\delta)$-choosable when
$a=\delta^{b-1}-((b-2)q+r)^{b-1-r}((b-2)q+r-1)^{r}$ (or larger) as we can take
the lists being exactly those mentioned before for minimising the expression.
∎

The same analysis also gives the result for $b\in\\{3,4\\}.$ When $b=3$, the
bound for $a$ is $\lfloor\frac{3}{4}\delta^{2}\rceil.$ When $b=4$, the same
analysis as in Proposition 17 gives that the bound for $a$ occurs in the first
case (non-trivial family), resulting in the following detailed proposition.

######  Proposition 18.

Let $\delta\geq 2$. The complete bipartite graph $G=(V{=}A\cup B,E)$ with
$|A|=a$ and $|B|=4$ is $(3,\delta)$-choosable if and only if

$a<\begin{cases}\frac{11}{16}\delta^{3}&\text{ if }\delta\equiv 0\pmod{4},\\\
\frac{11}{16}\delta^{3}+\frac{3}{16}\delta+\frac{1}{8}&\text{ if }\delta\equiv
1\pmod{4},\\\ \frac{11}{16}\delta^{3}+\frac{1}{4}\delta&\text{ if
}\delta\equiv 2\pmod{4},\\\
\frac{11}{16}\delta^{3}+\frac{3}{16}\delta-\frac{1}{8}&\text{ if }\delta\equiv
3\pmod{4}.\\\ \end{cases}$

##  8 Sharper than complete bipartite

In this section, we prove that complete graphs are not exactly extremal for
Problem 3. The complete bipartite graph $K_{\delta^{k}-1,k}$ is
$(k,\delta)$-choosable, but there are bipartite graphs with $\Delta_{A}=k$ and
$\Delta_{B}$ smaller than $\delta^{k}-1$ which are not $(k,\delta)$-choosable.

######  Proposition 19.

For any $\delta,k\geq 2$, there is a bipartite graph $G=(V=A\cup B,E)$ with
parts $A$ and $B$ having maximum degrees $k$ and $f(\delta,k)<\delta^{k}$,
respectively, that is not $(k,\delta)$-choosable. Moreover,
$f(\delta,k)\leq\sum_{i=1}^{\delta}i^{k-1}$.

###### Proof.

We recursively construct bipartite graphs $G_{i}=(A_{i}\cup B_{i},E_{i})$ with
parts $A_{i}$ and $B_{i}$ having maximum degree $k$ and
$\sum_{j=1}^{i}(\delta-j+1)^{k-1}$. We simultaneously define a
$(k,\delta)$-list-assignment $L_{i}$ of $G_{i}$ such that there is some vertex
$b_{i}\in B_{i}$ which can only be given one of $\delta-i$ colours out of its
list in any proper $L_{i}$-colouring.

Let $G_{1}$ be the complete bipartite graph $K_{\delta^{k-1},k}$, and write
$B_{1}=\\{v_{1},\ldots,v_{k}\\}$. For the vertices of $B_{1}$, we assign $k$
disjoint lists of length $\delta$, specifically,
$L(v_{j})=\\{(j-1)\delta+1,\dots,j\delta\\}$ for $j\in[k]$. For the vertices
of $A_{1}$, we assign as lists all possible $k$-tuples drawn from $\\{1\\}$
and $L(v_{j})$ for $2\leq j\leq k$. Since $b_{1}:=v_{1}$ cannot be given the
colour $1$ in any proper $L_{1}$-colouring, the conditions are satisfied for
$i=1$.

For the recursion, assume $i\geq 1$ and take the disjoint union of $k$ copies
of $G_{i}$, relabelling their $(k,\delta)$-list-assignments so that their
colour palettes are mutually disjoint. So the parts $A_{i+1},B_{i+1}$ of the
bipartition so far include the disjoint unions of the $k$ respective parts.
Let $v_{1},\dots,v_{k}$ be the $k$ copies of $b_{i}$, and for each $j\in[k]$
write $L^{\prime}(v_{j})$ for the set of $\delta-i$ colours to which the
colour of $v_{j}$ is restricted by assumption. By relabelling, we may assume
$1\in L^{\prime}(v_{1})$. We now add $(\delta-i)^{k-1}$ new vertices to
$A_{i+1}$ that are adjacent to every $v_{j}$. For these new vertices, we
assign as lists all possible $k$-tuples drawn from $\\{1\\}$ and
$L^{\prime}(v_{j})$ for $2\leq j\leq k$. This completes the definition of
$G_{i+1}$ and $L_{i+1}$. By induction, $b_{i+1}:=v_{1}$ may only be given a
colour from $L^{\prime}(v_{1})\setminus\\{1\\}$ in any proper
$L_{i+1}$-colouring, and moreover $b_{i+1}$ is of maximum degree in $B_{i+1}$.
So $(G_{i+1},L_{i+1},b_{i+1})$ satisfies the required conditions. This
completes the recursive step.

The graph $G:=G_{\delta}$ with parts $A=A_{\delta}$ and $B=B_{\delta}$ is not
$(k,\delta)$-choosable, since by construction we may not give any colour to
$b_{\delta}$ in any proper $L_{\delta}$-colouring. Furthermore, the maximum
degrees in $A$ and $B$ are respectively $k$ and
$\sum_{i=1}^{\delta}(\delta-i+1)^{k-1}=\sum_{i=1}^{\delta}i^{k-1}$, as
required. ∎

##  9 Degrees and $(k_{A},k_{B})$-choosability

In this section, we give a condition on the minimum degree to conclude that a
bipartite graph is not $(k_{A},k_{B})$-choosable, depending on the behaviour
for complete bipartite graphs.

######  Theorem 20.

Suppose the complete bipartite graph $G_{0}=(V{=}A_{0}\cup B_{0},E)$ with
$|A_{0}|=a$ and $|B_{0}|=b$ is not $(k_{A},k_{B})$-choosable. Then any
bipartite graph $G=(V{=}A\cup B,E)$ with parts $A$ and $B$ such that
$|A|\leq|B|$ and $B$ has minimum degree $\delta_{B}>4ab\log{4a}\log{k_{A}}$ is
not $(k_{A},k_{B})$-choosable.

###### Proof.

Let $\operatorname{\mathcal{F}}_{a}$ and $\operatorname{\mathcal{F}}_{b}$ be
the collections of lists that can be assigned to $A_{0}$ and $B_{0}$,
respectively, that certify non-$(k_{A},k_{B})$-choosability of $G_{0}$. Let
$p=1/(4b\log{k_{A}}).$ Randomly choose $X\subset A$, each vertex included
independently with probability $p$. Then $\,\mathbb{E}(|X|)=p|A|$ and so by
Markov’s inequality,

$\,\mathbb{P}(|X|>2p|A|)<\frac{1}{2}.$

Define a list-assignment $L_{X}$ of $X$, by assigning to every vertex of $X$
uniformly and independently a list of $\operatorname{\mathcal{F}}_{a}$. Call a
vertex $v$ in $B$ good if every member of $\operatorname{\mathcal{F}}_{a}$
appears as a list on a neighbour (in $X$) of $v.$ Note that

$\frac{\,\mathbb{P}(\text{some }F\in\operatorname{\mathcal{F}}_{a}\text{ does
not appear for
$v$})}{a}\leq\left(1-\frac{p}{a}\right)^{\delta_{B}}\leq\exp\left(-\frac{p}{a}\delta_{B}\right)<\frac{1}{4a}$

implying that

$\,\mathbb{P}(v\text{ is not good})<\frac{1}{4}.$

So by Markov’s inequality,

$\,\mathbb{P}\left(|\\{v\mid v\text{ is not
good}\\}|>|B|/2\right)\leq\frac{\,\mathbb{E}(|\\{v\mid v\text{ is not
good}\\}|)}{|B|/2}<\frac{1}{2}.$

By the probabilistic method, there is some $X\subset A$ and a list-assignment
$L_{X}$ of $X$ such that $|X|\leq 2p|A|$ and there are at least $|B|/2$ good
vertices. Fix this choice and let $B^{*}$ be the set of good vertices.

Fix an arbitrary $L_{X}$-colouring $c_{X}$ of $X$. There are at most
$k_{A}^{|X|}$ possibilities for the colouring $c_{X}$. Define a list-
assignment $L_{B^{*}}$ of $B^{*}$, by assigning to every vertex of $B^{*}$
uniformly and independently a list of $\operatorname{\mathcal{F}}_{b}$. Since
every $v\in B^{*}$ is good, all lists of $\operatorname{\mathcal{F}}_{a}$
appear in the neighbourhood of $v$ and at least one choice of a list in
$\operatorname{\mathcal{F}}_{b}$ would imply that $v$ cannot be properly
coloured with a colour of that list. Hence the probability that every $v\in
B^{*}$ can be properly $L_{B^{*}}$-coloured in agreement with $c_{X}$ is at
most

$\left(1-\frac{1}{b}\right)^{|B^{*}|}<\exp\left(-\frac{|B|}{2b}\right).$

The probability that some proper colouring of $G$ can completed given any
$L_{X}$-colouring $c_{X}$ is smaller than

$k_{A}^{|X|}\exp\left(-\frac{|B|}{2b}\right)\leq\exp\left(2p|A|\log{k_{A}}-\frac{|B|}{2b}\right)\leq
1.$

Thus by the probabilistic method there exists a list-assignment $L_{B^{*}}$ of
$B^{*}$ such that no proper $L_{B^{*}}$-colouring can be found in agreement
with any $L_{X}$-colouring. ∎

##  10 Conclusion

We have begun the investigation of an asymmetric form of list colouring for
bipartite graphs. In one direction, we have found good general sufficient
conditions through connections to independent transversals and to the coupon
collector problem. This has incidentally yielded a non-trivial advance towards
a difficult conjecture of Krivelevich and the first author. In another
direction, we have established broad necessary conditions through an
unexpected link between the bipartite choosability of complete graphs and a
classic extremal set theoretic or design theoretic parameter. This link has
fed naturally into the formulation of three attractive conjectures along these
lines. Because of the rich connections this problem has to other important
areas of combinatorial mathematics, we are hopeful that further study will
lead to novel insights. We remark that Conjecture 7 comprises three asymptotic
parameterisations of Problem 3 that we found most natural and interesting, all
derived essentially from Theorem 6. There could be several other nice choices.
Because the terrain is new, there are many interesting angles we have not yet
had the opportunity to fully explore.

One possibility, based on the connection to combinatorial design theory, comes
to mind. We have that $\overline{M}(2,q^{2},q^{2}+q+1)=q^{2}+q+1$ for every
prime power $q$ due to the finite projective planes. With a small modification
of the substitution of this fact into Corollary 12, we obtain that the
complete bipartite graph $K_{\frac{1}{6}q^{3}(q+1)(q^{2}+q+1),q^{2}+q+1}$ is
not $(3,q^{2})$-choosable. On the other hand, Lemma 14 shows this is not that
far from optimal, and in particular (2) shows that $K_{q^{6}/(80\log
q)^{2},q^{2}+q+1}$ is $(3,q^{2})$-choosable. It would be interesting to narrow
the gap. For the specific case $q=2$, a quick computer search checks that
$K_{20,7}$ is not $(3,4)$-choosable, but finding the largest $r$ such that
$K_{r,7}$ is $(3,4)$-choosable seems difficult.

## References

  * [1] N. Alon.  Degrees and choice numbers.  Random Structures Algorithms, 16(4):364–368, 2000.
  * [2] N. Alon and M. Krivelevich.  The choice number of random bipartite graphs.  Ann. Comb., 2(4):291–297, 1998.
  * [3] N. Alon and J. H. Spencer.  The probabilistic method.  Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.
  * [4] M. Bonamy and R. J. Kang.  List coloring with a bounded palette.  J. Graph Theory, 84(1):93–103, 2017.
  * [5] E. Davies, R. de Joannis de Verclos, R. J. Kang, and F. Pirot.  Colouring triangle-free graphs with local list sizes.  ArXiv e-prints, Dec. 2018.  To appear in Random Structures & Algorithms.
  * [6] B. Doerr.  Probabilistic tools for the analysis of randomized optimization heuristics.  In B. Doerr and F. Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 1–87. Springer International Publishing, Cham, 2020.
  * [7] Z. Dvořák, L. Esperet, R. J. Kang, and K. Ozeki.  Least conflict choosability.  ArXiv e-prints, Mar. 2018.
  * [8] P. Erdős, A. Gyárfás, and T. Łuczak.  Independent transversals in sparse partite hypergraphs.  Combin. Probab. Comput., 3(3):293–296, 1994.
  * [9] P. Erdős and J. Spencer.  Probabilistic methods in combinatorics.  Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974.  Probability and Mathematical Statistics, Vol. 17.
  * [10] P. Erdős, A. L. Rubin, and H. Taylor.  Choosability in graphs.  In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pages 125–157, Winnipeg, Man., 1980. Utilitas Math.
  * [11] P. E. Haxell.  A note on vertex list colouring.  Combin. Probab. Comput., 10(4):345–347, 2001.
  * [12] A. Johansson.  Asymptotic choice number for triangle-free graphs.  Technical Report 91-5, DIMACS, 1996.
  * [13] P. Keevash.  Hypergraph Turán problems.  In Surveys in combinatorics 2011, volume 392 of London Math. Soc. Lecture Note Ser., pages 83–139. Cambridge Univ. Press, Cambridge, 2011.
  * [14] M. Molloy.  The list chromatic number of graphs with small clique number.  J. Combin. Theory Ser. B, 134:264–284, 2019.
  * [15] D. Saxton and A. Thomason.  Hypergraph containers.  Invent. Math., 201(3):925–992, 2015.
  * [16] V. G. Vizing.  Coloring the vertices of a graph in prescribed colors.  Diskret. Analiz, 29 Metody Diskret. Anal. v Teorii Kodov i Shem:3–10, 101, 1976.

##  Appendix A Extremal analysis of approximate Steiner systems

###### Proof of Theorem 13.

First we prove the lower bound. Fix a family $\mathcal{F}$ of $k_{2}$-element
subsets of $[\ell]$ with cardinality less than the leftmost expression. Choose
$C$ a $k_{1}$-element subset of $[\ell]$ uniformly at random. For any fixed
$F\in\mathcal{F}$, we have

$\displaystyle\,\mathbb{P}(F\cap C=\emptyset)$ $\displaystyle=\binom{\ell-
k_{2}}{k_{1}}\left/\binom{\ell}{k_{1}}\right.=\frac{(\ell-k_{2})!(\ell-
k_{1})!}{\ell!(\ell-k_{1}-k_{2})!}.$

By a union bound and the choice of cardinality of $\mathcal{F}$,

$\displaystyle\,\mathbb{P}(F\cap C=\emptyset\text{ for some
}F\in{\mathcal{F}})\leq\sum_{F\in\mathcal{F}}\,\mathbb{P}(F\cap
C=\emptyset)<1.$

So with positive probability there is a set $C$ certifying that $\mathcal{F}$
has Property A$(k_{1},k_{2},\ell)$.

Next we prove the upper bound. Fix $C$ a $k_{1}$-element subset of $[\ell]$.
Let $F$ be a $k_{2}$-element subset of $[\ell]$ chosen uniformly at random.
Then

$\displaystyle\,\mathbb{P}(F\cap C=\emptyset)$ $\displaystyle=\binom{\ell-
k_{1}}{k_{2}}\left/\binom{\ell}{k_{2}}\right.=\frac{(\ell-k_{2})!(\ell-
k_{1})!}{\ell!(\ell-k_{1}-k_{2})!}.$

Let $\mathcal{F}=\\{F_{1},\dots,F_{m}\\}$ be a family of $m$ $k_{2}$-element
subsets of $[\ell]$ chosen uniformly at random. Based on the above
calculation,

$\displaystyle\,\mathbb{P}(F_{i}\cap C\neq\emptyset\text{ for all
}i\in\\{1,\dots,m\\})\leq\left(1-\frac{(\ell-k_{2})!(\ell-k_{1})!}{\ell!(\ell-
k_{1}-k_{2})!}\right)^{m}.$

There are $\binom{\ell}{k_{1}}$ choices for $C$, so we have

$\displaystyle\,\mathbb{P}(\mathcal{F}$ $\displaystyle\text{ contains a $C$
certifying Property~{}A$(k_{1},k_{2},\ell)$})$
$\displaystyle\leq\binom{\ell}{k_{1}}\exp\left(-m\frac{(\ell-k_{2})!(\ell-
k_{1})!}{\ell!(\ell-k_{1}-k_{2})!}\right).$

This last expression is less than $1$ if

$\displaystyle m>\frac{\ell!(\ell-k_{1}-k_{2})!}{(\ell-k_{2})!(\ell-
k_{1})!}\log\binom{\ell}{k_{1}},$

which establishes the upper bound. ∎


††footnotetext:  File: main.tex, printed: 2024-8-28, 6.21

# A note on the equivalence of Gromov boundary and metric boundary

Vasudevarao Allu  Vasudevarao Allu, Discipline of Mathematics, School of Basic
Sciences, Indian Institute of Technology Bhubaneswar, Argul, Bhubaneswar,
PIN-752050, Odisha (State), India<EMAIL_ADDRESS>and  Abhishek Pandey
Abhishek Pandey, Discipline of Mathematics, School of Basic Sciences, Indian
Institute of Technology Bhubaneswar, Argul, Bhubaneswar, PIN-752050, Odisha
(State), India<EMAIL_ADDRESS>
###### Abstract.

In this paper, we introduce the concept of quasihyperbolically visible spaces.
As a tool, we study the connection between the Gromov boundary and the metric
boundary.

###### Key words and phrases:

Gromov hyperbolic spaces, Gromov boundary, metric boundary,
quasihyperbolically visible spaces, quasihyperbolic metric, quasihyperbolic
geodesics, visibility

###### 2020 Mathematics Subject Classification:

Primary 30L10, 30L99, 30C65, 51F30, 53C23

##  1\. Introduction and results

For a metric space $(\Omega,d)$, its metric completion and metric boundary is
denoted by $\overline{\Omega}^{d}$ and
$\partial_{d}\Omega=\overline{\Omega}^{d}\setminus\Omega$, respectively. Let
$(\Omega,d)$ be a rectifiably connected, locally compact, noncomplete metric
space, and hence $\partial_{d}\Omega\neq\emptyset$. We say $(\Omega,d)$ is
minimally nice if the identity map from
$(\Omega,d)\to(\Omega,\lambda_{\Omega})$ is continuous, where
$\lambda_{\Omega}$ is the length metric on $\Omega$ with respect to $d$. Note
that every proper domain of $\mathbb{R}^{n}$ is minimally nice. Consider the
metric space $(\Omega,k)$, where $k$ is the quasihyperbolic metric $k$. Bonk,
Heinonen, and Koskela [8] have proved the following:

Theorem A. [8, Theorem 1.11] Let $\Omega\subset\mathbb{R}^{n}$ be a bounded
domain, then following are equivalent

  * (i)

$\Omega$ is uniform

  * (ii)

$(\Omega,k_{\Omega})$ is Gromov hyperbolic and the identity map
$id:(\Omega,k_{\Omega})\to(\Omega,d)$ extends as a homeomorphism
$\Phi:\overline{\Omega}^{G}\to\overline{\Omega}^{Euc}$ such that $\Phi$ is
quasisymmetrric homeomorphism from $\partial_{G}\Omega$ onto
$\partial_{Euc}\Omega$.

In view of Theorem A, it is natural to consider the following general
extension problem.

######  Problem 1.1.

Let $(\Omega,d)$ be a minimally nice space. Suppose $(\Omega,k)$ is Gromov
hyperbolic. When is the following true?
The identity map $id_{\Omega}:(\Omega,k)\to(\Omega,d)$ extends to a continuous
surjective map or a homeomorphism
$\widehat{id_{\Omega}}:\partial_{G}\Omega\to\partial_{d}\Omega$.

Note that, if we follow Väisälä [22, 2.21], Problem 1.1 inquires about the
conditions under which the natural map exists. Lammi [21, Theorem 1.1] showed
that for a locally compact, non-complete, quasi-convex space under the
assumption of Gehring-Hayman theorem and Gromov hyperbolicity, a suitable
growth condition of quasihyperbolic metric is sufficient for the homeomorphic
extension of the identity map from the Gromov boundary onto the metric
boundary. The growth condition in [21] implies that the space is bounded.
Recently, Zhou [24, Theorem 1.8] et al. studied this problem for unbounded
Gromov hyperbolic spaces. For more details on Problem 1.1 we refer to [17, 21,
23, 24] and references therein.

The primary objective of this paper is to study Problem 1.1. Our strategy for
studying Problem 1.1 arises from a recent work by the authors [1], where the
authors studied the visibility property with respect to the quasihyperbolic
metric. The concept of visibility has been introduced by Eberlein and O’Neill
in [12], where they basically introduced a general construction of
compactification of Hadamrd manifolds by attaching an abstract boundary or
boundary at infinity, which is called the ideal boundary. Using the notion of
an ideal boundary, Eberlein and O’Neill defined the term visibility manifold
(i.e. connecting ideal boundary points by geodesic line) for a complete
Riemannian manifold with nonpositive sectional curvature. Visibility is, in
fact, a consequence of the strict negative sectional curvature of a complete
Riemannian manifold. Bharali and Zimmer [7] have introduced a new class of
domains called Goldilocks domains, which satisfy a suitable form of visibility
with respect to Kobayashi distance. For bounded domains in $\mathbb{C}^{n}$
that satisfy this form of visibility with respect to Kobayashi distance,
Bharali and Maitra [6] coined a term called visibility domains. For more
details on visibility with respect to Kobayashi distance, interested readers
can refer to ([12, 6, 9, 11, 12]). Gromov hyperbolic space satisfies the
visibility property in the sense of Eberlein and O’Neill, i.e., every two
distinct Gromov boundary points can be joined by a geodesic line (see Remark
2.1).

The main motivation to study the visibility property in the quasihyperbolic
setting is the fact that visibility comes along with the property that the
identity map extends to a continuous map from the Gromov closure onto the
Euclidean closure; this is, a result by Nikolov, Bracci, and Thomas [9] in the
setting of Kobayashi distance. Allu and Pandey proved in [1, Theorem 1.3 and
1.4] that the same result holds true for the quasihyperbolic metric. This
motivates us to study Problem 1.1 using the visibility property, and for this
reason, we introduce the concept of quasihyperbolically visible spaces.

######  Definition 1.1.

Let $(\Omega,d)$ be a minimally nice space. We say that

  * (1)

$(\Omega,k)$ has the visibility property if the following holds:

    * ($*$)

For every pair of distinct points $p,q\in\partial_{d}X$, and sequence
$(x_{n}),(y_{n})$ in $X$ with $x_{n}\to p,y_{n}\to q$, there exists a compact
set $K$ in $\Omega$ such that every quasihyperbolic geodesic $\gamma_{n}$
joining $x_{n}$ and $y_{n}$ intersects $K$.

  * (2)

$(\Omega,d)$ satisfies the quashyperbolic visibility property if $(\Omega,k)$
has the visibility property.

  * (3)

$(\Omega,d)$ is quasihyperbolically visible, if $(\Omega,d)$ has the
quasihyperbolic visibility property.

In this line, we have the following result, which gives a condition for the
affirmative solution to Problem 1.1.

######  Theorem 1.1.

Let $(\Omega,d)$ be bounded minimally nice. Assume that $(X,k)$ is Gromov
hyperbolic. If $(\Omega,d)$ is quasihyperbolically visible, then the identity
map $id_{\Omega}$ extends to a continuous surjective map
$\widehat{id_{\Omega}}:\partial_{G}\Omega\to\partial_{d}\Omega$. In
particular, $\partial_{d}\Omega$ is compact. Moreover, in addition, if we
assume that $(\Omega,d)$ is quasi-convex and the Gehring-Hayman theorem holds
in $(\Omega,d)$, then the extension map is homeomorphism
$\widehat{id_{\Omega}}:\partial_{G}\Omega\to\partial_{d}\Omega$.

By Gehring-Hayman theorem holds in $(\Omega,d)$, we mean that there exists a
constant $C_{gh}\geq 1$ such that for each pair of points $x,y\in\Omega$ and
for each quasi-hyperbolic geodesic $\gamma$ joining $x$ and $y$, it holds
that-

$l(\gamma[x,y])\leq Cl(\sigma),$

where $\sigma$ is any other curve joining $x$ and $y$ in $\Omega$. In other
words, it says that quasihyperbolic geodesics are essentially the shortest
curves in $\Omega$. See [18, 19] for conditions on $(\Omega,d)$ to satisfy the
Gehring-Hayman theorem.

Our next result gives criteria for a minimally nice space to be a
quasihyperbolically visible space.

######  Theorem 1.2.

Let $(\Omega,d)$ bounded minimally nice space. Fix a base point
$x_{0}\in\Omega$ and $\phi:(0,\infty)\to(0,\infty)$ be an strictly increasing
function with $\phi(t)\to\infty$ as $t\to\infty$ such that

(1.2) $\int_{0}^{\infty}\frac{dt}{\phi^{-1}(t)}<\infty.$

If quasihyperbolic metric satisfies

(1.3)
$k(x_{0},x)\leq\phi\left(\frac{\delta_{\Omega}(x_{0})}{\delta_{\Omega}(x)}\right),$

then $(X,d)$ is quasihyperbolically visible.

######  Remark 1.1.

We use the same method as in [1] to prove Theorem 1.1 and Theorem 1.2. A few
adjustments are required due to the situation’s generality. Furthermore,
Theorem 1.1 and Theorem 1.2, implies/improve some of the known results in the
literature concerning Problem 1.1. Here is a list of few.

1. In [21] Lammi has proved the following result.

Theorem B. [21, Theorem 1.1] Let $(\Omega,d)$ be locally compact and non-
complete quasiconvex space. Assume that $(\Omega,k)$ is Gromov hyperbolic and
Gehring-Hayman theorem holds in $(\Omega,d)$. Let $w\in\Omega$ be a base point
and suppose that the quasihyperbolic metric satisfies

$k_{\Omega}(x_{0},x)\leq\phi\left(\frac{\delta_{\Omega}(x_{0})}{\delta_{\Omega}(x)}\right),$

where $\phi:(0,\infty)\to(0,\infty)$ is an increasing function which satisfies

$\sum_{j=1}^{\infty}\frac{1}{\phi^{-1}(j)}<\infty.$

Then the identification map $id:\partial_{G}\Omega\to\partial_{d}\Omega$ is a
homeomorphism, moreover $\partial_{d}\Omega$ is compact.  It is easy to see
that Theorem 1.1 together with Theorem 1.2 gives us Theorem B ∎

2\. $\varphi$-uniform domains. Let $(\Omega,d)$ be a rectifiably connected,
locally compact, non-complete bounded metric space. It is know that if
$(\Omega,d)$ is bounded and $\varphi$-uniform, then there is an increasing
function $\phi:[0,\infty)\to[0,\infty)$ such that for all $x\in\Omega$

$k_{\Omega}(x_{0},x)\leq\phi\left(\frac{\delta_{\Omega}(x_{0})}{\delta_{\Omega}(x)}\right)$

where $x_{0}\in\Omega$ satisfies
$\delta_{\Omega}(x_{0})=\max_{x\in\Omega}\delta_{\Omega}(x)$. In particular,
we can take

$\phi(t)=\varphi\left(\frac{\mbox{ diam
}(\Omega)t}{\delta_{\Omega}(x_{0})}\right).$

Note that the conditions

(1.4) $\int_{0}^{\infty}\frac{dt}{\phi^{-1}(t)}<\infty\,\,\,\mbox{ and
}\,\,\,\int_{0}^{\infty}\frac{dt}{\varphi^{-1}(t)}<\infty$

are mutually equivalent. Hence by Theorem 1.2, we get that bounded
$\varphi$-uniform domain under the condition (1.4) is quasihyperbolically
visible. This with Theorem 1.1 and [19, Theorem 5.1] gives us [24, Theorem 1.8
(1)]. ∎

##  2\. Preliminaries

###  2.1. Metric geometry

Let $(\Omega,d)$ be a metric space. A curve is a continuous function
$\gamma:[a,b]\rightarrow X$. Let $\mathcal{P}$ denote set of all partitions
$a=t_{0}<t_{1}<t_{2}<\cdots<t_{n}=b$ of the interval $[a,b]$. The length of
the curve $\gamma$ in the metric space $(X,d)$ is

$l_{d}(\gamma)=\sup_{\mathcal{P}}\sum_{k=0}^{n-1}d(\gamma(t_{k}),\gamma(t_{k+1})).$

A curve is said to be rectifiable if $l_{d}(\gamma)<\infty$. A metric space
$X$ is said to be rectifiably connected if every pair of points $x,y\in X$ can
be joined by a rectifiable curve. For a rectifiable curve $\gamma$, we define
arc length $s:[a,b]\rightarrow\left[0,l_{d}(\gamma)\right]$ by
$s(t)=l_{d}(\gamma|_{[a,t]})$. The arc length function is of bounded
variation. For any rectifiable curve $\gamma:[a,b]\to X$, there is a unique
map $\gamma_{s}:[0,l_{d}(\gamma)]\to X$ such that $\gamma=\gamma_{s}\circ s$,
and such a curve $\gamma_{s}$ is called the arclength parametrization of
$\gamma$.

######  Definition 2.1.

A curve $\gamma:[a,b]\to(\Omega,d)$ is said to be geodesic if it is an
isometry, i.e. for all $t,t^{\prime}\in[a,b]$,
$d(\gamma(t),\gamma(t^{\prime}))=|t-t^{\prime}|$. An isometry
$\gamma:[0,\infty)\to(\Omega,d)$ is called a geodesic ray, and an isometry
$\gamma:(-\infty,\infty)\to(\Omega,d)$ is called a geodesic line.

######  Definition 2.2.

A metric space $(\Omega,d)$ is said to be

  * (1)

a geodesic space if every pair of points $x,y\in\Omega$ can be joined by a
geodesic.

  * (2)

proper if every closed ball is compact in $\Omega$

  * (3)

intrinsic or a path metric space or a length space if for all $x,y\in\Omega$,
it holds that

$d(x,y)=\lambda_{\Omega}(x,y):=\inf_{\gamma}l_{d}(\gamma),$

where the infimum is taken over all rectifiable curves $\gamma$ in $\Omega$
joining $x,y$. $\lambda_{\Omega}(x,y)$ is konw as the inner length metric
associated to $(\Omega,d)$.

  * (4)

quasi-convex if there exists a constant $A\geq 1$ such that every pair of
points $x,y\in\Omega$ can be joined by a curve $\gamma$ such that
$l_{d}(\gamma)\leq A\,d(x,y)$.

###  2.2. Gromov hyperbolic space

Let $(\Omega,d)$ be a geodesic metric space, a geodesic triangle is the union
of geodesics $\gamma_{i}:[a_{i},b_{i}]\to X$, $i=1,2,3$ such that
$a_{i}<b_{i}$ for every $i=1,2,3$ and
$\gamma_{1}(b_{1})=\gamma_{2}(a_{1}),\gamma_{2}(b_{2})=\gamma_{3}(a_{3}),\gamma_{3}(b_{2})=\gamma_{1}(a_{1})$.
The geodesics $\gamma_{1},\gamma_{2}$ and $\gamma_{3}$ are called sides of the
geodesic triangle.

######  Definition 2.3.

Let $\delta\geq 0$. A geodesic metric space $(\Omega,d)$ is said to be
$\delta$-hyperbolic if every geodesic triangle is $\delta$-thin. That is, each
side of the geodesic triangle is contained in the $\delta$-neighborhood of the
union of the other two sides. A geodesic metric space $(\Omega,d)$ is said to
be Gromov hyperbolic if it is $\delta$-hyperbolic for some $\delta\geq 0$.

Let $(\Omega,d)$ is a proper geodesic Gromov hyperbolic space and
$p\in\Omega$. Let $\mathcal{G}_{p}$ be the space of all geodesic rays
$\gamma:[0,\infty)\to\Omega$ with $\gamma(0)=p$, endowed with the topology of
uniform convergence on compact subsets of $[0,\infty)$. Define an equivalence
relation $\sim$ on $\mathcal{G}_{p}$ as follows: Let
$\gamma,\sigma\in\mathcal{G}_{p}$ be two geodesic rays. Then

$\gamma\sim\sigma\iff\sup_{t\geq 0}d(\gamma(t),\sigma(t))<\infty.$

######  Definition 2.4.

  * (1)

The Gromov boundary of $\Omega$ is denoted by $\partial_{G}\Omega$ and is
defined as the quotient space $\mathcal{G}_{p}/\sim$ endowed with the quotient
topology.

  * (2)

The Gromov closure of $\Omega$ is denoted by $\overline{\Omega}^{G}$ and is
defined as $\overline{\Omega}^{G}=\Omega\cap\partial_{G}\Omega$.

The set $\overline{\Omega}^{G}$ admits a natural topology and with this
topology $\overline{\Omega}^{G}$ is a compactification of $\Omega$, known as
Gromov compactification of $\Omega$ (see for instance [10, Chapter III.H.3,
Proposition 3.7]).

To understand this topology, we need some additional notation: A generalized
ray is either a geodesic or a geodesic ray. For a geodesic ray
$\gamma\in\mathcal{G}_{p}$, define
$\mbox{End}(\gamma)=\\{\sigma:[0,\infty)\to\Omega:\sigma\mbox{ is a geodesic
ray with }\gamma(0)=p\mbox{ and }\sigma\sim\gamma\\}=[\gamma]$, and for a
geodesic $\gamma:[0,R]\to\Omega$ with $\gamma(0)=p$, where $R>0$, define
$\mbox{ End}(\gamma)=\gamma(R)$. Then a sequence
$\\{x_{n}\\}_{n\in\mathbb{N}}$ in $\overline{\Omega}^{G}$ converges to
$x\in\overline{\Omega}^{G}$ (denoted by $x_{n}\stackrel{{\scriptstyle
Gromov}}{{\longrightarrow}}x$), if, and only if, for every generalized ray
$\gamma_{n}$ with $\gamma_{n}(0)=p$ and $\mbox{ End}(\gamma_{n})=x_{n}$ its
every subsequence has a subsequence which converges uniformly on every compact
subset to a generalized ray $\gamma$ with $\gamma(0)=x_{0}$ and $\mbox{
End}(\gamma)=x$.

In view of the Gromov topology of $\overline{\Omega}^{G}$ we have the
following observation for geodesic rays and geodesic lines.

######  Remark 2.1.

For any geodesic ray $\gamma:[0,\infty)\to X$,

$\lim_{t\to\infty}\gamma(t)=\mbox{ End }(\gamma)=[\gamma]\in\partial_{G}X$

and for any geodesic line $\gamma:(-\infty,\infty)\to X$, both the following
limits exist and

$\lim_{t\to-\infty}\gamma(t)\neq\lim_{t\to\infty}\gamma(t).$

For a geodesic line $\gamma$, we denote
$\gamma(-\infty)=\lim_{t\to-\infty}\gamma(t)$ and
$\gamma(\infty)=\lim_{t\to\infty}\gamma(t)$.

For each $p\in\Omega$ and $\xi\in\partial_{G}\Omega$ there exists a geodesic
ray $\gamma:[0,\infty)\to\Omega$ such that $\mbox{ End }(\gamma)=\xi$, and for
each distinct points $\xi,\eta\in\partial_{G}\Omega$, there exists a geodesic
line $\gamma$ with $\gamma(-\infty)=\xi$ and $\gamma(\infty)=\eta$ (see [10,
Chapter III.H.3, Lemma 3.1 and Lemma 3.2]).

###  2.3. The Quasihyperbolic metric

Let $(\Omega,d)$ be a rectifiably connected, locally compact, noncomplete
metric space. Then the metric boundary $\partial_{d}\Omega$ is nonempty, and
we define the quasihyperbolic metric $k_{\Omega}$ in $\Omega$ by the length
element

$\frac{|dz|}{\delta_{\Omega}(z)},\,\,\,\,\delta_{\Omega}(z)=\mbox{ dist
}(z,\partial_{d}\Omega).$

Thus, $k_{\Omega}(x,y)=\inf_{\gamma}l_{k}(\gamma)$, where the infimum is taken
over all rectifiable curves $\gamma$ in $\Omega$ joining $x,y$ and

$l_{k}(\gamma)=\int_{\gamma}\frac{|dz|}{\delta_{\Omega}(z)}$

is called the quasihyperbolic length of a rectifiable curve $\gamma$. In view
of [8, Proposition 2.8], it is well-known that if $(\Omega,d)$ is minimally
nice, then $(\Omega,k_{\Omega})$ is a complete, proper and geodesic metric
space.

We recall some basic estimates for the quasihyperbolic metric. For all
$x,y\in\Omega$, we have

(2.1) $k_{\Omega}(x,y)\geq
log\left(1+\frac{\lambda_{\Omega}(x,y)}{\min\\{\delta(x),\delta(y)\\}}\right)\geq
log\left(1+\frac{|x-y|}{\min\\{\delta(x),\delta(y)\\}}\right)\geq\left|log\frac{\delta(y)}{\delta(x)}\right|$

and let $\gamma$ be a rectifiable curve in $\Omega$ joining $x$ and $y$, then

(2.2) $l_{n}(\gamma)\geq
log\left(1+\frac{l(\gamma)}{\min\\{\delta(x),\delta(y)\\}}\right).$

In view of (2.1), we have the following observation.

######  Observation 1.

Let $\Omega$ be a bounded domain. If sequences $\\{z_{n}\\}$,
$\\{w_{n}\\}\subset\Omega$ converge to two different points on
$\partial_{d}\Omega$, then

$\lim_{k\to\infty}k_{\Omega}(z_{n},w_{n})=\infty.$

In view of [8, Proposition 7.12, 7.14] and Balogh and Buckley [5, Theorem
0.1], we have the following important characterization of Gromov
hyperbolicity.

Theorem C. [8, Proposition 7.12, 7.14], [5, Theorem 0.1] Let
$\Omega\subset\mathbb{R}^{n}$ be a proper subdomain. Then
$(\Omega,k_{\Omega})$ is Gromov hyperbolic if, and only if, $\Omega$ satisfies
both a Gehring-Hayman condition and ball separation condition.

##  3\. Proof of Theorem 1.1

Throughout this section $(\Omega,d)$ is a bounded minimally nice space, and in
short we denote quasihyperbolic geodesic as qh-geodesic. We divide the proof
of Theorem 1.1 into several lemmas.

######  Lemma 3.1.

If $\gamma$ is a qh-geodesic ray in $\Omega$, then for any $t_{n}\to\infty$ as
$n\to\infty$, we have
$\lim\limits_{n\to\infty}\gamma(t_{n})\in\partial_{d}\Omega$.

Proof. Since $\gamma$ is a geodesic ray, i.e. $\gamma:[0,\infty)\to(\Omega,k)$
is an isometry we have

$|t_{n}|=k_{\Omega}(\gamma(0),\gamma(t_{n}))=\infty\,\,\,\,\mbox{ as
}n\to\infty.$

Therefore, in view of [14, Corollary 2.3], we have that
$\lim\limits_{n\to\infty}\gamma(t_{n})\in\partial_{d}\Omega$. ∎

######  Lemma 3.2.

Let $(\Omega,d)$ be quasihyperbolically visible. If $\gamma$ is a qh-geodesic
ray, then $\lim\limits_{t\to\infty}\gamma(t)$ exists in $\partial_{d}\Omega$.

Proof. For a qh-geodesic ray $\gamma$, consider following set

$L=\\{x\in\partial_{d}{\Omega}:\mbox{ there exists }t_{n}\to\infty\mbox{ such
that }\gamma(t_{n})\to x\mbox{ as }n\to\infty\\}.$

Suppose for contradiction that $L$ is not sigleton. Notice that $L$ is
connected so $L$ contains at least one point in $\partial\Omega$ (since the
metric completion $\overline{\Omega}$ is Hausdorff). Then, again by
connectedness, $L$ must contain at least two points in $\partial_{d}\Omega$,
say, $p,q$. Then following the proof of [1, Lemma 4.2], we get that $L\cap
K\neq\phi$, where $K$ is a compact set in $\Omega$ coming from the visibility
property, which is a contadiction. This completes the proof. ∎

######  Lemma 3.3.

Let $(\Omega,d)$ be quasihyperbolically visible. Fix $x_{0}\in\Omega$ and let
$\gamma$ and $\sigma$ be two qh-geodesic rays with $\gamma(0)=x_{0}=\sigma(0)$
such that $\gamma\sim\sigma$. Then

$\lim_{t\to\infty}\gamma(t)=\lim_{t\to\infty}\sigma(t).$

Proof. In view of Lemma 3.2, we have that
$\lim\limits_{t\to\infty}\gamma(t)\in\partial_{d}\Omega$. By contradiction
suppose

$\lim_{t\to\infty}\gamma(t)=p\neq q=\lim_{t\to\infty}\sigma(t).$

There exists a sequence $\\{s_{n}\\}$ with $s_{n}\to\infty$ such that
$\lim\limits_{k\to\infty}\gamma(s_{n})=p$ and
$\lim\limits_{n\to\infty}\sigma(s_{n})=q$. Write $z_{n}=\gamma(s_{n})$ and
$w_{n}=\sigma(s_{n})$, then $z_{n}\to p$ and $w_{n}\to q$. In view of
Observation 1, we have that
$\lim\limits_{k\to\infty}k_{\Omega}(z_{n},w_{n})=\infty$, which is a
contradiction to the fact that $\gamma\sim\sigma$. ∎

######  Lemma 3.4.

Suppose $(\Omega,d)$ is quasihyperbolically visible. Fix any point
$p\in\partial_{d}\Omega$ and $x_{0}\in\Omega$, then there exists a qh-geodesic
ray $\gamma$ issuing from $x_{0}$ such that
$\lim\limits_{t\to\infty}\gamma(t)=p$.

Proof. Fix $p\in\partial_{d}\Omega$, there is a sequence
$\\{x_{n}\\}\subset\Omega$ which converges to point $p$. Let $\gamma_{n}$ be
any sequence of qh-geodesics joining $x_{0}$ and $x_{n}$, then as $(\Omega,k)$
is a proper metric space, by Arzelá-Ascoli theorem there exists a subsequence
of $\\{\gamma_{n}\\}$ which converges uniformly on compacta to a qh-geodesic
ray $\gamma$. In view of Lemma 3.3, we have that
$\lim\limits_{t\to\infty}\gamma(t)=q\in\partial_{d}\Omega$. We need to show
that $p=q$. If not, let $p\neq q$, so there exists sequences $s_{n}\to\infty$
and $t_{n}\to\infty$ such that $\lim_{k\to\infty}\gamma_{n}(s_{n})=p$ and
$\lim_{k\to\infty}\gamma_{n}(t_{n})=q$. Upto a subsequence we can assume
$s_{n}<t_{n}$. Then by visibility property, there exists a comapct set
$K\subset\Omega$ such that $\gamma_{n}|_{[s_{n},t_{n}]}$ intersects with $K$
for sufficiently large $k$, say $\gamma_{n}(t^{\prime}_{n})\in K$ for some
$t^{\prime}_{n}\in[s_{n},t_{n}]$. Therefore,

$t^{\prime}_{n}=k_{\Omega}(x_{0}=\gamma_{n}(0),\gamma_{n}(t^{\prime}_{n}))\leq\max_{x\in
K}k_{\Omega}(x_{x},x)$

which gives that $t^{\prime}_{n}$ does not tend to $\infty$, a contradiction.
Hence, $p=q$. This completes the proof. ∎

Proof of Theorem 1.1. Assume that $\Omega$ is quasihyperbolically visible. Fix
a point $z_{0}\in\Omega$. In view of Lemma 3.2, define a map
$\Phi:\overline{\Omega}^{G}\to\overline{\Omega}^{Euc}$ as

$\Phi(z)=\begin{cases}z&\mbox{ if }z\in\Omega\\\\[8.53581pt] p&\mbox{ if
}\xi\in\partial_{G}\Omega.\end{cases}$

In view of Lemma 3.3, and Lemma 3.4 the map $\Phi$ is well defined and onto
respectively. To show that $\Phi$ is continuous we need to consider the
following two cases:

  * Case I.

If $\\{z_{n}\\}\subset\Omega$ is a sequence such that
$z_{n}\stackrel{{\scriptstyle Gromov}}{{\longrightarrow}}\xi$, where
$\xi\in\partial_{G}\Omega$. Since $z_{n}\stackrel{{\scriptstyle
Gromov}}{{\longrightarrow}}\xi$, which means that for every qh-geodesic
$\gamma_{n}:[0,T_{n}]\to\Omega$ with $\gamma_{n}(0)=z_{0}$ and
$\gamma_{n}(T_{n})=z_{n}$, every subsequence has a subsequence which converges
uniformly on compacta to a geodesic ray $\gamma\in\xi$. In view of Lemma 3.3,
we have $\lim\limits_{t\to\infty}\gamma(t)\in\partial_{d}\Omega$. Our aim is
to show that

$\lim\limits_{k\to\infty}z_{n}=\lim\limits_{t\to\infty}\gamma(t).$

As $\lim\limits_{t\to\infty}\gamma(t)=p\in\partial_{d}\Omega$. Then an
argument using visibility shows that $p=q$ (see [1, Lemma 4.5]).

  * Case II.

If $\\{\xi_{n}\\}\subset\partial_{G}\Omega$ is a sequence such that
$\xi_{n}\stackrel{{\scriptstyle Gromov}}{{\longrightarrow}}\xi$, where
$\xi\in\partial_{G}\Omega$
Let $\gamma_{n}$ be the representative from $\xi_{n}$. Then
$\xi_{n}\stackrel{{\scriptstyle Gromov}}{{\longrightarrow}}\xi$ gives that
every subsequence of $\gamma_{n}$ has a subsequence which converges uniformly
on compact subsets to a geodesic ray $\gamma\in\xi$. Then using the same
argument as in Case I, we get the desired.

Thus, in view of Case I and Case II, $\Phi$ is continuous.

Now, we only need to show that $\Phi$ is a homeomorphism. For this, let
$\xi,\eta\in\partial_{G}\Omega$, $\xi\neq\eta$ then there is a geodesic line
$\Gamma$ in $\Omega$ joining $\xi$ and $\eta$. Let
$p,q\in\partial_{Euc}\Omega$, be points such that
$\lim\lim\limits_{t\to\infty}\Gamma(t)=p$ and
$\lim\lim\limits_{t\to-\infty}\Gamma(t)=q$. We need to show that $p\neq q$,
for any sequence $t_{n}\to\infty$ and $s_{n}\to-\infty$, let
$x_{n}=\gamma(t_{n})$ and $y_{n}=\gamma(s_{n})$, then $x_{n}\to p$ and
$y_{n}\to q$. Since by assumption $(\Omega,d)$ is quasi-convex, there exists a
constant $A$ and sequence of curves $\gamma_{n}$ joining $x_{n}$, $y_{n}$ such
that

$\displaystyle l(\Gamma[x_{n},y_{n}])$ $\displaystyle\leq$ $\displaystyle
C\,l(\gamma_{n})\,\,\,(\mbox{by Gehring-Hayman theorem})$ $\displaystyle\leq$
$\displaystyle C\,A\,|x_{n}-y_{n}|\,\,\,(\mbox{by quasiconvexity})$

Note that (3) shows us that if $p=q$, then $l(\Gamma)=0$. Furthermore, this
implies $\xi=\eta$, which is a contradiction to Remark 2.1. Thus, $\Phi$ is a
continuous bijection from a compact space to a Hausdorff space. Hence, $\Phi$
is a homeomorphism. This completes the proof. ∎

##  4\. Proof of Theorem 1.2

To prove Theorem 1.2, we need the following important remark.

######  Remark 4.1.

It is often convenient to parametrize a cuve $\gamma$ in $(\Omega,d)$ by
quasihyperbolic length. We say that $g:[0,r]\to\Omega$ is a quasihyperbolic
parametrization of a curve $\gamma:[a,b]\to(\Omega,d)$ if $l_{k}(g[0,t])=t$
for all $t\in[0,r]$. Every rectifiable curve $\gamma$ in $(\Omega,d)$ has a
quasihyperbolic parametrization $g:[0,r]\to\gamma$, and $g$ satisfies the
Lipschitz condition

$d(g(s),g(t))\leq M|s-t|,$

where $M=\max\\{\delta(x):x\in\gamma\\}$. Since metric derivative for
Lipschitz curves exits a.e. (for details we refer to [3, p.2 and p. 24], [2],
and [4, Theorem 3.2]), we have

  * (i)

$r=l_{k}(g)$,

  * (ii)

$|g^{\prime}|(t)=\delta_{\Omega}(g(t))$, and

$d(g(s)),g(t))\leq\int_{s}^{t}|g^{\prime}|(r)\,dr$

almost everywhere, where $|g^{\prime}|(t)$ is the metric derivative in
$(\Omega,d)$. If $\gamma$ is a quasihyperbolic geodesic, then
$g:[0,r]\to(\Omega,k_{\Omega})$ is an isometry and we say that $g$ is a
quasihyperbolic geodesic from $g(0)$ to $g(r)$.

Proof of Theorem 1.2. Suppose $(\Omega,d)$ is not quasihyperbolically visible.
Then there are $p,q\in\partial_{d}\Omega$, $p\neq q$, and sequences
$\\{x_{n}\\},\\{y_{n}\\}\subset\Omega$ with $x_{n}\rightarrow p$ and
$y_{n}\rightarrow q$ as $n\to\infty$, and a sequence of quasihyperbolic
geodesics $\gamma_{n}:[a_{n},b_{n}]\to\Omega$ joining $x_{n}$ and $y_{n}$ such
that

(4.1) $\max_{t\in[a_{n},b_{n}]}\delta_{\Omega}(\gamma_{n}(t))\rightarrow
0,\mbox{ as }n\rightarrow\infty.$

By a suitable quasihyperbolic parameterization
$g_{n}:[a_{n},b_{n}]\rightarrow\Omega$ of $\gamma_{n}$ with
$g_{n}(a_{n})=x_{n}$, $g_{n}(b_{n})=y_{n}$ and
$|b_{n}-a_{n}|=l_{k}(g_{n}[a_{n},b_{n}])$, we can assume that, for all
$n,a_{n}\leq 0\leq b_{n}$ and

(4.2)
$\max_{t\in[a_{n},b_{n}]}\delta_{\Omega}(g_{n}(t))=\delta_{\Omega}(g_{n}(0)).$

Furthermore, by Remark 4.1 we have that each $g_{n}$ satisfies the following
Lipschitz condition

$d(g_{n}(s),g_{n}(t))\leq M_{n}|s-t|,\,\,\,s,t\in[a_{n},b_{n}],$

where, $M_{n}=\max\\{\delta_{\Omega}(x):x\in\gamma_{n}\\}$. In view of (4.1),
each $g_{n}$ is $M$-Lipschitz with respect to the Euclidean distance, where
$M=\sup_{n\geq 1}\\{M_{n}\\}$. Therefore, by Arzela-Ascoli theorem, up to
subsequence we can assume:

  * (i)

$a_{n}\rightarrow a\in[-\infty,0]$ and $b_{n}\rightarrow b\in[0,\infty]$

  * (ii)

$g_{n}$ converges uniformly on every compact subset of $(a,b)$ to a continuous
map $g:(a,b)\rightarrow\overline{\Omega}$ and $g_{n}(a_{n})\rightarrow p$,
$g_{n}(b_{n})\rightarrow q$.

We make the following observation

######  Observation 2.

$a<b$ and both $a$ and $b$ together can’t be finite.

  * •

We conclude from the fact $d(g_{n}(a_{n}),g_{n}(b_{n}))\leq
M|a_{n}-b_{n}|,\,\,\,\mbox{ for all }n$ that $a<b$.

  * •

By Remark 4.1, we have that $g_{n}:[a_{n},b_{n}]\to(\Omega,k_{\Omega})$ is an
isometry. This gives us that
$|b-a|=\lim\limits_{n\to\infty}|b_{n}-a_{n}|=\lim\limits_{n\to\infty}k(g_{n}(b_{n}),g_{n}(a_{n}))=\infty\,\,\,(\mbox{
by Observation \ref{observation}})$. Therefore, it is clear that both $a$ and
$b$ together can’t be finite.

######  Claim 1.

$g:(a,b)\rightarrow\overline{\Omega}^{d}$ is a constant map.

Proof of Claim 1. In view of (4.1), we have that $\delta_{\Omega}(g_{n}(t))$
converges uniformly to $0$. Then for $s<t\in(a,b)$, we have

(4.3)
$d(g(s),g(t))=\lim_{n\rightarrow\infty}d(g_{n}(s)-g_{n}(t))\leq\lim\limits_{n\to\infty}M_{n}|s-t|=0.$

This yields that $g$ is a constant map. ∎

Further using the quasihyperbolic growth in $\Omega$, we will establish a
contradiction by proving the following

######  Claim 2.

$g:(a,b)\rightarrow\overline{\Omega}^{d}$ is not a constant map.

Proof of Claim 2. Since $g_{n}$ is an isometry, we have

$\displaystyle|t|=k_{\Omega}(g_{k}(0),g_{k}(t))$ $\displaystyle\leq$
$\displaystyle k_{\Omega}(g_{k}(0),x_{0}))+k_{\Omega}(x_{0},g_{k}(t))$
$\displaystyle\leq$
$\displaystyle\phi\left(\frac{\delta_{\Omega}(x_{0})}{\delta_{\Omega}(g_{n}(0))}\right)+\phi\left(\frac{\delta_{\Omega}(x_{0})}{\delta_{\Omega}(g_{n}(t))}\right)$
$\displaystyle\leq$ $\displaystyle
2\phi\left(\frac{\delta_{\Omega}(x_{0})}{\delta_{\Omega}(g_{n}(t))}\right)\,\,\,(\mbox{by
}\eqref{***})$

In view of Observation 2, we have only following two cases to consider:

  * Case 1:

Both $a$ and $b$ are infinite.

  * Case 2:

Either only $a$ or only $b$ is finite. In other words, either only $a$ or only
$b$ is infinite.

Let us first consider the Case 1 and assume that $a=-\infty$ and $b=\infty$.
The fact that $b_{n}\to\infty$ and $a_{n}\to-\infty$ and the function $\phi$
is strictly increasing with $\lim\limits_{t\to\infty}\phi(t)=\infty$ imply
that there is a positive integer $n_{0}$ and positive constants $A$ and $B$
such that we have the following

  * (i)

whenever $t\in(B,b_{n}]$ and $n\geq n_{0}$, we have

$\frac{|t|}{2}\in\mbox{{range}}(\phi),\mbox{ and hence,
}\delta_{\Omega}(g_{n}(t))\leq\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{|t|}{2}\right)}\,.$

  * (ii)

whenever $t\in(a_{n},-A]$ and $n\geq n_{0}$, we have

$\frac{|t|}{2}\in\mbox{{range}}(\phi),\mbox{ and hence,
}\delta_{\Omega}(g_{n}(t))\leq\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{|t|}{2}\right)}\,.$

Let $\epsilon=||p-q||/2$, then we can choose $a^{*}\in(-\infty,-A)$ and
$b^{*}\in(B,\infty)$ such that

(4.4)
$||p-q||>\int_{b^{*}}^{+\infty}\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{t}{2}\right)}\,dt+\int_{-\infty}^{a^{*}}\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{|t|}{2}\right)}\,dt$

Therefore, we have

$\displaystyle d(g(b^{*})-g(a^{*}))$ $\displaystyle=$
$\displaystyle\lim_{n\to\infty}d(g_{n}(b^{*})-g_{n}(a^{*}))$
$\displaystyle\geq$
$\displaystyle\limsup_{k\rightarrow\infty}\left[d(g_{n}(b_{n}),g_{n}(a_{n}))-d(g_{n}(b_{n}),g_{n}(b^{*}))-d(g_{n}(a_{n}),g_{n}(a^{*}))\right]$
$\displaystyle\geq$
$\displaystyle||p-q||-\limsup_{k\rightarrow\infty}\int_{b^{*}}^{b_{k}}|g_{k}^{\prime}|(t)\,dt-\limsup_{k\rightarrow\infty}\int_{a_{n}}^{a^{*}}|g_{k}^{\prime}|(t)\,dt$
$\displaystyle\geq$
$\displaystyle||p-q||-\limsup_{k\to\infty}\int_{b^{*}}^{b_{n}}\delta_{\Omega}(g_{n}(t))\,dt-\limsup_{k\to\infty}\int_{a_{n}}^{a^{*}}\delta_{\Omega}(g_{n}(t))\,dt$
$\displaystyle\geq$
$\displaystyle||p-q||-\limsup_{k\rightarrow\infty}\int_{b^{*}}^{b_{n}}\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{t}{2}\right)}\,dt-\limsup_{k\rightarrow\infty}\int_{a_{n}}^{a^{*}}\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{|t|}{2}\right)}\,dt$
$\displaystyle\geq$
$\displaystyle||p-q||-\int_{b^{*}}^{+\infty}\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{t}{2}\right)}\,dt-\int_{-\infty}^{a^{*}}\frac{\delta_{\Omega}(x_{0})}{\phi^{-1}\left(\frac{|t|}{2}\right)}\,dt>0\,\,\,(\mbox{by
}\eqref{2}).$

Thus, $g$ is non-constant. For Case 2, following the same steps as Case 1, we
conclude that g is non-constant. ∎

Combining both the cases, we find that $g$ is not constant, which contradicts
Claim 1. This indicates the existence of the compact set $K$. Therefore,
$(\Omega,d)$ is quasihyperbolically visible. This concludes the proof of
Theorem 1.2. ∎

### Acknowledgements

The second named author thanks Prime Minister’s Research Fellowship (Id:
1200297), Govt. of India for their support.

## References

  * [1] V. Allu and A. Pandey, Visible quasihyperbolic geodesics, arXiv:2306.03815v2 (2023).
  * [2] L. Ambrosio, Metric space valued functions of bounded variation, Ann. Sc. Norm. Sup. Pisa, 17 (1990), 439–478.
  * [3] L. Ambrosio, N. Gigli, and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures, ETH Zürich, Birkhäuser Verlag, Basel. (2005).
  * [4] L. Ambrosio and B. Kirchheim, Rectifiable sets in metric and Banach spaces, Math. Ann. 318 (2000), 527–555.
  * [5] Z. M. Balogh and S. M. Buckley, Geometric characterizations of Gromov hyperbolicity, Invt. Math. 153 (2003), 261–301.
  * [6] G. Bharali and A. Maitra, A weak notion of visibility, a family of examples, and Wolff-Denjoy theorems, Ann. Sc. Norm. Super. Pisa Cl. Sci. (2021), 195–240.
  * [7] G. Bharali and A. Zimmer, Goldilocks domains, a weak notion of visibility, and applications, Adv. Math. 310 (2017), 377–425.
  * [8] M. Bonk, J. Heinonen and P. Koskela, Uniformizing Gromov hyperbolic domains, Asterisque 270 (2001), 1–99.
  * [9] F. Bracci, Nikolai Nikolov and P. J. Thomas, Visibility of Kobayashi geodesics in convex domains and related properties, Math. Z. 301 (2022), 2011–2035.
  * [10] M. R. Bridson and A. Haefliger, Metric spaces of Non-positive curvature, Grundlehren der Mathematics Wissenschaften (Fundamental Principles of Mathematical Sciences), vol. 319, Springer-Verlag, Berlin, 1999.
  * [11] V. S. Chandel, A. Maitra and A. D. Sarkar, Notions of visibility with respect to the Kobayashi distance: Comparison and Applications, arXiv:2111.00549v1 (2021).
  * [12] P. Eberlein and B. O’Neill, Visibility manifolds, Pac. J. Math. 46 (1973), 45–110.
  * [13] F. W. Gehring and O. Martio, Lipschitz classes and quasiconformal mappings, Ann. Acad. Sci. Fenn. Ser. A I Math. 10 (1985), 203–219.
  * [14] F. W. Gehring and B. P. Palka, Quasiconformally Homogeneous Domains, J. Anal. Math. 30 (1976), 172–199.
  * [15] F. W. Gehring and B. G. Osgood, Uniform domains and the Quasi-Hyperbolic Metric, J. Anal. Math. 36 (1979), 50–74.
  * [16] É. Ghys and P. De La Harpe, Sur les groupes hyperboliques d’apres Mikhael Gromov, Progress in Mathematics 83, Birkhäuser, Boston, 1990.
  * [17] S. Hencl and P. Koskela, Quasihyperbolic boundary conditions and capacity: uniform continuity of quasiconformal mappings, J. Anal. Math. 96 (2005), 19–35.
  * [18] P. Koskela, P. Lammi, Gehring-Hayman theorem for conformal deformations, Comment. Math. Helv. 88 (2013), 185–203.
  * [19] P. Koskela, P. Lammi and V. Manojlović, Gromov hyperbolicity and quasihyperbolic geodesics, Ann. Sci. Éc. Norm. Supér. 52 (2014), 975–990.
  * [20] P. Koskela, J. Onninen and J. T. Tyson, Quasihyperbolic boundary conditions and capacity: Hölder continuity of quasiconformal mappings, Comment. Math. Helv. 76 (2001), 416–435.
  * [21] P. Lammi, Quasihyperbolic boundary condition: compactness of the inner boundary, Ill. J. Math. 55 (2011), 1221–1233.
  * [22] J. Väisälä, Hyperbolic and Uniform domains in Banach spaces, Ann. Acad. Sci. Fenn. 30 (2005), 261–302.
  * [23] Q. Zhou, L. Li, and A. Rasila, Generalized John Gromov hyperbolic domains and extensions of maps, Math. Scand. 127 (2021), 10.7146/math.scand.a-128968.
  * [24] Q. Zhou, Y. Li and X. Li, Sphericalizations and applications in Gromov hyperbolic spaces, J. Math. Anal. Appl. 509, (2022) 125948.