---
OA_place: repository
OA_type: green
_id: '19798'
abstract:
- lang: eng
  text: 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.
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.\r\n\r\nMA 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."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
- first_name: Patrick
  full_name: Morris, Patrick
  last_name: Morris
citation:
  ama: Anastos M, Morris P. A note on finding large transversals efficiently. <i>Journal
    of Combinatorial Designs</i>. 2025;33(9):338-342. doi:<a href="https://doi.org/10.1002/jcd.21990">10.1002/jcd.21990</a>
  apa: Anastos, M., &#38; Morris, P. (2025). A note on finding large transversals
    efficiently. <i>Journal of Combinatorial Designs</i>. Wiley. <a href="https://doi.org/10.1002/jcd.21990">https://doi.org/10.1002/jcd.21990</a>
  chicago: Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals
    Efficiently.” <i>Journal of Combinatorial Designs</i>. Wiley, 2025. <a href="https://doi.org/10.1002/jcd.21990">https://doi.org/10.1002/jcd.21990</a>.
  ieee: M. Anastos and P. Morris, “A note on finding large transversals efficiently,”
    <i>Journal of Combinatorial Designs</i>, vol. 33, no. 9. Wiley, pp. 338–342, 2025.
  ista: Anastos M, Morris P. 2025. A note on finding large transversals efficiently.
    Journal of Combinatorial Designs. 33(9), 338–342.
  mla: Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals
    Efficiently.” <i>Journal of Combinatorial Designs</i>, vol. 33, no. 9, Wiley,
    2025, pp. 338–42, doi:<a href="https://doi.org/10.1002/jcd.21990">10.1002/jcd.21990</a>.
  short: M. Anastos, P. Morris, Journal of Combinatorial Designs 33 (2025) 338–342.
date_created: 2025-06-08T22:01:23Z
date_published: 2025-09-01T00:00:00Z
date_updated: 2025-12-30T08:37:37Z
day: '01'
department:
- _id: MaKw
doi: 10.1002/jcd.21990
ec_funded: 1
external_id:
  arxiv:
  - '2412.05891'
  isi:
  - '001495472300001'
intvolume: '        33'
isi: 1
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2412.05891
month: '09'
oa: 1
oa_version: Preprint
page: 338-342
project:
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
  grant_number: ESP3863424
  name: Combinatorial Optimisation Problems on Sparse Random Graphs
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Journal of Combinatorial Designs
publication_identifier:
  eissn:
  - 1520-6610
  issn:
  - 1063-8539
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: A note on finding large transversals efficiently
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2025'
...