Jakub PRZYBYŁO

(WMS, AGH)

Siła nieregularności grafów regularnych
-- liniowość ze względu na n/d

Niech $G$ będzie grafem prostym bez izolowanych krawędzi i z co najwyżej jednym izolowanym wierzchołkiem. Dla danej liczby naturalnej k, k-ważenie grafu $G$ definiowane jest jako dowolne odwzorowanie $f:E(G)\rightarrow \{1,2,\ldots,k\}$. Siłą nieregularności grafu $G$, $s(G)$, nazywamy najmniejszą liczbę naturalną k taką, że istnieje k-ważenie grafu $G$, dla którego $\sum_{e:u\in e}f(e)\neq\sum_{e:v\in e}f(e)$ dla wszystkich par różnych wierzchołków $u,v\in V(G)$. Można łatwo zauważyć, iż $s(G)\geqslant\big\lceil\frac{n+d-1}{d}\big\rceil$ dla wszystkich grafów d-regularnych, $d\geqslant 2$, rzędu n. Faudree i Lehel sformułowali następująca hipotezę.

Istnieje absolutna stała c taka, że

$$s(G)\leqslant \frac{n}{d}+c$$ (1)

dla każdego d-regularnego grafu $G$, $d\geqslant 2$, rzędu n.

Udało im się jednak jedynie pokazać, iż

$s(G)\leqslant \Big\lceil\frac{n}{2}\Big\rceil+9$ dla grafów regularnych. Około 15 lat później duży krok naprzód został uczyniony przez Frieze'a, Goulda, Karonskiego i Pfendera. Niech $G$ będzie d-regularnym grafem rzędu n bez izolowanych krawędzi i wierzchołków.

(a) Jeżeli $d\leqslant\lfloor(n\ln n)^{14}\rfloor$, wówczas $s(G)\leqslant 10nd+1$,

(b) Jeżeli $\lfloor(n\ln n)^{14}\rfloor +1 \leqslant d\leqslant \lfloor n^{12}\rfloor$, wówczas $s(G)\leqslant 48nd+1$,

(c) Jeżeli $d\geqslant \lfloor n^{12}\rfloor +1$, wówczas $s(G)\leqslant 240(\log n)nd+1$.

Ich wynik został ostatnio uzupełnionyy (i poprawiony w pewnych przypadkach) przez prze Cucklera i Lazebnika. Niech $G$ będzie d-regularnym grafem rzędu n bez izolowanych krawędzi i wierzchołków.

Jeżeli $d\geqslant 10^{43}n^{23}\log^{13}n$, wówczas $s(G)\leqslant 48nd+6$.

Niestety, te wyniki nie dawały nawet informacji, czy $s(G)$ (dla grafów d-regularnych) jest ograniczone przez jakąkolwiek liniową funkcję ze względu na $\frac{n}{d}$ (patrz Twierdzenie (c)). Wynika to natomiast z niedawno udowodnionego przeze mnie twierdzenia.

Niech $G$ będzie grafem d-regularnym rzędu n bez izolowanych wierzchołków i krawędzi. Wówczas

$$s(G)< 16\frac{n}{d}+6.$$

Jego dowód zostanie przedstawiony podczas referatu.

Serdecznie zapraszamy wszystkich chętnych !