페일리 그래프

페일리 그래프
위수가 13인 페일리 그래프
이름의 유래	레이몬드 페일리
꼭짓점	4로 나눈 나머지가 1인 소수의 거듭제곱 q
모서리	q(q - 1)/4
지름	2
특성	강한 정규 그래프
표기법	QR(q)

수학에서 페일리 그래프는 유한체에서 차가 제곱 잉여인 쌍을 변으로 연결하여 구성된 그래프이다. 페일리 그래프를 통해 그래프 이론의 도구를 정수론의 이차잉여에 적용할 수 있다.

페일리 그래프는 레이먼드 팔레이의 이름을 따서 명명되었고, 이차잉여로부터 아다마르 행렬을 구성하기 위한 페일리 구성과 밀접하게 관련되어 있다 (Paley 1933). 페일리 그래프는 Sachs (1962) 와 Erdős & Rényi (1963) 에 의해 독립적으로 소개되었다. Sachs는 자기 보완성을, 에르되시와 레니는 대칭성을 연구하였다.

페일리 유향 그래프(영어: Paley digraph)는 페일리 그래프와 비슷하게 구성한 유향 그래프이다. 이는 Graham & Spencer (1971)에 의해, 이전에는 무작위 토너먼트에 의해서만 성립하는 것으로 알려진 성질인, 꼭짓점 집합의 모든 작은 부분집합이 어떤 꼭짓점에 의해 지배된다는 성질을 갖는 토너먼트를 구성하는 방법으로써 Sachs, 에르되시, 레니와 독립적으로 도입되었다.

정의

$q$는 $q\equiv 1{\bmod {4}}$를 만족하는 소수의 거듭제곱이라고 하자. 즉, $q$는 피타고라스 소수 (4를 법으로 하여 1과 합동인 소수)의 임의의 거듭제곱이거나, 또는 홀수 비 피타고라스 소수의 짝수 거듭제곱이다. 이러한 $q$를 선택하였을 때 위수가 $q$인 유한체 $\mathbf {F} _{q}$에서 −1은 제곱근을 갖는다.

$V=\mathbf {F} _{q}$, $E=\left\{\{a,b\}:a-b\in (\mathbf {F} _{q}^{\times })^{2}\right\}$라고 하자.

$\{a,b\}$가 $E$에 포함되어 있을 때, $a$와 $b$의 순서는 중요하지 않다. −1이 제곱근을 가지므로 −1은 $\mathbf {F} _{q}$에서 제곱수이고, $a-b$가 제곱수인 것과 $b-a$가 제곱수인 것은 동치이기 때문이다.

차수가 $q$인 페일리 그래프는 $G=(V,E)$이다.

예시

$q=13$의 경우, $\mathbf {F} _{q}$는 13을 법으로 하는 모듈러 산술을 갖는다. 13을 법으로 하여 제곱근을 갖는 수는 다음 여섯 개이다.

• ±1(+1은 ±1의 제곱, −1은 ±5의 제곱)
• ±3(+3은 ±4의 제곱, −3은 ±6의 제곱)
• ±4(+4는 ±2의 제곱, −4는 ±3의 제곱).

페일리 그래프는 [0,12] 범위의 각 정수를 꼭짓점으로 가지고, 각 정수 $x$를 여섯 개의 이웃 $x\pm 1{\bmod {1}}3$, $x\pm 3{\bmod {1}}3$, $x\pm 4{\bmod {1}}3$과 연결하는 변을 갖는다.

성질

페일리 그래프의 여 그래프는 자기 자신과 동형이다. 한 가지 자기 동형은 법 q에서 어떤 비이차잉여 k를 고정하고 정점 x를 xk로 사상하여 얻을 수 있다. (Sachs 1962).

Paley 그래프는 매개변수 $(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4}}(q-1))$를 갖는 강한 정규 그래프이다.

응용

• 위수 9의 Paley 그래프는 국소적 선형 그래프, 룩 그래프, 3-3 듀오프리즘의 그래프이다.
• 위수 13의 Paley 그래프는 책 두께(Book embedding)가 4이고 대기열 번호가 3입니다 (Wolz 2018) .
• 위수가 17인 Paley 그래프 G는 G와 여 그래프가 모두 4-완전 그래프를 포함하지 않는 그래프 중 가장 큰 그래프이고, 이 크기에서 이 성질을 갖는 그래프는 G가 유일하다 (Evans et al. 1981). 따라서 램지 수 R (4, 4)=18이다.
• 위수가 101인 페일리 그래프 G는 G와 여 그래프가 모두 6-완전 그래프를 포함하지 않는 가장 큰 그래프이다.
• Sasukara et al. (1993)에서 Horrocks-Mumford 다발의 구성을 일반화하기 위해 페일리 그래프를 사용한다.

페일리 유향 그래프

$q$는 $q\equiv 1{\bmod {4}}$를 만족하는 소수의 거듭제곱이라고 하자. 즉, 위수가 q인 유한체 $\mathbf {F} _{q}$에서는 −1이 제곱근을 갖지 않는다. 따라서, $\mathbf {F} _{q}$의 서로 다른 원소로 이루어진 순서쌍 (a, b)에서 a-b 와 b-a 중 정확히 하나만이 제곱수이다. 페일리 유향 그래프(영어: Paley digraph)는 정점 집합 $V=\mathbf {F} _{q}$와 호 집합 $A=\left\{(a,b)\in \mathbf {F} _{q}\times \mathbf {F} _{q}\ :\ b-a\in (\mathbf {F} _{q}^{\times })^{2}\right\}$을 갖는 유향 그래프이다.

참고 문헌

• Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, A. J. (1996). “Maximal cliques in the Paley graph of square order”. 《J. Statist. Plann. Inference》 56: 33–38. doi:10.1016/S0378-3758(96)00006-7. 
• Broere, I.; Döman, D.; Ridley, J. N. (1988). “The clique numbers and chromatic numbers of certain Paley graphs”. 《Quaestiones Mathematicae》 11: 91–93. doi:10.1080/16073606.1988.9631945. 
• Chung, Fan R. K.; Graham, Ronald L.; Wilson, R. M. (1989). “Quasi-random graphs”. 《Combinatorica》 9 (4): 345–362. doi:10.1007/BF02125347. 
• Erdős, P.; Rényi, A. (1963). “Asymmetric graphs”. 《Acta Mathematica Academiae Scientiarum Hungaricae》 14 (3–4): 295–315. doi:10.1007/BF01895716. MR 0156334. 
• Evans, R. J.; Pulham, J. R.; Sheehan, J. (1981). “On the number of complete subgraphs contained in certain graphs”. 《Journal of Combinatorial Theory》. Series B 30 (3): 364–371. doi:10.1016/0095-8956(81)90054-X. 
• Graham, R. L.; Spencer, J. H. (1971). “A constructive solution to a tournament problem”. 《Canadian Mathematical Bulletin》 14: 45–48. doi:10.4153/CMB-1971-007-1. MR 0292715. 
• Mohar, Bojan (2005). “Triangulations and the Hajós conjecture”. 《Electronic Journal of Combinatorics》 12: N15. MR 2176532. 
• Paley, R.E.A.C. (1933). “On orthogonal matrices”. 《J. Math. Phys.》 12 (1–4): 311–320. doi:10.1002/sapm1933121311. 
• Sachs, Horst (1962). “Über selbstkomplementäre Graphen”. 《Publicationes Mathematicae Debrecen》 9: 270–288. MR 0151953. 
• Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka (1993). “Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle”. 《Proc. Japan Acad., Ser. A》 69 (5): 144–148. doi:10.3792/pjaa.69.144. 
•  White, A. T. (2001). 〈Graphs of groups on surfaces〉. 《Interactions and models》. Amsterdam: North-Holland Mathematics Studies 188. 
• Wolz, Jessica (2018). 《Engineering Linear Layouts with SAT》. Master's Thesis. University of Tübingen. 

외부 링크

• Brouwer, Andries E. “Paley graphs”. 
• Mohar, Bojan (2005). “Genus of Paley graphs”.