페일리 그래프
수학에서 페일리 그래프는 유한체에서 차가 제곱 잉여인 쌍을 변으로 연결하여 구성된 그래프이다. 페일리 그래프를 통해 그래프 이론의 도구를 정수론의 이차잉여에 적용할 수 있다.
페일리 그래프는 레이먼드 팔레이의 이름을 따서 명명되었고, 이차잉여로부터 아다마르 행렬을 구성하기 위한 페일리 구성과 밀접하게 관련되어 있다 틀:하버드 인용. 페일리 그래프는 틀:하버드 인용 본문 와 틀:하버드 인용 본문 에 의해 독립적으로 소개되었다. Sachs는 자기 보완성을, 에르되시와 레니는 대칭성을 연구하였다.
페일리 유향 그래프(틀:Llang)는 페일리 그래프와 비슷하게 구성한 유향 그래프이다. 이는 틀:Harvtxt에 의해, 이전에는 무작위 토너먼트에 의해서만 성립하는 것으로 알려진 성질인, 꼭짓점 집합의 모든 작은 부분집합이 어떤 꼭짓점에 의해 지배된다는 성질을 갖는 토너먼트를 구성하는 방법으로써 Sachs, 에르되시, 레니와 독립적으로 도입되었다.
정의
는 를 만족하는 소수의 거듭제곱이라고 하자. 즉, 는 피타고라스 소수 (4를 법으로 하여 1과 합동인 소수)의 임의의 거듭제곱이거나, 또는 홀수 비 피타고라스 소수의 짝수 거듭제곱이다. 이러한 를 선택하였을 때 위수가 인 유한체 에서 −1은 제곱근을 갖는다.
, 라고 하자.
가 에 포함되어 있을 때, 와 의 순서는 중요하지 않다. −1이 제곱근을 가지므로 −1은 에서 제곱수이고, 가 제곱수인 것과 가 제곱수인 것은 동치이기 때문이다.
차수가 인 페일리 그래프는 이다.
예시
의 경우, 는 13을 법으로 하는 모듈러 산술을 갖는다. 13을 법으로 하여 제곱근을 갖는 수는 다음 여섯 개이다.
- ±1(+1은 ±1의 제곱, −1은 ±5의 제곱)
- ±3(+3은 ±4의 제곱, −3은 ±6의 제곱)
- ±4(+4는 ±2의 제곱, −4는 ±3의 제곱).
페일리 그래프는 [0,12] 범위의 각 정수를 꼭짓점으로 가지고, 각 정수 를 여섯 개의 이웃 , , 과 연결하는 변을 갖는다.
성질
페일리 그래프의 여 그래프는 자기 자신과 동형이다. 한 가지 자기 동형은 법 q에서 어떤 비이차잉여 k를 고정하고 정점 x를 xk로 사상하여 얻을 수 있다. 틀:하버드 인용.
Paley 그래프는 매개변수 를 갖는 강한 정규 그래프이다.
응용
- 위수 9의 Paley 그래프는 국소적 선형 그래프, 룩 그래프, 3-3 듀오프리즘의 그래프이다.
- 위수 13의 Paley 그래프는 책 두께(Book embedding)가 4이고 대기열 번호가 3입니다 틀:하버드 인용 .
- 위수가 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인 유한체 에서는 −1이 제곱근을 갖지 않는다. 따라서, 의 서로 다른 원소로 이루어진 순서쌍 (a, b)에서 a-b 와 b-a 중 정확히 하나만이 제곱수이다. 페일리 유향 그래프(틀:Llang)는 정점 집합 와 호 집합 을 갖는 유향 그래프이다.