Nordhaus-Gaddum-type problems for lines in hypergraphs

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

Authors: Xiaomin Chen, Peihan Miao 

Publication date: 7 December 2015

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

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.

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

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

zbMATH Keywords

finite metric spacelines in graphslines in hypergraphs

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65)

Cites Work

• Graph theory
• On sets defining few ordinary lines
• A survey of Nordhaus-Gaddum type relations
• On Complementary Graphs
• Graph metric with no proper inclusion between lines
• Number of lines in hypergraphs
• 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)