М. В. Блудов, О. Р. Мусин, “Сбалансированные 2-подмножества”, Матем. заметки, 114:3 (2023), 469–473; Math. Notes, 114:3 (2023), 407

Ключевые слова: сбалансированные множества, лемма KKM, кооперативные игры, лемма Шпернера, теорема Бондаревой–Шепли.

1. Введение

Сбалансированные множества, как совокупность подмножеств конечного множества, в соответствии с весами, равномерно покрывающих все множество, впервые были рассмотрены в работах Бондаревой [1] и Шепли [2].

Обозначим через $[d]$ множество состоящее из элементов $\{1,2,\dots,d\}$. Пусть семейство $\Phi$ состоит из подмножеств $\{S_1,\dots,S_m\}$ множества $[d]$. Шепли [3] называет это семейство сбалансированным, если найдется такой набор неотрицательных весов $\{w_1,\dots,w_m\}$, что

Будем рассматривать семейства $F$, состоящие только из подмножеств с двумя элементами. Будем говорит, что семейство $F$ нечетного размера, если оно содержит нечетное число множеств.

Пусть $I=\{i_1,\dots,i_n\}$, где $n\geqslant3$. Будем говорить, что семейство $F$ является цикличным относительно $I$, если $F=\{(i_1,i_2),(i_2,i_3),\dots,(i_n,i_1)\}$. Если же $n=2$, то у нас есть ровно одно двухэлементное подмножество $I$. В этом случае назовем $F=\{(i_1,i_2)\}$ изолированным.

Доказательство следующей теоремы дано в п. 2.

Теорема 1. Пусть $\Phi$ – минимальное сбалансированное семейство двухэлементных подмножеств $[d]$. Тогда $\Phi=\{\Phi_\ell\}_{\ell=1,\dots,k}$ и $[d]$ можно разбить на подмножества $I_1,\dots,I_k$, т.е. $\Phi_\ell$ либо цикличное нечетного размера относительно $I_\ell$, либо изолированное.

Несложно описать все такие разбиения – это разбиение $d$ на слагаемые $2,3,5,\dots$ . Производящая функция этого разбиения имеет вид

Теорему 1 можно применить для корпоративных игр с коалициями из двух игроков. По теореме Бондаревой–Шепли условия непустоты ядра нужно проверять только на минимальных сбалансированных множествах. Поскольку мы знаем эти множества, то проверка условий значительно упрощается.

Здесь мы приведем общее геометрическое определение сбалансированных множеств.

Пусть дано множество точек $V=\{v_1,v_2,\dots,v_m\}$ в $\mathbb{R}^{d}$. Обозначим через $c_V$ центр масс этого множества. Тогда набор точек $v_{i_1},\dots,v_{i_k}$ будем называть сбалансированным, если $c_V$ лежит в выпуклой оболочке $\operatorname{conv}(v_{i_1},\dots,v_{i_k})$. Соответствующий набор индексов $I=\{i_1,\dots,i_k\}$ также будем называть сбалансированным.

Мы будем рассматривать минимальные сбалансированные множества, т.е. подмножества $V$ не содержащих меньших сбалансированных множеств. Множество всех таких наборов будем обозначать $\operatorname{BS}(V)$.

Лемма Шпернера о раскраске вершин триангуляции и ее версия для покрытий ККМ (лемма Кнастера–Куратовского–Мазуркевича) являются дискретными аналогами теоремы Брауэра о неподвижной точке. У леммы большое число приложений. В частности, эта лемма и ее обобщение лемма KKMS [3], [4] играют важную роль в теории игр и математической экономике.

Дискретными версиями теоремы Борсука-Улама являются леммы Такера, Ки Фана и Шашкина [5], [6]. У этих лемм также имеются многочисленные приложения.

В п. 3 нами рассматриваются теоремы A и B, которые используют сбалансированные наборы множества точек $V$ и являются обобщениями дискретных версий теорем о неподвижных точках. Если для некоторого множества $V$ известно его $\operatorname{BS}(V)$, то это дает явные версии этих теорем.

2. Доказательство теоремы 1

Пусть $\Phi$ – семейство, состоящее только из подмножеств с двумя элементами. Это семейство можно описать также с помощью ортонормированного базиса $e_1,\dots,e_{d}$ пространства $\mathbb{R}^{d}$. Рассмотрим точки вида

(Отметим, что точки $V_d$ являются серединами ребер правильного $(d-1)$-симплекса в $\Pi_d$, образованного концами векторов $e_1,\dots,e_d$. Многогранник $P_d$ является важным примером для дискретной геометрии, теории графов и теории кодов. В частности, $V_d$ является множеством с двумя расстояниями в $\mathbb{R}^{d-1}$ и для многих случаях $V_d$ является максимальным по числу точек среди таких множеств.)

Легко увидеть, что сбалансированные множества с $V=V_d$ будут соответствовать сбалансированным семействам $\Phi=\{S_1,\dots,S_m\}$, где $|S_i|=2$, $i=1,\dots,m$.

Очевидно, что центр масс $V_d$, $c_d=(1/d,\dots,1/d)\in \Pi_d$. Основная цель этого пункта – описание минимальных сбалансированных подмножеств $S \subset V_d$.

Рассмотрим полный граф $K_d$ с вершинами $\{a_1,\dots,a_d\}$. Мы будем отождествлять вершины $\{a_1,\dots,a_d\}$ с векторами $\{e_1,\dots,e_d\}$ и c их номерами $\{1,2,\dots,d\}$.

Пусть задано подмножество $S \subset V_d$. Это подмножество задает подграф $G(S)$ в $K_d$ по следующему правилу: $(i,j)$ является ребром $G(S)$, если и только если $e_{ij} \in S$.

Обозначим через $n(S)$ число вершин графа $G(S)$. Заметим, что ребра этого графа находятся во взаимно-однозначном соответствии с элементами множества $S$. Несложно понять, что

Лемма 2. Пусть $S\subset V_d$. Предположим, что $S=S_1\cup S_2$, $S_1\cap S_2=\varnothing$ и $G(S)$ является несвязным объединением графов $G(S_1)$ и $G(S_2)$. Тогда

$$ \begin{equation*} S_i\subset \mathbb R^{n(S_i)}, \quad i=1,2, \qquad \mathbb R^{n(S)}=\mathbb R^{n(S_1)} \oplus \mathbb R^{n(S_2)}. \end{equation*} \notag $$

Из этой леммы следует, что если граф $G(S)$ – несвязен, то разложив его на связные компоненты $G(S_1),\dots,G(S_k)$ получим, что $S_i$ лежат в попарно-ортогональных подпространствах в $\mathbb R^{n(S)}$. Этот факт доказывает следующую лемму.

Лемма 3. Пусть $S\subset V_d$ является сбалансированным множеством. Предположим, что $G(S_1),\dots,G(S_k)$ являются связными компонентами $G(S)$. Тогда для всех $i$ множество $S_i$ также является сбалансированным для $V=V_{n(S_i)}$.

Непосредственно из определения Шепли нетрудно получить следующую лемму.

Лемма 4. Пусть $S$ – минимальное сбалансированное множество, $|S|>1$ и граф $G(S)$ связен. Тогда у $G(S)$ нет висячих вершин.

Назовем $S\subset V_n$ циклическим, если граф $G(S)$ является $n$-угольником.

Лемма 5. Пусть $S$ – минимальное сбалансированное множество с $V=V_n$, $n>2$. Предположим, что граф $G(S)$ связен и $n(S)=n$. Тогда $n$ нечетно и $S$ циклическое.

Теорема Каратеодори о выпуклой оболочке. Для любой точки выпуклой оболочки подмножества евклидового пространства найдется содержащий ее невырожденный симплекс с вершинами в этом подмножестве.

Заметим, что $S$ является подмножеством $(n-1)$-мерного евклидового пространства. По условию леммы число вершин $G(S)$ равно $n$ и центр масс $c_n$ лежит в $\operatorname{conv}(S)$.

Из теоремы Каратеодори следует, что найдется невырожденный симплекс $s$ с вершинами лежащими в $S$, который содержит $c_n$. Так как симплекс $s$ невырожденный, число его вершин не превосходит $n$. Из условия минимальности $S$ вытекает, что множество вершин $s$ совпадает с $S$ и следовательно $|S|\leqslant n$.

У графа $G(S)$ число вершин равно $n$, а число ребер не превосходит $n$. Тогда из леммы 3 вытекает, что этот граф $n$-угольник.

Пусть $n=2k$, $S=\{(1,2)(2,3),\dots,(2k,1)\}$ и $S'=\{(1,2)(3,4),\dots,(2k-1,2k)\}$. Тогда $|S'|=k$. Поскольку выпуклая оболочка $S'$ по-прежнему покрывает центр масс $c_n$ и $S'\subset S$, то $S$ не минимально и $n$ не может быть четным.

Теорема 1 следует непосредственно из лемм 3 и 5.

3. Леммы Такера, Фана и Шашкина как следствия теоремы о сбалансированных множествах

3.1. Дискретные версии теорем о неподвижных точках

В работе [7] по покрытию пространства $X$ набором из $m$ открытых (или замкнутых) множеств и $V=\{v_1,v_2,\dots, v_m\}\subset\mathbb{R}^{d}$ строится отображение $f_V\colon X\to \operatorname{conv}(V)$. Раскраска $L\colon V(T)\to \{1,\dots,m\}$ вершин триангуляции $T$ многообразия $M$ является частным случаем покрытия. Поэтому можно определить отображение $f_L\colon T\to \operatorname{conv}(V)$. Основные результаты об этих отображениях содержатся в [7; теорема 3.1, следствие 3.2] и [8; теорема 4.2]. Мы приведем здесь следствия этих теорем.

Теорема A. Пусть $V:=\{v_1,\dots,v_m\}$ – множество точек в $\mathbb{R}^{d}$ и $F=\{F_1,\dots,F_m\}$ – замкнутое (или открытое) покрытие $n$-мерного шара такое что $f_V$ не гомотопно нулю на границе. Тогда найдется такой сбалансированный набор индексов $I\in\operatorname{BS}(V)$, что пересечение $\bigcap_{i \in I}F_i$ не пусто.

Теорема B. Пусть $V:=\{v_1,\dots,v_m\}$ – множество точек в $\mathbb{R}^{d}$. Пусть $T$ – триангуляция $n$-мерного шара и задана такая раскраска $L\colon V(T)\to \{1,\dots,m\}$, что отображение $f_L$ не гомотопно нулю на границе. Тогда найдется такой симплекс $s$ в $T$ и набор индексов $I\in\operatorname{BS}(V)$, что вершины $s$ раскрашены во все цвета из $I$.

Заметим, что условие “не гомотопно нулю” на границе выполняется для классических теорем о неподвижных точках. В частности, таковыми являются шпернеровская раскраска, покрытие ККМ и антиподальная раскраска на границе.

Как следствие теорем A и B, изучая сбалансированные множества вершин многогранников, можно получать дискретные версии теорем о неподвижных точках.

Пусть $m=d+1$, $n=d$, $F$ покрывает $d$-симплекс, а $V$ – это множество вершин $\Delta^d$ в $\mathbb{R}^{d}$. Предположим, что $F$ удовлетворяет условиям леммы ККМ на границе. Тогда это покрытие не является гомотопным нулю на границе $\Delta^d$ и из теоремы A вытекает лемма ККМ. Из леммы ККМ (или из теоремы B) легко следует лемма Шпернера:

Лемма. Для любой шпернеровской раскраски триангуляции симплекса $\Delta^{d}$ в $d+1$ цветов найдется симплекс, триангуляции вершины которого раскрашенны во все цвета.

Лемму Шепли KKMS [3], [4] также несложно вывести из теоремы A, см. [8; следствие 4.2]. Здесь точками $V$ будут центры масс любого $k$-подмножества вершин симплекса $\Delta^d$, где $1\leqslant k \leqslant d$.

Пусть $V=V_d$ и мы в условиях теорем A и B. Тогда из теоремы 1 получается новый результат для раскраски вершин триангуляции в $d(d-1)/2$ цветов.

3.2. Антиподальные сбалансированные 2-подмножества

Пусть $P$ – центрально-симметричный многогранник в $\mathbb{R}^{d}$, а $V=V(P)$ – множество его вершин. Иными словами, если $v\in V$, то $(-v)\in V$. В этом случае, центр масс $c_V=O$, где $O$ – начало координат $\mathbb{R}^{d}$. Легко видеть, что множество сбалансированных $2$-подмножеств $V$ состоит из антиподальных пар $(v,-v)$, $v\in V$.

Предположим, что в теореме B триангуляция $T$ и раскраска $L$ являются антиподальными на границе. Тогда можно показать (см. [6]–[8]), что $f_L$ не будет гомотопно нулю на границе и поэтому здесь можно применять теорему B.

1. Пусть $e_1,\dots,e_{d}$ стандартный ортонормированный базис $\mathbb{R}^{d}$ и $V=\{\pm e_1,\dots,\pm e_d\}$, т.е. $P$ – правильный $d$-кроссполитоп, а $V$ – множество его вершин. Несложно показать, что в этом случае $\operatorname{BS}(V)$ состоит только из пар антиподальных вершин. Применив теорему B, мы получим лемму Такера:

Лемма. Пусть $T$ – центрально-симметричная на границе триангуляция $d$-мерного шара и $L\colon V(T) \to \{+1,-1,+2,-2,\dots,+d,-d\}$ будет раскраской вершин $T$, удовлетворяющей $L(-v)=-L(v)$ для любой вершины $v$ на границе. Тогда существует ребро $[u,v]\in T$ c противоположными метками, т.е. $L(u)=-L(v)$.

2. В работе [5] был построен выпуклый многогранник $P(n,d)$ в $\mathbb{R}^{d}$ с $2n$ центрально-симметричными вершинами $v_1,-v_1,\dots,v_n,-v_n$, см. [5; теорема 5.2], у которого $\operatorname{BS}(V)$ состоит из пар антиподальных точек $(v_i,-v_i)$, $i=1,\dots,n$, и альтернированных $d$-симплексов с вершинами $(v_{k_0},-v_{k_1},\dots,(-1)^{d}v_{k_d})$ или $\{-v_{k_0},v_{k_1},\dots,(-1)^{d+1}v_{k_d}\}$, где $1 \leqslant k_0 < \dots < k_d \leqslant n$. Если использовать в качестве $V$ вершины $P(n,d)$, то теорема B доказывает лемму Ки Фана:

Лемма. Пусть $T$ – триангуляция $d$-мерного шара, которая центрально-симметричная на границе и $L \colon V(T) \to \{+1,-1,+2,-2,\dots,+n,-n\}$ будет раскраской вершин $T$, удовлетворяющей $L(-v)=-L(v)$ для любой вершины $v$ на границе. Предположим, раскраска не имеет ребра с противоположными метками. Тогда в $T$ найдется нечетное число альтернированно-раскрашенных $d$-симплексов, т.е. симплексов, метки вершин которых можно упорядочить в виде $(k_0,-k_1,k_2,\dots,(-1)^dk_d)$, где $1 \leqslant |k_0| < |k_1| < \dots < |k_d| \leqslant n$ и все $k_i$ одного знака.

3. В работе [6] рассматривается многомерное обобщение леммы Шашкина.

Лемма. Пусть $\mathbb{B}^{d-1}$ – $(d-1)$-мерный шар и $T$ – его триангуляция, центрально-симметричная на границе. Пусть $L\colon V(T) \to \{\pm 1,\dots,\pm d\}$ – антиподальная раскраска $T$, не имеющая ребер $[u,v]$ с $L(u)=-L(v)$. Тогда для любого множества цветов $\Lambda=\{\ell_1, \dots,\ell_d\}$ с $|\ell_i|=i$ для всех $i$ найдется нечетное число симплексов, раскрашенных в цвета $\Lambda$ или $(-\Lambda)$.

Приведенные в [6] доказательства не опираются на теорему B. Здесь мы покажем, как лемма Шашкина получается из этой теоремы.

Рассмотрим правильный $(d-1)$-симплекс $\Delta$ в $\mathbb{R}^{d-1}$ с центром масс в начале координат $O$ и вершинами $v_1,\dots,v_d$. Пусть $V$ состоит из точек $\pm v_1,\dots,\pm v_d$. Несложно показать, что $\operatorname{BS}(V)$ состоит из пар точек $(v_i,-v_i)$ и множеств $\{v_1,\dots,v_d\}$, $\{-v_1,\dots,-v_d\}$. Покрасим вершину $v_i$ в цвет $\ell_i$, а вершину $-v_i$ в цвет $(-\ell_i)$. Тогда отображение $f_L$ будет антиподальным на границе и теорема B влечет лемму Шашкина.

Образец цитирования: М. В. Блудов, О. Р. Мусин, “Сбалансированные 2-подмножества”, Матем. заметки, 114:3 (2023), 469–473; Math. Notes, 114:3 (2023), 407–411

Цитирование в формате AMSBIB

\RBibitem{BluMus23}

\by М.~В.~Блудов, О.~Р.~Мусин

\paper Сбалансированные 2-подмножества

\jour Матем. заметки

\yr 2023

\vol 114

\issue 3

\pages 469--473

\mathnet{http://mi.mathnet.ru/mzm13951}

\crossref{https://doi.org/10.4213/mzm13951}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4658792}

\transl

\jour Math. Notes

\yr 2023

\vol 114

\issue 3

\pages 407--411

\crossref{https://doi.org/10.1134/S0001434623090122}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85174578039}

1. Введение

2. Доказательство теоремы 1

3. Леммы Такера, Фана и Шашкина как следствия теоремы о сбалансированных множествах

3.1. Дискретные версии теорем о неподвижных точках

3.2. Антиподальные сбалансированные 2-подмножества

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ