2024/12/08 by Michael Anastos, Patrick Morris, Anastos, Michael +1 · 1 citation
Engineering · #Advanced Wireless Communication Techniques #Antenna Design and Optimization #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2412.05891
openalex publication_date 2024/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.