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.     

n-point sets and graphs of functions

We prove that, for every n?2, there exists an n-point set (a plane set which hits every line in exactly n points) that is homeomorphic to the graph of a function from R to R; for n?4, there exist both 0-dimensional and 1-dimensional examples. This raises the question (which we do not answer) of whether n-point sets for different n's could be homeomorphic.     

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.     

Dimensions of strong n-point sets

n-point sets (plane sets which hit each line in n points) and strong n-point sets (in addition hit each circle in n-points) exist (for n?2, n?3 respectively) by transfinite induction, but their properties otherwise are difficult to establish. Recently for n-point sets the question of their possible dimensions has been settled: 2- and 3-point sets are always zero-dimensional, while for n?4, one-dimensional n-point sets exist. We settle the same question for strong n-point sets: strong 4- and 5-point sets are always zero-dimensional, while for n?6, both zero-dimensional and one-dimensional strong n-point sets exist.     

Generating all subsets of a finite set with disjoint unions

If X is an n-element set, we call a family G⊂PX a k-generator for X if every x⊂X can be expressed as a union of at most k disjoint sets in G. Frein, Lévêque and Seb? conjectured that for n>2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k=2, and for n a sufficiently large multiple of k when k?3.     

Cross-intersecting sub-families of hereditary families

Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if for any i and j in {1,2,…,k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let X² denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{∅} of X² and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A₁,A₂,…,Ak (not necessarily distinct or non-empty) of H are maxima if A₁=A₂=?=Ak=S for some largest starSofH (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k?|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A₁=A₂=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case.     

On multi-coloured lines in a linear space

We prove that if X₁, X₂,…, X_k are pairwise disjoint sets of points in a linear space, each of cardinality n, whose union ∪_{j = 1}^kX_j, is not collinear, then there are at least (k ? 1) n lines in the space, which intersect at least two of th e X_j's. Equality occurs if and only if k = n + 1 and X₁,…, X_{n + 1} are obtained by taking n + 1 concurrent lines in a projective plane of order n, and omitting, from each of them, their common point. When n = 1, this reduces to a theorem of de Bruijn and Erdos (Indag. Math.10 (1984), 421–423).     

Transitive points via Furstenberg family

Let (X,T) be a topological dynamical system and F be a Furstenberg family (a collection of subsets of Z₊ with hereditary upward property). A point x∈X is called an F-transitive one if {n∈Z₊:Tnx∈U}∈F for every non-empty open subset U of X; the system (X,T) is called F-point transitive if there exists some F-transitive point. In this paper, we aim to classify transitive systems by F-point transitivity. Among other things, it is shown that (X,T) is a weakly mixing E-system (resp. weakly mixing M-system, HY-system) if and only if it is {D-sets}-point transitive (resp. {central sets}-point transitive, {weakly thick sets}-point transitive).It is shown that every weakly mixing system is Fip-point transitive, while we construct an Fip-point transitive system which is not weakly mixing. As applications, we show that every transitive system with dense small periodic sets is disjoint from every totally minimal system and a system is Δ^?(Fwt)-transitive if and only if it is weakly disjoint from every P-system.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

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.     

More About 4-Isosceles Planar Sets

A finite planar set is k-isosceles for k 3 if every k-point subset of the set contains a point equidistant from the other two. In [1] Fishburn obtains several important results about isosceles planar sets and poses a series of conjectures and open questions. We disprove Conjecture 1 in [1] and provide another 34 nonsimilar 4-isosceles 8-point planar sets which answer one of the open questions in [1] negatively.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Realizing cohomology classes as Euler classes

For a space X, let E _k (X), E _k ^s (X) and E _k ^?? (X) denote respectively the set of Euler classes of oriented k-plane bundles over X, the set of Euler classes of stably trivial k-plane bundles over X and the spherical classes in H ^k (X; ?). We prove some general facts about the sets E _k (X), E _k ^s (X) and E _k ^?? (X). We also compute these sets in the cases where X is a projective space, the Dold manifold P(m, 1) and obtain partial computations in the case that X is a product of spheres.     

Point transversals to translates of a trapezoid

Anm-transversal to a family of convex sets in the plane is anm-point set which intersects every members of the family. One of Grübaum’s conjectures says that a planar family of translates of a convex compact set has a 3-transversal provided that any two of its members intersect. Recently the conjecture has been proved affirmatively (see [4]). In the present paper we provide a different and straightforward proof for the conjecture for the family of translates of a closed trapezoid in the plane and give several concrete 3-transversals.     

Extending symmetric designs

If a symmetric 2-design with parameters (v, k, λ) is extendable, then one of the following holds: v = 4λ + 3, k = 2λ + 1; or v = (λ + 2)(λ² + 4λ + 2), k = λ² + 3λ + 1; or v = 111, k = 11, λ = 1; or v = 495, k = 39, λ = 3. In particular, there are at most three sets of extendable symmetric design parameters with any given value of λ. As a consequence, the only twice-extendable symmetric design is the 21-point projective plane.     

On the distortion required for embedding finite metric spaces into normed spaces

We investigate the minimum dimensionk such that anyn-point metric spaceM can beD-embedded into somek-dimensional normed spaceX (possibly depending onM), that is, there exists a mappingf: M→X with $$\frac{1}{D}dist_M (x,y) \leqslant \left| {f(x) - f(y)} \right| \leqslant dist_M (x,y) for any$$ Extending a technique of Arias-de-Reyna and Rodríguez-Piazza, we prove that, for any fixedD≥1,k≥c(D)n ^1/2D for somec(D)>0. For aD-embedding of alln-point metric spaces into the samek-dimensional normed spaceX we find an upper boundk≤12Dn ^1/[(D+1)/2]lnn (using thel _∞ ^k space forX), and a lower bound showing that the exponent ofn cannot be decreased at least forD?[1,7)∪[9,11), thus the exponent is in fact a jumping function of the (continuously varied) parameterD.     

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.     

Bilinear forms over a finite field,with applications to coding theory

Let Ω be the set of bilinear forms on a pair of finite-dimensional vector spaces over GF(q). If two bilinear forms are associated according to their q-distance (i.e., the rank of their difference), then Ω becomes an association scheme. The characters of the adjacency algebra of Ω, which yield the MacWilliams transform on q-distance enumerators, are expressed in terms of generalized Krawtchouk polynomials. The main emphasis is put on subsets of Ω and their q-distance structure. Certain q-ary codes are attached to a given $\text{X ? Ω}$; the Hamming distance enumerators of these codes depend only on the q-distance enumerator of X. Interesting examples are provided by Singleton systems $\text{X ? Ω}$, which are defined as t-designs of index 1 in a suitable semilattice (for a given integer t). The q-distance enumerator of a Singleton system is explicitly determined from the parameters. Finally, a construction of Singleton systems is given for all values of the parameters.     

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.