Intersection graphs for families of balls in \(R^n\) (Q1112070): Difference between revisions

Let \(B(x,r)\) denote a ball, (either open or closed) of radius \(r>0\) and center x, in the Euclidean space \({\mathbb{R}}^n\). Let \(\mu[A]\) be the \(n\)-dimensional Lebesgue volume of the subset \(A\) of \({\mathbb{R}}^n\) and let \(\epsilon\) denote a real number in \((0,1]\). A pair of balls \(B, B'\) are said to be \(\epsilon\)-disjoint if \(\mu(B\cap B')\leq (1-\epsilon)\min \{\mu(B),\mu(B')\}.\) A family \(F\) of balls is \(\epsilon\)-disjoint, if the balls are pairwise \(\epsilon\)-disjoint. Denote by \(\Gamma_{n,\epsilon}\) the set of all intersection graphs \(\Gamma(F)\) for \(\epsilon\)-disjoint families \(F\) of balls in \({\mathbb{R}}^n\). The authors show that there exists a least integer \(d=d(n,\epsilon)\) such that every graph in \(\Gamma_{n,\epsilon}\) has a vertex of degree at most d and also show that there exists a least integer \(m=m(n)\) such that every intersection graph \(\Gamma(F)\), where \(F\) is a family of balls, has a vertex \(v\) such that the subgraph induced by the vertices adjacent to \(v\) contains no independent set of size greater than \(m\).