Polynomial-size uniform subset conjecture for transitive group actions

From papers

Let $G$ be a group that acts transitively on a set $X$ . A subset $T\subset G$ is $X$ -uniform if, for every $x,y\in X$ ,

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

Polynomial-size uniform subset conjecture. There exists an $X$ -uniform subset $T\subset G$ such that

|T|\le |X|^c

for some universal constant $c>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.

Progress summary

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

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Polynomial-size uniform subset conjecture for transitive group actions
Let $G$ be a group that acts transitively on a set $X$ . A subset $T\subset G$ is $X$ -uniform if, for every $x,y\in X$ ,
$\frac{1}{|T|}\left|\{g\in T:g(x)=y\}\right|=\frac{1}{|X|}.$
Polynomial-size uniform subset conjecture. There exists an $X$ -uniform subset $T\subset G$ such that
$|T|\leq |X|^c$
for some universal constant $c>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).

Sources & referencesView supporting material

Primary source

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

1 week ago