A lower bound on the crossing number of uniform hypergraphs

DOI10.1016/J.DAM.2015.10.009zbMATH Open1339.05267arXiv1309.3625OpenAlexW1957208143MaRDI QIDQ298946FDOQ298946

Authors: Anurag Anshu, Saswata Shannigrahi 

Publication date: 21 June 2016

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

Abstract: In this paper, we consider the embedding of a complete $d$-uniform geometric hypergraph with $n$ vertices in general position in $mathbb{R}^d$, where each hyperedge is represented as a $(d-1)$-simplex, and a pair of hyperedges is defined to cross if they are vertex-disjoint and contains a common point in the relative interior of the simplices corresponding to them. As a corollary of the Van Kampen-Flores Theorem, it can be seen that such a hypergraph contains $Omega(frac{2}^{d}sqrtd)$ $nchoose2d$ crossing pairs of hyperedges. Using Gale Transform and Ham Sandwich Theorem, we improve this lower bound to $Omega(frac{2}^{d}logdsqrtd)$ $nchoose2d$.

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

Recommendations

• Rectilinear crossings in complete balanced \(d\)-partite \(d\)-uniform hypergraphs
• On the rectilinear crossing number of complete uniform hypergraphs
• \(k\)-sets and rectilinear crossings in complete uniform hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• Extremal problems for geometric hypergraphs

zbMATH Keywords

crossing simplicesGale transformgeometric hypergraphham sandwich theorem

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• The rectilinear crossing number of \(K_n\): closing in (or are we?)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• Title not available (Why is that?)
• Extremal problems for geometric hypergraphs
• Geometric drawings of \(K_{n}\) with few crossings

Cited In (5)

• Maximum rectilinear crossing number of uniform hypergraphs
• \(k\)-sets and rectilinear crossings in complete uniform hypergraphs
• Rectilinear crossings in complete balanced \(d\)-partite \(d\)-uniform hypergraphs
• On the rectilinear crossing number of complete uniform hypergraphs
• A new lower bound for the bipartite crossing number with applications

This page was built for publication: A lower bound on the crossing number of uniform hypergraphs

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