Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Resolution of the Erd\H{o}s-Sauer problem on regular subgraphs   In this paper we completely resolve the well-known problem of Erd\H{o}s and
Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph
can have without containing a $k$-regular subgraph, for some fixed integer
$k\geq 3$. We prove that any $n$-vertex graph with average degree at least
$C_k\log \log n$ contains a $k$-regular subgraph. This matches the lower bound
of Pyber, R\"odl and Szemer\'edi and substantially improves an old result of
Pyber, who showed that average degree at least $C_k\log n$ is enough.
  Our method can also be used to settle asymptotically a problem raised by
Erd\H{o}s and Simonovits in 1970 on almost regular subgraphs of sparse graphs
and to make progress on the well-known question of Thomassen from 1983 on
finding subgraphs with large girth and large average degree.

8
The categories of this paper are: hep-ex
35
The categories of this paper are: mtrl-th
36
The categories of this paper are: cmp-lg
3
The categories of this paper are: physics
10
The categories of this paper are: q-bio
23
The categories of this paper are: solv-int
5
The categories of this paper are: gr-qc
7
The categories of this paper are: hep-th
20
The categories of this paper are: acc-phys
21
The categories of this paper are: adap-org
31
The categories of this paper are: ao-sci
15
The categories of this paper are: nucl-ex
1
The categories of this paper are: cs
6
The categories of this paper are: astro-ph
33
The categories of this paper are: plasm-ph
22
The categories of this paper are: chao-dyn