Polynomial-size uniform subset conjecture for transitive group actions
Let be a group that acts transitively on a set . A subset is -uniform if, for every ,
Polynomial-size uniform subset conjecture. There exists an -uniform subset such that
for some universal constant . 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
Let be a group that acts transitively on a set . A subset is -uniform if, for every ,
Polynomial-size uniform subset conjecture. There exists an -uniform subset such that
for some universal constant . 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
- Greg Kuperberg, Shachar Lovett and Ron Peled, “Probabilistic existence of rigid combinatorial structures”, arXiv:1111.0492 (2011).
Progress summary
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.