Empty Rectangles and Graph Dimension
| dc.creator | Felsner, Stefan | |
| dc.date | 2006-01-31 | |
| dc.date.accessioned | 2026-07-07T06:59:32Z | |
| dc.date.available | 2026-07-07T06:59:32Z | |
| dc.description | 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 $π_1,π_2,\ol{π_1},\ol{π_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 $π_1,π_2,π_3,\ol{π_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)$. | |
| dc.identifier | https://arxiv.org/abs/math/0601767 | |
| dc.identifier | http://arxiv.org/abs/math/0601767 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/107779 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C10; 68R10; 06A07 | |
| dc.title | Empty Rectangles and Graph Dimension | |
| dc.type | text |