Classification of seven-point four-distance sets in the plane

A point set X in the plane is called a k-distance set if there are exactly k different distances between two distinct points in X. In this paper, we classify 7-point 4-distance sets and show that there are forty two 7-point 4-distance sets in the plane up to isomorphism, we also give some results about diameter graphs.     

On the multiple Borsuk numbers of sets

The Borsuk number of a set S of diameter d > 0 in Euclidean n-space is the smallest value of m such that S can be partitioned into m sets of diameters less than d. Our aim is to generalize this notion in the following way: The k -fold Borsuk number of such a set S is the smallest value of m such that there is a k-fold cover of S with m sets of diameters less than d. In this paper we characterize the k-fold Borsuk numbers of sets in the Euclidean plane, give bounds for those of centrally symmetric sets, smooth bodies and convex bodies of constant width, and examine them for finite point sets in the Euclidean 3-space.     

Inside S-inner product sets and Euclidean designs

A finite set X in the Euclidean space is called an s-inner product set if the set of the usual inner products of any two distinct points in X has size s. First, we give a special upper bound for the cardinality of an s-inner product set on concentric spheres. The upper bound coincides with the known lower bound for the size of a Euclidean 2s-design. Secondly, we prove the non-existence of 2- or 3-inner product sets on two concentric spheres attaining the upper bound for any d>1. The efficient property needed to prove the upper bound for an s-inner product set gives the new concept, inside s-inner product sets. We characterize the most known tight Euclidean designs as inside s-inner product sets attaining the upper bound.     

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.     

On products of k-spaces

As is well known, k-spaces are characterized as quotient spaces of locally compact spaces. For a certain k-space X, we give characterizations on X for X×Y to be a k-space for every space Y in some class of k-spaces. Also, for certation k-spaces X and Y, we give characterizations on X and Y for X×Y to be a k-space.     

Convex Pencils of Real Quadratic Forms

We study the topology of the set X of the solutions of a system of two quadratic inequalities in the real projective space ?P ⁿ (e.g. X is the intersection of two real quadrics). We give explicit formulas for its Betti numbers and for those of its double cover in the sphere S ⁿ ; we also give similar formulas for level sets of homogeneous quadratic maps to the plane. We discuss some applications of these results, especially in classical convexity theory. We prove the sharp bound b(X)??2n for the total Betti number of X; we show that for odd n this bound is attained only by a singular?X. In the nondegenerate case we also prove the bound on each specific Betti number b _k (X)??2(k+2).     

Distance paired domination numbers of graphs

In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.     

On Borsuk’s Conjecture for Two-Distance Sets

In this paper, we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We find a two-distance set consisting of 416 points on the unit sphere $S^{64}\subset\mathbb{R}^{65}$ which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk numbers are given.     

Spherical two-distance sets

A set S of unit vectors in n-dimensional Euclidean space is called spherical two-distance set, if there are two numbers a and b so that the inner products of distinct vectors of S are either a or b. It is known that the largest cardinality g(n) of spherical two-distance sets does not exceed n(n+3)/2. This upper bound is known to be tight for n=2,6,22. The set of mid-points of the edges of a regular simplex gives the lower bound L(n)=n(n+1)/2 for g(n).In this paper using the so-called polynomial method it is proved that for nonnegative a+b the largest cardinality of S is not greater than L(n). For the case a+b<0 we propose upper bounds on |S| which are based on Delsarte's method. Using this we show that g(n)=L(n) for 6<n<22, 23<n<40, and g(23)=276 or 277.     

Faces of Poisson�CVoronoi mosaics

For a stationary Poisson?CVoronoi tessellation in Euclidean d-space and for ${k\in \{1,\dots,d\}}$ , we consider the typical k-dimensional face with respect to a natural centre function. We express the distribution of this typical k-face in terms of a certain Poisson process of closed halfspaces in a k-dimensional space. Then we show that, under the condition of large inradius, the relative boundary of the typical k-face lies, with high probability, in a narrow spherical annulus.     

A note on the spherical embeddings of strongly regular graphs

A primitive symmetric association scheme of class 2 is naturally embedded as a two-distance set in the unit sphere of Euclidean space, with respect to the primitive idempotent E₁ of the Bose–Mesner algebra of the association scheme. Then it is shown that the ratio of the two distances of the two-distance set is instantly read from the character table (i.e., the first eigen matrix P) of the association scheme.     

A note in approximative compactness and midpoint locally k-uniform rotundity in Banach spaces

In this article, we prove the following results: (1) A Banach space X is weak midpoint locally k-uniformly rotund if and only if every closed ball of X is an approximatively weakly compact k-Chebyshev set; (2) A Banach space X is midpoint locally k-uniformly rotund if and only if every closed ball of X is an approximatively compact k-Chebyshev set.     

Contributions to the theory of domination,independence and irredundance in graphs

A vertex x in a subset X of vertices of an undirected graph is redundant if its closed neighbourhood is contained in the union of closed neighbourhoods of vertices of X?{x}. In the context of a communications network, this means that any vertex which may receive communications from X may also be informed from X?{x}. The lower and upper irredundance numbers ir(G) and IR(G) are respectively the minimum and maximum cardinalities taken over all maximal sets of vertices having no redundancies. The domination number γ(G) and upper domination number Γ(G) are respectively the minimum and maximum cardinalities taken over all minimal dominating sets of G. The independent domination number i(G) and the independence number β(G) are respectively the minimum and maximum cardinalities taken over all maximal independent sets of vertices of G.A variety of inequalities involving these quantities are established and sufficient conditions for the equality of the three upper parameters are given. In particular a conjecture of Hoyler and Cockayne [9], namely $\text{i+β?2p + 2δ - 2}\text{2pδ}$, is proved.     

Ball-covering property of Banach spaces

We consider the following question: For a Banach spaceX, how many closed balls not containing the origin can cover the sphere of the unit ball? This paper shows that: (1) IfX is smooth and with dimX=n<∞, in particular,X=R ⁿ,then the sphere can be covered byn+1 balls andn+1 is the smallest number of balls forming such a covering. (2) Let Λ be the set of all numbersr>0 satisfying: the unit sphere of every Banach spaceX admitting a ball-covering consisting of countably many balls not containing the origin with radii at mostr impliesX is separable. Then the exact upper bound of Λ is 1 and it cannot be attained. (3) IfX is a Gateaux differentiability space or a locally uniformly convex space, then the unit sphere admits such a countable ball-covering if and only ifX ^* isw ^*-separable.     

Submodular set functions,matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem

For the problem maxlcub;Z(S): S is an independent set in the matroid Xrcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z(?)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1/(1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z. This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1/(1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X, unifies and generalizes the bounds (e?1)/e known for uniform matroids and $\text{1}\text{2}$ for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1?(1?α/K)^k]/α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1/(p+α) where p is the minimum number of matroids that must be intersected to obtain X.     

Contact Numbers for Congruent Sphere Packings in Euclidean 3-Space

The contact graph of an arbitrary finite packing of unit balls in Euclidean 3-space is the (simple) graph whose vertices correspond to the packing elements and whose two vertices are connected by an edge if the corresponding two packing elements touch each other. One of the most basic questions on contact graphs is to find the maximum number of edges that a contact graph of a packing of n unit balls can have. Our method for finding lower and upper estimates for the largest contact numbers is a combination of analytic and combinatorial ideas and it is also based on some recent results on sphere packings. In particular, we prove that if C(n) denotes the largest number of touching pairs in a packing of n>1 congruent balls in Euclidean 3-space, then $0.695<\frac{6n-C(n)}{n^{\frac{2}{3}}}< \sqrt[3]{486}=7.862\dots$ for all $n=\frac{k(2k^{2}+1)}{3}$ with k??2.     

Space graphs and sphericity

For a finite point set in Euclidean n-space, if we connect each pair of points by a line segment whenever the distance between them is less than a certain positive constant, we obtain a space graph in n-space. The sphericity of a graph G is defined to be the minimum number n such that G is isomorphic to a space graph in n-space. In this paper we study the sphericities of graphs and present upper bounds on the sphericity for several types of graphs.     

Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M ⁿ providing that M ⁿ is not k-connected?     

Perfect, strongly eutactic lattices are periodic extreme

We introduce a parameter space for periodic point sets, given as unions of m translates of point lattices. In it we investigate the behavior of the sphere packing density function and derive sufficient conditions for local optimality. Using these criteria we prove that perfect, strongly eutactic lattices cannot be locally improved to yield a periodic sphere packing with greater density. This applies in particular to the densest known lattice sphere packings in dimension d?8 and d=24.