𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Intersection Properties of Subsets of Integers

✍ Scribed by Tibor Szabó

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
241 KB
Volume
20
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Let N k be the maximal integer such that there exist subsets A 1 , . . . , A N k ⊆ {1, 2, . . . , n} for which A i ∩ A j is an arithmetic progression of length at least k for every 1 ≤ i < j ≤ N k . Graham, Simonovits and Sós gave the exact value of N 0 . For k ≥ 2, Simonovits and Sós determined the asymptotic behavior of N k .

In this paper we prove a conjecture of Simonovits and Sós concerning the asymptotic value of N 1 . We show that

Moreover, we slightly improve the best-known construction, thus disproving their conjecture on the exact extremal system.

📜 SIMILAR VOLUMES

On Schur Properties of Random Subsets of
On Schur Properties of Random Subsets of Integers
✍ Ronald Graham; Vojtech Rödl; Andrzej Ruciński 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 792 KB

A classic result of I. Schur [9] asserts that for every r 2 and for n sufficiently large, if the set [n]=[1, 2, ..., n] is partitioned into r classes, then at least one of the classes contains a solution to the equation x+ y=z. Any such solution with x{y will be called a Schur triple. Let us say tha

Disjoint subsets of integers having a co
Disjoint subsets of integers having a constant sum
✍ Kiyoshi Ando; Severino Gervacio; Mikio Kano 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 262 KB

We prove that for positive integers n, m and k, the set (1, 2, . , n} of integers contains k disjoint subsets having a constant sum m if and only if 2k -1 G m c n(n + 1)/(2k).

On Optimal Subset Representations of Int
On Optimal Subset Representations of Integer Sets
✍ Mike Develin 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 121 KB

In this paper, we investigate representations of sets of integers as subset sums of other sets of minimal size, achieving results on the nature of the representing set as well as providing several reformulations of the problem. We apply one of these reformulations to prove a conjecture and extend a