Toidas gissning

Inom kombinatorisk matematik är Toidas gissning , på grund av Shunichi Toida 1977, en förfining av den motbevisade Ádáms gissning från 1967.

Påstående

Båda gissningarna gäller cirkulerande grafer . Dessa är grafer definierade från ett positivt heltal $n$ och en uppsättning $S$ av positiva heltal. Deras hörn kan identifieras med siffrorna från 0 till $n-1$ , och två hörn $i$ och $j$ är förbundna med en kant närhelst deras skillnad modulo ${\ displaystyle n}$ tillhör uppsättningen $S$ . Varje symmetri i den cykliska gruppen av additionsmodulo $n$ ger upphov till en symmetri av de $n$ -vertex cirkulantgraferna, och Ádám antog (felaktigt) att dessa är de enda symmetrierna i cirkulationsgraferna.

De kända motexemplen till Ádáms gissning involverar dock uppsättningar $S$ där vissa element delar icke-triviala divisorer med $n$ . Toidas gissning säger att när varje medlem av $S$ är relativt primtal till $n$ , då är de enda symmetrierna i cirkulationsgrafen för $n$ och $S$ symmetrier kommer från den underliggande cykliska gruppen.

Bevis

Gissningen bevisades i det speciella fallet där n är en huvudkraft av Klin och Poschel 1978 och av Golfand, Najmark och Poschel 1984.

Förmodan bevisades sedan fullt ut av Muzychuk, Klin och Poschel 2001 genom att använda Schur algebra , och samtidigt av Dobson och Morris 2002 genom att använda klassificeringen av ändliga enkla grupper .