Problem z widmem z odwrotnym wykresem?

Zwykle buduje się wykres, a następnie zadaje pytania o rozkład macierzy przylegania (lub niektórych bliskich krewnych, takich jak Laplacian ), rozkład wartości własnych (zwany także widmami wykresu ).

Ale co z problemem odwrotnym? Biorąc pod uwagę wartości własne, można (efektywnie) znajduje się wykres, który ma tę widma? $n$

Podejrzewam, że ogólnie jest to trudne do zrobienia (i może być równoważne z GI), ale co, jeśli nieco złagodzisz niektóre warunki? Co się stanie, jeśli stworzysz warunki, że nie ma wielu wartości własnych? Co powiesz na zezwolenie na wykresy, które mają „bliskie” widma według niektórych wskaźników odległości?

Wszelkie referencje lub pomysły byłyby mile widziane.

EDYCJA :

Jak zauważa Suresh, jeśli zezwolisz na niekierowane ważone wykresy za pomocą pętli własnych, problem ten stanie się dość trywialny. Miałem nadzieję uzyskać odpowiedzi na zbiorze prostych, nieważonych prostych wykresów, ale byłbym również zadowolony z prostych nieważonych prostych wykresów.

ds.algorithms graph-theory graph-algorithms spectral-graph-theory użytkownik834
źródło

Myślę, że może być konieczne zmodyfikowanie pytania do „nieważonych grafów bezkierunkowych bez własnych pętli” czy coś takiego? Czy mogę sobie wyobrazić skonstruowanie macierzy diagonalnej z wymaganymi wartościami własnymi i zadeklarowanie jej jako odłączonego wykresu z ważonymi pętlami własnymi?

Suresh Venkat,

Jeszcze prostsze pytanie (nie znam odpowiedzi) brzmi: jak skonstruować proste połączone wykresy, dla których podano kilka najważniejszych wartości własnych

Jarosław Bułatow

Alternatywnym sposobem zadawania pytania (wersja z prostymi nieukierunkowanymi grafami) jest: biorąc n liczb rzeczywistych (w pewnym formacie), zdecyduj, czy istnieje n × n symetryczna macierz 0/1 z zerowymi przekątnymi, tak aby jej n wartościami własnymi były podane liczby.

Tsuyoshi Ito,

@Yaroslav: Nie jestem pewien, ale ten problem wydaje mi się trudniejszy niż w przypadku, gdy podane są wszystkie wartości własne.

Tsuyoshi Ito,

Małe spostrzeżenie: Jeśli nie mamy żadnych ograniczeń dotyczących wartości własnych, problem jest naprawdę trudny (nawet nie obejmując części algorytmicznej), ponieważ implikuje to (nie) istnienie 57-regularnego wykresu Moore'a , z których wszystkie znane są wartości własne.

Hsien-Chih Chang 之之

Odpowiedzi:

Cvetcovic i wszystko w rozdziale 3.3 „Ostatnie wyniki w teorii grafów widm” podchodzi algorytmów konstruowania grafy danego widma w niektórych szczególnych przypadkach

Jarosław Bułatow
źródło

Trudne jest nawet pytanie, czy istnieje wykres z danym spektrum. Świadczy o tym otwarty problem określania, czy istnieje wykres obwodu 5 o średnicy 2 i rzędu 3250, którego widmo (jeśli istnieje) jest znane.

Jernej
źródło

Inną przeszkodą w zdefiniowaniu pytania jest to, że są to wykresy izospektralne (te same wartości własne), ale grafy nieizomorficzne. Biorąc pod uwagę listę wartości własnych w takim przypadku, jaki wykres chcesz? Może po prostu chcesz, aby algorytm zwrócił jeden losowy element zestawu takich grafów nieizomorficznych?

dabacon
źródło

Myślałem o czymś podobnym do próbkowania z przestrzeni wykresów, które są izospektralne, ale wydaje się, że szybko schodzimy do problemu równoważnego GI (tak mój komentarz powyżej). Dla uproszczenia moglibyśmy ograniczyć się do wszystkich różnych wartości własnych (które, jeśli IIC zapewnia unikalny wykres), ale tak naprawdę staram się tylko zobaczyć, co jest znane.

user834,

Nie sądzę, aby różne wartości własne zapewniały odtwarzalność, oto niektóre widma wykresów izospektralnych z 7 węzłów yaroslavvb.com/upload/save/cstheory-isospectral.png

Jarosław

Lubię formułę losowego elementu. Chciałbym wiedzieć, czy jest to odpowiednik GI. Jednym z powodów, dla których interesuję się formulacją elementów losowych, jest pytanie postawione w mojej pracy z Arorą i Steurerem na temat unikalnych gier, czy wykresy o określonym spektrum mogą być ekspansjami dla małych zestawów. Intuicyjnie można mieć nadzieję, że losowy wykres z tym spektrum będzie najlepszym możliwym ekspanderem dla wszystkich ustawionych rozmiarów, a zatem wgląd w widma odwrotne może być tam przydatny.

Boaz Barak,

@Yaroslav: Dziękuję za ten link i dziękuję za poprawienie mnie!

user834

@ user834: Re: Twój komentarz na temat problemu równoważnego z GI. Należy zauważyć, że określenie izomorfizmu wykresów z ograniczoną wielokrotnością wartości własnej (w szczególności wykresów bez wielu wartości własnych) można wykonać w czasie wielomianowym.

Joshua Grochow