Polylogarithmic bound for effective asymmetric coloring of inverse limits

Let Gr\mathscr{Gr} be the class of finite permutation groups, and let asy(G)\operatorname{asy}(G) denote the asymmetric coloring number of a finite permutation group GG. Let gg be a function as in the effective asymmetric coloring conjecture: for every epimorphic inverse sequence of finite permutation groups with disjoint domains, length at least g(G0)g(G_0) guarantees a zero-neutral zero-asymmetric 2-coloring of the inverse limit.

Polylogarithmic bound conjecture. There exists a polynomial pp such that the effective asymmetric coloring conjecture holds with

g(G)=p(log(asy(G))).g(G)=p\bigl(\log(\operatorname{asy}(G))\bigr).

The preceding argument gives the lower bound g(G)log2asy(G)g(G)\geq\log_2\operatorname{asy}(G) whenever the effective conjecture holds. This conjecture asks whether a polynomial in the logarithm gives a corresponding upper bound; its status is not given in the supplied text.

Sources & referencesView supporting material

Primary source

Laszlo Babai, “Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed”, arXiv:2110.08492 (2021).

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.