2025-11-14T13:52:11.419163

Eigenspace embeddings of imprimitive association schemes

Vidali

For a given symmetric association scheme $\mathcal{A}$ and its eigenspace $S_j$ there exists a mapping of vertices of $\mathcal{A}$ to unit vectors of $S_j$, known as the spherical representation of $\mathcal{A}$ in $S_j$, such that the inner products of these vectors only depend on the relation between the corresponding vertices; furthermore, these inner products only depend on the parameters of $\mathcal{A}$. We consider parameters of imprimitive association schemes listed as open cases in the list of parameters for quotient-polynomial graphs recently published by Herman and Maleki, and study embeddings of their substructures into some eigenspaces consistent with spherical representations of the putative association schemes. Using this, we obtain nonexistence for two parameter sets for $4$-class association schemes and one parameter sets for a $5$-class association scheme passing all previously known feasibility conditions, as well as uniqueness for two parameter sets for $5$-class association schemes.

academic

비원시 결합 방식의 고유공간 임베딩

기본 정보

논문 ID: 2504.08733
제목: Eigenspace embeddings of imprimitive association schemes
저자: Janoš Vidali (University of Ljubljana, Slovenia)
분류: math.CO (조합론)
제출 시간: 2025년 10월 16일 arXiv 제출
논문 링크: https://arxiv.org/abs/2504.08733

초록

주어진 대칭 결합 방식 $\mathcal{A}$ 와 그 고유공간 $S_j$ 에 대해, $\mathcal{A}$ 의 꼭짓점을 $S_j$ 의 단위 벡터로 매핑하는 구면 표현이 존재하며, 이들 벡터의 내적은 대응하는 꼭짓점 간의 관계에만 의존합니다. 또한 이러한 내적은 $\mathcal{A}$ 의 매개변수에만 의존합니다. 본 논문은 Herman과 Maleki가 최근 발표한 상 다항식 그래프 매개변수 목록에서 미해결 사례로 제시된 비원시 결합 방식 매개변수를 고려하여, 특정 고유공간으로의 부분 구조 임베딩 문제를 연구합니다. 이러한 임베딩은 가정된 결합 방식의 구면 표현과 일치합니다. 이 방법을 활용하여, 모든 알려진 가능성 조건을 만족하는 두 개의 4-클래스 결합 방식 매개변수 집합과 한 개의 5-클래스 결합 방식 매개변수 집합의 비존재성을 증명했으며, 두 개의 5-클래스 결합 방식 매개변수 집합의 유일성을 증명했습니다.

연구 배경 및 동기

해결할 문제: 본 논문은 결합 방식(association schemes)의 존재성과 유일성 문제, 특히 비원시 결합 방식을 연구합니다. 결합 방식은 조합론의 중요한 대상이며, 그 분류는 광범위하게 미해결된 문제입니다.
문제의 중요성: 결합 방식은 부호 이론, 설계 이론, 유한 기하학 등 여러 분야의 기초 구조입니다. 이러한 대상의 완전한 분류는 이들 분야의 기본 구조를 이해하는 데 중요한 의미를 갖습니다. 강정규 그래프(2-클래스 결합 방식)와 거리 정규 그래프 같은 특수 부분족에 대해서도 완전한 분류는 여전히 미해결 문제입니다.
기존 방법의 한계: 악수 보조정리, 절대 경계, Krein 매개변수 비음성 등의 전통적인 가능성 조건은 필요하지만 충분하지 않습니다. 많은 매개변수 집합이 모든 알려진 가능성 검증을 통과했지만, 실제로는 대응하는 결합 방식이 존재하지 않습니다.
연구 동기: 저자는 고유공간 임베딩 방법이라는 새로운 기술을 개발했으며, 결합 방식의 고유공간에서의 구면 표현을 연구하여 매개변수 집합의 가능성을 판단합니다. 이 방법은 비원시 결합 방식에 특히 적합한데, 이는 분석할 수 있는 더 작은 부분 구조를 가지기 때문입니다.

핵심 기여

고유공간 임베딩 기술 개발: 결합 방식의 부분 구조가 고유공간에 임베딩되는 방식을 연구하여 매개변수 집합의 가능성을 판단하는 새로운 방법을 제시했습니다.
세 가지 비존재성 결과 증명:
- 두 개의 4-클래스 결합 방식 매개변수 집합: [[12, 4, 4, 24], 6, 0, 3; 0, 1; 2]와 [[8, 8, 4, 24], 1, 0, 2; 2, 1; 1]
- 한 개의 5-클래스 결합 방식 매개변수 집합: [[6, 18, 2, 6, 12], 1, 0, 2, 0; 0, 0, 3; 0, 1; 2]
두 가지 유일성 결과 증명:
- 5-클래스 결합 방식 매개변수 집합 [[12, 2, 1, 12, 12], 6, 0, 4, 1; 0, 0, 1; 0, 1; 4]
- 5-클래스 결합 방식 매개변수 집합 [[6, 4, 4, 12, 18], 3, 0, 0, 1; 0, 1, 0; 2, 0; 2]
보조 소프트웨어 도구 개발: SageMath 기반의 eigenspace-embeddings 패키지를 개발하여 관련 알고리즘을 구현했습니다.
Herman-Maleki 데이터베이스의 체계적 분석: 상 다항식 그래프 매개변수 데이터베이스에 대한 포괄적인 가능성 검증을 수행하여 많은 불가능한 매개변수 집합을 식별했습니다.

각 꼭짓점 $x \in X$ 를 단위 벡터 $u_x = \sqrt{\frac{n}{m_j}}E_j 1_x$ 로 매핑
관계 $(x,y) \in R_i$ 에 대해 $\langle u_x, u_y \rangle = \frac{Q_{ij}}{m_j}$

2. 알고리즘 1: 고유공간 임베딩 알고리즘

입력: 고유공간 인덱스 j, 관계 행렬 C
출력: 단위 벡터 계수 행렬 U 또는 실패
for x = 1 to n' do
    h ← 1
    for y = 1 to x-1 do
        d ← C_xy - Σ(k=1 to h-1) a_xk * a_yk
        if h ≤ m_j ∧ a_yh ≠ 0 then
            a_xh ← d/a_yh; h ← h+1
        else if d ≠ 0 then 실패
    ||u_x||² 계산 및 1과의 동일성 검증

3. 비원시 결합 방식의 특수 구조

비자명한 원시 집합 $\tilde{0}$ 을 갖는 비원시 결합 방식의 경우:

꼭짓점 집합이 동치류 $\{X_\ell\}$ 로 분할됨
각 동치류 위의 유도된 부분 방식이 동일한 매개변수를 가짐
이러한 구조를 활용하여 더 작은 부분 구조를 분석할 수 있음

기술적 혁신점

고유공간 제약: 부분 구조가 고유공간에 임베딩될 수 있다는 요구를 통해 전통적 방법보다 강한 제약을 제공합니다.
계층적 구성 전략: 작은 부분 구조에서 시작하여 점진적으로 확장하며, 각 단계에서 임베딩의 존재성을 검증합니다.
계산 대수 방법: 확장된 수체 $F\sqrt{F}$ 를 사용하여 정확한 계산을 수행하며, 기호 계산의 복잡성을 피합니다.
보조정리 2의 적용: 특정 유형의 비원시 방식에 대해, 부분 구조 간 연결의 제한성을 증명하여 검증해야 할 경우의 수를 크게 줄입니다.

실험 설정

데이터 집합

Herman-Maleki 데이터베이스: 3-6 클래스 상 다항식 그래프의 매개변수 배열 포함
Hanaki-Miyamoto 분류: 작은 꼭짓점 수의 결합 방식의 완전한 분류
알려진 구성: 다양한 대수 및 기하학적 구성에서 나온 결합 방식

평가 지표

매개변수 집합의 가능성(알려진 조건 통과/불통과)
존재성(대응하는 결합 방식의 존재/비존재)
유일성(유일/여러 개의 비동형 방식)

비교 방법

전통적 가능성 조건:

악수 보조정리
중복도의 정수성
Krein 매개변수 비음성
절대 경계
금지된 4-튜플 조건
상 방식의 가능성

구현 세부사항

SageMath 컴퓨터 대수 시스템 기반
수체 계산을 위해 PARI 사용
그래프 생성 및 동형 검증을 위해nauty 사용
정수 선형 계획법을 위해 GLPK 사용(그래프 색칠)

QPG [[12, 4, 4, 24], 6, 0, 3; 0, 1; 2]:
- 45개 꼭짓점의 4-클래스 방식
- 보조정리 2를 사용하여 부분 구조 연결 패턴 분석
- $S_1$ 에 임베딩될 수 있는 유일한 3-클리크 구성 발견
- 그러나 나머지 꼭짓점에 대한 유효한 임베딩을 찾을 수 없음
QPG [[8, 8, 4, 24], 1, 0, 2; 2, 1; 1]:
- 100가지 가능한 부분 방식 구성 고려
- 각 경우에 대해 8000개의 후보 꼭짓점 검증
- 모든 경우에서 유효한 단위 벡터 표현을 찾지 못함
QPG [[6, 18, 2, 6, 12], 1, 0, 2, 0; 0, 0, 3; 0, 1; 2]:
- 45개 꼭짓점의 5-클래스 방식
- 그래프 생성을 통해 18가지 가능한 이분 그래프 발견
- 이 중 7가지가 2차원 부분공간으로의 임베딩을 허용하지만, 3-클리크로 확장할 때 모두 실패

유일성 결과

QPG [[12, 2, 1, 12, 12], 6, 0, 4, 1; 0, 0, 1; 0, 1; 4]:
- 40개 꼭짓점의 5-클래스 방식
- $S_1$ 의 구면 표현을 통해 구조 완전히 결정
- 이러한 매개변수를 갖는 유일한 결합 방식임을 증명
QPG [[6, 4, 4, 12, 18], 3, 0, 0, 1; 0, 1, 0; 2, 0; 2]:
- 45개 꼭짓점의 5-클래스 방식
- 토러스 $Z_5 \times Z_3 \times Z_3$ 위의 Cayley 그래프로 설명 가능
- 자기동형 군의 위수는 77760