Om varje kant (u, v) av en graf G = (V, E) är dekorerad med en permutation πu,v av k objekt, säger vi att det har en permuterad k-färgning om det finns en färgning σ : V → {1,... } sådan att σ(v) = πu,v(σ(u)) för alla (u, v). Baserat på argument från statistisk fysik, antar vi att tröskeln d k för permuterad k-färgbarhet i slumpmässiga grafer G(n, m = dn/2), där permutationerna på kanterna är jämnt slumpmässiga, är lika med tröskeln för standardgraf k-färgbarhet. Den ytterligare symmetri som ges av slumpmässiga permutationer gör det lättare att bevisa gränser på d k. Genom att tillämpa den andra moment metoden med dessa ytterligare symmetrier, och tillämpa den första moment metoden till en slumpmässig variabel som beror på antalet tillgängliga färger vid varje vertex, vi bundna tröskeln inom en additiv konstant. Specifikt visar vi att för varje konstant ε > 0, för tillräckligt stor k vi har I kontrast, de mest kända gränserna på d k för standard k-färgbarhet lämna en additiv lucka på cirka ln k mellan de övre och nedre gränserna.
Dani, Moore och Olson REF studerade ett "dekorerat" färgproblem där varje par av (u, v) hörn kommer med en permutation π u,v av k möjliga färger.
Tight bounds on the threshold for permuted k-colorability
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}