Maksymalny brak równowagi na wykresie?

Niech $G$ być połączony wykres $G = (V,E)$ z węzłami $V = 1 \dots n$ , a krawędzie $E$ . Niech $w_i$ oznacza (całkowitą) wagę wykresu $G$ , przy czym $\sum_i w_i = m$ całkowita waga na wykresie. Średnia waga na węzeł wynosi wtedy $\bar w = m/n$ . Niech $e_i = w_i - \bar w$ oznacza odchylenie węzła $i$ od środka. Dzwonimynierównowagawęzła . $|e_i|$ $i$

Załóżmy, że waga między dowolnymi dwoma sąsiednimi węzłami może różnić się co najwyżej o $1$ , tj.

w_{i} - w_{j} \leq 1 \forall (i, j) \in E .

$w_i - w_j \le 1\; \forall (i,j) \in E.$

Pytanie : Jaka jest największa nierównowaga sieć może mieć pod względem $n$ oraz $m$ ? Aby być bardziej precyzyjnym, wyobraź sobie wektor $\vec{e} = (e_1, \dots, e_n)$ . Byłbym równie zadowolony z wyników dotyczących $||\vec{e}||_1$ lub $||\vec{e}||_2$ .

Dla $||\vec{e}||_\infty$ , prosty związany pod względem średnicy wykresu można znaleźć: Ponieważ wszystkie $e_i$ muszą sumować się do zera, jeśli istnieje duża dodatnia $e_i$ , musi gdzieś być ujemny $e_j$ . Stąd ich różnica $|e_i - e_j|$ jest przynajmniej $|e_i|$ , ale ta różnica może wynosić co najwyżej najkrótszą odległość między węzłami $i$ i $j$ , co z kolei może wynosić co najwyżej średnicę wykresu.

Interesują mnie silniejsze granice, najlepiej dla $1$ - lub $2$ normalnej. Przypuszczam, że powinna ona obejmować pewną teorię grafów spektralnych, aby odzwierciedlić łączność grafu. Próbowałem wyrazić to jako problem maksymalnego przepływu, ale bezskutecznie.

EDYCJA: Więcej wyjaśnień. Interesuje mnie $1$ - lub $2$ norma, ponieważ dokładniej odzwierciedlają one całkowity brak równowagi. Trywialna relacja zostałaby uzyskana z $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$ i . Spodziewam się jednak, że ze względu na połączenie wykresu i moje ograniczenie różnicy obciążeń między sąsiednimi węzłami,inorma powinny być znacznie mniejsze. $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$ $1$ $2$

Przykład: Hypercube o wymiarze d, przy . Ma średnicę . Maksymalny brak równowagi wynosi wtedy co najwyżej . Sugeruje to, jako górne ograniczenie dla -norm . Jak dotąd nie byłem w stanie skonstruować sytuacji, w której jest to faktycznie uzyskiwane, najlepsze, co mogę zrobić, to coś podobnego do $n = 2^d$ $d = \log_2(n)$ $d$ $1$ $nd = n\log_2(n)$ $||\vec{e}||_1 = n/2$ , gdzie osadzam cykl w Hypercube, a węzły mają nierównowagę , , , itd. Więc tutaj granica jest wyłączona przez współczynnik , który uważam już za bardzo, ponieważ szukam (asymptotycznie) ciasnych granic. $0$ $1$ $0$ $-1$ $\log(n)$

graph-theory co.combinatorics spectral-graph-theory Lagerbaer
źródło

interesujące pytanie. czy jest jakaś konkretna aplikacja?

Suresh Venkat

@ András Salamon: Dziękujemy za edycję. @Suresh Venkat: Załóżmy, że wagi reprezentują liczbę agentów o jednakowych rozmiarach, którzy chcą zminimalizować swoje doświadczone obciążenie. Będą chcieli przejść z

jeśli

. Jeśli nikt nie chce się ruszać, nazywamy to równowagą Nasha. Pytanie: Jaki jest największy całkowity brak równowagi, jaki możemy mieć w równowadze Nasha?

i

$i$

j

$j$

w_{i} > w_{i}

$w_i > w_i$

Lagerbaer,

Czy zdarza ci się mieć przykład wykresu, na którym twoja prosta granica średnicy jest zbyt luźna?

mhum,

Cóż, mogę w prosty sposób powiązać pozostałe dwie normy, używając

. Interesuje mnie

- lub

norma, ponieważ dokładniej wychwytują „całkowity” brak równowagi. Dodałem przykład do mojego pytania.

| | \vec{e} | |_{1} \leq n | | \vec{e} | |_{\infty}

$||\vec{e}||_1 \leq n||\vec{e}||_\infty$

1

$1$

2

$2$

Lagerbaer,

Co do hipersześcianu, co jeśli ważymy wierzchołki według ich masy Hamminga? Dostaję coś takiego jak

dla

i myślę, że

będzie rzędu

\sqrt{d (n - 2)} / 2

$\sqrt{d(n - 2)}/2$

l_{2}

$l_2$

l_{1}

$l_1$

n d

$nd$

Artem Kaznatcheev

Odpowiedzi:

Ponieważ jest ograniczony przez średnicę , norma będzie trywialnie ograniczona przez , podobnie dla normy , z wyjątkiem $|e_i|$ $d$ $\ell_1$ $nd$ $\ell_2$ (w rzeczywistościnormajest ograniczona przez). $\sqrt{n}d$ $\ell_p$ $n^{1/p}d$

przypadek okazuje się być zaskakująco łatwe do analizy. $\ell_1$

W przypadku ścieżki łatwo zauważyć, że to , więc nie możesz zrobić nic lepszego niż . $\|\vec e\|_1$ $O(n^2)$ $O(nd)$

Aby uzyskać pełne drzewo -ary, możesz podzielić je na pół w katalogu głównym, ustawiając , rosnąco po jednej stronie i malejąco po drugiej, aż liście będą miały , wytwarzając ponownie ponownie. $k$ $w_{\text{root}} = 0$ $|e_i| = |w_i| = \log_k n$ $O(n\log_k n) = O(nd)$

W przypadku kliki tak naprawdę nie ma znaczenia, w jaki sposób rozkładasz ciężary, ponieważ będą one znajdować się w odległości od siebie, a to da ponownie. $1$ $O(n) = O(nd)$

Kiedy zdasz sobie sprawę, że mówimy tutaj o funkcji , a następnie przyjmujemy jej normę , o ile możesz dowolnie rozdzielić ciężary równomiernie w całym zakresie, granica będzie równa . $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$ $\ell_1$ $e_i \in [-d/2,d/2]$ $O(nd)$

Jedynym sposobem na zmianę tego jest granie w gry z masą. Na przykład, jeśli masz kilka gigantycznych klik w punktach, które są koniecznie zrównoważone, jak gigantyczna klika z dwoma wystającymi z niej ścieżkami o równej długości, możesz liczyć na granicę tylko (na przykład) . $O(d^2)$

Może to w pewnym stopniu dotyczyć ekspanderów, ale nie jestem pewien. Mogę sobie wyobrazić przypadek, w którym ustawiłeś na zwykłym wykresie, a następnie pozwoliłem, aby wartości rosły z każdym skokiem. Wydaje się prawdopodobne, że średnia mogłaby mieć największą masę, ale nie wiem, czy wystarczyłaby, aby wpłynąć na granicę. $w_1 = 0$

Myślę, że można rozumować podobnie około . $\ell_2$

EDYTOWAĆ:

$\ell_2$ $O(|E|/\lambda_2(L))$

Josephine Moeller
źródło

e_{i} = d / 2

$e_i = d/2$

O (n d)

$\mathcal{O}(nd)$

e_{i}

$e_i$

w_{i}

$w_i$

e_{i}

$e_i$

O (n d)

$O(nd)$

Pozwól, że podam inny przykład. Wykres dumbell z dwiema klikami ma bardzo niskie przewodnictwo, ale jego brak równowagi jest ograniczony przez 2.

Josephine Moeller

Granica związana ze strukturą byłaby czymś, z czego byłbym całkowicie zadowolony. Dlatego wspomniałem o wartościach własnych, ponieważ odnoszą się one do właściwości połączenia. Istnieją np. Granice średnicy, średniej ścieżki, liczby izoperymetrycznej itp. W kategoriach drugiego najmniejszego wektora własnego macierzy Laplaciana na wykresie.

Lagerbaer,

2 / n

$2/n$

$|w_i - 1/n\sum_k w_k|$ $w_k$ $w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i + w_i$ $w_k, v_1,...,v_k, w_i$ $w_i$ $w_k$ $w_{ki} = w_k - v_1 + v_1 - v_2 + v_2 - ... - v_k + v_k - w_i$

| w_{i} - 1 / n \sum_{k} w_{k} | = | w_{i} - 1 / n \sum_{k} (w_{k i} + w_{i}) | = | \sum_{k \neq i} \frac{w_{k i}}{n} |

$|w_i - 1/n\sum_k w_k| = |w_i - 1/n\sum_k (w_{ki} + w_i)| = |\sum_{k\neq i} \frac{w_{ki}}{n}|$

$w_{ki}$ $i$ $k$ $w_i - w_j \leq 1$ $i,j\in E$

| w_{i} - 1 / n \sum_{k} w_{k} | \leq \frac{(n - 1)}{n} D

$|w_i - 1/n\sum_k w_k| \leq \frac{(n-1)}{n} D$

$k$ $D+1$ $k$ $n$ $m$ $D+1$ $D$

Nicholas Ruozzi
źródło

D < \infty

$D<\infty$

0

$0$

0

$0$

k

$k$

k (n - 1) / n

$k(n-1)/n$

k

$k$

n

$n$

k

$k$ może być tak duży, jak to pożądane.

András Salamon,

G

$G$

| | \vec{e} | |_{\infty}

$||\vec{e}||_\infty$