Separating pairs of points of standard boxes. (English) Zbl 0592.05002

Authors’ summary: ”Let A be a set of distinct points in \({\mathbb{R}}^ d\). A 2-subset \(\{a,b\}\) of A is called separated if there exists a closed box with sides parallel to the axes, containing a and b but no other points of A. Let s(A) denote the number of separated 2-sets of A and put \(f(n,d)=\max \{s(A): A\subset {\mathbb{R}}^ d\), \(| A| =n\}\). We show that \(f(n,2)=[n^ 2/4]+n-2\) for all \(n\geq 2\) and that for each fixed dimension d \[ f(n,d) = (1-1/2^{2^{d-1}-1})\cdot n^ 2/2+o(n^ 2).'' \]
Reviewer: J.Carter


05A05 Permutations, words, matrices
05C99 Graph theory
Full Text: DOI


[1] I. Bárány, J. Lehel: Covering with Euclidean boxes, preprint.
[2] Bollobás, B., Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[3] Bollobás, B.; Erdös, P.; Straus, E.G., Complete subgraphs of chromatic graphs and hypergraphs, Utilitas math., 6, 343-347, (1974) · Zbl 0333.05116
[4] Erdös, P.; Stone, A.H., On the structure of linear graphs, Bull. amer. math. soc., 52, 1087-1091, (1946) · Zbl 0063.01277
[5] Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio math., 2, 463-470, (1935) · Zbl 0012.27010
[6] Gallai, T., On directed paths and circuits, (), 115-118 · Zbl 0159.54403
[7] Kruskal, J.B., Monotone subsequences, Proc. amer. math. soc., 4, 264-274, (1953) · Zbl 0052.04901
[8] Roy, B., Nombre chromatique et plus longs chemins d’un graphe, Revue AFIRO, 1, 127-132, (1967) · Zbl 0157.31302
[9] Cochand, M.; Duchet, P., Sons LES pavés, Annals discrete math., 17, 191-202, (1983) · Zbl 0522.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.