페일리 그래프

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

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

페일리 유향 그래프()는 페일리 그래프와 비슷하게 구성한 유향 그래프이다. 이는 에 의해, 이전에는 무작위 토너먼트에 의해서만 성립하는 것으로 알려진 성질인, 꼭짓점 집합의 모든 작은 부분집합이 어떤 꼭짓점에 의해 지배된다는 성질을 갖는 토너먼트를 구성하는 방법으로써 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 중 정확히 하나만이 제곱수이다. 페일리 유향 그래프()는 정점 집합 와 호 집합 을 갖는 유향 그래프이다.

 종수 

 참고 문헌 














 외부 링크 



분류:수론
분류:정규 그래프
분류:강한 정규 그래프