Transversals in generalized Latin squares

DOI10.26493/1855-3974.1316.2D2MaRDI QIDQ5225021zbMATH OpenOpenAlexWikidataFDO

Authors János Barát, Zoltán Lóránt Nagy

Publication date 25 July 2019

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.08220

zbMATH Keywords

anti-Ramsey problemsLatin squaresLovász local lemmatransversals

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15) Combinatorial probability (60C05)

Abstract: 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 $K_{n,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 $K_{n,n}$, which contains at least $l(n)$ different colors, admits a multicolored perfect matching. They conjectured that $l(n)leq{n}^2/2$ if $n$ is large enough. In this note we prove that $l(n)$ is bounded from above by $0.75n^2$ 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 $K_{2n}$ admits a multicolored $1$-factor.

Recommendations

• Transversals and multicolored matchings
• Decompositions into spanning rainbow structures
• Rainbow matchings and cycle-free partial transversals of Latin squares
• New bounds for Ryser’s conjecture and related problems
• Transversals in Latin Squares

Cites work

• An improvement of the Lovász local lemma via cluster expansion
• Combinatorial matrix theory
• scientific article; zbMATH DE number 3494450 (Why is no real title available?)
• scientific article; zbMATH DE number 1229733 (Why is no real title available?)
• scientific article; zbMATH DE number 1455120 (Why is no real title available?)
• Lopsided Lovász Local lemma and Latin transversals
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Rainbow generalizations of Ramsey theory: A survey
• Rainbow matchings and transversals
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Transversals and multicolored matchings
• Transversals in Latin arrays with many distinct symbols
• Transversals in Latin squares: a survey
• Transversals of latin squares and their generalizations

Cited in

(11)

• Transitive edge coloring of graphs and dimension of lattices
• Edge colorings of \(K_{2n}\) with a prescribed condition. I
• Parity of transversals of Latin squares
• Latin squares with maximal partial transversals of many lengths
• Covers and partial transversals of Latin squares
• Transversals and multicolored matchings
• On the number of symbols that forces a transversal
• New bounds for Ryser’s conjecture and related problems
• On the chromatic index of Latin squares
• A generalization of transversals for Latin squares
• Hamilton transversals in random Latin squares

This page was built for publication: Transversals in generalized Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5225021)