A note on fractional disjoint transversals in hypergraphs

作者：Henning Michael A^*; Yeo Anders

来源：Discrete Mathematics, 2017, 340(10): 2349-2354.

DOI：10.1016/j.disc.2017.05.001

• Transversal
• Hypergraph
• 3SAT

A transversal in a hypergraph H is a subset of vertices that has a nonempty intersection with every edge of H. A transversal family F of H is a family of (not necessarily distinct) transversals of H. The effective transversal-ratio of the family F is the ratio of the number of sets in over the maximum times r(F) any element appears in The fractional disjoint transversal number FDT(H) is the supremum of the effective transversal-ratio taken over all transversal families. That is, FDT(H) = sup(F)vertical bar F vertical bar/r(F). Using a connection with not-all-equal 3-SAT, we prove that if H is a 3-regular 3-uniform hypergraph, then FDT(H) >= 2, which proves a known conjecture. Using probabilistic arguments, we prove that for all k >= 3, if H is a k-regular k-uniform hypergraph, then FDT(H) >= 1/(1 - (k-1/k))(1/k)(1/k-1)), and that this bound is essentially best possible.

• 出版日期2017-10