Extremal Results on Intersection Graphs of Boxes in {\mathbb R}^d R d

DOI10.1007/978-3-319-28186-5_11MaRDI QIDQ5354940zbMATH OpenOpenAlexFDO

Authors Álvaro Martínez-Pérez, Deborah Oliveros, L. Montejano

Publication date 6 September 2017

Published in Convexity and Discrete Geometry Including Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

extremal graphfractional Hellyintersection graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: The main purpose of this paper is to study extremal results on the intersection graphs of boxes in $R^d$. We calculate exactly the maximal number of intersecting pairs in a family $F$ of $n$ boxes in $R^d$ with the property that no $k+1$ boxes in $F$ have a point in common. This allows us to improve the known bounds for the fractional Helly theorem for boxes. We also use the Fox-Gromov-Lafforgue-Naor-Pach results to derive a fractional ErdH{o}s-Stone theorem for semi-algebraic graphs in order to obtain a second proof of the fractional Helly theorem for boxes.

Recommendations

• Turán-type results for intersection graphs of boxes
• Intersection properties of boxes. II: Extremal families
• Grid intersection graphs and boxicity
• Intersection properties of boxes. I: An upper-bound theorem
• Sur la dimension de boîte des graphes
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
• On a conjecture regarding the upper graph box dimension of bounded subsets of the real line
• A characterization of intersection graphs of the maximal rectangles of a polyomino
• Boxicity of graphs with bounded degree

Cited in

(6)

• Intersection properties of boxes. I: An upper-bound theorem
• Intersection properties of boxes. II: Extremal families
• Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
• A fractional Helly theorem for boxes
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Turán-type results for intersection graphs of boxes

This page was built for publication: Extremal Results on Intersection Graphs of Boxes in $${\mathbb R}^d$$ R d

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