프루히트의 정리

Frucht의 정리는^[1] 1936년 Dénes Kőnig가 추측한 대수 그래프 이론의 정리로서, 1939년 Robert Frucht에 의해 증명되었다.^[2]그것은 모든 유한집단이 유한한 비방향 그래프의 대칭집합이라고 기술하고 있다.보다 강하게 말하면, 어떤 유한 그룹 G의 경우, 각각의 자동 형태 집단이 G에 이형성인 것처럼 무한히 많은 비 이형성 단순 연결 그래프가 존재한다.

증명 아이디어

G의 생성자를 구별하기 위해 가장자리에 색과 방향을 추가한 G의 Cayley 그래프가 원하는 자동형성 그룹을 갖는다는 것이 증명서의 주요 생각이다.따라서 각 교체 서브그래프 자체가 비대칭이고 동일한 색상의 가장자리를 교체하는 경우에만 교체할 수 있도록 이러한 가장자리를 적절한 하위그래프로 교체할 경우, 이러한 대체 작업을 수행함으로써 생성된 비방향 그래프도 대칭 그룹으로 G가 된다.^[3]

그래프 크기

세 가지 예외를 제외하고, 모든 그룹은 정점이 궤도를 두 개만 갖는 그래프의 대칭으로 나타낼 수 있다.따라서 그래프의 정점 수는 그룹의 최대 2배이다.더 큰 예외 집합에서는 대부분의 유한 집단을 정점 변환 그래프의 대칭으로 나타낼 수 있으며, 정점 수는 집단의 순서와 같다.^[4]

그래프의 특수 패밀리

Frucht의 정리에는 어떤 제한된 그래프 패밀리가 여전히 어떤 대칭 그룹을 실현하기에 충분한 그래프를 포함하고 있다는 것을 보여주는 더 강력한 버전이 있다.Frucht는^[5] 실제로 원하는 속성을 가진 3-정규 그래프들이 많이 존재한다는 것을 증명했다. 예를 들어, Frucht 그래프는 12개의 정점과 18개의 가장자리를 가진 3-정규 그래프로서 비교 대칭이 없으며, 사소한 그룹에게 이러한 유형의 실현을 제공한다.Gert Sabidussi는 모든 양의 정수 k(일반 그래프의 경우$$ k${\displaystyle \mathrm{k}}$ 3 ${\displaystyle k\geq 3},$ k-chromatic 그래프의 경우$$ ${\displaystyle \mathrm{k}}$ 2 {\$displaystyle k\geq 2})$에 대해 어떤 그룹도 카운트할 수 있는 구별되는 k-정수 있는 k-정수 그래프, k-vertex 연결 그래프 또는 k-chromatic 그래프의 대칭 그룹으로 실현할 수 있음을 보여주었다.^[6]모든 그래프는 가장자리와 정점의 격납건물 부분순서에서 재구성될 수 있으며, 모든 유한 부분순서는 Birkhoff의 표현정리에 의해 유한한 분배 격자로 등가한다는 사실로부터, 모든 유한집단은 분배 격자의 대칭으로, 그리고 t의 그래프로 실현될 수 있다는 사실을 따른다.중앙 그래프인 격자.^[3]모든 유한 집단을 강한 정규 그래프의 대칭 집단으로 실현할 수 있다.^[7]모든 유한 그룹은 또한 두 번째를 구분하는 그래프의 대칭으로 실현될 수 있다: 하나는 그래프를 두 가지 색으로 색칠하여 그래프의 대칭이 색을 보존하지 않도록 할 수 있다.^[8]

그러나 일부 중요한 등급의 그래프는 모든 그룹을 대칭으로 실현할 수 없다.카밀 조던은 나무의 대칭 집단은 사소한 집단을 포함하는 가장 작은 유한 집단의 집합으로 서로 직접 생산물에 의해 닫히고 대칭 집단을 가진 화환 생산물이라고 특징지었는데,^[9] 특히 순서 3의 순환 집단은 나무의 대칭 집단이 아니다.평면 그래프 또한 그들의 대칭으로 모든 그룹을 실현하다. 예를 들면, 평면 그래프의 대칭이 유일한 유한 단순 군이 순환 단체와 교차되어 그룹 .[10]더 일반적으로, 모든minor-closed 그래프 가족에 의해 모든 유한한 단체들을 대표하는 수 없는 경우 5{\displaystyle A_{5}} 할 능력이 안된다. 그그래프의 ^[11]대칭라슬로 바바이는 더욱 강하게 각 미성년자 폐쇄형 가족이 단지 많은 비주기적 유한한 단순 집단만을 대표할 수 있다고 추측한다.^[12]

무한 그래프 및 그룹

Izbicki는 1959년에 이러한 결과를 확장시켰고, 어떤 유한 대칭 그룹을 실현하는 무한 그래프들이 셀 수 없이 많다는 것을 보여주었다.^[13]마침내 1959년/1960년 요하네스 드 그루트와 사비두시는 어떤 집단(집단이 유한하다는 가정을 떨어뜨림)도 무한 그래프의 대칭 집단으로 실현될 수 있다는 것을 독립적으로 증명했다.^[14][15]

참조

원천

• Babai, László (1995), "Automorphism groups, isomorphism, reconstruction" (PDF), in Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Handbook of Combinatorics, vol. II, North-Holland, pp. 1447–1540.
• de Groot, Johannes (1959), "Groups represented by homeomorphism groups", Mathematische Annalen, 138: 80–102, doi:10.1007/BF01369667, hdl:10338.dmlcz/101909, ISSN 0025-5831, MR 0119193.
• Frucht, Robert (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe.", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
• Frucht, Robert (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987.
• Izbicki, Herbert (1959), "Unendliche Graphen endlichen Grades mit vorgegebenen Eigenschaften", Monatshefte für Mathematik, 63 (3): 298–301, doi:10.1007/BF01295203, MR 0105372.
• Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen, Leipzig: Akademische Verlagsgesellschaft, p. 5. 바바이(1995)가 인용한 바와 같다.
• Sabidussi, Gert (1957), "Graphs with given group and given graph-theoretical properties", Canadian Journal of Mathematics, 9: 515–525, doi:10.4153/cjm-1957-060-7, ISSN 0008-414X, MR 0094810.
• Sabidussi, Gert (1960), "Graphs with given infinite group", Monatshefte für Mathematik, 64: 64–67, doi:10.1007/BF01319053, MR 0115935.