Empty Rectangles and Graph Dimension

Details Empty Rectangles and Graph Dimension Empty Rectangles and Graph Dimension

2006-01-31

arxiv.org/abs/math/0601767v1

Mathematics

Combinatorics

Scientific paper

We consider rectangle graphs whose edges are defined by pairs of points in diagonally opposite corners of empty axis-aligned rectangles. The maximum number of edges of such a graph on $n$ points is shown to be 1/4 n^2 +n -2. This number also has other interpretations: * It is the maximum number of edges of a graph of dimension $\bbetween{3}{4}$, i.e., of a graph with a realizer of the form $\pi_1,\pi_2,\ol{\pi_1},\ol{\pi_2}$. * It is the number of 1-faces in a special Scarf complex. The last of these interpretations allows to deduce the maximum number of empty axis-aligned rectangles spanned by 4-element subsets of a set of $n$ points. Moreover, it follows that the extremal point sets for the two problems coincide. We investigate the maximum number of of edges of a graph of dimension $\between{3}{4}$, i.e., of a graph with a realizer of the form $\pi_1,\pi_2,\pi_3,\ol{\pi_3}$. This maximum is shown to be $1/4 n^2 + O(n)$. Box graphs are defined as the 3-dimensional analog of rectangle graphs. The maximum number of edges of such a graph on $n$ points is shown to be $7/16 n^2 + o(n^2)$.

Affiliated with

Also associated with

No associations

Rating

Empty Rectangles and Graph Dimension does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Empty Rectangles and Graph Dimension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Empty Rectangles and Graph Dimension will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-353880