← All problems

Polynomial-size uniform subset conjecture for transitive group actions

15 years old · traced to

Let GG be a group that acts transitively on a set XX. A subset T⊂GT\subset G is XX-uniform if, for every x,y∈Xx,y\in X,

1∣T∣∣{g∈T:g(x)=y}∣=1∣X∣.\frac{1}{|T|}|\{g\in T:g(x)=y\}|=\frac{1}{|X|}.

Polynomial-size uniform subset conjecture. There exists an XX-uniform subset T⊂GT\subset G such that

∣T∣≤∣X∣c|T|\le |X|^c

for some universal constant c>0c>0. This conjecture asks whether the isolation condition used in the paper's general existence theorem is redundant. It would imply polynomial-size designs for every transitive group action; the source identifies this as an open problem in design theory.

Equivalent formulations
  1. Let GG be a group that acts transitively on a set XX. A subset T⊂GT\subset G is XX-uniform if, for every x,y∈Xx,y\in X,

    1∣T∣∣{g∈T:g(x)=y}∣=1∣X∣.\frac{1}{|T|}\left|\{g\in T:g(x)=y\}\right|=\frac{1}{|X|}.

    Polynomial-size uniform subset conjecture. There exists an XX-uniform subset T⊂GT\subset G such that

    ∣T∣≤∣X∣c|T|\leq |X|^c

    for some universal constant c>0c>0. This conjecture asks for polynomial-size designs for every transitive group action. It captures the difficulty of obtaining bounded integer bases in the probabilistic construction; the supplied context identifies it as an open question.

    source: Greg Kuperberg, Shachar Lovett and Ron Peled, “Probabilistic existence of regular combinatorial structures”, arXiv:1302.4295 (2017).

References
  1. Greg Kuperberg, Shachar Lovett and Ron Peled, “Probabilistic existence of rigid combinatorial structures”, arXiv:1111.0492 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.