Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A counterexample to Stein's Equi-$ n$-square Conjecture


Authors: Alexey Pokrovskiy and Benny Sudakov
Journal: Proc. Amer. Math. Soc. 147 (2019), 2281-2287
MSC (2010): Primary 05B15
DOI: https://doi.org/10.1090/proc/14220
Published electronically: March 1, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In 1975 Stein conjectured that in every $ n\times n$ 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-\frac {1}{42}\ln n$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05B15

Retrieve articles in all journals with MSC (2010): 05B15


Additional Information

Alexey Pokrovskiy
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland
Email: dr.alexey.pokrovskiy@gmail.com

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland
Email: benjamin.sudakov@math.ethz.ch

DOI: https://doi.org/10.1090/proc/14220
Received by editor(s): February 28, 2018
Received by editor(s) in revised form: May 9, 2018
Published electronically: March 1, 2019
Additional Notes: The research of the first author was supported in part by SNSF grant 200021-175573.
The research of the second author was supported in part by SNSF grant 200021-175573.
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2019 American Mathematical Society