Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.05891 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913601120370688 |
|---|---|
| author | Anastos, Michael Morris, Patrick |
| author_facet | Anastos, Michael Morris, Patrick |
| contents | In an $n \times 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_05891 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on finding large transversals efficiently Anastos, Michael Morris, Patrick Combinatorics In an $n \times 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. |
| title | A note on finding large transversals efficiently |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.05891 |