Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.05339 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910999768989696 |
|---|---|
| author | Clow, Alexander Haxell, Penny Mohar, Bojan |
| author_facet | Clow, Alexander Haxell, Penny Mohar, Bojan |
| contents | In 1975 Lovász conjectured that every $r$-partite, $r$-uniform hypergraph contains $r-1$ vertices whose deletion reduces the matching number. If true, this statement would imply a well-known conjecture of Ryser from 1971, which states that every $r$-partite, $r$-uniform hypergraph has a vertex cover of size at most $r-1$ times its matching number. When $r=2$, Ryser's conjecture is simply Kőnig's theorem, and the conjecture of Lovász is an immediate corollary. Ryser's conjecture for $r=3$ was proven by Aharoni in 2001, and remains open for all $r\geq 4$.
Here we show that the conjecture of Lovász is false in the case $r=3$. Our counterexample is the line hypergraph of the Biggs-Smith graph, a highly symmetric cubic graph on 102 vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05339 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Counterexample to a Conjecture of Lovász Clow, Alexander Haxell, Penny Mohar, Bojan Combinatorics 05C65, 05C70, 05C69 In 1975 Lovász conjectured that every $r$-partite, $r$-uniform hypergraph contains $r-1$ vertices whose deletion reduces the matching number. If true, this statement would imply a well-known conjecture of Ryser from 1971, which states that every $r$-partite, $r$-uniform hypergraph has a vertex cover of size at most $r-1$ times its matching number. When $r=2$, Ryser's conjecture is simply Kőnig's theorem, and the conjecture of Lovász is an immediate corollary. Ryser's conjecture for $r=3$ was proven by Aharoni in 2001, and remains open for all $r\geq 4$. Here we show that the conjecture of Lovász is false in the case $r=3$. Our counterexample is the line hypergraph of the Biggs-Smith graph, a highly symmetric cubic graph on 102 vertices. |
| title | A Counterexample to a Conjecture of Lovász |
| topic | Combinatorics 05C65, 05C70, 05C69 |
| url | https://arxiv.org/abs/2505.05339 |