ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 39-47
https://doi.org/10.26493/1855-3974.1316.2d2
(Also available at http://amc-journal.eu)
Transversals in generalized Latin squares*
Janos Baratf
University ofPannonia, Department of Mathematics, 8200 Veszprem, Egyetem utca 10., Hungary and MTA-ELTE Geometric and Algebraic Combinatorics Research Group, H-1117 Budapest, Pdzmdny P. sitdny 1/C, Hungary
Zoltan Lorant Nagy *
MTA-ELTE Geometric and Algebraic Combinatorics Research Group, H-1117 Budapest, Pazmany P. setany 1/C, Hungary and ELTE Eotvos Lorand University, Department of Computer Science, H-1117 Budapest, Pazmany P. setany 1/C, Hungary
Received 31 January 2017, accepted 29 July 2018, published online 9 September 2018
We are seeking a sufficient condition that forces a transversal in a generalized Latin square. A generalized Latin square of order n is equivalent to a proper edge-coloring of Kn,n. A transversal corresponds to a multicolored perfect matching. Akbari and Alipour defined l(n) as the least integer such that every properly edge-colored Kn,n, which contains at least l(n) different colors, admits a multicolored perfect matching. They conjectured that l(n) < n2/2 if n is large enough. In this note we prove that l(n) is bounded from above by 0.75n2 if n > 1. We point out a connection to anti-Ramsey problems. We propose a conjecture related to a well-known result by Woolbright and Fu, that every proper edge-coloring of K2n admits a multicolored 1-factor.
Keywords: Latin squares, transversals, anti-Ramsey problems, Lovdsz local lemma. Math. Subj. Class.: 05B15, 05C15, 60C05
* We are grateful for an anonymous referee for pointing out numerous inaccuracies and for a valuable observation in the proof of Proposition 3.5, hence thereby improving the presentation of our paper.
tSupported by Szechenyi 2020 under the EFOP-3.6.1-16-2016-00015 and OTKA-ARRS Slovenian-Hungarian Joint Research Project, Grant No. NN-114614.
i Supported by OTKA Grant No. K 120154 and by the Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences.
E-mail addresses: barat@cs.elte.hu (Janos Barat), nagyzoli@cs.elte.hu (Zoltan Lorant Nagy)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
40
Ars Math. Contemp. 16 (2019) 157-171
1 Multicolored matchings and generalized Latin squares
A subgraph H of an edge-colored host graph G is multicolored if the edges of H have different colors. The study of multicolored (also called rainbow, heterochromatic) subgraphs dates back to the 1960's. However, the special case of finding multicolored perfect matchings in complete bipartite graphs was first studied much earlier by Euler in the language of Latin squares. Since then this branch of combinatorics, especially the mentioned special case, has been flourishing. Several excellent surveys were dedicated to the subject, see [8,9, 10, 13].
In this paper we mainly focus on the case when the host graph is a complete bipartite graph Kn,n, and the multicolored subgraph in view is a perfect matching (1-factor). There is a natural constraint on the coloring: it has to be proper.
These conditions can be reformulated in the language of Latin squares. A Latin square of order n is an n x n matrix, which has n different symbols as entries, and each symbol appears exactly once in each row and in each column. A generalized Latin square of order n is an n x n matrix, in which each symbol appears at most once in each row and in each column. A diagonal of a generalized Latin square of order n is a set of entries, which contains exactly one representative from each row and column. If the symbols are all different in a diagonal, then we call it a transversal.
Generalized Latin squares correspond to properly edge-colored complete bipartite graphs, while transversals correspond to multicolored 1-factors (perfect matchings). The so called partial transversals correspond to multicolored matchings. This intimate relation allows us to use the concept of symbols and colors interchangeably.
It is known that there exist Latin squares without a transversal. One might think that using more symbols should help finding a transversal. Therefore, it is natural to seek the sufficient number of symbols. We recall the following
Definition 1.1 (Akbari and Alipour [1]). Let 1(n) be the least number of symbols satisfying 1(n) > n that forces a transversal in any generalized Latin square of order n that contains at least 1(n) symbols.
In the terminology of matchings, they asked the threshold for the number 1(n) of colors such that any proper 1-coloring of Kn,n contains a multicolored perfect matching if 1 > l(n). Notice that the function l(n) is not obviously monotone increasing.
Akbari and Alipour determined l(n) for small n: 1(1) = 1,1(2) = 1(3) = 3,1(4) = 6. They also proved that 1(n) > n + 3 for n = 2° - 2 (2 < a e N). They posed the following
Conjecture 1.2 (Akbari and Alipour [1]). The difference 1(n) -n is not bounded if n ^ to, while 1(n) < n2/2 if n > 2.
Our main contribution is the following
Theorem 1.3. 1(n) < 0.75n2 if n > 1.
Although we conjecture that 1(n) = o(n2), we must mention that if we relax the settings by allowing symbols to appear more than once in the columns, then for all n, there exist n x n transversal-free matrices, which contain n2/2 + O(n) symbols [2].
The paper is built up as follows. In Section 2 we show the connection of the problem to a classical Erdos-Spencer result. We prove an upper bound on 1(n) using a refined variant of the Lovasz local lemma. We present the proof of Theorem 1.3, which is mainly built on Konig's theorem. Finally in Section 3, we propose the study of a function similar to 1(n), and investigate the relation to certain anti-Ramsey problems.
J. Barat and Z. L. Nagy: Transversals in generalized Latin squares
41
2 Two approaches to bound the number of symbols
2.1 Lovasz local lemma
It is a classical application of the Lovasz local lemma (LLL) that there exists a transversal in an n x n matrix if no color appears more than 1 n times. In fact, Erdos and Spencer [7] weakened the conditions of LLL by introducing the so called lopsided dependency graph G of the events, on which the following holds for every event Ei and every subfamily F of events {Ej : j & NG [i]}:
P(Ei | HjeFEj) < P(E),
where NG [i] denotes the closed neighborhood of vertex i in graph G. Under this assumption, it is enough to show the existence of an assignment i i—> > 0) which fulfills
P(Ei) < =-^--(2.1)
Lsc»G[i] 1 Ijes Mj
to obtain P(HiE) > 0.
Applying the ideas of Scott and Sokal [11]; Bissacot, Fernandez, Procacci and Scop-pola [4] observed that LLL remains valid if the summation in Inequality (2.1) is restricted to those sets S which are independent in G.
Let c(aij) denote the number of occurrences of the symbol aij in an n x n array A (n > 1). Let c„ (A) and c* j (A) measure the average occurrence in row i and column j as
Ci*(A) = ^^ c(ait)^ - n and c*j(A) = ^^ c(atj- n.
It can be viewed as some kind of weight-function on the rows and columns, where the weight is zero only if all entries admit uniquely occurring colors.
We follow the proof of the improvement on the Erdos-Spencer result in [4]. We show that P (nv Ev) > 0 holds for the set of events {Ev} that a random diagonal contains a particular pair v of monochromatic entries. Here |NG [v] | in the lopsided dependency graph G depends only on the number of monochromatic pairs (v, v') of entries, which shares (at least) one row or column with an entry from both v and v'. Thus if v consists of aij and aki, then |Ng[v]| < c„(A) + c*j(A) + cfc*(A) + c*;(A). Also if w, w' G Ng[v] covers the same row from {i, k} or column from {j, 1} then w and w' are adjacent in G. If we set mv := M ^v, then it is enough to provide a m such that
P(Ev)= . 1 . <	Mv	—	M
n(n 1) J2sCNa[v],S indep^jeS Mj J2sCNG[v], S indep. M|S|
Consequently, it is enough to set m in such a way that
M
^2sCNa [v], S indep. M
|S|
>
M	> 1
(1 + c„(A)m)(1 + c*j(A)m)(1 + ck*(A)M)(1 + c*i(A)m) ~ n(n - 1)
holds.
42
Ars Math. Contemp. 16 (2019) 157-171
It is easy to see that (1 + Up)(1 + Vp) < (1 + m)2 for all U, V e R, hence
M > 1
(1 + cVm)4 > n(n - 1)
implies the required condition, where
_ c„(A) + cj(A) + ck„(A) + c*(A)
4
Thus if we set ^ := , we obtain the following
Proposition 2.1. There always exists a transversal in a generalized Latin square unless 4 f
-J (c„(A) + cj (A) + cfc,(A) + c*;(A)) > n(n - 1)	(2.2)
holds for a pair of monochromatic entries aj and aki.
Corollary 2.2. l(n) < (1 - 2=5)n2 + 22=73n ~ 0.895n2 if n > 1.
Proof. Observe that n2 - c„ (A) or n2 - c*j (A) bounds from above the number of colors in A for then
A for all i, j e [1, n]. Consequently, if the number of colors is at least (1 - )n2 + 253n,
^ c„(A) < 4(n2 - n) and Q) c*j(A) < 4(n2 - n)
for every row i and column j, which in turn provides the existence of a transversal according to Proposition 2.1.	□
Remark 2.3. Note that while the proof of Erdos and Spencer points out the existence of one frequently occurring symbol, the proof above reveals that in fact many symbols must occur frequently to avoid a transversal.
2.2 Using Konig's theorem
We start with a lemma on the structure of partial transversals, which is essentially the consequence of the greedy algorithm. The following easy observation is due to Stein [12].
Result 2.4. Consider r rows in a generalized Latin square A of order n. If n^1 > r, then there exists a partial transversal of order r in A covering the r rows in view.
We need the following consequence:
Lemma 2.5. Consider p rows and q columns in an n x n generalized Latin square. If q < P < (n + 1)/2, then either
Case (a) q < p/2 and there exists a partial transversal of size p covering the p rows and q columns, or
Case (b) q > p/2 and there exists a partial transversal of size |_p/2j + q covering the p rows and q columns.
J. Barat and Z. L. Nagy: Transversals in generalized Latin squares
43
Proof. Both parts follow from the fact that we can build a partial transversal by choosing first min{q, [p/2]} different symbols in the array formed by the intersection of the p rows and q columns, and then we can extend this greedily by entries in the uncovered rows and columns of the array (essentially using Result 2.4).	□
We proceed by recalling a variant of Konig's theorem, see Brualdi, Ryser [5].
Lemma 2.6. There exists an all-1 diagonal in a 0/1 square matrix of order n if and only if there does not exist an all-0 submatrix of size x x y, where x + y > n + 1.
Now we prove another upper bound on l(n).
Theorem 2.7. If a generalized Latin square of order n contains at least 0.75n2 symbols, then it has a transversal.
Proof. First notice that the statement holds for n = 1,2. We proceed by induction. Consider a generalized Latin square A of order n, which contains at least 0.75n2 symbols. A symbol is a singleton if it appears exactly once in A. We refer to the other symbols as repetitions. A submatrix is called a singleton-, resp. repetition-submatrix if every entry of the matrix is a singleton, resp. repetition.
Let p be the number of rows consisting only of repetitions and q be the number of columns consisting only of repetitions. We refer to these as full rows and columns, and assume that q < p. Notice that p < n/2, since the number of symbols is at least 0.75n2. Our aim is to choose a partial transversal that covers all full rows and columns, and then we complete this to a transversal by adding only singletons. First we apply Lemma 2.5 to get a partial transversal that covers the full rows and columns. Next, we omit the rows and columns that are covered by the chosen partial transversal. We obtain a generalized Latin square A' of order n - p in Case (a) or of order n - |_p/2j - q in Case (b). Now we are done by Lemma 2.6, if there are not too large repetition-submatrices in A'.
Suppose to the contrary that such a repetition-submatrix of size x x y exists in one of the cases, where x + y is larger than the order of A'. Note first that in either case, A' does not contain full rows and columns. Therefore, we can choose a singleton ai in A' such that at least x repetitions appear in its row. Similarly, we can choose a singleton a2 in A' such that at least y repetitions appear in its column.
Claim 2.8. There exists a singleton a such that the row of a or the column of a contains more than n/2 repetitions in the original Latin square A.
Proof. In Case (a) of Lemma 2.5: q < p/2. The number of repetitions in the row of a1 is at least q + x and number of repetitions in the column of a2 is at least p + y. Thus the statement holds since p + q + x + y>p + q +(n - p) > n.
In Case (b) of Lemma 2.5: q > p/2. The number of repetitions in the row of a1 is at least q + x and number of repetitions in the column of a2 is at least p + y. Thus the statement holds since p + q + x + y>p + q +(n -|_p/2j- q) > n.	□
In view of Claim 2.8, if we omit the row and column of the singleton a, we obtain a generalized Latin square B of order n - 1, which admits more than 0.75n2 - (2n - 1) + n/2 > 0.75(n - 1)2 symbols. By the induction hypothesis, there exists a transversal in B, hence it can be completed to a transversal of A by adding a.	□
44	Ars Math. Contemp. 16 (2019) 157-171
3 Discussion
At the time of submission, we learned that Best, Hendrey, Wanless, Wilson and Wood [3] achieved results similar to ours. As the best upper bound, they proved l(n) < (2 - i/2)n2.
Nevertheless, not only the conjecture of Akbari and Alipour remained open, but it is plausible that it can be strengthened in the order of magnitude as well. In fact, the bound 2n2 is intimately related to the number of singletons, which took a crucial part in both our proof and the proof in [3]. If the number of colors does not exceed 2n2, then there might be no singletons at all. However, our first probabilistic proof implies also that either there exists a transversal in a generalized Latin square of order n with Cn2 colors (C > 0.45), or the number of singletons is large. This fact points out that the constant 1/2 in Conjecture 1.2 is highly unlikely to be sharp. More precisely, we show the following
Proposition 3.1. If the number of singletons is less than (2C + 0.25 (| )3 — 1 + o(1))n2 in a generalized Latin square of order n with Cn? symbols, then there exists a transversal.
Proof. Suppose first that in every row and column, the sum c„(A) and c*¿ (A) are below 0.25 (4)3 (n2 — n). This in turn implies the existence of a transversal by Proposition 2.1. On the other hand, if for example c„(A) exceeds that bound, then consider only the symbols not appearing in row i, and let us denote by nk the number of symbols which occur exactly k times overall, with none of those occurrences being in row i. Clearly Efc nk = Cn2 — n and £k knk = (n(n — 1) — a,(A)) < (1 — 0.25 (4)3)(n2 — n). Consequently, for the number of singletons not appearing in the ith row,
ni > 2 ^ nk — ^ knk > (2C + 0.25 — 1 + o(1))n2, kk4
which makes this case impossible.	□
A special case, that appears as a bottleneck in some arguments concerns generalised Latin squares, where each repeated symbol has maximum multiplicity. We show that also in this special case, one can find a transversal.
Lemma 3.2. If A is a generalised Latin square of order n, where each symbol has multiplicity 1 or n (and both multiplicities occur), then A has a transversal.
Proof. We associate an edge-colored complete bipartite graph GA to A such that vertices on one side correspond to rows the other side to columns and the colors of the edges to the symbols. Our goal is to find a multicolored matching.
Notice that the Latin property implies that a symbol with multiplicity n corresponds to a perfect matching. Let us remove all edges corresponding to symbols with multiplicity n. If there are r such colors, then the remaining bipartite graph is (n — r)-regular. As an easy corollary of Hall's theorem, any regular bipartite graph contains a perfect matching. In our
case there are only singleton colors on the edges, so the perfect matching is multicolored.
□
It seems likely that if the number of colors is large, then we not only obtain one transversal, but also a set of disjoint transversals. This motivates the study of the following function.
J. Barat and Z. L. Nagy: Transversals in generalized Latin squares
45
Definition 3.3. Let I* (n) be the least integer satisfying I* (n) > n such that for any proper edge-coloring of Kn,n by at least 1*(n) colors, the colored graph can be decomposed into the disjoint union of n multicolored perfect matchings.
Conjecture 3.4. 1*(n) < n2/2 if n is large enough.
We remark that the difference of l(n) and l* (n) is at least linear in n if l(n) = n.
Proposition 3.5. 1*(n) — l(n) > n — 1.
Proof. Suppose first that there exists a transversal-free generalised Latin square of order n, i.e., l(n) > n.
For n < 2 the claim is straightforward. Suppose n > 3. By definition, there exists a transversal-free generalized Latin square A of order n with l(n) — 1 symbols. Since l(n) < 0.75n2, we can find a set S of n — 1 different repetitions, where n — 1 < 0.25n2. We assign new symbols to the entries of S to create a new generalized Latin square A' of the same order. Since S cannot cover n disjoint transversals, and there were no transversals disjoint to S, matrix A' cannot be decomposed to n transversals, but contains l(n) + n — 2 symbols. Now consider the case when l(n) = n, which implies that n must be odd. Take the cyclic Latin square of order n — 1 (which has no transversal, since n — 1 is even) and add one row and column of singletons. The resulting matrix has n—1+2n —1 = 3n—2 symbols in it. However, it cannot be decomposed into transversals because such a decomposition would need to include a transversal of the embedded cyclic group table.	□
Remark 3.6. Observe that the above result implies 1*(n) > 2n — 1 for all n. Notice that there are some orders n, for which l(n) = n, e.g. n € {1,3,7}, see also [3].
The question we studied concerning l(n) clearly has an anti-Ramsey flavor. The anti-Ramsey number AR(n, G) for a graph family G, introduced by Erdos, Simonovits and Sos [6], is the maximum number of colors in an edge coloring of Kn that has no multicolored (rainbow) copy of any graph in G. To emphasize this connection, we propose the following problem.
Problem 3.7. What is the least number of colors t(n, 2), which guarantees a rainbow 2-factor subgraph on at least n — 1 vertices in a properly edge-colored complete graph Kn colored by at least t(n, 2) colors?
Perhaps the size n — 1 of the 2-factor subgraph seems artificial in some sense at first, or at least it could be generalized to any given function f (n). We recall that for the function t(n, 1) corresponding to 1-factors, Woolbright and Fu provided the following related result. In Problem 3.7, we have to allow two values n — 1 and n to avoid parity issues.
Proposition 3.8 ([14]). Every properly colored K2n has a multicolored 1-factor if the number of colors is at least 2n — 1 and n > 2. That is, t(n, 1) = n — 1.
In another formulation, the necessary number of colors for a proper edge-coloring is already sufficient to guarantee a multicolored perfect matching. It might happen that it also forces a much larger structure as required in Problem 3.7. We propose the following
Conjecture 3.9. Any proper edge-coloring of K2n by at least 2n — 1 colors contains a multicolored 2-factor on 2n — 1 or 2n vertices.
46
ArsMath. Contemp. 16(2019)39-47
If the above conjecture fails, then possibly there are proper edge-colorings of Kn without multicolored 2-factors of size n or n -1. In that case, we can use a connection between t(n, 2) and l(n) to show a lower bound.
Proposition 3.10. l(n) > t(n, 2) + 1.
Proof. Consider an edge-coloring C of the complete graph Kn on vertex set V without multicolored 2-factors of size n or n - 1. We associate to C a coloring of the complete bipartite graph Kn n on partite classes U and W as follows: let us assign the color of ViVj e E(Kn) (i,j e [1, n]) to the edge uiWj e E(Kn,n) if i = j, and color the set of independent edges uiwi (i e [1,n]) by a separate color. Suppose that we found a multicolored 1-factor M in the complete bipartite graph. We omit at most one edge of M if we delete the edges uiwi and M' remains. Consider the edges vkvi in Kn, for which ukwl is contained in the multicolored M' of edges. This edge set is multicolored too, and each vertex has degree 2.	□
References
[1]	S. Akbari and A. Alipour, Transversals and multicolored matchings, J. Combin. Des. 12 (2004), 325-332, doi:10.1002/jcd.20014.
[2]	J. Barat and I. M. Wanless, Rainbow matchings and transversals, Australas. J. Combin. 59 (2014), 211-217, https://ajc.maths.uq.edu.au/pdf/5 9/ajc_v59_p211. pdf.
[3]	D. Best, K. Hendrey, I. M. Wanless, T. E. Wilson and D. R. Wood, Transversals in Latin arrays with many distinct symbols, J. Combin. Des. 26 (2018), 84-96, doi:10.1002/jcd.21566.
[4]	R. Bissacot, R. Fernandez, A. Procacci and B. Scoppola, An improvement of the Lovasz local lemma via cluster expansion, Combin. Probab. Comput. 20 (2011), 709-719, doi:10.1017/ s0963548311000253.
[5]	R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, volume 39 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1991, doi:10.1017/ cbo9781107325708.
[6]	P. Erd6s, M. Simonovits and V. T. S6s, Anti-Ramsey theorems, in: A. Hajnal, R. Rado and V. T. S6s (eds.), Infinite and Finite Sets, Volume II, North-Holland, Amsterdam, volume 10 of Col-loquia Mathematica Societatis Janos Bolyai, pp. 633-643, 1975, proceedings of a Colloquium held at Keszthely, June 25 - July 1, 1973, dedicated to Paul Erd6s on his 60th birthday.
[7]	P. Erd6s and J. Spencer, Lopsided Lovasz local lemma and Latin transversals, Discrete Appl. Math. 30 (1991), 151-154, doi:10.1016/0166-218x(91)90040-4.
[8]	S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: a survey, Graphs Combin. 26 (2010), 1-30, doi:10.1007/s00373-010-0891-3.
[9]	M. Kano and X. Li, Monochromatic and heterochromatic subgraphs in edge-colored graphs -a survey, Graphs Combin. 24 (2008), 237-263, doi:10.1007/s00373-008-0789-5.
[10]	C. F. Laywine and G. L. Mullen, Discrete Mathematics Using Latin Squares, volume 49 of Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1998.
[11]	A. D. Scott and A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovasz local lemma, J. Stat. Phys. 118 (2005), 1151-1261, doi:10.1007/s10955-004-2055-4.
[12]	S. K. Stein, Transversals of Latin squares and their generalizations, Pacific J. Math. 59 (1975), 567-575,http://projecteuclid.org/euclid.pjm/1102905365.
J. Barat and Z. L. Nagy: Transversals in generalized Latin squares
47
[13]	I. M. Wanless, Transversals in Latin squares: a survey, in: R. Chapman (ed.), Surveys in Combinatorics 2011, Cambridge University Press, Cambridge, volume 392 of London Mathematical Society Lecture Note Series, pp. 403-437, 2011, doi:10.1017/cbo9781139004114.010, papers from the 23rd British Combinatorial Conference held at the University of Exeter, Exeter, July 3-July 8, 2011.
[14]	D. E. Woolbright and H.-L. Fu, On the existence of rainbows in 1-factorizations of K2n, J. Combin. Des. 6 (1998), 1-20, doi:10.1002/(sici)1520-6610(1998)6:1(1::aid-jcd!)3.0.co;2-j.