Research project is (co) funded by the Slovenian Research Agency.
UL Member: Faculty of Mathematics and Physics
Code: N1-0355
Project: Matchings, transversals, and hypergraphs
Period: 1. 8. 2024 - 31. 7. 2027
Range per year: 0,67 FTE, category: B
Head: Csilla Bujtás
Research activity: Natural sciences and mathematics
Research Organisations, Researchers and Citations for bibliographic records
Project description:
Hypergraphs are set systems over an underlying vertex set. The central topics of this proposal are minimum transversals and maximum matchings in a hypergraph H. A transversal is a vertex set intersecting every edge of H, while a matching is a set of vertex-disjoint edges. A hypergraph H is k-uniform if each edge contains k vertices. The first part of the project focuses on finding upper bounds on the transversal number of a k-uniform hypergraph, mainly in terms of its order and size, while the second part concentrates on the interplay between the transversal and matching numbers of uniform hypergraphs. The specific goals of the project are the following:
(O-1) Upper bounds on the transversal numbers of k-uniform hypergraphs.
For each k >1, finding a minimum transversal is an NP-hard problem over the class of k-uniform hypergraphs. Consequently, establishing upper bounds on the transversal number τ(H) and designing polynomial-time algorithms that output sufficiently small transversals impact practical and theoretical problems. We will focus on the upper bounds written in the form of τ(H)≤c_k (n+m) where c_k is a constant, and H is a k-uniform hypergraph with n vertices and m edges. The tight values of the constant c_k was proved for k=2, 3, and 4 around 1990. Although the attempts to determine the sharp values for k=5 and 6 continued in the last three decades, we still do not have tight results for any k with k >4. The first objective of the proposed project is to improve the existing results concerning upper bounds on the transversal numbers of k-uniform hypergraphs.
(O-2) Upper bounds on the transversal numbers of k-uniform hypergraphs under specific conditions.
While objective (O-1) asks for upper bounds over the entire class of k-uniform hypergraphs, several intriguing questions and conjectures relate to the upper bounds when only hypergraphs with specific properties are considered. The most important subclasses we plan to investigate are hypergraphs with equal order and size, linear hypergraphs, open and closed neighborhood hypergraphs of graphs. This objective also relates to the Thomassé-Yeo Conjecture, which predicts that τ(H)≤4n/11 holds for every 5-uniform hypergraph H with n vertices and n edges.
(O-3) Upper bounds on the ratio of the transversal and matching numbers of triangle hypergraphs.
This objective is related to Tuza’s 42-year-old conjecture, which is listed among the 100 most important conjectures on graph theoretical problems in the classical book of Bondy and Murty. Although it concerns simple graphs, the problem can be modeled by comparing the matching and transversal numbers of (specific) 3-uniform hypergraphs. The mentioned ratio τ(H)/ν(H) is conjectured to be at most 2, while the best established upper bound is 66/23. Concerning Tuza’s Conjecture, the situation with K_4-free graphs are special. There is no known example with τ(H)=2ν(H). However, a probabilistic approach shows that for every positive ϵ, there exists a K_4-free graph G such that the corresponding triangle hypergraph H satisfies τ(H)>(2-ϵ) ν(H). In the planned research, we will concentrate on triangle hypergraphs obtained from K_4-free graphs and improve the upper bound 66/23.
(O-4) Characterization of 3-uniform hypergraphs that satisfy τ(H)=3ν(H).
Each k-uniform hypergraph H satisfies τ(H)≤kν(H), and sharp examples are also known for every k≥2. However, the characterization of the extremal hypergraphs is still unknown if k>2. We aim to fill this gap for k=3 to better understand maximum matchings in hypergraphs in general.
