The Tuza–Vestergaard Theorem

Michael A. Henning; Christian Löwenstein; Anders Yeo

doi:10.1137/22M1475508

The Tuza–Vestergaard Theorem

Michael A. Henning^*, Christian Löwenstein, Anders Yeo

^*Kontaktforfatter

University of Johannesburg

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstract

The transversal number τ(H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then τ(H) ≤ 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture.

Originalsprog	Engelsk
Tidsskrift	SIAM Journal on Discrete Mathematics
Vol/bind	37
Udgave nummer	2
Sider (fra-til)	1275-1310
Antal sider	36
ISSN	0895-4801
DOI	https://doi.org/10.1137/22M1475508
Status	Udgivet - 2023

Bibliografisk note

Funding Information:
*Received by the editors December 2, 2022; accepted for publication (in revised form) February 14, 2023; published electronically June 22, 2023. https://doi.org/10.1137/22M1475508 Funding: The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Wu\"rttemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B. \dagger Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa ([email protected], [email protected]). \ddagger Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark ([email protected]).

Funding Information:
The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Württemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B.

Publisher Copyright:
Copyright © by SIAM.

Dokumenter og links

10.1137/22M1475508

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@article{e5aef5854e244695be301bed52e8a814,

title = "The Tuza–Vestergaard Theorem",

abstract = "The transversal number τ(H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then τ(H) ≤ 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture.",

keywords = "hypergraph, transversal",

author = "Henning, {Michael A.} and Christian L{\"o}wenstein and Anders Yeo",

note = "Funding Information: *Received by the editors December 2, 2022; accepted for publication (in revised form) February 14, 2023; published electronically June 22, 2023. https://doi.org/10.1137/22M1475508 Funding: The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Wu\{"}rttemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B. \dagger Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa ([email protected], [email protected]). \ddagger Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark ([email protected]). Funding Information: The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-W{\"u}rttemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B. Publisher Copyright: Copyright {\textcopyright} by SIAM.",

year = "2023",

doi = "10.1137/22M1475508",

language = "English",

volume = "37",

pages = "1275--1310",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics",

number = "2",

}

TY - JOUR

T1 - The Tuza–Vestergaard Theorem

AU - Henning, Michael A.

AU - Löwenstein, Christian

AU - Yeo, Anders

N1 - Funding Information: *Received by the editors December 2, 2022; accepted for publication (in revised form) February 14, 2023; published electronically June 22, 2023. https://doi.org/10.1137/22M1475508 Funding: The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Wu\"rttemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B. \dagger Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa ([email protected], [email protected]). \ddagger Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark ([email protected]). Funding Information: The research of the first author was supported in part by the University of Johannesburg and the South African National Research Foundation. The second author received financial support for this research project from the Baden-Württemberg Stiftung through the Eliteprogramme for Postdocs. The research of the third author is supported by the Danish research council under grant DFF-7014-00037B. Publisher Copyright: Copyright © by SIAM.

PY - 2023

Y1 - 2023

N2 - The transversal number τ(H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then τ(H) ≤ 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture.

AB - The transversal number τ(H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then τ(H) ≤ 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture.

KW - hypergraph

KW - transversal

U2 - 10.1137/22M1475508

DO - 10.1137/22M1475508

M3 - Journal article

AN - SCOPUS:85166005667

SN - 0895-4801

VL - 37

SP - 1275

EP - 1310

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

The Tuza–Vestergaard Theorem

Abstract

Bibliografisk note

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater