Maximum rectilinear crossing number of uniform hypergraphs

DOI10.1007/S00373-023-02711-2MaRDI QIDQ6083186zbMATH OpenOpenAlexFDO

Authors Rahul Gangopadhyay, Ayan

Publication date 31 October 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

\(d\)-partite \(d\)-uniform hypergraphscomplete uniform hypergraphsgale transformneighborly polytopeorder typerectilinear crossing number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We improve the lower bound on the $d$-dimensional rectilinear crossing number of the complete $d$-uniform hypergraph having $2d$ vertices to $Omega(2^{d}d)$ from $Omega(2^{d}sqrtd)$. We also establish that $3$-dimensional rectilinear crossing number of a complete $3$-uniform hypergraph having $ngeq9$ vertices is at least $dfrac4342dbinomn6$. Anshu et al. conjectured that among all $d$-dimensional convex drawings of a complete $d$-uniform hypergraph having $n$ vertices, the number of crossing pairs of hyperedges is maximized if all its vertices are placed on the $d$-dimensional moment curve and proved this conjecture for $d=3$. It is trivially true for $d=2$, since any convex drawing of the complete graph $K_n$ produces $nchoose4$ pairs of crossing edges. We prove that their conjecture is true for $d=4$ by using Gale transform. In fact, we prove a stronger statement. We prove that among all $4$-dimensional rectilinear drawings of a complete $4$-uniform hypergraph having $n$ vertices, the number of crossing pairs of hyperedges is maximized if all its vertices are placed on the $4$-dimensional moment curve. We also prove that the maximum $d$-dimensional rectilinear crossing number of a complete $d$-partite $d$-uniform balanced hypergraph is $(2^{d-1}-1){nchoose2}^d$, where $n$ denotes the number of vertices in each part. We then prove that finding the maximum $d$-dimensional rectilinear crossing number of an arbitrary $d$-uniform hypergraph is NP-hard and give a randomized scheme to create a $d$-dimensional rectilinear drawing of a $d$-uniform hypergraph $H$ producing the number of crossing pairs of hyperedges up to a constant factor of the maximum $d$-dimensional rectilinear crossing number of $H$.

Recommendations

• On the rectilinear crossing number of complete uniform hypergraphs
• \(k\)-sets and rectilinear crossings in complete uniform hypergraphs
• Rectilinear crossings in complete balanced \(d\)-partite \(d\)-uniform hypergraphs
• A lower bound on the crossing number of uniform hypergraphs
• The maximum rectilinear crossing number of the n dimensional cube graph

Cites work

• \(k\)-sets and rectilinear crossings in complete uniform hypergraphs
• A continuous analogue of the upper bound theorem
• A generalization of Caratheodory's theorem
• A lower bound on the crossing number of uniform hypergraphs
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• Approximating the maximum rectilinear crossing number
• Convex Polytopes
• Enumerating order types for small point sets with applications
• Extremal problems for geometric hypergraphs
• scientific article; zbMATH DE number 3121295 (Why is no real title available?)
• scientific article; zbMATH DE number 4214050 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3258069 (Why is no real title available?)
• scientific article; zbMATH DE number 3394160 (Why is no real title available?)
• Lectures on Polytopes
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• On the Maximum Crossing Number
• On the obfuscation complexity of planar graphs
• On the rectilinear crossing number of complete uniform hypergraphs
• Primitive Radon partitions for cyclic polytopes
• Rectilinear crossings in complete balanced \(d\)-partite \(d\)-uniform hypergraphs
• Some Erdős-Szekeres type results about points in space
• The graph crossing number and its variants: a survey
• The maximum numbers of faces of a convex polytope
• The rectilinear crossing number of K_n: closing in (or are we?)
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)

Cited in

(4)

• The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\)
• scientific article; zbMATH DE number 6000731 (Why is no real title available?)
• scientific article; zbMATH DE number 1839818 (Why is no real title available?)
• scientific article; zbMATH DE number 7084983 (Why is no real title available?)

This page was built for publication: Maximum rectilinear crossing number of uniform hypergraphs

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