Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Asymmetric list sizes in bipartite graphs   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 \ge \Delta_A^\varepsilon$ and $k_B \ge \Delta_B^\varepsilon$ for
any $\varepsilon>0$ provided $\Delta_A$ and $\Delta_B$ are large enough;
  * if $k_A \ge C \log\Delta_B$ and $k_B \ge C \log\Delta_A$ for some absolute
constant $C>1$; or
  * if $\Delta_A=\Delta_B = \Delta$ and $ k_B \ge 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.

0
The categories of this paper are: hep-ph
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
1
The categories of this paper are: cs
26
The categories of this paper are: bayes-an
10
The categories of this paper are: q-bio
28
The categories of this paper are: alg-geom
29
The categories of this paper are: funct-an
20
The categories of this paper are: acc-phys
27
The categories of this paper are: comp-gas
30
The categories of this paper are: q-alg
7
The categories of this paper are: hep-th
6
The categories of this paper are: astro-ph
35
The categories of this paper are: mtrl-th
25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin