On simplices in diameter graphs in ℝ4

Agraph G is a diameter graph in ?^d if its vertex set is a finite subset in ?^d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in ?⁴ contains the complete subgraph K on five vertices, then any triangle in G shares a vertex with K. The geometric interpretation of this statement is as follows. Given any regular unit simplex on five vertices and any regular unit triangle in ?⁴, then either the simplex and the triangle have a common vertex or the diameter of the union of their vertex sets is strictly greater than 1.

     

On Polygons Excluding Point Sets

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that ${B\cup R}$ is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k ≥ K. Some other related problems are also considered.     

Distances realized by sets covering the plane

A proof is given of the (known) result that, if real n-dimensional Euclidean space Rⁿ is covered by any n + 1 sets, then at least one of these sets is such that each distance d(0 < d < ∞) is realized as the distance between two points of the set. In particular, this result holds if the plane is covered by three sets; but it does not necessarily hold if the plane is covered by six sets. If each set in a covering of the plane fails to realize the same distance d, say d = 1, and if the sets are either closed or simultaneously divisible into region (in a sense to be made precise), then at least six sets are needed and seven suffice, and the number of closed sets needed is at least as great as the number simultaneously divisible into regions.     

Subspace intersection graphs

Given a set R of affine subspaces in R^d of dimension e, its intersection graph G has a vertex for each subspace, and two vertices are adjacent in G if and only if their corresponding subspaces intersect. For each pair of positive integers d and e we obtain the class of (d,e)-subspace intersection graphs. We classify the classes of (d,e)-subspace intersection graphs by containment, for e=1 or e=d−1 or d≤4.     

A New Lower Bound Based on Gromov’s Method of Selecting Heavily Covered Points

Boros and Füredi (for d=2) and Bárány (for arbitrary d) proved that there exists a positive real number c _d such that for every set P of n points in R ^d in general position, there exists a point of R ^d contained in at least $c_{d}\binom{n}{d+1}$ d-simplices with vertices at the points of P. Gromov improved the known lower bound on c _d by topological means. Using methods from extremal combinatorics, we improve one of the quantities appearing in Gromov??s approach and thereby provide a new stronger lower bound on c _d for arbitrary d. In particular, we improve the lower bound on c ₃ from 0.06332 to more than 0.07480; the best upper bound known on c ₃ being 0.09375.     

Disjoint independent dominating sets in graphs

A set X of vertices of G is an independent dominating set if no two vertices of X are adjacent and each vertex not in X is adjacent to at least one vertex in X. Independent dominating sets of G are cliques of the complement $\text{G}$ of G and conversely.This work is concerned with the existence of disjoint independent dominating sets in a graph G. A new parameter, the maximum number of disjoint independent dominating sets in G, is studied and the class of graphs whose vertex sets partition into independent dominating sets is investigated.     

AnR danalogue of Valentine’s theorem on 3-convex sets

This paper deals with anR ^danalogue of a theorem of Valentine which states that a closed 3-convex setS in the plane is decomposable into 3 or fewer closed convex sets. In Valentine’s proof, the points of local nonconvexity ofS are treated as vertices of a polygonP contained in the kernel ofS, yielding a decomposition ofS into 2 or 3 convex sets, depending on whetherP has an even or odd number of edges. Thus the decomposition actually depends onc(P′), the chromatic number of the polytopeP′ dual toP. A natural analogue of this result is the following theorem: LetS be a closed subset ofR ^d, and letQ denote the set of points of local nonconvexity ofS. We require thatQ be contained in the kernel ofS and thatQ coincide with the set of points in the union of all the (d − 2)-dimensional faces of somed-dimensional polytopeP. ThenS is decomposable intoc(P′) closed convex sets.     

Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations

We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with p ∈ R² and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R²: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.     

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

On directional convexity

Motivated by problems from calculus of variations and partial differential equations, we investigate geometric properties of D-convexity. A function f: R ^d → R is called D-convex, where D is a set of vectors in R ^d, if its restriction to each line parallel to a nonzero v ∈ D is convex. The D-convex hull of a compact set A ⊂ R ^d, denoted by co^D(A), is the intersection of the zero sets of all nonnegative D-convex functions that are zero on A. It also equals the zero set of the D-convex envelope of the distance function of A. We give an example of an n-point set A ⊂ R ² where the D-convex envelope of the distance function is exponentially close to zero at points lying relatively far from co ^D(A), showing that the definition of the D-convex hull can be very nonrobust. For separate convexity in R ³ (where D is the orthonormal basis of R ³), we construct arbitrarily large finite sets A with co ^D(A) ≠ A whose proper subsets are all equal to their D-convex hull. This implies the existence of analogous sets for rank-one convexity and for quasiconvexity on 3 × 3 (or larger) matrices. This research was supported by Charles University Grants No. 158/99 and 159/99.     

Transitive sets in Euclidean Ramsey theory

A finite set X in some Euclidean space Rn is called Ramsey if for any k there is a d such that whenever Rd is k-coloured it contains a monochromatic set congruent to X. This notion was introduced by Erd?s, Graham, Montgomery, Rothschild, Spencer and Straus, who asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. This question (made into a conjecture by Graham) has dominated subsequent work in Euclidean Ramsey theory.In this paper we introduce a new conjecture regarding which sets are Ramsey; this is the first ever ‘rival’ conjecture to the conjecture above. Calling a finite set transitive if its symmetry group acts transitively—in other words, if all points of the set look the same—our conjecture is that the Ramsey sets are precisely the transitive sets, together with their subsets. One appealing feature of this conjecture is that it reduces (in one direction) to a purely combinatorial statement. We give this statement as well as several other related conjectures. We also prove the first non-trivial cases of the statement.Curiously, it is far from obvious that our new conjecture is genuinely different from the old. We show that they are indeed different by proving that not every spherical set embeds in a transitive set. This result may be of independent interest.     

Polynomial Interpolation on the Unit Sphere and on the Unit Ball

The problem of interpolation on the unit sphere S ^d by spherical polynomials of degree at most n is shown to be related to the interpolation on the unit ball B ^d by polynomials of degree n. As a consequence several explicit sets of points on S ^d are given for which the interpolation by spherical polynomials has a unique solution. We also discuss interpolation on the unit disc of R ² for which points are located on the circles and each circle has an even number of points. The problem is shown to be related to interpolation on the triangle in a natural way.     

Empty Monochromatic Simplices

Let S be a k-colored (finite) set of n points in $\mathbb{R}^{d}$ , d≥3, in general position, that is, no (d+1) points of S lie in a common (d?1)-dimensional hyperplane. We count the number of empty monochromatic d-simplices determined by S, that is, simplices which have only points from one color class of S as vertices and no points of S in their interior. For 3≤k≤d we provide a lower bound of $\varOmega(n^{d-k+1+2^{-d}})$ and strengthen this to Ω(n ^d?2/3) for k=2. On the way we provide various results on triangulations of point sets in  $\mathbb{R}^{d}$ . In particular, for any constant dimension d≥3, we prove that every set of n points (n sufficiently large), in general position in $\mathbb{R}^{d}$ , admits a triangulation with at least dn+Ω(logn) simplices.     

Strong Feller properties for distorted Brownian motion with reflecting boundary condition and an application to continuous N-particle systems with singular interactions

Assuming that Ω⊂Rn, n?2, is an open, relatively compact set with boundary ∂Ω of Lebesgue measure zero we prove strong Feller properties for a class of distorted Brownian motions in with reflecting boundary condition. Dirichlet form techniques give the existence of a weak solution to the corresponding stochastic differential equation for quasi all starting points in the sense of the associated martingale problem. Combining this result with the strong Feller properties we can construct a weak solution for specified starting points. If Ω has C²-boundary the construction works for all starting points, where the drift term is not singular, even on the boundary. But also for a certain class of sets with less smooth boundary our approach works for all points in Ω, where the drift term is not singular, and at least some points from ∂Ω. Our techniques allow very singular drift terms. This enables us to construct continuous N-particle gradient stochastic dynamics in cuboids Λ⊂Rd, d∈N, with reflecting boundary condition and singular interactions for dN?2. We can start the stochastic dynamics in all initial configurations having at most one particle in ∂Λ, provided ∂Λ is locally smooth there.     

On a generalization of distance sets

A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.     

A Lower Bound for Weak ɛ -Nets in High Dimension

   Abstract. A finite set N ⊂ R ^d is a weak ε-net for an n -point set X ⊂ R ^d (with respect to convex sets) if it intersects each convex set K with |K ∩ X| ≥ ε n . It is shown that there are point sets X ⊂ R ^d for which every weak ε -net has at least const ⋅

Orthogonal polynomials in several variables for measures with mass points

Let dν be a measure in ? ^d obtained from adding a set of mass points to another measure dμ. Orthogonal polynomials in several variables associated with dν can be explicitly expressed in terms of orthogonal polynomials associated with dμ, so are the reproducing kernels associated with these polynomials. The explicit formulas that are obtained are further specialized in the case of Jacobi measure on the simplex, with mass points added on the vertices, which are then used to study the asymptotics kernel functions for dν.     

A gallai-type problem

Two disjoint sets in R^m are said to be n-incident if every flat spanned by n distinct points of one set contains a point of the other. We obtain bounds for the dimension of the flat spanned by the union of n-incident sets and consider a related problem.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

Pebble Sets in Convex Polygons

Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane. We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points.