×

Almost color-balanced perfect matchings in color-balanced complete graphs. (English) Zbl 1479.05118

Summary: 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\) 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 T. Kittipassorn and P. Sinsap [“On the existence of zero-sum perfect matchings of complete graphs”, Preprint, arXiv:2011.00862] whether every \(k\)-edge colored color-balanced complete graph \(K_{2 k n}\) has a color-balanced perfect matching \(M\). For a perfect matching \(M\) of \(K_{2 k n}\), a natural measure for the total deviation of \(M\) from being color-balanced is \(f(M) = \sum_{i = 1}^k | m_i(M) - n |\). While not every \(k\)-edge colored color-balanced complete graph \(K_{2 k n}\) 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 ( k \sqrt{ k n \ln ( k )} )\) 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C55 Generalized Ramsey theory
05D10 Ramsey theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
11B50 Sequences (mod \(m\))
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Azuma, K., Weighted sums of certain dependent random variables, Tohoku Math. J., 19, 357-367 (1967) · Zbl 0178.21103
[2] Carathéodory, C., Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Ann., 64, 95-115 (1907) · JFM 38.0448.01
[3] Caro, Y., Zero-sum problems - a survey, Discrete Math., 152, 93-113 (1996) · Zbl 0856.05068
[4] Caro, Y.; Hansberg, A.; Lauri, J.; Zarb, C., On zero-sum spanning trees and zero-sum connectivity · Zbl 1481.05078
[5] Ehard, S.; Mohr, E.; Rautenbach, D., Low weight perfect matchings, Electron. J. Comb., 27, Article P4.49 pp. (2020) · Zbl 1456.05070
[6] Erdős, P.; Spencer, J., Lopsided Lovász local lemma and latin transversals, Discrete Appl. Math., 30, 151-154 (1991) · Zbl 0717.05017
[7] Fujita, S.; Kaneko, A.; Schiermeyer, I.; Suzuki, K., A rainbow k-matching in the complete graph with r colors, Electron. J. Comb., 16 (2009), # R51 · Zbl 1181.05040
[8] Gao, W.; Geroldinger, A., Zero-sum problems in finite abelian groups: a survey, Expo. Math., 24, 337-369 (2006) · Zbl 1122.11013
[9] Hatami, P.; Shor, P. W., A lower bound for the length of a partial transversal in a Latin square, J. Comb. Theory, Ser. A, 115, 1103-1113 (2008) · Zbl 1159.05303
[10] Keevash, P.; Pokrovskiy, A.; Sudakov, B.; Yepremyan, L., New bounds for Ryser’s conjecture and related problems · Zbl 1490.05269
[11] Kittipassorn, T.; Sinsap, P., On the existence of zero-sum perfect matchings of complete graphs · Zbl 1509.05148
[12] Kostochka, A.; Yancey, M., Large rainbow matchings in edge-coloured graphs, Comb. Probab. Comput., 21, 255-263 (2012) · Zbl 1241.05115
[13] Molloy, M.; Reed, B., Graph Colouring and the Probabilistic Method (2002), Springer-Verlag: Springer-Verlag Berlin Heidelberg · Zbl 0987.05002
[14] Ryser, H. J., Neuere Probleme der Kombinatorik, (Vorträge über Kombinatorik Oberwolfach (July 1967), Mathematisches Forschungsinstitut Oberwolfach), 24-29
[15] Stein, S. K., Transversals of Latin squares and their generalizations, Pac. J. Math., 59, 567-575 (1975) · Zbl 0302.05015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.