Article ID Journal Published Year Pages File Type
4650150 Discrete Mathematics 2009 17 Pages PDF
Abstract

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ρ,Δ∈R a set AA of integers is (ρ,Δ)(ρ,Δ)- smooth   if abs(|I|⋅ρ−|I∩A|)<Δ for any interval II of integers; a set AA 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⊆NA,B⊆N, the composition   of AA and BB is the subset DD of AA such that, for all ii, the iith member of AA is in DD if and only if the iith member of NN is in BB. This operator enables the partition of a (ρ,Δ)(ρ,Δ)-smooth set into two sets that are (ρ1,Δ)(ρ1,Δ)-smooth and (ρ2,Δ)(ρ2,Δ)-smooth, for any ρ1,ρ2ρ1,ρ2 and ΔΔ obeying some reasonable restrictions. Another powerful tool for constructing smooth sets is a one-to-one partial function ff from the unit interval into the natural numbers having the property that any real interval X⊆[0,1)X⊆[0,1) has a subinterval YY which is ‘very close’ to XX s.t. f(Y)f(Y) is (ρ,Δ)(ρ,Δ)-smooth, where ρρ is the length of YY and ΔΔ is a small constant.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,