A point set puzzle revisited

Two discrete point sets in Rⁿ are said to be homometric if their difference sets coincide. Homometric point sets were first studied in the 1930s in connection with the interpretation of x-ray diffraction patterns; today they appear in many contexts. Open questions still abound, even for point sets on the line. Under what conditions does a difference set S−S characterize S uniquely? If it does not, how can we find all the sets S_i,i=1,…, that give rise to it, and how are these sets related?     

The existence of large set of symmetric partitioned incomplete latin squares

In this paper, we investigate the existence of large sets of symmetric partitioned incomplete latin squares of type g^u (LSSPILSs) which can be viewed as a generalization of the well‐known golf designs. Constructions for LSSPILSs are presented from some other large sets, such as golf designs, large sets of group divisible designs, and large sets of Room frames. We prove that there exists an LSSPILS(g^u) if and only if u ≥ 3, g(u ? 1) ≡ 0 (mod 2), and (g, u) ≠ (1, 5).     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

An inverse theorem for the restricted set addition in Abelian groups

Let A be a set of k5 elements of an Abelian group G in which the order of the smallest nonzero subgroup is larger than 2k−3. Then the number of different elements of G that can be written in the form a+a^′, where a,a^′A, a≠a^′, is at least 2k−3, as it has been shown in [Gy. Károlyi, The Erdős–Heilbronn problem in Abelian groups, Israel J. Math. 139 (2004) 349–359]. Here we prove that the bound is attained if and only if the elements of A form an arithmetic progression in G, thus completing the solution of a problem of Erdős and Heilbronn. The proof is based on the so-called ‘Combinatorial Nullstellensatz.’     

Substandard models of finite set theory

A survey of the isomorphic submodels of V_ω, the set of hereditarily finite sets. In the usual language of set theory, V_ω has 2^?0 isomorphic submodels. But other set‐theoretic languages give different systems of submodels. For example, the language of adjunction allows only countably many isomorphic submodels of V_ω (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Facets of the independent set polytope

Theoretical results pertaining to the independent set polytope P^ISP=conv{x{0,1}ⁿ:Axb} are presented. A conflict hypergraph is constructed based on the set of dependent sets which facilitates the examination of the facial structure of P^ISP. Necessary and sufficient conditions are provided for every nontrivial 0-1 facet-defining inequalities of P^ISP in terms of hypercliques. The relationship of hypercliques and some classes of knapsack facet-defining inequalities are briefly discussed. The notion of lifting is extended to the conflict hypergraph setting to obtain strong valid inequalities, and back-lifting is introduced to strengthen cut coefficients. Preliminary computational results are presented to illustrate the usefulness of the theoretical findings.Mathematics Subject Classification (2000): 90C11, 90C57, 90C35     

A minimal Cantor set in the space of 3-generated groups

We construct and study a family of 3-generated groups parametrized by infinite binary sequences w. We show that two groups of the family are isomorphic if and only if the sequences are cofinal and that two groups cannot be distinguished by finite sets of relations. We show a connection of the family with 2-dimensional holomorphic dynamics.      

Sharply 1-transitive subsets of certain permutation groups

In this paper we give a method for constructing sharply 1-transitive permutation sets inside a finite permutation group with certain properties and we apply this method to obtain a family of sharply 1-transitive permutation subsets of the sharply 3-transitive permutation group M(p ^2f ) on PG(1, p ^2f ) for p ^f 1 (mod 4).Work supported by G.N.S.A.G.A. and M.P.I.     

A note on difference sets in dihedral groups

It is proved that there are no nontrivial difference sets in dihedral groups of order 4p^t, where p is a prime, t > 0 is a positive integer. Received: 22 February 2002     

On the symmetry function of a convex set

We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational complexity. Given a point , let sym(x,S) denote the symmetry value of x in S: , which essentially measures how symmetric S is about the point x, and define x ^* is called a symmetry point of S if x ^* achieves the above maximum. The set S is a symmetric set if sym (S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function of sym (S) and/or sym (x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties of convex sets and functions. The results in this paper include functional properties of sym (x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on convex sets. We provide a characterization of symmetry points x ^* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x ^* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding the symmetry function and its connection to other areas of convexity theory. Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.     

Some descriptive set theory and core models

We analyse the trees given by sharps for Π¹₂ sets via inner core models to give a canonical decomposition of such sets when a core model is Σ¹₃ absolute. This is by way of analogy with Solovay's analysis of Π¹₁ sets into ω₁ Borel sets — Borel in codes for wellorders. We find that Π¹₂ sets are also unions of ω₁ Borel sets — but in codes for mice and wellorders. We give an application of this technique in showing that if a core model, K, is Σ¹₃ absolute thenTheorem. Every real is in K iff every Π¹₃ set of reals contains a Π¹₃ singleton.     

A remark on a maximal function over a Cantor set of directions

LetM _e ⁰ be the maximal operator over segments of length 1 with directions belonging to a Cantor set. It has been conjectured that this operator is bounded onL ². We consider a sequence of operators over finite sets of directions converging toM _e ⁰ . We improve the previous estimate for the (L ²,L ²)-norm of these particular operators. We also prove thatM _e ⁰ is bounded from some subsets ofL ² toL ². These subsets are composed of positive functions whose Fourier transforms have a very weak decay or are supported in a vertical strip. Partially supported by Spanish DGICYT grant no. PB90-0187.     

A fixed-parameter-tractable algorithm for set packing

1. IntroductionIt is a useful and challenging task to find efficient algorithms for many computationalhard problems. Recently, the research on Fixed-Parameter nactable Theory arouses muchinterest. FOr example, different fixed- p ax amet er- t rac t ab le- algori t hms for many well- knowndecisio11 pruble11ls illc1udi11g 3-dimellsio11al IIlatchiIlg: a11d vertex--cover Problen1 have beenPrese11ted in [1 8]. Jia11er Chen, DoIlald K. FYiesen al1d Weijia Jia proPosed a coll1pletelynew appro…     

CALCULUS ON CANTOR TRIADIC SET （I）——DERIVATIVE

For real-valued functions defined on Cantor triadic ,set. a derivative with corresponding formula of Newton-Leihniz‘s type is given In particular, for the self-simltar functions and alter-nately jumping functions defined in this paper, their derivative and exceptional sets are studied ac-curately by using ergodic theory on Е2 and Duffin-Scbaeffer‘s theorem coneerning metric diophan-tine approximation. In addition, Haar basis of L2(Е2) is constructed and Flaar expansion of stan-drd self-similar function is given.     

On orderable set functions and continuity I

A set functionv (which is not necessarily additive) on a measurable spaceI is called orderable if for each measurable order ℛ onI there is a measureϱ ^ℛ ν(J) =ν(J) onI such that for all subsetsJ ofI that are initial segements,ϱ ^ℛ ν. Properties such as nonatomicity, nullness of sets, and weak continuity are shown to be inherited from orderable set functionsv toϱ ^ℛ ν and vice versa. A characterization of set functions which are absolutely continuous (with respect to some positive measure) in the set of orderable set functions is also given. Reporduction of this report was partially supported by the Office of Naval Research under contract N-000 14-67-0112-0011; The U.S. Atomic Energy Commission contract AT (04-3)-326-PA #18; and The National Science Foundation, Grant GP 31393X. Reproduction in whole or in part is permitted for any purposes of the United States Government. This document has been approved for public release and sale; its distribution is unlimited. Research of this report was carried out at Tel Aviv University.     

Independent sets in regular graphs and sum-free subsets of finite groups

It is shown that there exists a function∈(k) which tends to 0 ask tends to infinity, such that anyk-regular graph onn vertices contains at most 2^{(1/2+∈(k))n} independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory. Research supported in part by the United States-Israel Binational Science Foundation and by a Bergmann Memorial Grant.     

On a class of some special sets on thek-skeleton of a convex compact set

In this paper, generalizing the notion of a path we define ak-area to be the setD={g(t):t ∈J} on thek-skeleton of a convex compact setK in a Hilbert space, whereg is a continuous injection map from thek-dimensional convex compact setJ to thek-skeleton ofK. We also define anE ^k-area onK, whereE ^k is ak-dimensional subspace, to be ak-area with the propertyπ(g(t))=t,t ∈π(K), whereπ is the orthogonal projection onE ^k. This definition generalizes the notion of an increasing path on the 1-skeleton ofK. The existence of such sets is studied whenK is a subset of a Euclidean space or of a Hilbert space. Finally some conjectures are quoted for the number of such sets in some special cases.     

An extremal set theoretical characterization of some steiner systems

Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦( _t ⁿ )( _k ^2k-t-1 )/( _t ^2k-t-1 ). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach.     

Higher generation subgroup sets and the $ \Sigma $-invariants of graph groups

We present a general condition, based on the idea of n-generating subgroup sets, which implies that a given character represents a point in the homotopical or homological -invariants of the group G. Let be a finite simplicial graph, the flag complex induced by , and the graph group, or 'right angled Artin group', defined by . We use our result on n-generating subgroup sets to describe the homotopical and homological -invariants of in terms of the topology of subcomplexes of . In particular, this work determines the finiteness properties of kernels of maps from graph groups to abelian groups. This is the first complete computation of the -invariants for a family of groups whose higher invariants are not determined - either implicitly or explicitly - by ¹. Received: October 18, 1996