Families intersecting on an interval

We shall be interested in the following Erd?s-Ko-Rado-type question. Fix some set B⊂[n]={1,2,…,n}. How large a subfamily A of the power set P[n] can we find such that the intersection of any two sets in A contains a cyclic translate (modulo n) of B? Chung, Graham, Frankl and Shearer have proved that, in the case where B=[t] is a block of length t, we can do no better than taking A to consist of all supersets of B. We give an alternative proof of this result, which is in a certain sense more ‘direct’.     

Sumset phenomenon in countable amenable groups

Jin proved that whenever A and B are sets of positive upper density in Z, A+B is piecewise syndetic. Jin's theorem was subsequently generalized by Jin and Keisler to a certain family of abelian groups, which in particular contains Zd. Answering a question of Jin and Keisler, we show that this result can be extended to countable amenable groups. Moreover we establish that such sumsets (or — depending on the notation — “product sets”) are piecewise Bohr, a result which for G=Z was proved by Bergelson, Furstenberg and Weiss. In the case of an abelian group G, we show that a set is piecewise Bohr if and only if it contains a sumset of two sets of positive upper Banach density.     

Sumsets contained in infinite sets of integers

If the positive integers are partitioned into a finite number of cells, then Hindman proved that there exists an infinite set B such that all finite, nonempty sums of distinct elements of B all belong to one cell of the partition. Erdös conjectured that if A is a set of integers with positive asymptotic density, then there exist infinite sets B and C such that B + C ? A. This conjecture is still unproved. This paper contains several results on sumsets contained in finite sets of integers. For example, if A is a set of integers of positive upper density, then for any n there exist sets B and F such that B has positive upper density, F has cardinality n, and B + F ? A.     

Low upper bounds in the LR degrees

We say that A≤_LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0^′.     

Bases for sets of integers

We are interested in expressing each of a given set of non-negative integers as the sum of two members of a second set, the second set to be chosen as economically as possible.So let us call B a basis for A if to every a ∈ A there exist b, b′ ∈ B such that a = b + b′. We concern ourselves primarily with finite sets, A, since the results for infinite sets generally follow from these by the familiar process of condensation.     

Kirchberger-type theorems for separation by convex domains

We say that a convex set K in ? ^d strictly separates the set A from the set B if A ? int(K) and B ? cl K = ø. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in ? ^d with the property that for every T ? A?B of cardinality at most d + 2, there is a half space strictly separating T ? A and T ? B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in ? ^d is d + 2.In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.     

On Partial Classes Containig All Monotone and Zero-Preserving Total Boolean Functions

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ??(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ??(A) can be finite or infinite. We state some general results on ??(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.     

Lipschitz image of a measure-null set can have a null complement

We give two examples which show that in infinite dimensional Banach spaces the measure-null sets are not preserved by Lipschitz homeomorphisms. There exists a closed setD ? ?₂ which contains a translate of any compact set in the unit ball of ?₂ and a Lipschitz isomorphismF of ?₂ onto ?₂ so thatF(D) is contained in a hyperplane. LetX be a Banach space with an unconditional basis. There exists a Borel setA?X and a Lipschitz isomorphismF ofX onto itself so that the setsX/A andF(A) are both Haar null.     

An iterative method for a system of linear complementarity problems with perturbations and interval data

In this paper, we introduce a total step method for solving a system of linear complementarity problems with perturbations and interval data. It is applied to two interval matrices [A] and [B] and two interval vectors [b] and [c]. We prove that the sequence generated by the total step method converges to ([x^∗],[y^∗]) which includes the solution set for the system of linear complementarity problems defined by any fixed A∈[A],B∈[B],b∈[b] and c∈[c]. We also consider a modification of the method and show that, if we start with two interval vectors containing the limits, then the iterates contain the limits. We close our paper with two examples which illustrate our theoretical results.     

Cubic planar hamiltonian graphs of various types

Let U be the set of cubic planar hamiltonian graphs, A the set of graphs G in U such that G-v is hamiltonian for any vertex v of G, B the set of graphs G in U such that G-e is hamiltonian for any edge e of G, and C the set of graphs G in U such that there is a hamiltonian path between any two different vertices of G. With the inclusion and/or exclusion of the sets A,B, and C, U is divided into eight subsets. In this paper, we prove that there is an infinite number of graphs in each of the eight subsets.     

On a Problem Related to Homomorphism Groups in the Theory of Abelian Groups

In this paper, for any reduced Abelian group A whose torsion-free rank is infinite, we construct a countable set A(A) of Abelian groups connected with the group A in a definite way and such that for any two different groups B and C from the set A(A) the groups B and C are isomorphic but Hom(B,X) ? Hom(C,X) for any Abelian group X. The construction of such a set of Abelian groups is closely connected with Problem 34 from L. Fuchs’ book “Infinite Abelian Groups,” Vol. 1.     

On Supersets of Wavelet Sets

Considering a single dyadic orthonormal wavelet ψ in L ²(?), it is still an open problem whether the support of $\widehat{\psi}$ always contains a wavelet set. As far as we know, the only result in this direction is that if the Fourier support of a wavelet function is “small” then it is either a wavelet set or a union of two wavelet sets. Without assuming that a set S is the Fourier support of a wavelet, we obtain some necessary conditions and some sufficient conditions for a “small” set S to contain a wavelet set. The main results, which are in terms of the relationship between two explicitly constructed subsets A and B of S and two subsets T ₂ and D ₂ of S intersecting itself exactly twice translationally and dilationally respectively, are (1) if $A\cup B\not\subseteq T_{2}\cap D_{2}$ then S does not contain a wavelet set; and (2) if A∪B?T ₂∩D ₂ then every wavelet subset of S must be in S?(A∪B) and if S?(A∪B) satisfies a “weak” condition then there exists a wavelet subset of S?(A∪B). In particular, if the set S?(A∪B) is of the right size then it must be a wavelet set.     

Noisy colored point set matching

We propose a process for determining approximated matches, in terms of the bottleneck distance, under color preserving rigid motions, between two colored point sets A,B∈R², |A|≤|B|. We solve the matching problem by generating all representative motions that bring A close to a subset B^′ of set B and then using a graph matching algorithm. We also present an approximate matching algorithm with improved computational time. In order to get better running times for both algorithms we present a lossless filtering preprocessing step. By using it, we determine some candidate zones which are regions that contain a subset S of B such that A may match one or more subsets B^′ of S. Then, we solve the matching problem between A and every candidate zone. Experimental results using both synthetic and real data are reported to prove the effectiveness of the proposed approach.     

Twisted Frobenius Extensions of Graded Superrings

We define twisted Frobenius extensions of graded superrings. We develop equivalent definitions in terms of bimodule isomorphisms, trace maps, bilinear forms, and dual sets of generators. The motivation for our study comes from categorification, where one is often interested in the adjointness properties of induction and restriction functors. We show that A is a twisted Frobenius extension of B if and only if induction of B-modules to A-modules is twisted shifted right adjoint to restriction of A-modules to B-modules. A large (non-exhaustive) class of examples is given by the fact that any time A is a Frobenius graded superalgebra, B is a graded subalgebra that is also a Frobenius graded superalgebra, and A is projective as a left B-module, then A is a twisted Frobenius extension of B.     

On additively regular seminearrings

The most natural seminearrings, i.e., the seminearrings of all self-maps of additive semigroups are necessarily multiplicatively regular but they need not be additively regular. The purpose of this paper is to investigate additively regular seminearrings. We mainly focus on the study of congruences in various types of additively regular seminearrings such as additively inverse, additively Clifford and Bandelt seminearrings. We deduce that for a restricted type of additively inverse seminearrings there exists an inclusion preserving bijective correspondence between the set of all normal congruences and that of all full k-ideals. Finally, we characterize those seminearrings which are the subdirect product of a distributive lattice and a zero symmetric near-ring.     

On smooth sets of integers

This work studies evenly distributed sets of integers—sets whose quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation. Namely, for ρ,Δ∈R a set A of integers is (ρ,Δ)- smooth if for any interval I of integers; a set A is Δ-smooth if it is (ρ,Δ)-smooth for some real number ρ. The paper introduces the concept of Δ-smooth sets and studies their mathematical structure. It focuses on tools for constructing smooth sets having certain desirable properties and, in particular, on mathematical operations on these sets. Three additional papers by us are build on the work of this paper and present practical applications of smooth sets to common and well-studied scheduling problems.One of the above mathematical operations is composition of sets of natural numbers. For two infinite sets A,B⊆N, the composition of A and B is the subset D of A such that, for all i, the ith member of A is in D if and only if the ith member of N is in B. This operator enables the partition of a (ρ,Δ)-smooth set into two sets that are (ρ₁,Δ)-smooth and (ρ₂,Δ)-smooth, for any ρ₁,ρ₂ and Δ obeying some reasonable restrictions. Another powerful tool for constructing smooth sets is a one-to-one partial function f from the unit interval into the natural numbers having the property that any real interval X⊆[0,1) has a subinterval Y which is ‘very close’ to X s.t. f(Y) is (ρ,Δ)-smooth, where ρ is the length of Y and Δ is a small constant.     

SOME RAMSEY THEORY IN BOOLEAN ALGEBRA FOR COMPLEXITY CLASSES

It is known that for two given countable sets of unary relations A and B on ω there exists an infinite set H ? ω on which A and B are the same. This result can be used to generate counterexamples in expressibility theory. We examine the sharpness of this result.     

Squarefree numbers in sumsets

We solve a problem of Filaseta by proving, that if N is sufficiently large, A ⊆ [N], |A| > N/9 and A + Adoes not contain any squarefree integer then all elements of A are congruent to 0 (mod 4) or 2 (mod 4). In order to show the main result we characterize the structure of all dense sets, whose elements sum to no squarefree number.