MAX-CUT: вероятностное округление/Задачи/eupce-6-19 — различия между версиями

Текущая версия на 21:10, 17 декабря 2024

Проверено: StasFomin 21:10, 17 декабря 2024 (UTC)

@@ Строка 1: / Строка 1: @@
-{{проверено|}}
+{{проверено|[[Участник:StasFomin|StasFomin]] 21:10, 17 декабря 2024 (UTC)}}
-<!-- Probability and Computing -->
+{{bonus}}
-[[File:eupce-6-19_2023-05-19_12-22-45_image0.png|480px]]
+<latex>
-[[File:eupce-6-19_2023-05-19_12-23-03_image0.png|480px]]
+Let $G=(V, E)$ be an undirected graph and suppose each $v \in V$ is
+associated with a set S(v) of $8r$ colors, where $r \geq 1$.
+Suppose, in addition, that for each $v \in V$ and $c \in S(V)$
+there are at most $r$ neighbors $u$ of $v$ such that $c$ lies in $S(u)$.
+Prove that there is a proper coloring of $G$ assigning to each vertex $v$ a color from its class $S(v)$ such that, for any edge $(u,v) \in E$, the colors assigned to $u$ and $v$ are different.
+You may want to let $A_{u,v,c}$ be the event that $u$ and $v$ are both colored with color $c$ and then consider the family of such events.
+</latex>
+<!-- [[File:eupce-6-19_2023-05-19_12-22-45_image0.png|480px]]
+[[File:eupce-6-19_2023-05-19_12-23-03_image0.png|480px]] -->
 [[Категория:Теоретические задачи]]