점 10개, 이웃 6개 — 두 매개변수를 무한대로 보내도 이 그래프는 무너지지 않았다 (arXiv 2610.40054v1)

열 개의 점, 여섯 개의 이웃

J(5,2)를 손으로 그려 보자. 크기 5인 집합 {1,2,3,4,5}에서 원소 둘을 고르는 방법은 모두 10가지다. 이 10개의 부분집합이 그래프의 꼭짓점이 된다. 두 부분집합이 원소를 하나만 바꿔서 얻어지는 관계, 예컨대 {1,2}와 {1,3}이면 선을 긋는다. {1,2}에서 선이 뻗는 상대는 몇 개일까. 남은 세 원소 중 하나로 2를 갈아치우는 경우 3가지, 1을 갈아치우는 경우 3가지, 합해서 6개다. 점 10개가 각각 이웃 6개를 갖고, 어느 두 점이든 두 다리 안에서 만난다. 지름이 2인 그래프다.

이렇게 정의가 두 줄이면 끝나는 그래프가 존슨 그래프 J(n,k)다. n개짜리 집합의 k개 부분집합을 꼭짓점으로 삼고, 교집합의 크기가 k−1인 두 집합을 잇는다. 대칭군 Sym(n)이 그래프 전체를 자기 자신으로 옮기고, n이 2k보다 크면 그 대칭군이 사실상 전부다. 논문은 이 단순한 족(family)을 모형이론, 즉 그래프를 논리식으로 읽는 학문의 눈으로 들여다본다.

존슨 그래프 J(5,2). 꼭짓점 10개가 각각 이웃 6개와 이어져 있다 — David Eppstein, CC0 (Wikimedia Commons)

이웃을 들여다보면 체스판이 나온다

논문 전체의 기계 장치가 되는 성질이 하나 있다. 꼭짓점 v의 이웃들이 만드는 부분그래프는 룩 그래프 R(n−k, k)와 동형이다. 룩 그래프는 체스판의 칸마다 점을 놓고 같은 행이나 같은 열에 있는 두 칸을 잇는 그래프다. J(n,k)에서 v가 {1,…,k}라 하면 이웃은 v의 원소 하나를 바깥 원소로 바꾼 것이다. 무엇을 뺐는가가 행을, 무엇을 넣었는가가 열을 정한다. 그래서 (n−k)×k 크기의 격자가 이웃 안에 그대로 들어앉는다.

이 국소 구조가 결정적이다. v를 기준으로 반지름 r인 구(ball)의 꼭짓점은 뺀 원소 r개와 넣은 원소 r개의 쌍으로 유일하게 적힌다. 논문 4장은 이 사실을 1차 논리식 18개로 풀어낸다. 상수 기호 세 개(v, a, b)를 붙여 이웃의 행·열 대표를 정의하고, 각 거리 r마다 열 대표들의 r-집합과 행 대표들의 r-집합으로 가는 전단사 함수를 정의 가능하게 만든다. 무한히 큰 그래프를 유한한 논리식 뭉치로 붙잡는 작업이다.

룩 그래프. 같은 행이나 열의 칸이 이어진다. 존슨 그래프에서 한 꼭짓점의 이웃은 정확히 이 모양이다 — Smithers888, Public domain (Wikimedia Commons)

두 매개변수를 동시에 무한대로 보낸다

k를 고정하면 재미가 없다. J(ω, k)는 크기 n인 순수 집합과 서로 해석 가능해서 이론이 완전 범주적이고 모얼리 계수가 k다. 반대로 n을 고정하면 그래프가 유한히 많을 뿐이라 극한 이론이 없다. 논문이 보는 것은 n, k, n−k가 모두 함께 무한대로 가는 경로다. 이때 각 문장의 참·거짓이 결국 안정되는 극한 이론 T_J를 정의한다.

도구는 에렌포이히트-프레세 게임이다. 두 그래프에서 번갈아 점을 고르고, 정해진 라운드가 끝났을 때 대응된 점들이 같은 원자 명제를 만족하면 복제자(Duplicator)가 이긴다. 논문의 정리 3.0.2는 복제자가 ⌊log t⌋ 라운드를 버틴다고 말한다. t가 min(k, n−k) 규모이므로 라운드 수는 매개변수의 로그만큼만 늘어난다. 끝없이 커지는 두 그래프가 논리적으로는 놀랄 만큼 오래 구별되지 않는다는 뜻이다.

핵심 보조정리가 지름을 쓴다. J(n,k)의 지름은 k이고 서로소인 두 꼭짓점은 거리 k만큼 떨어진다. 반지름 t/(2m+1)짜리 구 m−1개로는 그 최단 경로 위의 점을 전부 덮을 수 없다는 것이 lemma 3.0.1의 계산이다. 그래서 복제자는 너무 멀리 떨어진 점은 서로 상호작용하지 않는다고 무시하면서 살아남는다. 이 무시 덕분에 논법이 무한 그래프와 여러 조각으로 흩어진 그래프까지 그대로 통한다.

반전 — 야생을 예상했는데 길들여져 있었다

직관은 반대를 가리킨다. k가 커지면 꼭짓점은 집합의 부분집합이고 그 부분집합들은 집합론적으로 자유롭다. ω의 멱집합이 만드는 불 대수는 안정(stable)은커녕 질서정연하지 않다. 그래서 두 매개변수가 함께 자라면 극한도 그렇게 야생이 되리라 예상하기 쉽다. 논문은 이 예상을 정면으로 뒤집는다. T_J는 완전(complete)하며 ω-안정이고 모얼리 계수는 정확히 ω다.

계산은 구체적이다. 반지름 r인 구의 모얼리 계수는 2r이다. 뺀 원소 r개와 넣은 원소 r개가 각각 강극소(strongly minimal)인 집합에서 오기 때문에 계수가 정확히 두 배로 붙는다. r을 키우면 계수가 끝없이 올라가 ω가 하한이 된다. 상한은 작은 집합이라는 개념이 만든다. 유한 개의 유한 반지름 구에 담기는 집합은 계수가 유한하고, 임의의 두 큰 정의 가능 집합은 반드시 교집합을 가진다. 그래서 ω 위에 무한히 많은 서로소 조각을 쌓을 수 없다.

완전성의 증거는 모델 분류다. 논문은 공리계 Σ를 제시하고, 연결된 모델이 Σ를 만족하면 어떤 무한 기수 κ≥λ에 대해 J′(κ,λ)와 동형임을 보인다. J′(κ,λ)는 중심집합 A에서 원소를 r개씩 맞바꿔 얻는 그래프다. 전체 모델은 이런 조각들의 분리 합집합이고, 저자들은 이를 뒤섞인 존슨 그래프(jumbled Johnson graph)라 부른다.

두 번째 반전 — 그런데 단조 의존은 아니다

여기서 끝나면 그냥 좋은 소식이다. 그런데 논문은 같은 이론이 단조 의존(monadically dependent)이 아니라는 것을 보인다. 단조 의존은 모델에 단항 술어를 아무리 덧붙여도 의존성이 유지된다는 성질이다. 안정성과는 다른 축이고, 두 축이 갈라지는 바로 그 지점이 이 논문의 표적이다.

반례는 가장 작은 무한 그래프에서 나온다. J(ℵ0, 2)의 꼭짓점을 세 가족으로 나눈다. A는 {2n+1, 0}, B는 {2n+2, 0}, C는 {2n+1, 2m+2} 꼴이다. x, y, z가 서로 다르고 극대 클리크를 이룬다는 1차 논리식 ψ를 쓰면, A·B·C를 이름 붙인 뒤 ψ는 A×B에서 C로 가는 전단사, 곧 완전 이분 그래프의 간선 하나하나를 지정한다. 그러면 C의 부분집합을 단항 술어로 이름 붙이는 것만으로 A∪B 위의 임의의 이분 그래프를 정의할 수 있다. 무작위 이분 그래프를 골라 넣으면 독립 성질이 나온다. 단조 의존이 깨지는 것이다.

이 반전이 계산 복잡도에서 갖는 무게

이 구분은 장식이 아니다. 단조 안정인 그래프 클래스에서는 1차 논리 모델 검사가 고정 매개변수로 다룰 수 있는 문제(FPT)가 된다. 더 나아가 반쪽 그래프(half-graph)를 반유도 부분그래프로 배제하는 유전 클래스에서는 단조 안정성이 다룰 수 있음과 다룰 수 없음의 경계선이라는 것이 정리로 알려져 있다. 유전 클래스 전체에서 FPT 모델 검사가 가능한 것과 단조 의존인 것이 동치라는 추측도 있고, 한 방향은 최근에 증명됐다.

존슨 그래프는 그 경계 바로 바깥에 선다. ω-안정이라는 강한 질서를 갖고 있으면서도, 단항 술어 하나를 붙이는 순간 임의의 이분 그래프가 튀어나온다. 저자들은 이 결과를 존슨 그래프가 다룰 수 있는 세계의 바로 바깥에 있다는 신호로 읽는다. 안정성만 보고 판단하면 틀린다는 것이 이 사례의 교훈이다.

저자들이 스스로 남긴 한계

논문은 자기 범위를 분명히 밝힌다. 첫째, 이 게임 논법이 주는 구별력은 로그 라운드에 묶여 있다. 더 긴 게임에서 두 그래프가 갈라지는지는 이 방법으로 답하지 않는다. 둘째, 다룬 것은 존슨 그래프라는 한 족이다. 6장은 해밍 그래프 H(d,q)와 유한체 위의 부분공간 그래프 PGJ(n,k,F)를 다음 후보로 지목하면서, 그 극한 이론이 완전한지조차 아직 모른다고 적는다. 무한 하이퍼큐브가 ω-안정이라는 기존 결과를 인용할 뿐이다.

셋째, 복잡도에 관한 진술은 정리가 아니라 정황이다. 경계 바로 바깥이라는 표현은 추측과 최근의 부분 결과 위에 서 있고, 존슨 그래프 클래스에서 모델 검사가 실제로 FPT가 아님을 이 논문이 증명하지는 않는다. 넷째, 공리계는 아주 작은 그래프, 즉 C(n,k)가 3보다 작은 경우를 명시적으로 제외한다. 그 경우들은 E의 해석을 직접 적어 처리한다.

그래서 질문을 하나 남기자. 우리는 보통 규칙적인 구조와 논리적으로 다루기 쉬운 구조를 같은 말로 쓴다. 존슨 그래프는 그 둘이 갈라지는 반례다. 대칭이 완벽하고 이론이 ω-안정인데, 이름표 하나만 붙이면 임의의 이분 그래프가 나온다. 여러분이 아는 다른 대상 중에도 이렇게 질서는 있는데 이름을 붙이면 무너지는 것이 있을까. 있다면 무엇인지, 그리고 그 붕괴가 실제 계산에서 문제가 된 적이 있는지 궁금하다.

참고 자료

Bjarki Geir Benediktsson, Dugald Macpherson, Isolde Adler, Model Theory of Johnson Graphs, arXiv:2610.40054v1 (math.LO), 2026년 10월 29일. https://arxiv.org/abs/2610.40054

선행 연구: Isolde Adler, Bjarki Geir Benediktsson, Dugald Macpherson, Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs, Discrete Applied Mathematics 312 (2022) 29–44. 모델 검사 경계에 관해서는 Jan Dreier 외, First-Order Model Checking on Monadically Stable Graph Classes, FOCS 2024.