Различимость и линейная независимость для $H$-хроматических симметрических функций

Основная информация

• ID статьи: 2511.08665
• Название: Distinguishability and linear independence for $H$-chromatic symmetric functions
• Авторы: Shao Yuan Lin, Laura Pierson
• Классификация: math.CO (комбинаторика)
• Дата публикации: 13 ноября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2511.08665

Аннотация

В данной работе исследуются $H$-хроматические симметрические функции $X_G^H$, которые являются обобщением классических хроматических симметрических функций (ХСФ) $X_G$ и используются для отслеживания гомоморфизмов из графа $G$ в граф $H$. Основные направления исследования включают: (1) способность автохроматических симметрических функций $X_G^G$ различать различные деревья, с проверкой всех деревьев до 12 вершин; (2) доказательство того, что автоХСФ различают деревья и недеревья (с одним исключением); (3) анализ разложений по степенным суммам для полных двудольных графов с доказательством гипотезы о $p$-монотонности; (4) построение различных базисов пространств симметрических функций с использованием $H$-ХСФ; (5) введение концепции $H$-хроматического полинома.

Исследовательский контекст и мотивация

Предпосылки проблемы

1. Обобщение классических хроматических симметрических функций: Стэнли в 1995 году ввел хроматические симметрические функции $X_G$, которые обобщают хроматический полином графа на симметрические функции. Иглз и соавторы в 2022 году дополнительно обобщили это понятие до $H$-хроматических симметрических функций $X_G^H$, определяемых как: $X_G^H(x_1, x_2, \ldots) := \sum_{f:G\to H} \sum_{\phi:V(H)\to\{1,2,\ldots,|V(H)|\}} \prod_{v\in V(G)} x_{\phi(f(v))}$ где $f$ — гомоморфизм графов, $\phi$ — разметка вершин.
2. Проблема различимости: Центральным вопросом является способность $H$-ХСФ различать графы как инварианты. Для классической ХСФ известно, что она не различает все графы, но предполагается, что она различает все деревья. Для $H$-ХСФ, особенно для автоХСФ $X_G^G$, способность к различению оставалась неясной.

Значимость исследования

1. Теория гомоморфизмов графов: Гомоморфизмы графов — фундаментальное понятие в комбинаторике и теоретической информатике; $H$-ХСФ предоставляют новый инструмент для изучения структуры гомоморфизмов
2. Теория симметрических функций: Исследование того, могут ли $H$-ХСФ образовывать базис пространства симметрических функций, обогащает теорию симметрических функций
3. Инварианты графов: Разработка более тонких инвариантов графов имеет важное значение для проблемы изоморфизма графов и классификации графов

Ограничения существующих методов

1. Ограничения классической ХСФ: Известно, что существуют различные графы с одинаковой ХСФ (например, пример Стэнли)
2. Неизвестность $H$-ХСФ: Иглз и соавторы выдвинули несколько гипотез, которые остались нерешенными, включая:
   • Различают ли автоХСФ все деревья
   • $p$-монотонность $\omega(X_G^H)$
   • Можно ли построить базис с использованием $H$-ХСФ для фиксированного $H$ (не полного графа)

Основные вклады

1. Способность различения автоХСФ:
   • Доказано, что автоХСФ различают деревья и недеревья, за исключением $X_{P_3}^{P_3} = X_{K_1\sqcup K_2}^{K_1\sqcup K_2}$
   • С помощью Sage проверено, что все деревья до 12 вершин различаются автоХСФ
   • Доказано, что автоХСФ определяют количество ног паучьих графов и последовательность степеней гусеничных графов
2. Теория разложений по степенным суммам:
   • Доказано, что когда $H=S_{n+1}$ (звездный граф) и $n$ достаточно велико, $\omega(X_G^{S_{n+1}})$ является $p$-монотонной
   • Даны явные формулы разложений по степенным суммам для $H=K_{2,n}$ и $H=K_{m,n}$
3. Построение базисов симметрических функций:
   • Доказано, что автоХСФ полных многодольных графов образуют базис $\Lambda$
   • Построены различные методы для образования базисов $\Lambda^n$ при фиксированном $H$ (не полном графе)
   • Доказано, что при $n\geq 12$ фиксированный $G$ (даже с допуском петель) не может образовать базис $\Lambda^n$
4. $H$-хроматический полином:
   • Определен $H$-хроматический полином $\chi_G^H(k) := X_G^H(1^k)$ и доказано, что это действительно полином
   • Даны явные формулы и исследована связь с $H$-ХСФ

Подробное описание методов

Определение задачи

Исследование следующих свойств $H$-хроматических симметрических функций $X_G^H$:

• Входные данные: два графа $G$ и $H$
• Выходные данные: симметрическая функция $X_G^H \in \Lambda$
• Цель: анализ способности различения $X_G^H$, алгебраической структуры и комбинаторного смысла

Основная методология

1. Метод анализа автоХСФ

Анализ эндоморфизмов двудольных графов (Proposition 2.2.1): Для связного двудольного графа $G$ с двудольным разбиением $V(G) = V_k \sqcup V_{n-k}$, путем анализа коэффициентов $[m^n_{n-k,k-\ell+1,1^{\ell-1}}]X_G^G$ можно восстановить первые $k$ членов звездной последовательности, то есть $\sum_{v\in V(G)} \binom{\deg(v)}{\ell}$.

Ключевые технические инновации:

• Использование свойства, что гомоморфизмы графов должны сохранять двудольную структуру
• Применение принципа включения-исключения для подсчета гомоморфизмов определенных типов
• Установление прямой связи между коэффициентами мономов и параметрами структуры графа

2. Техника разложения по степенным суммам

Случай звездного графа (Lemma 3.1.2): Для $H=S_{n+1}$, когда $n$ достаточно велико: $X_G^{S_{n+1}} = \sum_{(b_1,\ldots,b_\ell)\in\{1,2\}^\ell} n! \sum_{j=k_1^{b_1}+\cdots+k_\ell^{b_\ell}}^{|V(G)|} (-1)^{j-(k_1^{b_1}+\cdots+k_\ell^{b_\ell})} p_{j,1^{|V(G)|-j}} \cdots$

Стратегия доказательства $p$-монотонности:

1. Представление коэффициентов степенных сумм как суммирования по двудольным разбиениям связных компонент
2. Применение отображения $\omega$: $\omega(p_\lambda) = (-1)^{|\lambda|-\ell(\lambda)}p_\lambda$
3. Доказательство того, что все ненулевые коэффициенты имеют одинаковый знак $(-1)^{k_2^1+\cdots+k_2^\ell}$

3. Метод построения базиса

Базис полных многодольных графов (Proposition 4.1.1): Доказано, что $\{X_{K_\lambda}^{K_\lambda} : \lambda \vdash n\}$ образуют базис $\Lambda$ путем:

• Наблюдения, что минимальная длина монома $X_{K_\lambda}^{K_\lambda}$ равна $\ell(\lambda)$
• Установления треугольной матрицы перехода с мономиальным базисом $\{m_\lambda\}$

Построение базиса при фиксированном $H$ (Proposition 4.2.2): Когда $H$ — дизъюнктное объединение клик и по крайней мере одна клика имеет размер $\geq 3$, можно построить базис:

• Для каждого $\lambda$ построить $G_\lambda$ как дизъюнктное объединение полных многодольных графов
• Использовать строгий контроль длины мономов для установления треугольности

Технические инновационные моменты

1. Фреймворк анализа типов: Введение концепции "гомоморфизма типа $\lambda$", то есть гомоморфизма, размеры прообразов которого образуют разбиение $\lambda$, что обеспечивает унифицированное комбинаторное объяснение
2. Тонкое применение принципа включения-исключения: При разложении по степенным суммам рассматривается не только, какие вершины используются, но и как они помечаются, что приводит к точным формулам коэффициентов
3. Приближение спектрального радиуса (Proposition 2.4.10): Для паучьего графа $T_\lambda$ доказано $|\text{End}(T_\lambda)| = 2^{\ell(\lambda)}\rho^{n-1}(\|x_0\|_{\ell(\lambda)}^{\ell(\lambda)}\|x_0\|_1^{e(\lambda)}\|x_1\|_1^{o(\lambda)} + \cdots) + o(\rho^{n-1})$ где $\rho$ — спектральный радиус, $x$ — собственный вектор
4. Аргумент размерности: Путем проектирования на подпространство мономов длины 2 доказано несуществование базиса при фиксированном $G$ (Proposition 4.3.1)

Экспериментальная установка

Вычислительные инструменты

• Программное обеспечение Sage: используется для вычисления $H$-ХСФ и проверки гипотез
• Детали реализации: авторы предоставили функции Sage в репозитории GitHub

Диапазон проверки

1. Различимость деревьев (Proposition 2.3.1):
   • Проверены все деревья с 10-12 вершинами
   • Для случаев, когда вычисления превышают время ожидания, используются размер группы автоморфизмов и сумма квадратов степеней как вспомогательные критерии
   • Специально обработаны два паучьих графа с 12 вершинами $T_1$ и $T_2$
2. Существование базиса (§4.2):
   • Для $n=3,4,5,6$ вычислены $p_H(n)$ (доля графов $H$, для которых можно построить базис)
   • Результаты: $p_H(2)=0.5, p_H(3)=0.5, p_H(4)\approx 0.636, p_H(5)\approx 0.794, p_H(6)\approx 0.885$

Численные свидетельства

Таблицы показывают тенденцию роста $p_H(n)$ с увеличением $n$, что намекает на $p_H(n)\to 1$ при $n\to\infty$, но скорость роста не определена.

Экспериментальные результаты

Основные результаты

1. Различимость деревьев автоХСФ:
   • ✓ Все неизоморфные деревья до 12 вершин различаются автоХСФ
   • ✓ АвтоХСФ различают деревья и недеревья (кроме $P_3$ и $K_1\sqcup K_2$)
   • ✓ АвтоХСФ определяют количество связных компонент леса (кроме того же исключения)
2. Монотонность степенных сумм:
   • ✓ Для $H=S_{n+1}$, когда $n\geq k_1^1+\cdots+k_\ell^1$, $\omega(X_G^{S_{n+1}})$ является $p$-монотонной
   • ✓ Все члены $p_{\lambda}$ (где $\ell(\lambda)=m$) в $\omega(X_G^{K_{m,n}})$ имеют одинаковый знак
3. Построение базисов:
   • ✓ АвтоХСФ полных многодольных графов образуют базис $\Lambda$
   • ✓ Различные $H$ (включая $n$-клики, дизъюнктные объединения клик, пути с петлями и т.д.) могут образовывать базис $\Lambda^n$
   • ✗ Некоторые $H$ (такие как дизъюнктные объединения с малым числом ребер, $K_n$ с удаленными ребрами) не могут образовать базис
   • ✗ При $n\geq 12$ фиксированный $G$ не может образовать базис (даже с допуском петель)

Ключевые теоремы

Proposition 2.3.2 (Различимость деревьев и недеревьев): Если $T$ — дерево и $X_T^T = X_G^G$, то $G$ также является деревом, за исключением случая $T=P_3$ и $G=K_1\sqcup K_2$.

Идея доказательства:

1. Через длину монома доказать, что $G$ должен быть двудольным
2. Анализ соотношения числа ребер: $|E(G)| \cdot 2^{\kappa(G)} = (n-1) \cdot 2$
3. Вывод, что $\kappa(G)\leq 2$, и проверка того, что только $n=3$ — особый случай

Proposition 3.1.1 ($p$-монотонность): Когда $n\geq k_1^1+\cdots+k_\ell^1$, все $p$-коэффициенты $\omega(X_G^{S_{n+1}})$ имеют одинаковый знак.

Proposition 4.3.1 (Невозможность при фиксированном $G$): При $n\geq 12$ не существует графа $G$ и набора графов $\{H_\lambda\}$ таких, что $\{X_{H_\lambda}^G\}$ натягивают $\Lambda^n$.

Анализ примеров

Example 2.1.3 (Графы с одинаковой ХСФ, но различными автоХСФ): Два 5-вершинных графа Стэнли имеют одинаковую ХСФ, но:

• Левый граф имеет 8 автоморфизмов (можно переставлять два треугольника, отражать каждый треугольник)
• Правый граф имеет только 2 автоморфизма (можно только переставлять две вершины на диагонали)
• Поэтому $[m_1^5]X_{\text{left}}^{\text{left}} = 8 \neq 2 = [m_1^5]X_{\text{right}}^{\text{right}}$

Example 6.1.6 ($H$-хроматический полином): Для $H=C_4$ (4-цикл) и $G$ — двудольного дерева (разбиение размеров $a,b$): $\chi_G^H(k) = 16k(k-1) + (2^{a+2}+2^{b+2}-16)k(k-1)(k-2) + (2^{a+b+1}-2^{a+2}-2^{b+2}+8)k(k-1)(k-2)(k-3)$

Связанные работы

Теория хроматических симметрических функций

1. Stanley (1995): Введение классической ХСФ $X_G$, доказательство $p$-позитивности $\omega(X_G)$
2. Cho & van Willigenburg (2016): Построение хроматических базисов, доказательство того, что ХСФ натягивают $\Lambda^n$
3. Crew & Spirkl (2020, 2021): Развитие теории взвешенных ХСФ и базисов полных многодольных графов

Теория $H$-ХСФ

1. Eagles et al. (2022): Введение $H$-ХСФ, выдвижение нескольких гипотез:
   • АвтоХСФ различают деревья
   • $p$-монотонность
   • Проблемы существования базиса
2. Вклад данной работы:
   • Частичное доказательство гипотезы о различимости деревьев (до 12 вершин)
   • Доказательство $p$-монотонности при достаточно больших $H$
   • Систематический ответ на вопросы о возможности построения базиса

Теория гомоморфизмов графов

1. Bonato & Prałat (2009): Ядра и эндоморфизмы случайных графов
2. Erdős & Rényi (1963): Асимптотически почти все графы несимметричны
3. Данная работа использует эти результаты для доказательства того, что большинство пар графов имеют одинаковые автоХСФ (Corollary 2.1.2)

Спектральная теория графов

1. Oliveira et al. (2018): Упорядочение спектральных радиусов паучьих графов
2. Данная работа применяет спектральные методы к подсчету эндоморфизмов (Proposition 2.4.10)

Заключение и обсуждение

Основные выводы

1. Способность различения: АвтоХСФ демонстрируют сильную способность различения на деревьях и лесах, что поддерживает гипотезу Иглза и соавторов
2. Алгебраическая структура: Разложения по степенным суммам имеют хорошие свойства в случае полных двудольных графов; $p$-монотонность выполняется при надлежащих условиях
3. Теория базисов: $H$-ХСФ могут образовывать базис пространства симметрических функций, но требуют тщательного выбора $H$ или $G$
4. Полиномиальное обобщение: $H$-хроматический полином — естественное обобщение хроматического полинома, содержащее более богатую информацию

Ограничения

1. Вычислительная сложность:
   • Для деревьев с высокой степенью вычисление $X_T^T$ может превысить время ожидания ($|\text{End}(T)| \geq d^d$ для вершины степени $d$)
   • Ограничивает возможность проверки деревьев большего размера
2. Требования условий:
   • $p$-монотонность требует, чтобы $H$ был "достаточно большим" ($|V(H)|\geq k_1^1+\cdots+k_\ell^1$)
   • Построение базиса имеет строгие требования к структуре $H$
3. Исключительные случаи:
   • $X_{P_3}^{P_3} = X_{K_1\sqcup K_2}^{K_1\sqcup K_2}$ — единственное, но важное исключение
   • Намекает на то, что полная характеризация может потребовать обработки особых случаев малых графов
4. Нерешенные проблемы:
   • Гипотеза о полной различимости деревьев остается недоказанной (проверена только до 12 вершин)
   • Существование базиса при фиксированном $G$ для $n=8$ до $11$ не определено
   • Асимптотическое поведение $p_H(n)$ не определено

Будущие направления

1. Открытые проблемы (явно выдвинутые в статье):
   • Question 2.4.11: Различают ли автоХСФ все достаточно большие паучьи графы?
   • Question 4.2.9: Полная характеризация того, какие $H$ позволяют построить базис $\Lambda^{|V(H)|}$
   • Question 4.2.10: Асимптотическое поведение $p_H(n)$ (предположение: $p_H(n)\to 1$)
   • Question 4.3.6: Может ли фиксированный $G$ построить базис при $n=8$ до $11$?
   • Question 6.2.1: Для данного $H$, какие графы имеют одинаковый $\chi_G^H$, но различные $X_G^H$?
2. Расширение методологии:
   • Обобщение спектральных методов на более широкие семейства деревьев
   • Разработка более эффективных алгоритмов вычисления $H$-ХСФ
   • Исследование связей между $H$-ХСФ и другими инвариантами графов
3. Углубление теории:
   • Исследование комбинаторной интерпретации $H$-ХСФ
   • Установление соотношений удаления-сжатия для $H$-хроматического полинома
   • Исследование применения $H$-ХСФ к проблеме изоморфизма графов

Глубокая оценка

Преимущества

1. Солидный теоретический вклад:
   • Систематическое продвижение нескольких гипотез, выдвинутых Иглзом и соавторами
   • Предоставление полных доказательств и контрпримеров
   • Установление новой теоретической базы (такой как анализ типов, спектральные методы)
2. Методологическая инновативность:
   • Умелое сочетание комбинаторных, алгебраических и спектральных методов
   • Тонкое применение техники включения-исключения
   • Простые и мощные аргументы размерности
3. Достаточная вычислительная проверка:
   • Использование Sage для крупномасштабной проверки
   • Предоставление воспроизводимого кода
   • Численные свидетельства поддерживают теоретические гипотезы
4. Ясное изложение:
   • Хорошо организованная структура, от частного к общему
   • Множество примеров и иллюстраций
   • Четкое обозначение открытых проблем

Недостатки

1. Вычислительные ограничения:
   • Проверка деревьев только до 12 вершин (ограничено вычислительной мощностью)
   • Некоторые результаты требуют предположения "достаточно большой", но без явных границ
2. Обработка исключений:
   • Исключение $P_3$ и $K_1\sqcup K_2$ повторяется в нескольких теоремах
   • Хотя авторы это признают, отсутствует глубокое объяснение того, почему это единственное исключение
3. Систематичность построения базиса:
   • Построение в Proposition 4.2.2 довольно техническое
   • Отсутствуют унифицированные условия характеризации
   • Вычисление $p_H(n)$ только до $n=6$
4. Недостаточное обсуждение приложений:
   • Основной фокус на теоретические свойства
   • Отсутствует обсуждение применения $H$-ХСФ к практическим задачам теории графов

Влияние

1. Академический вклад:
   • Значительное продвижение теории $H$-ХСФ
   • Новая перспектива для теории симметрических функций
   • Установление глубокой связи между гомоморфизмами графов и симметрическими функциями
2. Методологическая ценность:
   • Применение спектральных методов в комбинаторном подсчете может быть обобщено
   • Фреймворк анализа типов может быть использован для других инвариантов графов
3. Открытость:
   • Выдвижение нескольких явных открытых проблем
   • Указание направлений для последующих исследований
   • Предоставление воспроизводимых вычислительных инструментов

Применимые сценарии

1. Теоретические исследования:
   • Теория гомоморфизмов графов
   • Теория симметрических функций
   • Алгебраическая комбинаторика
2. Вычислительные приложения:
   • Вычисление инвариантов графов
   • Классификация и идентификация графов
   • Анализ симметрии в задачах комбинаторной оптимизации
3. Образовательные цели:
   • Демонстрация комплексного применения комбинаторных, алгебраических и спектральных методов
   • Предоставление богатых примеров и вычислительных примеров

Библиография

Ключевые ссылки включают:

1. Stanley (1995): "A symmetric function generalization of the chromatic polynomial of a graph" — основополагающая работа по введению хроматических симметрических функций
2. Eagles et al. (2022): "H-chromatic symmetric functions" — непосредственный предшественник данной работы, выдвинувший основные гипотезы
3. Cho & van Willigenburg (2016): "Chromatic bases for symmetric functions" — теория хроматических базисов
4. Crew & Spirkl (2020, 2021): Работы по взвешенным ХСФ и базисам полных многодольных графов
5. Godsil & Royle (2001): "Algebraic Graph Theory" — стандартный справочник по спектральной теории графов

Общая оценка: Это высокачественная теоретическая работа по комбинаторике, которая вносит существенный вклад в теорию $H$-хроматических симметрических функций. Авторы систематически ответили на несколько вопросов, поставленных предшественниками, методы доказательства разнообразны и глубоки, вычислительная проверка достаточна. Хотя некоторые результаты требуют технических предположений и основная гипотеза еще полностью не решена, работа создает прочную основу для будущих исследований в этой области. Особенно достойны похвалы четкое изложение авторами открытых проблем и честное обсуждение ограничений.