The edge-pattern convex-combination conjecture

Let PP be a dd-regular edge-rooted pattern of depth rr and girth 2r+22r+2. For each edge-rooted pattern, let e(P)\mathbf{e}(P) denote its constraint vector, and let Tr(d)\mathcal{T}'_r(d) be the specified family of dd-regular edge-rooted trees of depth rr. The constraint e(P)\mathbf{e}(P) is weaker than a convex combination of constraints from this family in the sense that there exist T1,,TmTr(d)T_1,\dots,T_m\in\mathcal{T}'_r(d) and λ1,,λm[0,1]\lambda_1,\dots,\lambda_m\in[0,1] with

i=1mλi=1\sum_{i=1}^m\lambda_i=1

and, for every α(Q+)r+1\bm{\alpha}\in{\left(\mathbb{Q}^+\right)}^{r+1},

α ⁣(i=1mλie(Ti))1    α ⁣e(P)1.\bm{\alpha}^{\!\top}\left(\sum_{i=1}^m\lambda_i\mathbf{e}(T_i)\right)\ge 1\quad\implies\quad\bm{\alpha}^{\!\top}\mathbf{e}(P)\ge 1.

This would explain why the bounds obtained from edge-rooted trees remain valid at girth 2r+22r+2, and would generalize the cases checked for r=2r=2 and d{3,4}d\in\{3,4\}.

Sources & referencesView supporting material

Primary source

François Pirot and Jean-Sébastien Sereni, “Fractional chromatic number, maximum degree and girth”, arXiv:1904.05618 (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.