# Diameter of subset sum graph

We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$. Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its elements. Let $A = \{S\subseteq X$ | $k\leq w(S) \leq c \}$.

Form a graph with vertices $A$ and an edge $S-T$ iff $S\cap T\in A$.

Is anything known about the diameters of the connected components of this graph? In particular, is there an upper bound in terms of $|X|$? I know of no case where the diameter exceeds $|X|/2$, for example. I do not claim this is optimal, and any non-obvious bound would be very interesting, especially if it is polynomial in $|X|$.

This question comes from theoretical computer science, but it seems purely combinatorial, and perhaps an expert in extremal combinatorics has some insight into it.

• $w(A)$ or simply $w(S)$ (for the second time)? – Włodzimierz Holsztyński Aug 2 '13 at 17:24
• @WlodzimierzHolsztynski Thanks! Fixed. – Robin Houston Aug 2 '13 at 17:25
• Nice question. Did you try any examples? It should not be too difficult to compute the diameter if $X$ is not too large. – Mark Sapir Aug 2 '13 at 18:35
• @MarkSapir The ‘worst’ example I know is a trivial one: if $X$ has $2n$ elements of weight $1$, with $k=n-1$ and $c=n$, then the diameter is $n$. I have looked at a few classes of examples, but so far they are all consistent with the hypothesis that the diameter is at most $|X|/2$. – Robin Houston Aug 2 '13 at 20:57
• As an example, if $X$ contains all binary string with length $n$ and the weight function be the Hamming weight of strings, then the diameter of the graph is at most $|Cr(n,k)-Cr(n,c)+1|$. Did you examined the bound $(c-k)|X|/2$? Also, you can construct good examples with finite topological spaces or $[n,k,d]$ codes with known weight distribution as like as Reed-Muller codes and BCH codes. – Shahrooz Janbaz Aug 2 '13 at 21:47