Toidas domněnka - Toidas conjecture - Wikipedia

v kombinační matematika, Toidova domněnka, kvůli Shunichi Toida v roce 1977,^[1] je zdokonalení vyvrácených Ádámova domněnka z roku 1967.

Prohlášení

Obě dohady se týkají oběhové grafy. Jedná se o grafy definované z kladného celého čísla ${ displaystyle n}$ a sada ${ displaystyle S}$ kladných celých čísel. Jejich vrcholy lze identifikovat pomocí čísel od 0 do ${ displaystyle n-1}$a dva vrcholy ${ displaystyle i}$ a ${ displaystyle j}$ jsou spojeny hranou, kdykoli je jejich rozdíl modulo ${ displaystyle n}$ patří do sady ${ displaystyle S}$. Každá symetrie cyklická skupina přidání modulo ${ displaystyle n}$vede k symetrii ${ displaystyle n}$-vertexové cirkulační grafy a Ádám se domníval (nesprávně), že to jsou jediné symetrie cirkulačních grafů.

Známé protiklady Ádámovy domněnky však zahrnují množiny ${ displaystyle S}$ ve kterém některé prvky sdílejí netriviální dělitele ${ displaystyle n}$Toidova domněnka říká, že když každý člen ${ displaystyle S}$ je relativně prime na ${ displaystyle n}$, pak jediné symetrie cirkulačního grafu pro ${ displaystyle n}$ a ${ displaystyle S}$ jsou symetrie pocházející z podkladové cyklické skupiny.

Důkazy

Domněnka byla prokázána ve zvláštním případě, kdy n je hlavní silou Klin a Poschel v roce 1978,^[2] a Golfand, Najmark a Poschel v roce 1984.^[3]

Dohad byl poté plně prokázán Muzychukem, Klinem a Poschelem v roce 2001 použitím Schurova algebra,^[4] a současně Dobsonem a Morris v roce 2002 pomocí klasifikace konečných jednoduchých skupin.^[5]

Poznámky

Tento teorie čísel související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.