Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Almost color-balanced perfect matchings in color-balanced complete
  graphs   For a graph $G$ and a not necessarily proper $k$-edge coloring $c:E(G)\to \{
1,\ldots,k\}$, let $m_i(G)$ be the number of edges of $G$ of color $i$, and
call $G$ {\it color-balanced} if $m_i(G)=m_j(G)$ for every two colors $i$ and
$j$. Several famous open problems relate to this notion; Ryser's conjecture on
transversals in latin squares, for instance, is equivalent to the statement
that every properly $n$-edge colored complete bipartite graph $K_{n,n}$ has a
color-balanced perfect matching. We contribute some results on the question
posed by Kittipassorn and Sinsap (arXiv:2011.00862v1) whether every $k$-edge
colored color-balanced complete graph $K_{2kn}$ has a color-balanced perfect
matching $M$. For a perfect matching $M$ of $K_{2kn}$, a natural measure for
the total deviation of $M$ from being color-balanced is
$f(M)=\sum\limits_{i=1}^k|m_i(M)-n|$. While not every color-balanced complete
graph $K_{2kn}$ has a color-balanced perfect matching $M$, that is, a perfect
matching with $f(M)=0$, we prove the existence of a perfect matching $M$ with
$f(M)=O\left(k\sqrt{kn\ln(k)}\right)$ for general $k$ and $f(M)\leq 2$ for
$k=3$; the case $k=2$ has already been studied earlier. An attractive feature
of the problem is that it naturally invites the combination of a combinatorial
approach based on counting and local exchange arguments with probabilistic and
geometric arguments.

23
The categories of this paper are: solv-int
15
The categories of this paper are: nucl-ex
13
The categories of this paper are: quant-ph
31
The categories of this paper are: ao-sci
30
The categories of this paper are: q-alg
14
The categories of this paper are: math-ph
1
The categories of this paper are: cs
4
The categories of this paper are: cond-mat
27
The categories of this paper are: comp-gas
16
The categories of this paper are: stat
24
The categories of this paper are: dg-ga
21
The categories of this paper are: adap-org
37
The categories of this paper are: supr-con
7
The categories of this paper are: hep-th
8
The categories of this paper are: hep-ex
28
The categories of this paper are: alg-geom