VI Международная студенческая научная конференция Студенческий научный форум - 2014

Частично упорядоченные множества. Цепи и антицепы. Теоремы Шпернера и Дилуорса

Соответствием между множествами X и Y называется любое наперед заданное подмножество , где -прямое произведение множеств , т.е. такое, что множество . Если , то говорят, что элемент у соответствует элементу х или что элементы х и у находятся в соответствии Z, и пишут xZy (нет соответствие) или Z(x,y) элемент у называют образом х, а х — прообразом у при соответствии Z.

Рассмотрим эти три способа задания соответствия на конкретных примерах. Пусть соответствие пусть соответствие определяется по правилу: четно, т.е. тогда и только тогда, когда четно. Z = {х + у — четное число}, и задания этого соответствия на рис. 1.3.

Графическое (а) -точки координатами ; табличное (б)-если четно, то единица, если нет, то 0: и геометрическое (б)-если четно, то между ними есть ребро, если нет, то нет ребра. Из рис. 1.3. видно, что при геометрическом задании Z принадлежность (ж, у) обозначается точкой на плоскости; при графическом — отрезком; при табличном — единицей, такая таблица называется матрицей инцидентности соответствия.

3а)

3б)

3в)

Рис.3–Соответствие «-четно» и способы задания

Отношение есть соответствие между одинаковыми множествами; двухместное отношение называется бинарным.

Различают следующие свойства бинарного отношения на множестве X:

• рефлексивность, если для любого выполняется ;

• антирефлексивность, если для любого выполняется ;

• симметричность, если для любых из следует ;

• антисимметричность, если для любых из и следует, что х = у;

• транзитивность, если для любых из и следует, что : «ученик моего ученика –не мой ученик» — пример нетранзитивного отношения;

• дихотомичностъ, если для любых , либо xRy, либо yRx.

Отношения часто возникают на практике. Например, знакомство между людьми рефлексивно и симметрично, но не всегда транзитивно. Всякая иерархичность тоже есть бинарное отношение, так что бинарными отношениями удобно характеризовать различные упорядоченные множества.

Упорядоченное множество есть пара , где X — множество, а — бинарное отношение . Если для выполняется , т.е. , то удобно интерпретировать это как то, что х «больше», чем у, в смысле отношения ; если не выполняется ни , ни yRx, то х и у называются несравнимыми элементами в . Рассмотрим основные типы упорядоченных множеств:

• совершенно неупорядоченное множество — это , где ;

• линейно упорядоченное множество — это , где обладает свойствами рефлексивности, антисимметричности, транзитивности и дихотомичности. Примером такого множества могут служить натуральные числа, упорядоченные по величине, т. е. по отношению ;

• частично упорядоченным множеством называется упорядоченное множество , в котором рефлексивно, антисимметрично и транзитивно.

Частично упорядоченное множество (ЧУМ) M — это множество, для любых двух элементов a, b которого известно, находятся они в некотором отношении ≺ или нет. При этом должны быть выполнены следующие аксиомы:

• если a≺b и b≺c,то a≺c;

• если a≺b, то ;

• неравенства a ≺b и b≺ a не могут быть выполнены одновременно.

Третья аксиома, очевидно, следует из первых двух. Множество, любые два элемента которого сравнимы, то есть множество, для любых элементов a и b которого выполнено одно из соотношений a≺b,a=b и b≺a, называют линейно упорядоченным или, коротко, цепью. Элемент a называют максимальным (соответственно, минимальным), если неравенство a≺b (соответственно, b≺a) не выполнено ни для какого другого элемента b.

Цепьюв упорядоченном множестве называется последовательность его элементов такая, что

Длинаконечной цепи есть число ее членов минус единица.

Антицепь — это подмножество упорядоченного множества, состоящее исключительно из попарно несравнимых элементов.

Примеры ЧУМ:

1. Множество всех вещественных чисел (оно не только частично, но и даже линейно упорядочено, то есть любые два числа можно сравнить);

2. Множество всех отрезков прямой, где один отрезок считается больше другого, если все точки первого лежат правее точек второго;

3. Множество всех натуральных чисел, упорядоченное по делимости (то есть одно число больше или равно другого, если первое число делится на второе без остатка);

4. Множество всех подмножеств данного множества, упорядоченное по включению (то есть одно множество больше или равно другого, если все элементы второго множества являются и элементами первого множества).

Справедливы следующие утверждения (.

Теорема: В частично упорядоченном множестве из mn+1 элементов есть либо цепь из идущих в порядке возрастания m+1 элементов, либо n+1 попарно несравнимых элементов (так называемая антицепь).

Лемма.Пусть dнаибольшее количество элементов цепи данного конечного частично упорядоченного множества M. Тогда Mможно разбить на d антицепей.

Теорема Шпернера. Наибольшее количество подмножеств -элементного множества, взаимно не содержащих друг друга, равно .

Экстремальной конструкцией, реализующей это значение, может служить, например, множество всех -элементных подмножеств -элементного множества, поскольку все подмножества одинаковой мощности попарно невложимы друг в друга.

Остановимся теперь на некоторых подходах к решению этих и подобных экстремальных задач. Наиболее употребительным остается способ двустороннего оценивания, который удобно продемонстрировать на простом конкретном примере.

ТЕОРЕМА 1. Пусть задано множество из различных натуральных чисел, в котором среди любых трех элементов можно выбрать два, одно из которых делится на другое. Тогда эти числа можно покрасить в два цвета так, чтобы для любых двух чисел одного цвета одно делилось на другое.

Доказательство. Расположим числа по возрастанию. Возьмём наименьшее и окрасим его в первый цвет. Дальше будем рассматривать числа по порядку. До тех пор, пока каждое очередное число будет делиться на предыдущее рассмотренное число, будем использовать только первый цвет. Если так будет продолжаться до конца, то второй цвет вообще не понадобится. Если же очередное число не окажется кратным предыдущего, то придётся использовать второй цвет. (Заметьте: после этого максимальные числа двух цветов не делятся друг на друга.)

Рассмотрим следующее число. Оно делится хотя бы на одно из двух максимальных окрашенных чисел (разных цветов). Если только на одно, то, покрасив его в тот же цвет, получим предыдущую ситуацию. Если же оно делится на оба максимальных, то временно окрасим его в третий цвет. Если следующее число делится на максимальное число третьего цвета, то и его красим в третий цвет, и так пока не встретим число, не делящееся на максимальное числотретьего цвета. Это число должно делиться хотя бы на одно из максимальных чисел первых двух цветов. Покрасим его в соответствующий цвет, а все числа третьего цвета — в другой цвет; опять получим ситуацию, когда максимальные числа (разных цветов) не делятся друг на друга. Повторяя эти действия, мы получим искомую раскраску.

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

Доказательство проводится аналогично доказательству теоремы 1.

Если поменять слова «цепь» и «антицепь» местами, то мы получим гораздо более трудно доказываемое свойство частично упорядоченных множеств.

Теорема Дилуорса. Обозначим через n наибольшее количество элементов антицепи данного конечного частично упорядоченного множества M. Тогда Mможно разбить на цепей.

Другими словами, если N — наименьшее количество цепей, на которые можно разбить данное конечное частично упорядоченное множество M, а n—наибольшее количество его попарно несравнимых элементов (то есть наибольшая мощность антицепи), то n=N.

Например: 23691218 24 36 48

Цепь 1: 2 ≺ 6 ≺ 12 ≺ 24 ≺ 48

Цепь 1:: 3 ≺ 9 ≺ 18≺ 36

Антицепи:: (23)(29) (912)

список использованной литературы

1. Баранов В. И., Стечкин Б. С. Экстремальные комбинаторные задачи и их приложения. — М.: ФИЗМАТЛИТ, 2004. - 240с.

2. Stasys Jukna. Extremal Combinatorics. Springer- Verlag Berlin Heidelberg 2001, 2011.

3. О.И. Мельников. Теория графов в занимательных задачах.- М.: Книжный дом «ЛИБРИКОМ», 2013.-240с.

Код для цитирования: Скопировать