A note on finding large transversals efficiently
Anastos M, Morris P. 2025. A note on finding large transversals efficiently. Journal of Combinatorial Designs.
Download (ext.)
Journal Article
| Epub ahead of print
| English
Scopus indexed
Author
Anastos, MichaelISTA;
Morris, Patrick
Department
Grant
Abstract
In an n×n array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than βn times, the array contains a transversal of size (1−β/4−o(1))n . In particular, if the array is filled with n symbols, each appearing n times (an equi- n square), we get transversals of size (3/4−o(1))n. Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals.
Publishing Year
Date Published
2025-05-26
Journal Title
Journal of Combinatorial Designs
Publisher
Wiley
Acknowledgement
We are very grateful to Matthew Kwan and Alp Müyesser with whom we had many interesting discussions leading to the results of this note. We also thank the anonymous reviewers for their suggestions improving the presentation of this note.
MA was supported by the Austrian Science Fund (FWF) [10.55776/ESP3863424] and by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant—project number 101034413. PM was supported by the European Union's Horizon Europe Marie Skłodowska-Curie grant RAND-COMB-DESIGN—project number 101106032.
ISSN
eISSN
IST-REx-ID
Cite this
Anastos M, Morris P. A note on finding large transversals efficiently. Journal of Combinatorial Designs. 2025. doi:10.1002/jcd.21990
Anastos, M., & Morris, P. (2025). A note on finding large transversals efficiently. Journal of Combinatorial Designs. Wiley. https://doi.org/10.1002/jcd.21990
Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals Efficiently.” Journal of Combinatorial Designs. Wiley, 2025. https://doi.org/10.1002/jcd.21990.
M. Anastos and P. Morris, “A note on finding large transversals efficiently,” Journal of Combinatorial Designs. Wiley, 2025.
Anastos M, Morris P. 2025. A note on finding large transversals efficiently. Journal of Combinatorial Designs.
Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals Efficiently.” Journal of Combinatorial Designs, Wiley, 2025, doi:10.1002/jcd.21990.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2412.05891
Google Scholar