A counterexample to Stein's equi-n-square conjecture

DOI10.1090/PROC/14220MaRDI QIDQ5377048zbMATH OpenOpenAlexWikidataFDO

Authors Alexey Pokrovskiy, Benny Sudakov

Publication date 23 May 2019

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Transversal (matching) theory (05D15)

Abstract: In 1975 Stein conjectured that in every $nimesn$ array filled with the numbers $1,dots,n$ with every number occuring exactly $n$ times, there is a partial transversal of size $n-1$. In this note we show that this conjecture is false by constructing such arrays without partial transverals of size $n-frac142lnn$.

Recommendations

• Research problem 40
• Has Every Latin Square of Order n a Partial Latin Transversal of Size n - 1?
• Transversals in rectangular arrays
• On a conjecture of Stein
• New bounds for Ryser’s conjecture and related problems

Cites work

• Combinatorial Matrix Theory
• Covering with Latin transversals
• Decompositions into spanning rainbow structures
• Fair representation by independent sets
• scientific article; zbMATH DE number 6473829 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Lopsided Lovász Local lemma and Latin transversals
• Multipartite hypergraphs achieving equality in Ryser's conjecture
• On a conjecture of Stein
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Research problem 40
• Transversals of latin squares and their generalizations

Cited in

(12)

• A counter-example to a conjecture relating complete sets of frequency squares and affine geometries
• Balanced equi-n-squares
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Has Every Latin Square of Order n a Partial Latin Transversal of Size n - 1?
• New bounds for Ryser’s conjecture and related problems
• Rainbow structures in locally bounded colorings of graphs
• Repeated patterns in proper colorings
• Almost fair perfect matchings in complete bipartite graphs
• Bounded degree graphs and hypergraphs with no full rainbow matchings
• A note on finding large transversals efficiently
• Every Latin hypercube of order 5 has transversals
• Graph theory. Abstracts from the workshop held January 6--12, 2019

This page was built for publication: A counterexample to Stein's equi-\(n\)-square conjecture

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