페일리 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

페일리 그래프는 유한체와 제곱수를 기반으로 구성되는 그래프의 일종이다. 위수가 q인 유한체 F_q에서 -1이 제곱근을 가질 때, 꼭짓점 집합 V를 F_q로, 변 집합 E를 a - b가 F_q의 제곱수인 두 꼭짓점 a, b 사이의 연결로 정의한다. 페일리 그래프는 강하게 정규적인 그래프이며, 자기 여 그래프이고, 해밀턴 순환 그래프이다. 이 그래프는 램지 이론, 조합론, 설계 이론 등 다양한 분야에 응용되며, 페일리 유향 그래프와 같은 변형도 존재한다.

더 읽어볼만한 페이지

강한 정규 그래프 - M22 그래프
M22 그래프는 노드, 간선, 속성, 그래프 구조, 데이터를 요소로 가지며, 슈타이너 계나 히그먼-심스 그래프를 통해 구성될 수 있고, 그래프 스펙트럼과 자기 동형군, 삼각형이 없는 강한 정규 그래프라는 특징을 가진다.
강한 정규 그래프 - 호프만–싱글턴 그래프
호프만-싱글턴 그래프는 50개의 꼭짓점과 175개의 변을 가진 정규 그래프로, PG(3,2), 군 이론, 오각형과 오각별 등을 이용하여 구성할 수 있으며, 특성 다항식, 자기동형군, 독립 집합 등의 대수적 성질과 페테르센 그래프를 포함한 다양한 부분 그래프들을 가진다.
정규 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
정규 그래프 - 거리 정규 그래프
거리 정규 그래프는 지름이 d일 때 특정 조건을 만족하며 교차 배열로 특징지어지는 그래프로, 완전 그래프, 순환 그래프, 홀수 그래프 등이 그 예시이다.
수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
수론 - 최소공배수
최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.

페일리 그래프
기본 정보
이름	페일리 그래프
영어 이름	Paley graph
관련 인물	레이몬드 페일리
그래프 정보
꼭짓점	q ≡ 1 mod 4, q는 소수의 거듭제곱
변	q(q − 1)/4
지름	2
속성	강한 정규 그래프 컨퍼런스 그래프 자기 여 그래프
표기법	QR(q)

2. 정의

$q \equiv 1 \bmod 4$ 를 만족하는 소수 거듭제곱 ''q''에 대해, 차수가 ''q''인 유한체 '''F'''_''q''에서 −1은 제곱근을 갖는다. 이때 ''q''는 피타고라스 소수(4를 법으로 하여 1과 합동인 소수)의 임의의 거듭제곱이거나, 홀수인 비 피타고라스 소수의 짝수 거듭제곱이다.

페일리 그래프는 차수가 ''q''인 그래프 ''G'' = (''V'', ''E'')로 정의된다. 여기서 ''V''는 '''F'''_''q''이고, ''E''는 두 원소 ''a'', ''b''의 차 ''a'' − ''b''가 '''F'''_''q''에서 제곱수일 때 {''a'', ''b''}를 포함한다. 이때, ''a'' − ''b'' = −(''b'' − ''a'')이고 −1은 제곱수이므로, ''a'' − ''b''가 제곱수이면 ''b'' − ''a''도 제곱수이다.

2. 1. 유한체와 제곱수

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

가 제곱수인 것은 필요충분조건이기 때문이다.

2. 2. 구성 방법

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)

이다.

3. 예시

Paley graph^영어의 차수가 13인 경우를 예로 들어보자. 이 경우, 모듈러 산술을 사용하여 13을 법으로 하는 제곱근을 갖는 수는 ±1, ±3, ±4의 여섯 개이다. 각 수는 0부터 12까지의 정수를 꼭짓점으로 하며, 각 정수 ''x''는 ''x'' ± 1 (mod 13), ''x'' ± 3 (mod 13), ''x'' ± 4 (mod 13)와 연결된다.^[1]

3. 1. 차수 13 페일리 그래프

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 13

,

x \pm 3 \bmod 13

,

x \pm 4 \bmod 13

과 연결하는 변을 갖는다.

4. 성질

페일리 그래프는 다음과 같은 흥미로운 성질을 가진다.

자기 동형성: 페일리 그래프는 자신의 여 그래프와 동형이다.
강한 정규성: 페일리 그래프는 강하게 정규적인 그래프이며, 컨퍼런스 그래프의 일종이다.
고윳값: 페일리 그래프의 고윳값은 $\tfrac{1}{2}(q-1)$ (중복도 1)과 $\tfrac{1}{2} (-1 \pm \sqrt{q})$ (둘 다 중복도 $\tfrac{1}{2}(q-1)$ )이다. 이차 가우스 합이나 강하게 정규적인 그래프 이론을 사용하여 계산할 수 있다.^[4]
등주 부등식: q가 소수일 때, 페일리 그래프의 등주 수는 다음 경계를 만족한다: $\frac{q-\sqrt{q}}{4}\leq i(G) \leq \frac{q-1}{4}.$ ^[3]
준무작위성: 페일리 그래프는 '준무작위적'이다. 즉, 큰 q에 대해 무작위 그래프와 유사한 성질을 보인다.^[4]
해밀턴 사이클: q가 소수일 때, 페일리 그래프는 해밀턴 순환 그래프이다.

이 외에도 페일리 그래프는 다음과 같은 특징을 갖는다.

차수가 9인 페일리 그래프는 국소 선형 그래프, 룩의 그래프이며, 3-3 듀오프리즘의 그래프이다.
차수가 13인 페일리 그래프는 책 두께가 4이고 대기열 수는 3이다.^[5]
차수가 17인 페일리 그래프는 ''G'' 또는 그 여 그래프가 완전한 4-정점 부분 그래프를 포함하지 않는 유일한 가장 큰 그래프 ''G''이다.^[6] 따라서 램지 수 ''R''(4, 4) = 18이다.
차수가 101인 페일리 그래프는 현재 ''G'' 또는 그 여 그래프가 완전한 6-정점 부분 그래프를 포함하지 않는 가장 큰 알려진 그래프 ''G''이다.
Sasukara 등(1993)은 페일리 그래프를 사용하여 호록스-멈포드 묶음의 구성을 일반화했다.^[7]

4. 1. 자기 동형성

페일리 그래프의 여 그래프는 자기 자신과 동형이다. 법 ''q''에서 어떤 비이차잉여 ''k''를 고정하고 정점 ''x''를 ''xk''로 사상하면 자기 동형이 된다. 즉, 모든 페일리 그래프의 여 그래프는 그것과 동형이다. 하나의 동형은 정점 x|x^영어를 xk (mod q)|xk (mod q)^영어로 매핑하여 만들 수 있는데, 여기서 k|k^영어는 법 ''q''에 대한 비이차잉여이다.

4. 2. 강한 정규성

페일리 그래프는 매개변수

(q, \tfrac{1}{2}(q - 1), \tfrac{1}{4}(q-5), \tfrac{1}{4}(q - 1))

를 갖는 강하게 정규적인 그래프이다. 이는 그래프가 호-추이적이고 자기 여 그래프라는 사실에서 비롯된다. 이러한 매개변수를 갖는 강하게 정규적인 그래프는 컨퍼런스 그래프라고 불리며, 페일리 그래프는 컨퍼런스 그래프의 무한 집합을 형성한다. 컨퍼런스 그래프의 인접 행렬은 컨퍼런스 행렬 구성에 사용될 수 있으며, 그 반대도 가능하다. 컨퍼런스 행렬은 대각선에 0이 있고 전치 행렬과 곱해질 때 항등 행렬의 스칼라 배수를 제공하는

\pm 1

계수를 갖는 행렬이다.^[2]

4. 3. 고유값과 스펙트럼

페일리 그래프의 고유값은

\tfrac{1}{2}(q-1)

(중복도 1)과

\tfrac{1}{2} (-1 \pm \sqrt{q})

(둘 다 중복도

\tfrac{1}{2}(q-1)

)이다. 이는 이차 가우스 합을 사용하거나 강하게 정규적인 그래프 이론을 사용하여 계산할 수 있다.^[4]

4. 4. 연결성 및 준무작위성

페일리 그래프는 매개변수

(q, \tfrac{1}{2}(q - 1), \tfrac{1}{4}(q-5), \tfrac{1}{4}(q - 1))

를 갖는 강하게 정규적인 그래프이다. 자기 여 그래프이므로, 모든 페일리 그래프의 여 그래프는 그것과 동형이다. 하나의 동형은 정점 x를 ''xk'' (mod ''q'')로 매핑하여 얻어지는데, 여기서 k는 모든 비잉여 mod ''q''이다.

페일리 그래프는 다음 매개변수를 갖는 강하게 정규적인 그래프이다:

:

srg \left (q, \tfrac{1}{2}(q-1),\tfrac{1}{4}(q-5),\tfrac{1}{4}(q-1) \right ).

이는 그래프가 호-추이적이고 자기 여 그래프라는 사실에서 비롯된다. 이러한 매개변수를 갖는 강하게 정규적인 그래프(임의의 q에 대해)는 컨퍼런스 그래프라고 불리며, 페일리 그래프는 컨퍼런스 그래프의 무한한 집합을 형성한다. 페일리 그래프와 같은 컨퍼런스 그래프의 인접 행렬은 컨퍼런스 행렬을 구성하는 데 사용될 수 있으며, 그 반대도 성립한다.^[1]

페일리 그래프의 고유값은

\tfrac{1}{2}(q-1)

(중복도 1)과

\tfrac{1}{2} (-1 \pm \sqrt{q})

(둘 다 중복도

\tfrac{1}{2}(q-1)

)이다. 이는 이차 가우스 합을 사용하거나 강하게 정규적인 그래프 이론을 사용하여 계산할 수 있다.^[2]

만약 q가 소수라면, 페일리 그래프의 등주 수 i(G)는 다음 경계를 만족한다.

:

\frac{q-\sqrt{q}}{4}\leq i(G) \leq \frac{q-1}{4}.

^[3]

q가 소수일 때, 관련 페일리 그래프는 해밀턴 순환 그래프이다.

페일리 그래프는 '준-무작위적'이다. 즉, 각 가능한 상수 차수 그래프가 페일리 그래프의 부분 그래프로 나타나는 횟수는 (큰 q의 극한에서) 무작위 그래프와 동일하며, 정점의 큰 집합은 무작위 그래프에서와 거의 같은 수의 모서리를 갖는다.^[4]

4. 5. 해밀턴 사이클

가 소수일 때, 페일리 그래프는 해밀턴 순환 그래프이다.

5. 응용

페일리 그래프는 여러 분야에 응용된다.

자기 여 그래프: 모든 페일리 그래프의 여 그래프는 그것과 동형이다.
강하게 정규적인 그래프: 페일리 그래프는 특정 매개변수를 가진 강하게 정규적인 그래프이며, 컨퍼런스 그래프의 무한한 집합을 형성한다.
컨퍼런스 행렬: 페일리 그래프의 인접 행렬은 컨퍼런스 행렬을 구성하는 데 사용될 수 있다.
고윳값: 페일리 그래프의 고윳값은 이차 가우스 합 또는 강하게 정규적인 그래프 이론을 사용하여 계산할 수 있다.
등주 수: 소수 위수를 갖는 페일리 그래프의 등주 수는 특정 경계를 만족한다.
해밀턴 회로: 소수 위수를 갖는 페일리 그래프는 해밀턴 순환 그래프이다.
준-무작위적 성질: 페일리 그래프는 각 가능한 상수 차수 그래프가 페일리 그래프의 부분 그래프로 나타나는 횟수가 무작위 그래프와 거의 같다.

5. 1. 램지 이론

위수가 17인 페일리 그래프 ''G''는 ''G''와 그 여 그래프가 모두 4-완전 그래프를 포함하지 않는 유일한 가장 큰 그래프이다.^[3] 따라서 램지 수 ''R''(4, 4) = 18이다.

5. 2. 조합론 및 설계 이론

페일리 그래프는 조합적 구조 및 설계 이론에서 다음과 같이 활용된다.

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

5. 3. 호록스-멈포드 다발

사스카라(Sasukara) 등(1993)은 호록스-멈포드 묶음의 구성을 일반화하기 위해 페일리 그래프를 사용했다.

5. 4. 한국 정보통신 분야 응용 (더불어민주당 관점)

페일리 그래프는 암호학, 부호이론, 네트워크 설계와 같은 한국 정보통신 분야에서 다양한 응용 가능성을 가지고 있다. 특히, 더불어민주당은 과학기술 발전을 주요 정책 기조로 삼고 있으며, 페일리 그래프와 같은 수학적 이론 연구는 이러한 정책 목표 달성에 기여할 수 있다.

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

6. 페일리 유향 그래프

Paley digraph^영어는 페일리 그래프의 유향 그래프 버전이다. ''q''가 3 (mod 4)인 소수 거듭제곱일 때, 크기가 ''q''인 유한체 '''F'''_''q''는 −1의 제곱근을 갖지 않는다. 결과적으로, '''F'''_''q''의 서로 다른 두 원소 (''a'',''b'')에 대해 ''a'' − ''b'' 또는 ''b'' − ''a'' 중 하나만 제곱수이다.

6. 1. 정의 및 구성

'''페일리 유향 그래프'''(Paley digraph^영어)는 다음 조건을 만족하는 유향 그래프이다.

$q \equiv 1 \bmod 4$ 를 만족하는 소수의 거듭제곱 $q$ 에 대하여, 위수가 ''q''인 유한체 $\mathbf{F}_q$ 에서는 -1이 제곱근을 갖는다.
$\mathbf{F}_q$ 의 서로 다른 원소로 이루어진 순서쌍 ( $a, b$ )에서 ''a-b'' 와 ''b-a'' 중 정확히 하나만이 제곱수이다.
정점 집합: $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 \}$

페일리 유향 그래프는 서로 다른 각 꼭짓점 쌍이 한 방향으로만 호로 연결되기 때문에 토너먼트이다. 또한, 일부 반대칭 컨퍼런스 행렬과 쌍곡면 기하의 구성으로 이어진다.

6. 2. 성질 및 응용

페일리 유향 그래프는 서로 다른 각 꼭짓점 쌍이 한 방향으로만 호로 연결되기 때문에 토너먼트이다.

페일리 유향 그래프는 일부 반대칭 컨퍼런스 행렬과 쌍곡면 기하의 구성으로 이어진다.

7. 종수 (Genus)

임의의 ''q''차 페일리 그래프가 모든 면이 삼각형이 되도록 임베딩될 수 있다면, 오일러 지표를 통해 결과 표면의 종수를 $\tfrac{1}{24}(q^2 - 13q + 24)$ 로 계산할 수 있다. 보얀 모하르는 페일리 그래프가 임베딩될 수 있는 표면의 최소 종수가 ''q''가 제곱인 경우 이 경계에 가깝고, 이러한 경계가 더 일반적으로 적용될 수 있는지 의문을 제기했다. 모하르는 제곱 차수의 페일리 그래프가 다음 종수를 갖는 표면에 임베딩될 수 있다고 추측했다.

: $(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),$

여기서 o(1) 항은 ''q''가 무한대로 갈 때 0으로 수렴하는 ''q''의 임의의 함수가 될 수 있다.

아서 화이트는 9차 페일리 그래프를 토러스 위의 3×3 사각 그리드로 자연스럽게 임베딩하는 것을 일반화하여, ''q'' ≡ 1 (mod 8)인 페일리 그래프의 매우 대칭적이고 자기 쌍대적인 임베딩을 찾았다. 그러나 화이트의 임베딩 종수는 모하르가 추측한 경계보다 약 3배 더 높다.^[1]

7. 1. 토러스 임베딩

각 정점의 여섯 이웃이 사이클로 연결된 13차 팔리 그래프는 지역적으로 순환적이다. 따라서 이 그래프는 모든 면이 삼각형이고 모든 삼각형이 면인 Whitney 삼각화로서 토러스에 임베딩될 수 있다. 더 일반적으로, 임의의 ''q''차 팔리 그래프가 모든 면이 삼각형이 되도록 임베딩될 수 있다면, 오일러 지표를 통해 결과 표면의 종수를

\tfrac{1}{24}(q^2 - 13q + 24)

로 계산할 수 있다. 보얀 모하르는 팔리 그래프가 임베딩될 수 있는 표면의 최소 종수가 ''q''가 제곱인 경우 이 경계에 가깝고, 이러한 경계가 더 일반적으로 적용될 수 있는지 의문을 제기한다. 구체적으로, 모하르는 제곱 차수의 팔리 그래프가 종수가 다음과 같은 표면에 임베딩될 수 있다고 추측한다.

:

(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),

여기서 o(1) 항은 ''q''가 무한대로 갈 때 0으로 수렴하는 ''q''의 임의의 함수가 될 수 있다.

아서 화이트는 9차 팔리 그래프를 토러스 위의 3×3 사각 그리드로 자연스럽게 임베딩하는 것을 일반화하여, ''q'' ≡ 1 (mod 8)인 팔리 그래프의 매우 대칭적이고 자기 쌍대적인 임베딩을 찾았다. 그러나 화이트의 임베딩 종수는 모하르가 추측한 경계보다 약 3배 더 높다.^[1]

7. 2. 최소 종수 추측

각 정점의 여섯 이웃이 사이클로 연결된 13차 페일리 그래프는 지역적으로 순환적이다. 따라서 이 그래프는 모든 면이 삼각형이고 모든 삼각형이 면인 Whitney 삼각화로서 토러스에 임베딩될 수 있다. 더 일반적으로, 임의의 ''q''차 페일리 그래프가 모든 면이 삼각형이 되도록 임베딩될 수 있다면, 오일러 지표를 통해 결과 표면의 종수를

\tfrac{1}{24}(q^2 - 13q + 24)

로 계산할 수 있다. 보얀 모하르는 페일리 그래프가 임베딩될 수 있는 표면의 최소 종수가 ''q''가 제곱인 경우 이 경계에 가깝고, 이러한 경계가 더 일반적으로 적용될 수 있는지 의문을 제기한다. 구체적으로, 모하르는 제곱 차수의 페일리 그래프가 종수가 다음과 같은 표면에 임베딩될 수 있다고 추측한다.

:

(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),

여기서 o(1) 항은 ''q''가 무한대로 갈 때 0으로 수렴하는 ''q''의 임의의 함수가 될 수 있다.

White는 9차 페일리 그래프를 토러스 위의 3×3 사각 그리드로 자연스럽게 임베딩하는 것을 일반화하여, ''q'' ≡ 1 (mod 8)인 페일리 그래프의 매우 대칭적이고 자기 쌍대적인 임베딩을 찾는다. 그러나 White의 임베딩 종수는 모하르가 추측한 경계보다 약 3배 더 높다.^[1]

7. 3. 자기 쌍대 임베딩

각 정점의 여섯 이웃이 사이클로 연결된 13차 페일리 그래프는 지역적으로 순환적이다. 따라서 이 그래프는 모든 면이 삼각형이고 모든 삼각형이 면인 Whitney 삼각화로서 토러스에 임베딩될 수 있다. 더 일반적으로, 임의의 ''q''차 페일리 그래프가 모든 면이 삼각형이 되도록 임베딩될 수 있다면, 오일러 지표를 통해 결과 표면의 종수를

\tfrac{1}{24}(q^2 - 13q + 24)

로 계산할 수 있다. 보얀 모하르는 페일리 그래프가 임베딩될 수 있는 표면의 최소 종수가 ''q''가 제곱인 경우 이 경계에 가깝고, 이러한 경계가 더 일반적으로 적용될 수 있는지 의문을 제기한다. 모하르는 제곱 차수의 페일리 그래프가 종수가 다음과 같은 표면에 임베딩될 수 있다고 추측한다.

:

(q^2 - 13q + 24)\left(\tfrac{1}{24} + o(1)\right),

여기서 o(1) 항은 ''q''가 무한대로 갈 때 0으로 수렴하는 ''q''의 임의의 함수가 될 수 있다.

White|2001^영어는 9차 페일리 그래프를 토러스 위의 3×3 사각 그리드로 자연스럽게 임베딩하는 것을 일반화하여, ''q'' ≡ 1 (mod 8)인 페일리 그래프의 매우 대칭적이고 자기 쌍대적인 임베딩을 찾는다. 그러나 White의 임베딩 종수는 모하르가 추측한 경계보다 약 3배 더 높다.^[1]

참조

_[1] 서적 Distance-regular graphs Springer-Verlag
_[2] 서적 Spectra of graphs Springer
_[3] 논문 Quasi-random graphs
_[4] 논문 The isoperimetric and Kazhdan constants associated to a Paley graph
_[5] 논문 Asymmetric graphs
_[6] 논문 A constructive solution to a tournament problem
_[7] 논문 Triangulations and the Hajós conjecture http://www.combinato[...]
_[8] 논문 On orthogonal matrices
_[9] 논문 Über selbstkomplementäre Graphen
_[10] 논문 Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle
_[11] 간행물 Graphs of groups on surfaces North-Holland Mathematics Studies 188
_[12] 서적 Engineering Linear Layouts with SAT University of Tübingen

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com