Nordhaus-Gaddum-type problems for lines in hypergraphs

DOI10.1016/J.DAM.2015.06.016zbMATH Open1327.05250OpenAlexW1486041051MaRDI QIDQ897617FDOQ897617

Authors Xiaomin Chen, Peihan Miao 

Publication date 7 December 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.0474

zbMATH Keywords

finite metric spacelines in graphslines in hypergraphs

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65)

Abstract: We study the number of lines in hypergraphs in a more symmetric setting, where both the hypergraph and its complement are considered. In the general case and in some special cases, the lower bounds on the number of lines are much higher than their counterparts in single hypergraph setting or admit more elegant proofs. We show that the minimum value of product of the number of lines in both hypergraphs on $n$ points is easily determined as $$; and the minimum value of their sum is between $Omega(n)$ and $O(nlogn)$. We also study some restricted classes of hypergraphs; and determine the tight bounds on the minimum sum when the hypergraph is derived from an Euclidean space, a real projective plane, or a tree.

Recommendations

• Number of lines in hypergraphs
• Lines in hypergraphs
• On the number of hyperedges in the hypergraph of lines and pseudo-discs
• scientific article; zbMATH DE number 969103
• Line hypergraphs

Cites work

• A survey of Nordhaus-Gaddum type relations
• Graph metric with no proper inclusion between lines
• Graph theory
• Number of lines in hypergraphs
• On Complementary Graphs
• On sets defining few ordinary lines
• Problems related to a de Bruijn-Erdös theorem
• The orchard problem

Cited in

(2)

• On the number of hyperedges in the hypergraph of lines and pseudo-discs
• Number of lines in hypergraphs

This page was built for publication: Nordhaus-Gaddum-type problems for lines in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897617)