Siła nieregularności grafu prostego $G$, $s(G)$, definiowana jest jako
najmniejsze $k$, dla którego istnieje przypisanie wag ze zbioru
$\{1,2,\ldots,k\}$ krawędziom grafu $G$ indukujące parami różne ważone stopnie
wszystkich wierzchołków, lub równoważnie - najmniejsza możliwa
maksymalna wielokrotność krawędzi w nieregularnym multigrafie otrzymanym
z $G$ przez zwielokrotnienie jego wybranych krawędzi. Centralnym problemem
otwartym dotyczącym tego parametru jest hipoteza sformułowana w pracy z
1987 roku, której autorami byli Faudree i Lehel. Sugeruje ona, iż
istnieje stała $C$ taka, że $s(G)$ nie przekracza wartości $n/d+C$ dla każdego
$d$-regularnego grafu $G$ o $n$ wierzchołkach i $d>1$ (podczas gdy elementarne
rozumowanie polegające na podwójnym zliczaniu implikuje, iż $s(G)>n/d$).
Najlepszy znany wynik dotyczący postulowanego ograniczenia górnego
gwarantuje, że $s(G)< 6+6n/d$. Podczas referatu zarysuję ideę dowodu, iż
hipoteza ta jest asymptotycznie prawdziwa, jeżeli tylko $d$ nie jest ani
zbyt małe, ani zbyt duże w stosunku do $n$.