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.

  • $\begingroup$ $w(A)$ or simply $w(S)$ (for the second time)? $\endgroup$ – Włodzimierz Holsztyński Aug 2 '13 at 17:24
  • $\begingroup$ @WlodzimierzHolsztynski Thanks! Fixed. $\endgroup$ – Robin Houston Aug 2 '13 at 17:25
  • $\begingroup$ Nice question. Did you try any examples? It should not be too difficult to compute the diameter if $X$ is not too large. $\endgroup$ – Mark Sapir Aug 2 '13 at 18:35
  • $\begingroup$ @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$. $\endgroup$ – Robin Houston Aug 2 '13 at 20:57
  • $\begingroup$ 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. $\endgroup$ – Shahrooz Janbaz Aug 2 '13 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.