로바스 추측

그래프 이론에서 로바스 추측(1969년)은 그래프의 해밀턴 경로에 관한 고전적인 문제다.다음과 같이 적혀 있다.

모든 유한 연결 정점 변환 그래프에는 해밀턴 경로가 포함되어 있다.

원래 Laszlo Lovász는 그 문제를 정반대로 진술했지만, 이 버전은 표준이 되었다.1996년, 라슬로 바바이는 이 추측을 날카롭게 반박하는 추측을 발표했지만,^[1] 두 추측 모두 여전히 널리 열려 있다.하나의 counterrexample이 반드시 일련의 counterrexample로 이어질지는 알 수 없다.

역사적 발언

매우 대칭적인 그래프에서 해밀턴 경로를 찾는 문제는 꽤 오래되었다.도날드 크누스가 <컴퓨터 프로그래밍의 기술> 제4권에 기술한 바와 같이,^[2] 문제는 영국의 야영학(벨링)에서 비롯되었다.그러한 해밀턴의 경로와 사이클은 그레이 코드와도 밀접하게 연결되어 있다.각각의 경우에 구조는 명백하다.

로바스 추측의 변형

해밀턴 사이클

또 다른 버전의 로바스 추측은 다음과 같이 말한다.

모든 유한 연결 정점 변환 그래프는 알려진 5개의 백점샘플을 제외하고 해밀턴 사이클을 포함한다.

해밀턴 사이클이 없는 정점 변환 그래프의 알려진 예는 5가지로 알려져 있다(그러나 해밀턴 경로로는), 전체 그래프 ${\displaystyle {K\mathrm{}}_{}}$ ${\$ 피터슨 그래프, 콕시터 그래프 및 각 정점을 삼각형으로 대체하여 피터슨 및 콕시터 그래프에서 파생된 두 개의 그래프).^[3]

케이리 그래프

해밀턴 주기가 없는 5개의 정점 변환 그래프 중 케이리 그래프는 없다.이러한 관찰은 다음과 같은 추측을 더 약하게 만든다.

연결된 모든 유한한 Cayley 그래프에는 해밀턴 사이클이 포함되어 있다.

Cayley 그래프 공식의 장점은 그러한 그래프가 유한 $그룹{\displaystyle }$ G ${\displaystyle G}$과 생성 $세트{\displaystyle }$ S ${\displaystyle S}$에 대응한다는 것이다$.$ 따라서 추측이$$ 완전한 일반성으로 공격하기보다는 어떤 $G{\displaystyle }$ ${\displaystyle G}$과 $S{\displaystyle }$ ${\displaystyty$ S$}$을 가질 것을 요구할 수 있다.

방향 케이리 그래프

지시된 Cayley 그래프에 대해 Lovasz의 추측은 거짓이다.로버트 알렉산더 랭킨에 의해 다양한 배아들이 얻어졌다.그럼에도 불구하고, 아래의 결과들 중 많은 것들이 이 제한적인 환경에 있다.

특례

아벨리아 집단의 모든 지도층 케이리 그래프에는 해밀턴의 경로가 있지만, 주력이 아닌 모든 주기층에는 해밀턴의 주기가 없는 지도층 케이리 그래프가 있다.^[4]1986년 D.위테는 로바스 추측이 p-그룹들의 케이리 그래프를 지탱하고 있음을 증명했다.특수 발전기의 경우 일부 진전이 있었지만, 다이헤드 그룹에도 개방되어 있다.

그룹 $G{\displaystyle }$= ${\displaystyle {Sn}_{}}$ ${\$가 대칭 그룹일 경우 매력적인 생성 세트가 많다.예를 들어, Lovász 추측에는 다음과 같은 세트 생성 사례가 있다.

• ${\displaystyle a}$=${\displaystyle }$( ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$… ,${\displaystyle n}$)${\displaystyle }$, ${\displaystyle b}$=${\displaystyle }$( ${\displaystyle 1}$,${\displaystyle 2}$) ${\displaystyle a=(1,2,\buffer ,n),b=(1,2)}($긴 주기 및 전환).
• ${\displaystyle s_{}}$ ${\displaystyle {1\mathrm{}}_{}}$=${\displaystyle }$( ${\displaystyle 1}$,${\displaystyle }$2${\displaystyle }$)${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$= (${\displaystyle 2}$,${\displaystyle 3}$)${\displaystyle }$, …${\displaystyle {}_{}}$, s${\displaystyle {}_{}{\mathrm{n}}_{}}$- 1${\displaystyle }$= ( ${\displaystyle n}$- ${\displaystyle 1}$,${\displaystyle }$n ) ${\displaystyle s_{1$}=(1$,2), s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)}($Coxeter generator)이 경우 스타인하우스에 의해 해밀턴 사이클이 생성된다.존슨-트로터 알고리즘.
• $\{{\displaystyle 1}$,${\displaystyle 2}$, .${\displaystyle }$, ${\displaystyle n\}}$ ${\displaystyle \{1,2,..,n\}$에 있는 라벨링된 트리에 해당하는 모든 전이 세트$.$
• ${\displaystyle a=(1,2),b=(1,2)(3,4)\cdots,c=(2,3)(4,5)\cdots }$

Stong은 화환 제품 Z wr_m Z의_n Cayley 그래프에 대한 추측이 m이 짝수이거나 3일 때 자연적 최소 생성 설정이라는 것을 보여주었다.특히 이것은 화환 제품 Z₂ wr Z의_n Cayley 그래프로 생성될 수 있는 큐브 연결 사이클에 대한 것이다.^[5]

일반 그룹

일반 유한집단의 경우, 몇 가지 결과만 알려져 있다.

• ${\displaystyle S}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b}$ ${\displaystyle \},}$( ${\displaystyle b{}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle 1}$ ${\displaystyle S=\{a,b\},(ab)^{2}=1}($랭킹 생성기)
• ${\displaystyle S}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c}$ ${\displaystyle \},}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$= ${\displaystyle {}^{}{}^{}{2\mathrm{}}^{}}$=${\displaystyle }$[ ${\displaystyle a,}$ ${\displaystyle b}$ ${\displaystyle ]}$= ${\displaystyle 1}$ ${\displaystyle$ S$=\{a,b,c\},a^{2}=b^{2}={$2}=$c^{2}=[a,b$]=$1}($Raport-Straser 생성기)
• ${\displaystyle S}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c}$ ${\displaystyle \},}$ ${\displaystyle a}$ ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle 1}$,${\displaystyle {}^{}}$= a${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle a}$ ${\displaystyle S=\{a,b,c\},a^{2}=1,c=a^{-1}ba}($Pak–Radoichich 생성기^[6])
• ${\displaystyle S=\{a,b\},a^{2}=b^{s}=(ab)^{3}=1,}$ where ${\displaystyle G ,s=2~mod~4}$ (here we have (2,s,3)-presentation, Glover–Marušič theorem).^[7]

마지막으로, $모든{\displaystyle }$ 유한 그룹 G ${\displaystyle G}$에 대해 최대 ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle 2}$ ${\displaystyle {}_{}}$ G $displaystyle \log _{2} G }$에 크기 세트가 생성되어$$ 해당$$ Cayley 그래프가 Hamiltonian(Pak-Radoichich)인 것으로 알려져 있다.이 결과는 유한 단순 집단의 분류에 근거한다.

Lovasz 추측도 크기가 $\Omega {\displaystyle \mathrm{}}$(${\displaystyle {\log }^{}}$ ${\displaystyle {5\mathrm{}}^{}}$⁡ ${\displaystyle G}$) ${\displaystyle \Oomega (\log ^{5}$ G $)}$인 임의 생성 세트에 대해 설정되었다$.$^[8]

참조