$(\min, \max)$-equivalence of posets and nonnegative Tits forms
We study the relationship between the (min, max)-equivalence of posets and properties of their quadratic Tits form related to nonnegative definiteness. In particular, we prove that the Tits form of a poset S is nonnegative definite if and only if the Tits form of any poset $(\min, \max)$-equivalent...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська Англійська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2008
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/3234 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509286369591296 |
|---|---|
| author | Bondarenko, V. M. Stepochkina, M. V. Бондаренко, В. М. Степочкина, М. В. Бондаренко, В. М. Степочкина, М. В. |
| author_facet | Bondarenko, V. M. Stepochkina, M. V. Бондаренко, В. М. Степочкина, М. В. Бондаренко, В. М. Степочкина, М. В. |
| author_sort | Bondarenko, V. M. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:48:57Z |
| description | We study the relationship between the (min, max)-equivalence of posets and properties of their quadratic Tits form related to nonnegative definiteness. In particular, we prove that the Tits form of a poset S is nonnegative definite if and only if the Tits form of any poset $(\min, \max)$-equivalent to S is weakly nonnegative. |
| first_indexed | 2026-03-24T02:38:41Z |
| format | Article |
| fulltext |
УДК 512.64+512.56
В. М. Бондаренко, М. В. Степочкина (Ин-т математики НАН Украины, Киев)
(MIN, MAX)-ЭКВИВАЛЕНТНОСТЬ ЧАСТИЧНО
УПОРЯДОЧЕННЫХ МНОЖЕСТВ
И НЕОТРИЦАТЕЛЬНЫЕ ФОРМЫ ТИТСА
We study connection between the (min, max)-equivalence of posets and properties of their quadratic Tits
form, connected with nonnegative definiteness. In particular, we prove that the Tits form of a poset S
is nonnegative definite if and only if the Tits form of any poset, which is (min, max)-equivalent to S, is
weakly nonnegative.
Вивчається зв’язок мiж (min, max)-еквiвалентнiстю частково впорядкованих множин та властиво-
стями їх квадратичної форми Тiтса, пов’язаних iз невiд’ємною визначенiстю. Зокрема, доведено,
що форма Тiтса частково впорядкованої множини S невiд’ємно визначена тодi i лише тодi, коли
форма Тiтса будь-якої частково впорядкованої множини, яка (min, max)-еквiвалентна S, є слабко
невiд’ємною.
1. Введение. Пусть S — частично упорядоченное (сокращенно ч. у.) множество,
которое предполагается конечным и не содержащим элемента 0. Eго квадратичной
формой Титса называют квадратичную форму qS : ZS∪0 → Z, задаваемую равен-
ством
qS(z) = z2
0 +
∑
i∈S
z2
i +
∑
i<j,i,j∈S
zizj − z0
∑
i∈S
zi.
Впервые такая форма была рассмотрена Ю. А. Дроздом в работе [1], где доказано,
что ч. у. множество S имеет конечный (представленческий) тип над полем k тогда
и только тогда, когда его форма Титса слабо положительна. В [2] показано, что S
имеет ручной тип тогда и только тогда, когда форма Титса слабо неотрицательна.
Положительные формы1 Титса и их приложения в теории представлений Титса
изучались во многих работах (см., например, [3 – 7]). Настоящая работа посвящена
изучению ч. у. множеств с неотрицательной формой Титса.
Напомним понятие (min, max)-эквивалентности ч. у. множеств [4].
Для минимального (соответственно максимального) элемента a ∈ S обозначим
через S↑a (соответственно S↓a) ч. у. множество T = T ′ ∪ {a}, где T ′ = S \ {a} как
ч. у. множества (тогда T и S равны как обычные множества), а элемент a является
уже максимальным (соответственно минимальным), причем a сравнимо с x в T
тогда и только тогда, когда a несравнимо с x в S. Будем писать S↑↑xy вместо (S↑x)↑y,
S↑↓xy вместо (S↑x)↓y и т. д.
Ч. у. множество T назовем (min, max)-эквивалентным ч. у. множеству S, если
T равно некоторому ч. у. множеству вида
S = Sε1ε2...εp
x1x2...xp
, p ≥ 0,
1Мы говорим „положительная форма”, а не „положительно определенная форма”, в связи с уже
устоявшимся термином „слабо положительная форма”. То же самое касается и неотрицательных
форм.
c© В. М. БОНДАРЕНКО, М. В. СТЕПОЧКИНА, 2008
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9 1157
1158 В. М. БОНДАРЕНКО, М. В. СТЕПОЧКИНА
где εi ∈ {↑, ↓} и xi, i ∈ {1, . . . , p}, — минимальный (соответственно максимальный)
элемент S
ε1ε2...εi−1
x1x2...xi−1 , если εi =↑ (соответственно εi = ↓); при p = 0 считаем, что
S = S. При этом не требуется, чтобы элементы x1, x2, . . . , xp были различны.
В случае, когда все εi равны ↑ (соответственно ↓), будем говорить, что ч. у.
множество T min-эквивалентно (соответственно max-эквивалентно) ч. у. множе-
ству S. Согласно следствию 2 и предложению 11 [6] (min, max)-, min- и max-
эквивалентности действительно являются отношениями эквивалентности, причем
все они равносильны.
Отметим, что понятие (min, max)-эквивалентности можно естественным обра-
зом продолжить до понятия (min, max)-изоморфизма, считая, что ч. у. множества
S и S′ (min, max)-изоморфны, если существует ч. у. множество T, которое (min,
max)-эквивалентно S и изоморфно S′; аналогично для min-эквивалентности и max-
эквивалентности.
Перейдем к формулировке основных результатов этой статьи.
Напомним, что квадратичная форма f(z) = f(z1, . . . , zm): Zm → Z (Z — мно-
жество всех целых чисел) называется слабо неотрицательной, если она принимает
неотрицательное значение на любом векторе с неотрицательными координатами.
Форма, которая принимает неотрицательное значение на всех векторах, называется
неотрицательной (см. примечание 1); в этом случае пишем f(z) ≥ 0.
Ч. у. множество S назовем NP -критическим (соответственно WNP -критичес-
ким), если форма Титса любого его собственного подмножества является неотрица-
тельной (соответственно слабо неотрицательной), но форма Титса самого S таковой
не является.
Целью данной статьи является доказательство следующих теорем.
Теорема 1. Для произвольного фиксированного ч. у. множества S имеют
место следующие утверждения:
1) если форма Титса любого ч. у. множества, которое min-эквивалентно S,
слабо неотрицательна, то форма Титса самого S неотрицательна;
2) если форма Титса S неотрицательна, то форма Титса любого ч. у. мно-
жества, которое min-эквивалентно S, также неотрицательна (и тем более слабо
неотрицательна).
Теорема 2. Ч. у. множество S является NP -критическим тогда и только
тогда, когда оно min-эквивалентно некоторому WNP -критическому ч. у. мно-
жеству.
В условиях теорем 1 и 2 min-эквивалентность можно заменить на max-экви-
валентность или (min, max)-эквивалентность (в силу их равносильности, о чем
говорилось выше), а также на min-, max- или (min, max)-изоморфизм.
Заметим, что WNP -критические ч. у. множества, которых всего 6, известны
(см. п. 4). Теорема 2 дает эффективный метод изучения NP -критических мно-
жеств.
Аналогичные результаты, но относительно положительных и слабо положи-
тельных форм Титса, получены авторами (наряду со многими другими результата-
ми) в работе [6].
2. Определения и обозначения для ч. у. множеств. Пусть T = (T0,≤)
— ч. у. множество. Под подмножеством X ч. у. множества T всегда понимаем
любое подмножество X ⊆ T0 вместе с индуцированным отношением частичного
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
(MIN, MAX)-ЭКВИВАЛЕНТНОСТЬ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ ... 1159
порядка, который будем обозначать тем же символом (тогда для x, y ∈ X запись
„x ≤ y в T ” равносильная записи „x ≤ y в X”); одноэлементные подмножества
отождествляются с самими элементами. Для простоты будем писать x ∈ T вместо
x ∈ T0, X ⊂ T вместо X ⊂ T0 и т. п. (эти естественные упрощения использовались
и во введении).
Подмножество X называем нижним (соответственно верхним), если x ∈ X
всякий раз, когда x < y (соответственно x > y) и y ∈ X, и плотным, если x ∈ X
всякий раз, когда y < x < z и y, z ∈ X. Очевидно, что нижние и верхние подмно-
жества являются плотными. Через
←
A и
→
A, где A — подмножество T, будем обо-
значать соответственно наименьшее нижнее и наименьшее верхнее подмножество
в T, содержащее A. Подмножество
↔
A=
←
A ∩
→
A, являющееся наименьшим плотным
подмножеством, которое содержит A, будем называть замыканием подмножества
A в S.
Запись X < Y для подмножеств T будет означать, что x < y для любых
x ∈ X, y ∈ Y Заметим, что Z < ∅ и ∅ < Z для любого подмножества Z. Далее,
запись x >< y означает, что элементы x и y несравнимы. Положим T><(a) = {x ∈
∈ T |x >< a}. Для элемента a ∈ T обозначим через {a}< (соответственно {a}>)
подмножество всех x ∈ T таких, что x < a (соответственно x > a).
Шириной ч. у. множества T называется максимальное число ее попарно несрав-
нимых элементов; обозначается она через w(T ).
Ч. у. множество T называют суммой подмножеств A и B и пишут T = A + B,
если T = A ∪ B и A ∩ B = ∅. Если при этом A < B, то эту сумму называ-
ют ординальной, а если x >< y для любых x ∈ A, y ∈ B, — прямой; в первом
случае будем писать T = {A < B}, а во втором — T = A
∐
B. Эти определе-
ния естественно обобщаются на случай произвольного числа подмножеств. Ч. у.
множество называется примитивным, если оно является прямой суммой цепей
(линейно упорядоченных множеств).
3. Свойства min-эквивалентных ч. у. множеств. Min-эквивалентность ч. у.
множеств обозначается символом ∼=min (а ∼= означает изоморфизм ч. у. множеств).
Если T2
∼=min T1, то (согласно определению) T2 и T1 равны как обычные мно-
жества; значит, каждое подмножество X ⊂ T1 является подмножеством и в T2, но
не обязательно с тем же частичным порядком. Если же отношение порядка на X
не изменилось, то часто (чтобы отметить этот факт) будем писать X◦ вместо X
(для X ⊂ T2).
Пусть S — ч. у. множество. Конечную последовательность α = (x1, x2, . . . , xp)
элементов xi ∈ S назовем min-допустимой, если выражение S = S↑↑...↑x1x2...xp
имеет
смысл (случай p = 0 не исключается). В этом случае будем также писать S = S↑α.
Множество всех min-допустимых последовательностей обозначаем P(S), а
множество всех таких последовательностей без повторений — P1(S). Подмно-
жество в S, состоящее из всех элементов xi последовательности α ∈ P1(S), будем
обозначать через [α]S . Заметим, что если S и T min-эквивалентны, то не всегда
существует α ∈ P1(S) такое, что T = S↑α (см. п. 6 в [6]).
Согласно следствию 5 [6] в P1(S) существует последовательность α такая,
что [α]S = X, тогда и только тогда, когда подмножество X нижнее. А согласно
следствию 9 [6], если α, β ∈ P1(S) и [α]S = [β]S , то S↑α = S↑β . Значит, для нижнего
подмножества X естественно определить ч. у. множество S↑X , считая, что S↑X =
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
1160 В. М. БОНДАРЕНКО, М. В. СТЕПОЧКИНА
= S↑α, где α ∈ P1(S) — любая из последовательностей таких, что [α]S = X. Из
предложения 6 [6] следует, что в S = S↑X подмножество X будет уже верхним, а
значит, Y = S \X — нижним (с теми же частичными порядками); при этом y < x
для y ∈ Y и x ∈ X (в S) тогда и только тогда, когда y >< x в S. В частности, если
S = X
∐
Y (соответственно S = {X < Y }), то S↑X = {Y < X} (соответственно
S↑X = X
∐
Y ).
Приведем теперь некоторые утверждения, необходимые для дальнейшего изло-
жения. Как и раньше, S — произвольное ч. у. множество. Через M−(S) (соот-
ветственно M+(S)) будем обозначать множество всех его минимальных (соответ-
ственно максимальных) элементов.
Лемма 1 (лемма о циклической перестановке). Пусть X = R
∐
{M < N} —
подмножество ч. у. множества S. Тогда существуют T1, T2
∼=min S, в которых
соответственно X = M◦
∐
{N◦ < R◦} и X = N◦
∐
{R◦ < M◦}.
Действительно, в качестве T1 и T2 можно взять ч. у. множество T = S↑Y соот-
ветственно при Y = S\
→
N и Y =
←
M .
Следствие 1. Если S содержит подмножества A и B такие, что A < B,
то A ∪B = A◦
∐
B◦ в некотором T ∼=min S.
Действительно, в условии леммы нужно положить M = A, N = B, R = ∅.
Следствие 2. Пусть L = L1
∐
. . .
∐
Lm — примитивное подмножество S
(L1, . . . , Lm — непустые цепи) и c — элемент S такой, что c > Li для любого
i 6= m и {c}< ∩Lm = ∅. Тогда существует T1
∼=min S, содержащее примитивное
подмножество L′ = L◦1
∐
. . .
∐
L◦m−1
∐
L′m, где L′m — цепь порядка |Lm| + 1,
содержащая L◦m.
Действительно, случай w(L) < 3 тривиален, а при w(L) ≥ 3 нужно применить
лемму для M = L1 + . . . + Lm−1, N = {c}, R = Lm.
Лемма 2. Пусть L — плотное подмножество S. Тогда существует T ∼=min
∼=min S, в котором L является нижним подмножеством с тем же частичным
порядком.
Действительно, в качестве T можно взять T = S↑P при P = ∪x∈M−(L){x}<.
В заключение этого пункта приведем одно утверждение в общем случае (т. е.
для последовательностей из P(S); оно доказано в [6] (лемма 26).
Предложение 1. Пусть α = (x1, x2, . . . , xm) ∈ P(S), X — подмножество S
и αX — подпоследовательность α, состоящая из всех xi ∈ X. Тогда αX ∈ P(X)
и X↑αX
— подмножество S↑α.
4. Свойства квадратичной формы Титса, связанные с ее неотрицатель-
ностью. Согласно основному результату работы [4] квадратичные формы Титса
min-эквивалентных ч. у. множеств являются эквивалентными. Отсюда, в частно-
сти, имеем следующее утверждение.
Предложение 2. Пусть S и T — min-эквивалентные ч. у. множества. Тогда
их формы Титса одновременно являются или не являются неотрицательными.
Напомним, что полуцепью называется ординальная сумма S = {A1 < A2 . . .
. . . < As} антицепей Ai длины 1 и 2 (антицепь длины m — это ч. у. множество,
состоящее из m попарно несравнимых элементов). Это эквивалентно тому, что
w(S) < 3 и S не содержит подмножеств ширины 2 вида {a}
∐
{b < c}. Множества
Ai называются звеньями полуцепи. В случае, когда все звенья одноэлементные, S
— цепь.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
(MIN, MAX)-ЭКВИВАЛЕНТНОСТЬ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ ... 1161
Предложение 3. Если ч. у. множество S является прямой суммой двух полу-
цепей, то его форма Титса неотрицательна.
Доказательство. В силу леммы о циклической перестановке при X = S,
M = ∅ и предложения 2 достаточно считать, что S — полуцепь; кроме того, можно,
очевидно, считать, что все ее звенья двухэлементные. Итак, пусть S = {A1 <
< A2 < . . . < As}, где Ai = {i−, i+}. Тогда легко видеть, что 2qS(z) = z2
0 +
+
∑s
i=1
(zi− − zi+)2 +
(
z0 −
∑
j∈S
zj
)2
, откуда имеем, что форма qS(z) неотри-
цательна.
Наконец, приведем утверждение о неотрицательности формы Титса для неко-
торых конкретных ч. у. множеств, которое понадобится в дальнейшем.
Лемма 3. Квадратичная форма Титса является неотрицательной для сле-
дующих ч. у. множеств:
S1 =
{
1 ≺ 5, 2 ≺ 6, 3 ≺ 7, 4 ≺ 8, 1 ≺ 6, 2 ≺ 7, 3 ≺ 8, 4 ≺ 5
}
,
S2 =
{
2 ≺ 5, 3 ≺ 6, 4 ≺ 7, 2 ≺ 6, 3 ≺ 7, 4 ≺ 5
}
,
S3 =
{
2 ≺ 5, 3 ≺ 6, 4 ≺ 7, 1 ≺ 5, 1 ≺ 6, 1 ≺ 7
}
,
S4 =
{
2 ≺ 4, 5 ≺ 6 ≺ 7 ≺ 8 ≺ 9, 3 ≺ 4, 3 ≺ 6
}
,
S5 =
{
2 ≺ 5 ≺ 6, 4 ≺ 7 ≺ 8, 3 ≺ 5, 3 ≺ 7
}
,
S6 =
{
1 ≺ 4, 2 ≺ 5, 6 ≺ 7 ≺ 8 ≺ 9, 2 ≺ 4, 3 ≺ 5, 3 ≺ 7
}
,
S7 =
{
1 ≺ 3, 2 ≺ 3, 4 ≺ 6, 5 ≺ 6, 2 ≺ 7, 4 ≺ 7, 7 ≺ 8
}
,
S8 =
{
1 ≺ 3 ≺ 4, 6 ≺ 7 ≺ 8, 2 ≺ 3, 2 ≺ 9, 5 ≺ 7, 5 ≺ 9
}
,
S9 =
{
1 ≺ 4 ≺ 7, 2 ≺ 5 ≺ 8, 3 ≺ 6 ≺ 9, 1 ≺ 8, 2 ≺ 9, 3 ≺ 7
}
,
S10 =
{
1 ≺ 2, 3 ≺ 4, 5 ≺ 6 ≺ 7 ≺ 8 ≺ 9, 3 ≺ 7
}
,
S11 =
{
1 ≺ 2, 3 ≺ 4 ≺ 5, 6 ≺ 7 ≺ 8 ≺ 9, 1 ≺ 5, 3 ≺ 8
}
,
S12 =
{
1 ≺ 2, 3 ≺ 4 ≺ 5 ≺ 6, 7 ≺ 8 ≺ 9, 1 ≺ 5, 3 ≺ 9
}
,
S13 =
{
1 ≺ 2 ≺ 3, 4 ≺ 5 ≺ 6, 7 ≺ 8 ≺ 9, 5 ≺ 8
}
,
S14 =
{
2 ≺ 3 ≺ 4, 5 ≺ 6 ≺ 7 ≺ 8 ≺ 9, 2 ≺ 8
}
.
В условии леммы предполагается, что каждое из множеств Si состоит из эле-
ментов 1, 2, . . . , s, где s — наибольшее число, содержащееся в его определении в
явном виде.
Неотрицательность квадратичной формы Титса для перечисленных ч. у. мно-
жеств доказана в [8] (см. лемму 4.3).
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
1162 В. М. БОНДАРЕНКО, М. В. СТЕПОЧКИНА
5. WNPWNPWNP -критические ч. у. множества. Пусть 〈p〉 обозначает цепь 1 <
< 2 < . . . < p, а 〈p, q, . . . , r〉 — прямую сумму цепей 〈p〉, 〈q〉, . . . , 〈r〉. Положим
N = {1 ≺ 2, 3 ≺ 4, 1 ≺ 4}.
Предложение 4. Ч. у. множество является WNP -критическим тогда и
только тогда, когда оно изоморфно одному из следующих ч. у. множеств: N1 =
= 〈1, 1, 1, 1, 1〉, N2 = 〈1, 1, 1, 2〉, N3 = 〈2, 2, 3〉, N4 = 〈1, 3, 4〉, N5 = 〈1, 2, 6〉,
N6 = N
∐
〈5〉.
Доказательство. Из теоремы A [2] и предложения 3 [1] следует, что, во-
первых, любое ч. у. множество с не слабо неотрицательной формой Титса со-
держит в качестве подмножества некоторое Ni, и, во-вторых, любое собственное
подмножество каждого из Ni имеет слабо неотрицательную форму Титса. При до-
казательстве теоремы B [2] показано, что форма Титса каждого из Ni не является
слабо неотрицательной. Из этих трех фактов следует, очевидно, справедливость
доказываемого предложения.
Ч. у. множества N1 –N6 впервые появились в статье Л. А. Назаровой [9]
(посвященной описанию ручных ч. у. множеств), и поэтому будем называть их
критическими множествами Назаровой. Их подмножества K1 = 〈1, 1, 1, 1〉, K2 =
= 〈2, 2, 2〉, K3 = 〈1, 3, 3〉, K4 = 〈1, 2, 5〉, K5 = N
∐
〈4〉 называют критическими
множествами Клейнера; появившиеся в работе [10], они играют такую же роль,
как и множества Назаровой, но уже при описании ч. у. множеств конечного типа.
В случае, когда P — заранее определенное ч. у. множество (например, P = Ki
или P = Ni), будем говорить, что ч. у. множество T содержит P, если T содержит
X, изоморфное P ; если при этом T = P, то будем говорить, что T имеет вид P.
Непосредственно из определений имеем следующие утверждения.
Лемма 4. Замыкание неплотного подмножества вида Ki содержит некото-
рое Nj .
Лемма 5. Если примитивное ч. у. множество T содержит как собственное
подмножество некоторое Ki, то оно содержит некоторое Nj .
Из последней леммы и следствий 1, 2 имеем такое утверждение.
Лемма 6. Если ч. у. множество S содержит некоторое примитивное K =
= Ki и x ∈ S — такой элемент, что K ′ = K ∩ {x}< имеет ширину w ≥ w(S)− 1
и выделяется прямым слагаемым из K (в частности, совпадает с K), то суще-
ствует T ∼=min S, содержащее некоторое Nj .
Действительно, это следует из леммы 5, если предварительно в случае w(K ′) =
= w(S) воспользоваться следствием 1 при A = K, B = x (с учетом того, что в
этом случае K ′ = K), а в случае w(K ′) = w(S) − 1 — следствием 2 при L = K,
Lm = K \K ′.
Докажем теперь следующее утверждение.
Предложение 5. Любое WNP -критическое ч. у. множество является NP -
критическим.
Доказательство. Согласно определению форма Титса WNP -критического
множества не является неотрицательной. Далее, используя предложение 4, легко
видеть, что любое максимальное подмножество M каждого WNP -критического
множества является либо подмножеством (не обязательно собственным) некоторо-
го критического множества Клейнера, либо прямой суммой двух полуцепей (общее
число двухэлементных звеньев которых не превышает 1). В первом случае фор-
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
(MIN, MAX)-ЭКВИВАЛЕНТНОСТЬ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ ... 1163
ма Титса множества M неотрицательна по лемме 4.3 работы [8], а во втором —
по предложению 3 (согласно предложению 21 [6] во втором случае форма Титса
положительна).
6. Теорема о ч. у. множествах без WNPWNPWNP - критических подмножеств. Будем
рассматривать такие ч. у. множества, что любые min-эквивалентные им ч. у. мно-
жества не содержат критических множеств Назаровой; совокупность всех таких
ч. у. множеств обозначим через F .
Основным при доказательстве теорем 1 и 2 будет следующее утверждение.
Теорема 3. Форма Титса ч. у. множества S ∈ F неотрицательна.
Заметим, что теорему 3 достаточно доказать для любого фиксированного ч. у.
множества, которое min-эквивалентно S. Мы будем пользоваться этим, выбирая в
различных случаях наиболее подходящее ч. у. множество.
Перейдем к доказательству теоремы 3. Очевидно, что w(S) ≤ 4 (иначе S ⊃ N1).
Если любое ч. у. множество T ∼=min S не содержит критических множеств Клейне-
ра, то согласно предложению 24 [6] форма Титса ч. у. множества S положительна.
Поэтому будем считать, что S содержит хотя бы одно K ∼= Ki, 1 ≤ i ≤ 5, причем
S 6= K (так как ч. у. множества Ki имеют неотрицательную форму Титса; это
следует хотя бы из леммы 3).
Рассмотрим сначала случай, когда K ∼= K1.
В силу леммы 2 при L = K1 можно считать, что K = M−(S); пусть K =
= {a1, a2, a3, a4}. Подмножество {ai}>∩{aj}> обозначим через Lij ; так как Lji =
= Lij , в дальнейшем, при рассмотрении этих множеств, будем всегда считать (из
соображений удобства), что i < j. Поскольку w(S) = 4 и S 6⊇ N2, объединение
всех L̂ij = Lij ∪ {ai, aj} равно S. Кроме того, в силу леммы 6 подмножества Lij и
Lpq не пересекаются при (i, j) 6= (p, q). Тогда каждое Lij — полуцепь (возможно,
пустая), иначе K∪Lij содержит N1 или N2 (в зависимости от того, существует ли
в Lij подмножество X ∼= 〈1, 1, 1〉 или Y ∼= 〈1, 2〉).
Если непустой является только одна из полуцепей Lij (ширины 1 или 2) или
непусты только две полуцепи Lij и Lpq при {i, j} ∩ {p, q} = ∅, то S — прямая
сумма двух полуцепей и в силу предложения 3 qS(z) ≥ 0. Сюда же по сути отно-
сится случай, когда существует хотя бы одно Lij , являющееся полуцепью ширины
2, поскольку тогда каждое Lpq при |{i, j}∩{p, q}| = 1 пустое, так как в противном
случае подмножество, состоящее из двух несравнимых элементов a, b ∈ Lij , лю-
бого элемента c ∈ Lpq и элементов подмножества K \ {ai, aj} (порядка 2), имеет
вид N2.
Таким образом, для K ∼= K1 осталось рассмотреть случай, когда каждое Lij
является цепью (возможно, пустой), причем все Lij попарно не пересекаются и
существуют Lpq, Lrs 6= ∅ такие, что |{p, q} ∩ {r, s}| = 1. Положим lij = |Lij | и
обозначим через m = m(S) число непустых Lij .
Если при этом либо a) m = 4, либо b) m = 3 и для (попарно различных
и непустых) Lij , Lpq, Lrs выполняются равенства
∣∣{i, j} ∩ {p, q}
∣∣ = 1,
∣∣{p, q} ∩
∩ {r, s}
∣∣ = 1,
∣∣{i, j} ∩ {r, s}∣∣ = 1,
∣∣{i, j} ∩ {p, q} ∩ {r, s}
∣∣ = 0, либо c) m = 3 и
для (попарно различных и непустых) Lij , Lpq, Lrs выполняется равенство
∣∣{i, j}∩
∩ {p, q} ∩ {r, s}
∣∣ = 1, то (с точностью до перенумерации минимальных элементов)
имеет место один из таких случаев: 1.1) l12 = l23 = l34 = l14 = 1; 1.2) l12 ≥ 1,
l23 ≥ 1, l34 ≥ 1, l14 > 1; 2.1) l12 = l23 = l13 = 1; 2.2) l12 ≥ 1, l23 ≥ 1, l13 > 1;
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
1164 В. М. БОНДАРЕНКО, М. В. СТЕПОЧКИНА
3.1) l12 = l13 = l14 = 1; 3.2) l12 ≥ 1, l13 ≥ 1, l14 > 1. Здесь случаи 1.1 и 1.2
соответствуют условию a), случаи 2.1 и 2.2 — условию b), случаи 3.1 и 3.2 —
условию c). Заметим, что не указанные lij мы считаем нулевыми2.
Если же не выполняется ни одно из условий a) – c), то (с точностью до пере-
нумерации минимальных элементов) либо m = 2 и при этом L23, L34 6= ∅, либо
m = 3 и при этом L12, L23, L34 6= ∅. Положим в этих случаях соответственно
l = (l23, l34) и l = (l12, l23, l34), считая возможным (при рассмотрении конкретных
ч. у. множеств) некоторые координаты вектора l задавать не конкретным числом, а
неравенствами вида > z и ≥ z, где z — некоторое натуральное число, а также более
привычными неравенствами вида z1 ≤ s ≤ z2. В этой ситуации имеет место, как
легко видеть, один из следующих случаев: 4.1) l = (1, 1 ≤ s ≤ 4); 4.2) l = (1, > 4);
5.1) l = (2, 2); 5.2) l = (≥ 2, > 2); 6.1) l = (1, 1, 1 ≤ s ≤ 3); 6.2) l = (1, 1, > 3);
7.1) l = (1, 2, 1); 7.2) l = (1, > 2, 1); 8.1) l = (2, 1, 2); 8.2) l = (≥ 2, 1, > 2);
9) l = (≥ 1, > 1, > 1).
Проанализуем теперь случаи 1.1 – 1.9.
В случаях i.1 при i = 1, 2, . . . , 8 ч. у. множество S содержится, с точностью до
изоморфизма, в Si (см. лемму 3). В случаях 1.2 и 2.2 S содержит N2, в случаях 3.2,
7.2 и 9 —N3, в случаях 5.2 и 8.2 —N4, в случае 4.2 —N5 и в случае 6.2 —N6. Отсюда
(с учетом леммы 3) следует, что если S ∈ F , то его форма Титса неотрицательна.
Пусть теперь K ∼= Ki при i > 1. Считаем, что любое T ∼=min S не содержит K1
(поскольку случай K ∼= K1 уже рассмотрен); тогда по следствию 1 ч. у. множество
T не содержит подмножеств вида Q13 = {R1 < R3}, Q31 = {R3 < R1} и Q22 =
= {R2 < R′2}, где R1
∼= 〈1〉 — множество, состоящее из одного элемента u0, R2
∼=
∼= 〈1, 1〉 (соответственно R′2
∼= 〈1, 1〉) — множество, состоящее из двух несравнимых
элементов u1 и u2 (соответственно u′1 и u′2) и R3
∼= 〈1, 1, 1〉— множество, состоящее
из трех попарно несравнимых элементов v1, v2 и v3.
Далее, по лемме 4 подмножество K является плотным. А тогда в силу леммы 2
при L = Ki можно считать, что K — нижнее подмножество S. Отсюда, в частности,
имеем M−(K) = M−(S). Полагаем M−(K) = {a1, a2, a3} и M+(K) = {b1, b2, b3},
причем считаем, что a1 ≤ b1, a2 < b2, a3 < b3.
Рассмотрим сначала случаи K ∼= Ki при i 6= 5.
Положим Bij = {bi}> ∩ {bj}>, Lij = {ai}> ∩ {bj}> (будем рассматривать
их только для i 6= j) и, кроме того, Ci = {bi}< ∪ bi. По лемме 5 K является
максимальным примитивным подмножеством как в самом S, так и в каждом T ∼=min
∼=min S, в которомK ∼= Ki. Тогда по лемме 6 Bij = ∅, а значит, S\K — объединение
всех подмножеств Lij (иначе S содержитK1), причем они попарно не пересекаются
(иначе S ⊃ Q31). Кроме того, если Lij непусто, то Lis при j 6= s и Lji являются
пустыми (иначе соответственно S ⊃ Q13 и S ⊃ Q22). Из Bij = ∅ и w(S) = 3
следует также, что Lij является цепью.
Как и в случае K ∼= K1, число непустых Lij обозначим через m = m(S) и
положим lij = |Lij |.
Пусть сначала K ∼= K2. Если при этом m = 3, то (с точностью до перестановки
в индексах чисел 1, 2, 3) имеет место один из следующих случаев: 10.1) l12 = l23 =
= l31 = 1; 10.2) l12 ≥ 1, l23 ≥ 1, l31 > 1. Если же m = 1, 2, имеет место один из
таких случаев (в которых не указанные lij являются нулевыми): 11.1) 1 ≤ l12 ≤ 3;
2Это соглашение будет иметь место и при рассмотрении случаев K ∼= Ki при i > 1.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
(MIN, MAX)-ЭКВИВАЛЕНТНОСТЬ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ ... 1165
11.2) l12 > 3; 12.1) l12 = 1, l23 = 2; 12.2) l12 ≥ 1, l23 > 2; 13.1) l12 = 2, l23 = 1;
13.2) l12 > 2, l23 ≥ 1.
Проанализуем теперь случаи 10.1 – 13.2.
В случаях i.1 при i = 10, 11, 12, 13 ч. у. множество S содержится, с точностью
до изоморфизма, в Si−1 (см. лемму 3). В случаях 10.2, 11.2, 12.2 и 13.2 S содержит
соответственно N3, N5, N6 и N4. Отсюда (с учетом леммы 3) следует, что если
S ∈ F , то его форма Титса неотрицательна.
Пусть теперь K ∼= K3; при этом можно считать, что любое T ∼=min S не
содержит K2 (так как случай K ∼= K2 уже рассмотрен). Согласно введенным
выше обозначениям M−(K) = {a1, a2, a3} и M+(K) = {b1, b2, b3}, где a1 = b1,
a2 < b2, a3 < b3; обозначим через c2 и c3 „недостающие” элементы подмножества
K: a2 < c2 < b2, a3 < c3 < b3.
Отметим, что множество Kij = {ci}> ∩ {bj}> является пустым, если i 6= j
и при этом i, j 6= 1, так как в противном случае согласно следствию 2 при L =
= L1
∐
L2
∐
L3, L1 = {ai, ci}, L2 = {aj , cj , bj} и L3 = {a1}, некоторое T1
∼=min S
содержит N3. Далее, Li1 при i = 2, 3 совпадает с Ki1, иначе K ∪ (Li1 \ Ki1)
содержит N3. При этом если Li1 6= ∅, то m = 1, так как в случае, когда Lij 6= ∅,
j 6= 1, подмножество K ∪ Li1 ∪ Lij содержит Q13, а в случае, когда Lji 6= ∅,
j 6= 1, — K2.
Значит (с точностью до перестановки в индексах чисел 2 и 3), имеет место один
из таких случаев: 14.1) l21 ≤ 2; 14.2) l21 > 2; 15.1) l23 ≤ 2; 15.2) l23 > 2. И
в случаях 14.1 и 15.1 ч. у. множество S содержится, с точностью до изоморфизма,
соответственно в S13, S14 (см. лемму 3), а в случаях 14.2 и 15.2 S содержит
соответственно N4 и N5. Итак, для S ∈ F его форма Титса неотрицательна.
Покажем теперь, что в случае K ∼= K4 существует T ∼=min S, содержащее K2
или K3, а соответствующие случаи уже рассмотрены. Согласно введенным выше
обозначениям M−(K) = {a1, a2, a3} и M+(K) = {b1, b2, b3}, где a1 = b1, a2 < b2,
a3 < b3; обозначим через c3, d3, e3 „недостающие” элементы подмножества K :
a3 < c3 < d3 < e3 < b3.
Подмножество L23 является пустым, так как в противном случае, если f обо-
значает максимальный элемент L23, S↑P при P = S \ f содержит N6 (более то-
чно, K ∪ f имеет вид N6). Если L32 6= ∅ и g ∈ L32, то g > c3, иначе подмно-
жество (K \ a3) ∪ g имеет вид N4; тогда по следствию 2 при L = L1
∐
L2
∐
L3,
L1 = {a3, c3}, L2 = C2, L3 = a1, существует T1
∼=min S, в котором K∪g имеет вид
K2. Если же L31 6= ∅ и h ∈ L31, то h > d3, иначе (K \ {a3, c3} ∪ h имеет вид N3;
тогда по следствию 2 при L = L1
∐
L2
∐
L3, L1 = C1, L2 = {a3, c3, d3}, L3 = C2,
существует T1
∼=min S, в котором K ∪ h имеет вид K3. Наконец, если L21 6= ∅ и
t ∈ L21, то K ∪ t имеет вид N6.
Нам осталось рассмотреть случай, когда K ∼= K5.
Обозначим через U подмножество K, состоящее из элементов a1, b1, a2, b2,
причем считаем, что a1 < b2. „Недостающие” элементы K обозначим через c3
и d3, считая, что c3 < d3. Тогда K = U
∐
C3, где C3 = {a3 < c3 < d3 < b3};
положим C1 = {a1, b1}, C2 = {a2, b2}.
Нам понадобится одно утверждение, которое (в нужной для нас общнос-
ти) конкретизирует следствие 2 и очевидным образом вытекает из его доказа-
тельства.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
1166 В. М. БОНДАРЕНКО, М. В. СТЕПОЧКИНА
Следствие 3. Пусть S, L = L1
∐
. . .
∐
Lm и c — те же, что в условии
следствия 2, причем m = 3, |L1| = i, |L2| = j, |L3| = max(i, j) − 1 и при этом
i ≤ j и i + j = 4. Тогда существует T1
∼=min S, содержащее Kj .
Покажем, что случай K ∼= K5 сводится к рассмотренным случаям K ∼= K2 и
K ∼= K3, а именно, существует T ∼=min S, содержащее K2 или K3.
Предположим, что это не так, т. е. что каждое ч. у. множество T, min-эквивалент-
ное S, не содержит ни K2, ни K3, и покажем, что в этом случае приходим к
противоречию.
Покажем сначала, что S разложимо (относительно прямой суммы, которая опре-
делена выше). Пусть это не так, тогда существует x такой, что {x}< ∩ U 6= ∅ и
{x}< ∩ C3 6= ∅; значит, x > a3. Положим R = {x}< ∩ U. Очевидно, что b2 /∈ R
(иначе K ∪ x содержит Q31). По той же причине R не может одновременно со-
держать элементы a1 и a2 (соответственно b1 и a2). Кроме того, если a1 ∈ R,
то и b1 ∈ R, иначе K ∪ x содержит Q13. Таким образом, для R остается всего
две возможности: a) R = C1; b) R = {a2}. Cлучай a) невозможен, так как при
x >< c3 подмножество K ∪ x содержит K3, а при x > c3 в силу следствия 3 для
L1 = C1, L2 = {a3, c3}, L3 = {a2} и c = x существует T1
∼=min S, содержащее K2.
Cлучай b) также невозможен, так как при x >< b3 подмножество M+(K) ∪ x имеет
вид K1, а при x > b3 в силу следствия 3 для L1 = a2, L2 = C3 \ b3, L3 = C1 и
c = x существует T1
∼=min S, содержащее K3 (легко видеть, что из доказательства
следствия 2 вытекает, что существует даже T1
∼=min S, содержащее N4).
Итак, S разложимо в прямую сумму двух собственных подмножеств; понятно,
что одно из них содержит U, а другое — C3. Значит, существует x такой, что либо
{x}< ∩ U = ∅, {x}< ∩ C3 6= ∅, либо наоборот {x}< ∩ U 6= ∅, {x}< ∩ C3 = ∅.
В первом случае при x >< b3 подмножество M+(K) ∪ x имеет вид K1, а при
x > b3 подмножество K∪ x — вид N6. Покажем, что и второй случай невозможен.
Положим V = T><(x)∩U. Легко видеть, что V является подмножеством U ширины
w ≤ 1 (иначе K ∪ x содержит K1); кроме того, V — верхнее подмножество, ибо
подмножество U \V = {x}<∩U является нижним. И в случае w = 1 подмножество
K ∪ x содержит Q22, если V = {b2}, и N4, если V = {b1} или V = C2. Если же
V пусто, то по лемме о циклической перестановке (при M = U, N = x, R = C3)
существует T1
∼=min S, в котором K ∪ x имеет вид N6.
Итак, пришли к противоречию и, следовательно, существует T ∼=min S, содер-
жащее K2 или K3.
Теорема 3 доказана.
7. Доказательство теорем 1 и 2. Теперь нетрудно доказать теоремы 1 и 2.
Докажем сначала теорему 2. Если ч. у. множество S min-эквивалентно WNP -
критическому множеству N , то в силу предложений 2 и 5 форма Титса qS(z) не
является неотрицательной. Легко видеть, что из предложения 1 (с учетом пред-
ложений 2 и 5) следует, что каждое собственное подмножество R ⊂ S имеет
неотрицательную форму Титса; действительно, иначе N имело бы собственное
подмножество Q ∼=min R, форма Титса которого не является неотрицательной, а
это противоречило бы тому факту, что множество N является NP -критическим.
Таким образом, S является NP -критическим.
Наоборот, если S является NP -критическим, то по теореме 3 оно min-эквива-
лентно некоторому ч. у. множеству S′, которое содержит WNP -критическое мно-
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
(MIN, MAX)-ЭКВИВАЛЕНТНОСТЬ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ ... 1167
жество N ∼= Ni. Но тогда (снова в силу предложений 1 и 2) S′ = N, а значит, S
min-эквивалентно N.
Переходим к доказательству теоремы 1. Утверждение 2 теоремы непосред-
ственно следует из предложения 2. Если же S удовлетворяет условию утверж-
дения 1, то любое ч. у. множество, которое min-эквивалентно S, не содержит
WNP -критических подмножеств (согласно определению последних), а значит, по
теореме 3 S имеет неотрицательную форму Титса.
1. Дрозд Ю. А. Преобразования Кокстера и представления частично упорядоченных множеств //
Функц. анализ и его прил. – 1974. – 8. – C. 34 – 42.
2. Завадский А. Г., Назарова Л. А. Частично упорядоченные множества ручного типа // Матрич-
ные задачи. – Киев: Ин-т математики АН УССР, 1977. – С. 122 – 143.
3. Бондаренко В. М., Полищук А. М. О критерии положительной определенности для одного
класса бесконечных квадратичных форм // Нелiнiйнi коливання. – 2003. – 6, № 1. – С. 3 – 14.
4. Bondarenko V. M. On (min, max)-equivalence of posets and applications to the Tits forms // Вiсн.
Київ. ун-ту. Фiзика i математика. – 2005. – № 1. – С. 24 – 25.
5. Bondarenko V. M., Styopochkina M. V. On posets of width two with positive Tits form // Algebra
and Discrete Math. – 2005. – № 2. – P. 11 – 22.
6. Бондаренко В. М., Степочкина М. В. (Min, max)-эквивалентность частично упорядоченных
множеств и квадратичная форма Титса // Проблеми аналiзу i алгебри: Зб. праць Iн-ту матема-
тики НАН України. – 2005. – 2, № 3. – С. 18 – 58.
7. Bondarenko V. M., Styopochkina M. V. On finite posets of infinite type and their Tits forms // Algebra
and Discrete Math. – 2006. – № 2. – P. 17 – 21.
8. Бондаренко В. М., Завадский А. Г., Назарова Л. А. О представлениях ручных частично упо-
рядоченных множеств // Представления и квадратичные формы. – Киев: Ин-т математики АН
УССР, 1979. – С. 75 – 106.
9. Назарова Л. А. Частично упорядоченные множества бесконечного типа // Изв. АН СССР.
Сер. мат. – 1975. – 39, № 5. – С. 963 – 991.
10. Клейнер М. М. Частично упорядоченные множества конечного типа // Зап. науч. сем. ЛОМИ.
– 1972. – 28. – C. 32 – 41.
Получено 05.02.08
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 9
|
| id | umjimathkievua-article-3234 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus English |
| last_indexed | 2026-03-24T02:38:41Z |
| publishDate | 2008 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/6a/73b73f3db974d97fecadf5c6f9dd896a.pdf |
| spelling | umjimathkievua-article-32342020-03-18T19:48:57Z $(\min, \max)$-equivalence of posets and nonnegative Tits forms $(\min, \max)$-эквивалентность частично упорядоченных множеств и неотрицательные формы Титса Bondarenko, V. M. Stepochkina, M. V. Бондаренко, В. М. Степочкина, М. В. Бондаренко, В. М. Степочкина, М. В. We study the relationship between the (min, max)-equivalence of posets and properties of their quadratic Tits form related to nonnegative definiteness. In particular, we prove that the Tits form of a poset S is nonnegative definite if and only if the Tits form of any poset $(\min, \max)$-equivalent to S is weakly nonnegative. Вивчається зв'язок між (min, max)-еквiвалентнiстю частково впорядкованих множин та властивостями їх квадратичної форми Тітса, пов'язаних із невід'ємною визначеністю. Зокрема, доведено, що форма Тітса частково впорядкованої множини S невід'ємно визначена тоді i лише тоді, коли форма Тітса будь-якої частково впорядкованої множини, яка $(\min, \max)$-еквівалентна S, є слабко невід'ємною. Institute of Mathematics, NAS of Ukraine 2008-09-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3234 Ukrains’kyi Matematychnyi Zhurnal; Vol. 60 No. 9 (2008); 1157–1167 Український математичний журнал; Том 60 № 9 (2008); 1157–1167 1027-3190 rus en https://umj.imath.kiev.ua/index.php/umj/article/view/3234/3214 https://umj.imath.kiev.ua/index.php/umj/article/view/3234/3215 Copyright (c) 2008 Bondarenko V. M.; Stepochkina M. V. |
| spellingShingle | Bondarenko, V. M. Stepochkina, M. V. Бондаренко, В. М. Степочкина, М. В. Бондаренко, В. М. Степочкина, М. В. $(\min, \max)$-equivalence of posets and nonnegative Tits forms |
| title | $(\min, \max)$-equivalence of posets and nonnegative Tits forms |
| title_alt | $(\min, \max)$-эквивалентность частично упорядоченных множеств и неотрицательные формы Титса |
| title_full | $(\min, \max)$-equivalence of posets and nonnegative Tits forms |
| title_fullStr | $(\min, \max)$-equivalence of posets and nonnegative Tits forms |
| title_full_unstemmed | $(\min, \max)$-equivalence of posets and nonnegative Tits forms |
| title_short | $(\min, \max)$-equivalence of posets and nonnegative Tits forms |
| title_sort | $(\min, \max)$-equivalence of posets and nonnegative tits forms |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3234 |
| work_keys_str_mv | AT bondarenkovm minmaxequivalenceofposetsandnonnegativetitsforms AT stepochkinamv minmaxequivalenceofposetsandnonnegativetitsforms AT bondarenkovm minmaxequivalenceofposetsandnonnegativetitsforms AT stepočkinamv minmaxequivalenceofposetsandnonnegativetitsforms AT bondarenkovm minmaxequivalenceofposetsandnonnegativetitsforms AT stepočkinamv minmaxequivalenceofposetsandnonnegativetitsforms AT bondarenkovm minmaxékvivalentnostʹčastičnouporâdočennyhmnožestvineotricatelʹnyeformytitsa AT stepochkinamv minmaxékvivalentnostʹčastičnouporâdočennyhmnožestvineotricatelʹnyeformytitsa AT bondarenkovm minmaxékvivalentnostʹčastičnouporâdočennyhmnožestvineotricatelʹnyeformytitsa AT stepočkinamv minmaxékvivalentnostʹčastičnouporâdočennyhmnožestvineotricatelʹnyeformytitsa AT bondarenkovm minmaxékvivalentnostʹčastičnouporâdočennyhmnožestvineotricatelʹnyeformytitsa AT stepočkinamv minmaxékvivalentnostʹčastičnouporâdočennyhmnožestvineotricatelʹnyeformytitsa |