Комплексы систем представителей в исследовании комбинаторных свойств частично упорядоченных множеств и несовместных систем линейных неравенств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ

Институт математики и механики

На правах-рукописи

МАТВЕЕВ Андрей Олегович

КОМПЛЕКСЫ СИСТЕМ ПРЕДСТАВИТЕЛЕЙ В ИССЛЕДОВАНИИ КОМБИНАТОРНЫХ.СВОЙСТВ ЧАСТИЧНО УПОРЯДОЧЕННЫХ МНОЖЕСТВ И НЕСОВМЕСТНЫХ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ

01.01.09 - математическая кибернетика

Автореферат

диссертации на соискание ученой степени • кандидата физико-математическйх наук

Екатеринбург 1994

Работа выполнена в Уральском государственном техническом университете - УГШ, на кафедре автоматики и информационных технологий.

Научные руководители:

доктор технических наук, профессор В.Г. ЛА5УКЕЦ. кандидат технических наук, ведущий научный сотрудник Д.Н. ГАЙНАНОВ

Официальные оппоненты:

доктор физико-математических наук, профессор Г.П. ЕГОРЫЧЕЗ кандидат физико-математических наук С.З. ПЛОТНИКОВ

Ведущая организация?

Уральский государственный университет

Защита состоится кояЪоя 1994 Года в 15 час. на заседании специализированного совета К 002.07.01 по присуждению ученой степени кандидата наук в институте математики и механики Уральского отделения РАН (620066, г.Екатеринбург, ул.С.Ковалевской, 16).

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.

Автореферат разослан " Ч' октяЪев 1994 года.

Ученый секретарь специализированного совета к.ф.-м.'н., ст.н.с.

.Д.СКАРИН

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Методы исследования несобственных задач математического программирования и распознавания образов в силу их связи с многочисленными приложениями составляют важный раздел математической науки. В многообразии таких задач традиционно особо выделяют проблематику несовместных систем линейных неравенств1'. В исследованиях несовместных систем линейных неравенств, связанных с углубленным изучением строения семейств совместных и несовместны:; подсистем, могут эффективно,использоваться методы современной комбинаторики 2'. Данная работа посвящена развитию и адаптации ряда комбинаторных методов к теории линейных неравенств.

Цель работы' состоит в перечислении, выяснении структуры и определении комбинаторных инвариантов семейств совместных подсистем (СП) и несовместных подсистем (НП)-несовместной системы линейных неравенств (НСЛН) с использованием предложенных методов комбинаторного анализа произвольных частично упорядоченных (ч.у.) множеств.

Методика исследования заключается в систематическом использовании комбинаторики ч.у. множеств в сочетании с установленным ранее соответствием свойств НСЛН и выпуклых -многогранников.

Научная новизна. Установлена система соотношений, позволяющая опосредованно исследовать комбинаторику абстрактного симплициального комплекса (АСК). • Уточнены комбинаторные свойства ч.у. множеств важного класса. Проведен

11 Еремин К.И., Мазуров Вл.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования. - М..Наука, 1983.

2)Стенли Р. Перечислительная комбинаторика. - М.: Мир, 1990.

z

всесторонний анализ комбинаторного строения НСЛН. Все результаты являются новыми. .

Теоретическая и практическая ценность. Методы, нацеленные на исследование НСЛН, сформулированы в форме, позволяющей использовать их по отношению к комбинаторным объектам достаточно общего айда. Результаты, касаюедеся НСЛН, могут быть продолжены на комитетные конструкции, находящие эффективное применение в прикладном распознавании образов.

Апробация работа. Основные результаты работы обсуждались на научных семинарах кафедры автоматики и ^информационных технологий, кафедры высшей математики и уравнений математической физики Уральского государственного технического университета и отдела исследования операций Института математики и механики Ур РАН.

Публикации. По теме диссертации опубликовано 5 работ.

Структура и объем диссертации. Работа (119 с.) состоит из введения, трех глав, заключения и списка литературы (89 названий).

СОДЕРЖАНИЕ РАБОТЫ

Во введении" кратко описывается проблематика работы и излагается содержание диссертации по главам.

В11 главы I вводится понятие комплекса систем представителей (КСП).

Пусть и«1в]:«[1,.. .,<*}}, где #4:=ае1, - семейство

' У

непустых, конечных и попарно различных множеств; д(<*) - АСК, состоящий из всех подмножеств ("граней") множеств из л\ - семейство минимальных систем представителей для А.

Определение 1. л будем называть представительно самосопряженным, если зя(ш(^))=4, - в этом случае семейства

ч

л и œU) будем называть представительно сопряженными.

Определение 2. АСК ¿"pU):«A({UU\£|r«aU)]) будем называть

комплексом систем представителей для 4. ' _

В §2 . главы I приводятся соотношения, описывавшие

комбинаторику пары {АСК;КСП).

Пусть Ш:= U А , п*:- П «^МиАД.....Ш\Л }.

jetai 1 jetei 1

f (д)' - количество граней мощности (j+1) из АСК д; размерность

д, dimA:=nax|G|-l; приведенная эйлерова характеристика д, ссД <11вД

*(д):= £ (-l)Jf (д). Пусть д - АСК с множеством вершин иг , 1—г J

}, К - поле и 1д = [xj Zi Jix<iz<...<ir,

1 1 2 r-

[Xj ,. }ед| - идеал кольца многочленов Xix,,... ,xel, порожденный всеми такими свободами от квадратов одночленами

I

х,- х^ ...Xj , что ÎXj } не являются гранями д.

'г ж2 г 1.2 г

Фгктор-кольцо К[д] K{xlt...,хп3/1д называется кольцом

Стэнли-Рейсяера комплекса л. Оно разлагается в прямую сумму

К[д] = К[д1 -»К[д] линейных пространств К1д1ж однородных

многочленов степени п. Размерность - HCKÎд! :=dim^K[д]^

векторного пространства К[д] называет функцией Гильберта, а

формальный степенной ряд F(KU].é):= £ НСК1д],я)-ё* от

■го

переменкой"t - рядом .Гильберта. Известно, что F(K[д],t")= -1 , (йп(д)+...+й , . где А(д):=(Л (д),

... .л , (i))«zd,BA*2, причеи векторы й(д) и f(A):=if,(i),

d 1 mù * 1 , 1

..'.,f .u))ez't,mi полностью определяет друг друга.

d 1 вА

Предлояение 1. Для произвольного л с яЫ) .= {St,... ,

хШл)) = Е (-l)j-#{?cle] J |Tl=j,

jeici *.ет

¿(AU1)) = £ C-l)J.i{rs[aI I in=J. U

jetai «.«г

S

¿(д—и)) = £ (-1)'.#{Гб(«1 I ил "4*0.

3€(СП 1СТ

и если л -семейство Шпернера (т.е. уа»^[а], А^^А^ ¿(¿•ги)) « £ <-1>'.*{Тв[®] | и В мм}.

,)С1а) «.ет

Предложение 2.

2.1) Для произвольного а>1, и |ц4|-1,

2.2) Если то 2.1) справедливо при замене в нем д(«£х) на д(<4) и д*г(«<) на д*гиА). Если - семейство Шпернера,

то 2.1) справедливо при замене в нем ¿Ы1) на д"г(®и)). Предложение 3.

3.1) Для произвольного л, с>1,

¿(диА)) = (-1 ),ы,-1-хишгШ.

3.2) Если о»=". 70 3.1) справедливо при замене в нем дЫ1) на д(«0 и д*г(«<) на д*г(*гх). Если л - семейство Елернера,

то 3.1) справедливо при замене в кем дСл1) на д*г(я(»г)). Предложение 4.

4.1) Для произвольного л, «>1,

1 1 -1 dim iUA) = (Uii - _ Z j—i

I Uli 1-1

dim t'^U) = lUti - E

f/A-'U))

ПШП l j+1'

* f/AU*»

rtUWf] l j+li

- 1 и

- 1.

4.2) Если (у=и, то 4.1) справедливо при замене в нем д(<4А) на.л(л) и д*г(л) на д"г(4а). Если л - семейство Шаернера, то 4.1) справедливо при замене в нем Д{<4Х) на д*г(®(<«)).

Предложение 5.

5.1)' Для произвольного 4, а>1, и ш>0, H(KUUA)],m) = ['^^J ~ '

НСК[д"й)1.ш> - C^^J -'Х'^.^.о-а^^'Г-1) •

5.2) Если п»1=э, то 5.1) справедливо при замене в нем д(«4А) на &Ы) и на д"гиА). Если л - семейство Шпернера,

то 5.1) справедливо при замене в нем д(*А) на д"г(и(.х)). Введем з рассмотрение вектор л(д):=(ло(д'),л (д),...,

(л). определяемый соотношением F(KU],t)=

-i—-r-U (д)м (A)t+...+A,, . (A)t,u4'). Векторы Ш) и

(l~t) IV»!

А(Д) полностью определяют друг друга, но л(д) обладает специфическими свойствами: Предложение 6.

6.1) Для произвольного о>1, и laÄ»|LM|-dimA"r(rf)-2, aUa))=0; для lsbiU4|-ciimAUA)-2, лм(д*ги))=0. . 6.2) Если п4=э, то 6.1) справедливо при замене з нем ¿(а1) на &(л) и на д"г{|Если л - семейство Шпернера,

то 6.1) справедливо при замене в нем д(«гА) на д"г(я(л)).

6.3) Если д не изоморфен булевой решетке, то

lUiil

£ Л (д) = 0.

J-0

Предложение 7.

7.1) Для произвольного а>1, и *>0,

л <iua)) » (-1)**1-- ,

" J-* w 1

Л (д-(4)) - (-1)"*1- '^'PI-aCaC^)) .

* J.k w J

7.2) Если то 7.1) справедливо при замене в нем aUa) на дU) и (л) на д*г(лА). Если л ~ семейство Шпернера,

то 7.1) справедливо при замене в нем ¿.(л1) на д*г(я(4>).

В |3 главы .1 приведены новые следстзия фундаментальной теоремы Филиппа Холла.

Пусть Р - произвольное конечное ч.у. множестзо, Р -пополнение Р новыми наибольшим и наименьшим элементами 0 и 1.

Обозначим через ц(Р)(0,1) число Мебиуса для Р, где и„(0Д) * р

- значение функции Мебиуса и.(х,у) ч.у. множестаа Р при х=0

р

и у1. По определению, ух«Р, дА (х.х):«1; и,(х,у):=- Л

Р Р хЛх«у Р

для всех пар х<у«Р. Введенная в рассмотрение Джан-Карло Рота функция Мебиуса ч.у. множества является ваянейщим объектом и инструментом исследований г современной комбинаторике. Если теорема Ф.Холла связывает к(Р) со структурой семейства цепей из Р, то приводимые в параграфе ее следствия связывают д(Р) со структурой семейства пар несравнимых элементов из Р. Предложение 8.

Будем обозначать через СИ*Х(Р) семейство всех насыщенных цепей в Р, а через А^СР) — семейство всех антицепей мощности 0+1) в Р. Полагаем (-¡С""(Р)=в (в противном случае, как известно, ц(Р)=0). Выполняются соотношения: .

8.1) дСР)

£ .(- 1)1-#{Гс[#Св"(Р)1 | п сь=а).

-

8.2) ц(Р) - (-О .X<A<AJ<P)-1)).

*

8.3) ц(Р) = (-1)""'1.

Е (-1)>-#{Гс[#А1<Р)1 | |Г|=/, и а4=Р}, (р>>

*^«А1(Р)

Предложение 9.

9.1) Пусть АСК Д не изоморфен булевой решетке и д:=ди1

- его пополнение наибольшим элементом 1. Пусть С,оах(д\0)

а

- семейство насыщенных цепей в ч.у. мнояестве д\0; Аг(л\0) -семейство всех антицепей мощности 2 в Д\0. Тогда предложение 8 справедливо при замене в нем Р на A\Ô и и(Р) на *(д). .

9.2) Пусть г - конечная эйлерова решетка { т.е., по • определению, для нее для всех х*у«г, Их,у)

- длина интервала [х,у]с2 ), например, решетка граней ограниченного выпуклого многогранника. Пусть С***(г\{0, 13) —

- семейство всех насыщенных цепей в ч.у. множестве г\{0,1}; А5(2\{0,1}) - семейство всех антицепей мощности 2 в £\[0,1}. Тогда предложение 8 справедливо при'замене в нем Р. на 0,1}

и д(Р) на Mo(Ô,ï)=(-l)pt£)=- PtE,"1(-l)J-«r,, где -

j-O J . ^

количестзо элементов ранга j решетки £, р(г):=К0,1) - ранг решетки £ .

В главе II исследуются АСК, порождаемые атомами и коатомами решетки'£; всюду предполагается, что i - конечная, атомарная, неатомарная, с относительными дополнениями и ранговой функцией " (например, геометрическая или решетка граней многогранника).

В §1 главы II вводится в рассмотрение понятие диагонали решетки, обобщающее известные понятие базйса геометрической решетки и понятие диагонали многогранника, принадлежащее Д.Н.Гайнгнову. .

Определение 3« Нижней [соответственно зерхней] диагональю решетки 2 будем назызать такое минимальное по включению неупорядоченное подмножество Del, что sup D=1 I соответственно inf D=0]. Минимальное по включению неупорядоченное подмножество. De£, для которого одновременно sup D= 1 и inf Р=0, -будем называть главной-диагональю 2. " .

Если Хсг, то через cdU.X), 1Ш(гД) и яз(£Д) обозначим соответственно семейства нижних, верхних и главных диагоналей реиетки 2, целиком содержащихся в подмножестве X. Обозначим

S

тоиД):вг»(е,Х)лШ)(£1Х). Свойства семейств я> и гш для рассматриваемой нами решетки дуальны, поэтому сформулируем лишь свойства семейств гя>, я> и яз*. Предложение 10.

10.1) Р«г»(£):«=гг(г,г) т 0 - минимальное по включению подмножество г, для которого л 5(х)»{1}, где з(х):={ус£|хзу}

к€С

- главный фильтр, порождаемый, элементом х.

10.2) Яегии), М.1} - В - антицепь.

10.3) &>(г) ~ семейство Шпернера.

Следующее предложение связывает материал глав I и II: Предложение 11. Пусть С:=£'-)>:={х«£1р(х)«\Л, 0<,7<р(£), -

j-h^й уровень г, и для любого хе£, С(х):=о(х)лС, где {у«г|уах] - главный идеал, порождаемый элементом х; . с(£(р(£)-1>):={с(х)1хе£ср(г»-1)} тогда секейства с(2(р<£>-1»)^

и £!>(£.,С) ябляются представительно сопряженными покрытиями.С. Каждое из - этих семейств - представительно самосопряженное покрытие С. Следовательно, . - •

д(с(£<р<2,-г))) = д--(-а,(£>С)) и

д'г(С(г'р,£,-1,)А) = д(гг>(г.ОА) . Предложение 12. Пусть а услозиях условия предложения 11, 1<.}<р(£)-1. Тогда

12.1) Кавдое из семейств т'(г,С) и то(£,С) - представительнс самосопряженное, покрытие С.

12.2) пЯ?(£,С)=а.

Главные диагонали следует искать среди нижних и верхних диагоналей:

Предложение 13.

13.1) Пусть £):=?©(2,£); аналогично обозначим семейства р®'(£) и 1ш(е) . Тогда ТО(£)\{0Д}={0€Я)(£)|1п£ 1К)}и {Сегго(г)15ир 1>=1}.

• 13.2) и^гМОД} - в точности семейство пар дополнительных * .

э.тзментов из г.

Предложение 14.

14.1) Пусть Х=е\{6,1} и min p(x)=ir, шах р(х)=»1. Тогда

Х«Х х«Х ■

Ьега(г.х) - 2stDi»p(e)-2+i,'

D*W(Z,X) * 2slD\sk-l,

D«?v(.t,X) » 2s|Di*max (p(e)-l+l,Jc-l).а

14.2) Если г - полумодулярная, то '

Гр(г)'

üe£D(2,2<J') » iDlt -j— ,

где - наименьшее целое, большее или равное z.

В iZ главы II уточняется связь между строением решетки 2 и значением ее функции Мебиуса.

Предложение 15 (переформулировка теоремы Дж.-К.Рота о сечений). Пусть С:=е'-,\ 0<j<p(t).

»j(Ö, 1) (-1 )"J"l-i(4(?»(£, С)"1)) . В частности,

д2(6, 1) - (-«"»".¿МяХе, 2tl,')x)) .

Предложение 16. Пусть С 2tl> - множество атомов . •

решетки г и семейство C(atf>te,"t 1) определено в предложении 11. Пусть «Кг.сМ^,... ,Ру}. Тогда

16.1) u2(Q,i)=i(A(C(e(p<£'"1'))).

16.2) M,(6,i>- Е (~l)J-#{rc(fT ]| tTl — j, л C(x )=e},

где xt€2(p<2>"1'.

16.3) H.iÖ.iM-l)"1"1. E (-1)J '#(Гс[г ] | lTi=»j, Uüt=Cl.

jeiri t«r

16.4) а.(0,1)*=- E E (-1)

k-2 2ЧГ1

16.5) uE(0,l>

c E Sciri.

iSl-i

fir - I U D I

1 .«s • wx - к

— E X ("D

k.l

I n )| tWr 1

lîl-i .

Укажем на частную интерпретацию предложения 16.1). Теорема

Л.Эйлера, оперируя размерностными параметрами описания

ограниченного'выпуклого d-мерного многогранника ?, констатирует,

- - а

что для его решетки граней £, jj.(0,1)=(-1)<1*1=- г (-1) -W (?),

J-0

где К^(?) - количество {j-1)-ыерных граней Я; Ко(я):=1. Предложение 16.1) можно рассматривать здесь как теоретико-множественный аналог теоремы Эйлера: д£(0,1)=(-1)а*1= ^(¿({vert Н\Н - гипергрань ?})), где vert обозначает множество вершин. • " ■■

Предложение 17. Пусть д - АСК, не изоморфный булевой

решетке; л определен в предложении 9.1. Пусть Б и-Гмножества

атомов и коатомоз решетки д соответственно. Тогда

и-(0, 1) » ж(д(1з(у)пВ | У«ЕШ = х(д((5(у)"£ I Уе£})) . д

Глава III посвящена исследованию комбинаторных свойств

несовместной системы однородных строгих линейных неравенств ранга л над пространством 1?°:

5:={<агх> > 0 | ,йа^ =1}, х^к", где А={а,,...) - конечная упорядоченная последовательность

1 В

векторов из кп, пгл+3. Допускается наличие в А попарно ■ совпадающих и' противонаправленных векторов. <а^х> - скалярное произведение векторов aJ и х, 1-й обозначает эвклидозу корму.

Пусть семейство подмножеств J:«{Je|3«(q]} [ соответственно :={It|i«[p]} ] множества ¡а] является семейством мультииндексов сех МСП [соответственно всех МНП ] системы S; и тк -оличества совместных и несовместных подсистем мощности к i-ответственно. Зсейу полагаем в мультиивдексои совместной одсистемы четной мощности.

3 51 главы III вводится б рассмотрение класс систем S, шбикаторные свойства которых является объектом исследования I главе III.

Определение А. .Систему S будем называть Гейл-полиэдральной .•истемой, если кавдая открытая полусфера единичной сферы S""1 :одернит не менее двух'зектороз из множества задасдих векторов А.

Определение 5. Гейл-полкэдральнуо систему S будем называть "ейл-сиу.плицигльнсЛ, если каждая ее МНП содержит (п+1) iepaseKCTBO. ГеЙл-полкэдральнуг систему S.будем называть Гейл-тростой, если каждое ее неравенство содержится з (п+р-в+1) £21. „

3 §2 главы III анализируется комбинаторное строение Гейл-полкэдральных систем, комбинаторные сзойстза которых в определенном сжсле эквивалентны сзойстзам выпуклых кяогограякикоз.

Материал глаз I и II связывает утверждение, Еытекакпзе из известных соотнссеьгий l=n(JA) к I), справедливых для

произвольной несовместной системы 5: -

Преддоненле 18. Для произвольной несовместной системы S a(J) = д"Ч1) и дС1А) - .

Материал глав II и III связывает утверяденке, вытекатее из анализа универсальных соотношений (базирующихся на свойствах преобразования Д.Гекла) из 3> ¿ря наложении на них дополнительных ограничений:

УЗ

Предложение 19. Если система Б - Гейл-полиэдральная, то семейство I [ соответственно J 1 подмножеств множества [ш] является семейством мультииндексов ее МНП ( соответственно МСП ] тогда и только тогда, когда Iх [ соответственно ^ ] - семейство мультииндексов наборов вершин гиперграней [ соответственно наборов вершин, составляющих диагонали ] некоторого (т-п-1)-мерного ограниченного выпуклого многограннш-? с « вершинами, причем т не является пирамидой.

Предложение 20. Для произвольной несовместной системы Э,

20.1} Пусть Оак*(т], тогда

■ й-

Е (-!)'■

Одновременно, ж ж

(¡и ч ,ш\ ,•

Гсщ.

z

■

1 Л «1,1 1вГ

Я - I и II ш - к

где 1и«1.

21.2) Максимальная мощность среди максимальных совместных подсистем равна ' -

я

а - .Е 1-0

••1

0

Минимальная мощность среди минимальных несовместных подсистем равна

3) Гайнанов Д.Н. О комбинаторных свойствах несовместных систем линейных неравенств и выпуклых многогранников // Математические заметки. - 1985. - т.38, пЗ. - с.463-474.

И - X "

i-o

Предложение 21. Для Гейл-пслиэдральнсй системы S,

21.1) ¿(¿(J))=MH64-M4eT={-i)n*1, где Mjje4 и Мчет -количество совместных подсистем системы S нечетной и четной мощности соответственно.

21.2) ¿(д(1А))-<-1)"-" или NHe4-N4eT=(-l)n, где NHe4 и N4eT - количество несовместных подсистем системы S нечетной и четной мощности соответственно.

Предложение 22. Для Гейл-полпэдральной системы S,

22.1) (-1)-1 = Z (-l)'-#{7cU]jiri=j, п •

"Ij

22.2) (-1)-°= Е (-D^^rcipJUTHj, U I =ia}} .

J€tP» * "Il

Предложение 22. Пусть смстеыа 5 - Гейл-поллздргльная;

Р - ч.у. множество мультиивдексоз ее совместна подсистем, упорядоченных по вклхзчекко, и С - семейство всех насыщенных цепей з ч.у. множестве Рч{в}. Пусть А - семейство всех неупорядоченных пар несравнимых по Еклвченкзв непустых мультииндексов совместных подсистем системы S. Тогда

22.1) (-1)п*1= Е (-l)J-if{îfil#C]|lî,l=j. П <ч=и}.

IPI -

22.2)- (-1)" = (-1) -хШАЧ).

22.3)

(-!)•>" = (-1-)'Г1. £ {-l)J-*{rc{#A]|iri=j, U а -РЧ{«1}.

. ter,

jel«Al

Предложение 23. Пусть система S - Гейл-полкэдральная, Р - ч.у. множество мудьткиндексов ее несовместных подсистеи.

упорядоченных по включении, й С - семейство всех насыщенных цепей в ч.у. множестве Р\[ш]. Пусть А - семейство всех неупорядоченных пар несравнимых по включению мультииндекеов несовместных подсистем системы Б. Тогда

23.1) (-1)—п = I (-1)^#{Гс[#С]1!Т|^, П

23.2) (-1)-" = (-1)""-ж(д(Ад)).

23.3)

Ч«А -

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

Предложение 24. ("Гейл-двойственностн"). '

Пусть 5 - система из т неравенств ранга л, обладающая р минимальными несовместными подсистемами. Пусть чКБ) и КБ) -семейства мультииндекеов ее ЫСП и ЙНП соответственно.

Система Б - Гейл-полиэдралькая тогда и только тогда, когда существует такая Тейл-полиэдральная" система-8° из р неравенств ранга п+у-и, обладающая а минимальными несовместными подсистемами, что ( »КБ0) и КБ0) обозначают семейства мультииндекеов ее МСП_и ЫНП соответственно):

24.1) Для каждого мультииндекса (Б) найдется такой индекс [р] неравенства из системы Б0, что #{1е1(5°)^е1}=|14 причем это соответствие - взаимно однозначное.

24.2) Для каждого мультииндекса 1^1(2°) найдется такой индекс ис[д] неравенства из системы Б, что #{1е1(Б)]1«1}=!111, причем это соответствие - взаимно однозначное.

24.3) Для каждого мультииндекса О с^Э) найдется семейств

&

/льтииадексов МНИ л cl(S°), =®-tJ t, такое, что U I=ipj, • * *

ричем это соответствие - ззаимно однозначное.

24.4) Для каждого мультииндекса Jm«J(S°) найдется семейство

ультииндексов МКП л clCS), =p-|J I, такое, что U * • *

ричем это соответствие - взаимно однозначное.

Определение 6. Будем называть Гейл-полиэдральные системы и S° с указанными в предложении 24 свойствами Гейл-дзойстзенными истемами.

В $3 главы III исследуются комбинаторные свойства ейл-симплициальных и Гейл-простых систем, занимающих среди всех 'ейл-полиэдральных систем положение, сходное с полояением имплициальных и простых многогранников среди зсех многогранников.

Предложение 25. Если-система S - Гейл-симплициальная, то .•емейство I [ соответственно J ! подмножеств множества [и] свляется семейством мультииндексов ее МНП i соответственно {СП ] тогда и только тогда,, когда [ соответственно JL ] ■ семейство мультииндексоз наборов вершин гиперграней ' соответственно наборов вершин, составляющих диагонали j «которого (ш-п-1)-мерного ограниченного выпуклого :имплициального многогранника я с и вершинами, причем т не галяется симплексом.

Следующее предложение, раскрывающее "геометрию" Гейл-симплициальной системы S, может быть принято в качестве эе определения. ,

Предложение 26. Гейл-полиэдральная система S -Гейл-симплициальная тогда и только тогда, • когда каждая ее подсистема ранга не выше (п-1), совместна.

В частности, любая Гейл-полиэдральная система S ранга 1 -Гейл-симплициальная; любая Гейл-полиэдральная система S ранга 2,, среди задающих векторов которой отсутствуют противонаправленные.

i7

- Гейл-симплициальная.

Для Гейл-симплициальной системы, помимо предложения 21, справедливы дополнительные линейные соотношения:

Предложение 27. ("Соотношения Дена-Соммервиля"). Пусть система Б - Гейл-симплициальная; г - формальная переменная. Тогда

27.1)

"к = (к) при 0 * к * п' V . = V = О,

ж — 1 ж

Будем называть эти соотношения соотношениями Дена-Соммервиля для совместных подсистем Гейл-симплициальной системы Б.

27.2) Замена в 27,1) к\-1>к на тк приводит к соотношениям Дена-Соммервиля для несовместных подсистем.

27.3) Для л+1*:*я,

• 27.4) Для ¿«{1.....1Ы-п)/2}},

¿.'•«-'•Рй')". - ■

Здесь - наибольшее целое, меньшее или равное г.-

27.5) Заменой в"27.3) и 27.4) гк на ^ -»> можно получить

аналогичные соотношения для

Например, согласно 27.1) для Гейл-симплициальной системы £

1. Если ш=п+3, то "„„^[г]-®-

2. Если т=п+4, то

И

3. Если п=я+5, то

И тан далее.

Для Гейл-симплициальнкх систем можно указать точные нижние и верхние границы для количеств подсистем.

Предложение 28. (Аналог теоремы П.МакМюллена о верхней границе для симплициальных многогранников). Положим ■ в (п-л-1,п) :=

£. ш-гп* & ГП-ГП'

л-симплициальной системы Э и для п+1зк* ~^ а ,(ш-п-Х,о) и

(3 - к.^*-*-^ •

Предложение 29. (Аналог теоремы Д.Барнетта о нижней

"к '

границе для симплициальных многогранников). Положим (л?-п-2)и - (о-я)(и-л-З) „ при «7=0,

(^Т1).^ - при .Ый-л-3)

Тогда для Гейл-симплициальной системы $ и для л+1а£ав-2,

Т ь В (ш-Л-1,Д!) И к "к-п-!

"к * (к) ■

Помимо соотношений Дена-Соммервиля, верхних и * нижних -границ, можно дать полную характеризацию натуральночисленных векторов, компонентами которых являются количества г^ и vk для некоторой Гейл-симплициальной системы. Она состоит в следующем:

Как известно, для любых двух натуральных чисел к и t

существует единственный способ записать Ь в виде суммы

'" ('{М'кК- *("})

так, что Ьк>Ькш1>.. .>Ъ*рО. Пусть

Пусть для несовместной системы Б и для (Ыаш-л-1

Через эти величины однозначно выражаются количества т : Далее, определим вектор

.(в):-^«).^«).....8L(..n.1).aJ(S))c2^•"—

следующим образом: ео(8):=Ь0(5) и «^.-^(БН^^Б) для .

Вновь количества гк однозначно восстанавливаются:

т~} ¿-о х ^в-Л-Г» 1

Предложение 30.-(Аналог результатов П.МакМаллена, Л.Биллерг К.Ли и Р.Стенли). Пусть д, л « и, Ле1, ЕгС+З и

е- ^о'8».....>✓*»'*«

30.1) а - вектор в(5) для некоторой Гейл-симплидиальной системы 3 тогда-и только тогда, когда для в выполняется

8Й=1, И дая ВСех£*1-

30.2) Заменой в рассуждениях, предшествующих предложение 31

. НЙ к

количеств совместных подсистем Гейл-скмплицигльной системы Б.

Отметим, что все приведенные выае утвеждения о Гейл-синплициальных системах имеет сходные аналоги для Гейл-простых систем в силу следующего обстоятельства:

т. на , можно получить аналогичную полную характера--лт

Предложение 31. Система Э - Гейл-симплициальная тогда и

:олько тогда, когда Гейл-двойственная к ней система Б0 -'ейл-простая. •

В приложении к диссертации кратко рассмотрена связь между теорией несовместных систем линейных неравенств и теорией <онфигураций гиперплоскостей.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ'

1. Показано, что основные комбинаторные свойства произвольного абстрактного симплициального комплекса (количество граней, размерность, эйлерова характеристика и строение кольца Стенли-Рейснера) могут быть исследованы посредством анализа иного комплекса, порождаемого системами представителей для гиперграней исходного комплекса.

2. Приведены следствия теоремы Ф.Холла, эквивалентные указанию новых способов вычисления функции Мебиуса произвольного частично упорядоченного множества.

' 3. Проведен анализ строения уровней решеток важного класса, включающего в себя геометрические решетки и решетки граней-многогранников.

4. Приведены следствия теоремы Дж.-К.Рота о сечении, эквивалентные указанию новых способов вычисления функции Мебиуса решеток.

5. Введен в рассмотрение класс несовместных систем линейных неравенств, комбинаторные свойства которых в определенном смысле аналогичны комбинаторным свойствам решеток'граней многогранников, так называемых Гейл-полиэдральных систем. Проведено всестороннее исследование комбинаторного строения семейств совместных и несовместных подсистем Гейл-полиэдральных систем. Показано,

что с каждым из этих семейств существенно связана инварианты

(-1}р, где г - либо п, либо <п+1); п - ранг системы.

Поназано, что каждой Гейл-полиэдральной системе S ранга п из га неравенств, обладающей р минимальными несовместными подсистемами, отвечает такая Гейл-полиэдральная система S° ранг (п+р-ш) из р неравенств, обладающая и минимальными несовместным подсистемами, что комбинаторные свойства S и S0 дуальны.

6. Среди Гейл-полиэдральных систем-выделен подкласс систем комбинаторные свойства которых совпадают со свойствами решеток граней симплициальных многогранников. Для количеств совместных и несовместных подсистем таких систем приведены соотношения Дена-Соммервиля, указаны точные верхние и нижние границы; дана полная характеризация количеств подсистем.

7. Проанализирована связь между теорией несовместных систем линейных неравенств и теорией конфигураций гиперплоскостей.

ПУБЛИКАЦИИ.

1. Gainanov D.N., Mat.veev А.О. Lattice diagonals and geometric pattern recognition problems // Pattern recognition and Image analysis 1991, v.l, пЗ, p. 277-282.

2. Gainanov D.N.', Matveev A.O. Finite lattice diagonals and their relation to pattern recognition // Pattern

'recognition and inage analysis - 1993. - v.3, ri2 - p.84-91.

3. ГаЙнанов Д.Н., Матвеев A.O. Комбинаторные свойства Гейл-полиэдральных систем линейных неравенств / Деп. ВИНИТИ 6.1.93, П10-В93. 41 с.

4. Матвеев А.О. Функция Мебиуса и антицепи решеток / Деп. ВИНИТИ 24.8.93, П2323-В93. 13 с.

5. Матвеев А.О. Аддитивная связь решений перечислительных задач о покрытиях и системах представителей / Деп. ВИНИТИ 10.1.94, П45-В94. 24 с.