Lower bounds on the size of maximum independent sets and matchings in hypergraphs of rank three

Michael A. Henning*, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let α(H) and α′(H) be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that α(H)≥|V(H)|/7 with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then α(H)≥(3|V(H)|-1)/17 and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3-uniform hypergraph of order at least 8 and with maximum degree at most three, then α′(H)≥3|E(H)|/17 and there is a connected 3-uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on 2Δ(H)+1 vertices, where Δ(H) denotes the maximum degree in H, then α(H)≥|V(H)|/2Δ(H) and this bound is asymptotically best possible.

OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
Vol/bind72
Udgave nummer2
Sider (fra-til)220-245
Antal sider26
ISSN0364-9024
DOI
StatusUdgivet - jan. 2013
Udgivet eksterntJa

Fingeraftryk

Dyk ned i forskningsemnerne om 'Lower bounds on the size of maximum independent sets and matchings in hypergraphs of rank three'. Sammen danner de et unikt fingeraftryk.

Citationsformater