Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4

Нажмите для полного просмотра!

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №2

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №3

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №4

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №5

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №6

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №7

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №8

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №9

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №10

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №11

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №12

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №13

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №14

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №15

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №16

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №17

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №18

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №19

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №20

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №21

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №22

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №23

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №24

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №25

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №26

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №27

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №28

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №29

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №30

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №31

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №32

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №33

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №34

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №35

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №36

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №37

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №38

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №39

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №40

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №41

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №42

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №43

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №44

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №45

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №46

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №47

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №48

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №49

Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4, слайд №50

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Улучшение оценки числа ребер в задаче Эрдеша-Хайнала однородности 4. Доклад-сообщение содержит 50 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Об улучшении оценки числа ребер в задаче Эрдеша-Хайнала однородности 4 весна 2016

Слайд 2

Описание слайда:

Свойство B

Слайд 3

Описание слайда:

Основные понятия:

Слайд 4

Описание слайда:

История вопроса:

Слайд 5

Описание слайда:

Известно, что m(2) = 3, a m(3) = 7

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Постановка задачи:

Слайд 8

Описание слайда:

Что уже известно про m(4)

Слайд 9

Описание слайда:

"Вопрос о том, насколько можно доверять такому результату, остается открытым. Подводя итоги, мы с твердой уверенностью можем лишь утверждать, что 17 m(4) 23“ (А. М. Райгородский, Д. А. Шабанов, Задача Эрдеша– Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы, 2011, 121). Оценка в 17 ребер была получена в 1993 г. М. Гольдбергом и Х. Расселом

Слайд 10

Описание слайда:

Теорема 1. Пусть H = (V, E) произвольный гиперграф однородности 4. Тогда при E < 19. χ(H) = 2

Слайд 11

Описание слайда:

Нужно только показать, что m13(4) > 18 и m14(4) > 18

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

Определение 1. Введем ri как число ребер инцидентных i вершине. Упорядочим вершины: r1 r2 . . . rv.

Слайд 14

Описание слайда:

Доказательство:

Слайд 15

Описание слайда:

Теорема 4. Пусть H(V, E) — произвольный гиперграф : , |E| = 18, k = 4, |V | = 13 и r1 = 5. Тогда χ(H) = 2

Слайд 16

Описание слайда:

Доказательство. Напомним, что 5 = r1 r2 · · · r13, поэтому . . Пока просто запомним такой результат.

Слайд 17

Описание слайда:

Cлучай 1. rc =7

Слайд 18

$. |V|=13, r_{1}=4 Под сбалансированной раскраской будем понимать отображение φ : {V } → {Black, White} :|#VBlack − #VWhite|1$

Описание слайда:

. |V|=13, r_{1}=4 Под сбалансированной раскраской будем понимать отображение φ : {V } → {Black, White} :|#VBlack − #VWhite|1

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Доказательство. Докажем, что block4,13 111. Заметим, что по построению ∀ i, j vi ∩ vj ∅, поэтому ∀ i ∈ [2, 13] |v1 ∩ vi| = 1.

Слайд 21

Описание слайда:

Число сбалансированных раскрасок двенадцати вершин равно 1/2 · Число раскрасок при наличии хотя бы одного одноцветного ребра-

Слайд 22

$Определение 4. Введем следующие обозначения: E1 = {e ∈ E : |e ∩ v1| = 0, ∃ f ∈ E : |f ∩ v1| = 0, |e ∩ f| = 0 ∨ 3}-тип 1. На Рис. . такими являются 1,2 и 3. E2 = E \ {E1 ∪ F = {f ∈ E : |f ∩ v1| = 1}}-2 тип, E2∗ = {e ∈ E2 : ∃ f ∈ F ∧ |e ∩ f| = 3}.-тип 2*.$

Описание слайда:

Определение 4. Введем следующие обозначения: E1 = {e ∈ E : |e ∩ v1| = 0, ∃ f ∈ E : |f ∩ v1| = 0, |e ∩ f| = 0 ∨ 3}-тип 1. На Рис. . такими являются 1,2 и 3. E2 = E \ {E1 ∪ F = {f ∈ E : |f ∩ v1| = 1}}-2 тип, E2∗ = {e ∈ E2 : ∃ f ∈ F ∧ |e ∩ f| = 3}.-тип 2*.

Слайд 23

Описание слайда:

Теорема 3. Пусть H = (V, E) произвольный гиперграф однородности 4 с |E| = 18, |V | = 13 и r1 = 4. Тогда χ(H) = 2 Доказательство. Вначале докажем две технические леммы

Слайд 24

Описание слайда:

Лемма 2. Найдется 19 блокирующих раскрасок для v1 при которых одноцветно зафиксированное ребро типа 2*.

Слайд 25

Описание слайда:

Лемма 3. Либо найдется ребро типа 2, не являющееся типом 2*, либо(неисключающее) ∆4,13 > 0

Слайд 26

$Алгоритм 1: построение правильной раскраски, в случае, когда найдется ребро e ∈ E2 \ E2∗$

Описание слайда:

Алгоритм 1: построение правильной раскраски, в случае, когда найдется ребро e ∈ E2 \ E2∗

Слайд 27

Описание слайда:

Слайд 28

Описание слайда:

v∗alone = 2 Случай 1 ( e пересекается со всеми фиксированными) .

Слайд 29

Описание слайда:

Слайд 30

Описание слайда:

v∗alone = 3

Слайд 31

Описание слайда:

Возвращаемся к случаю r=5

Слайд 32

Описание слайда:

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Слайд 35

Описание слайда:

Слайд 36

Описание слайда:

Слайд 37

Описание слайда:

Слайд 38

Описание слайда:

Слайд 39

Описание слайда:

Получение противоречия

Слайд 40

Описание слайда:

Слайд 41

Описание слайда:

Cлучай 3. rc =6

Слайд 42

Описание слайда:

Таблица всевозможных пересечений D

Слайд 43

Описание слайда:

n = 1: нашли вершину D, являющуюся аналогом C из случая 1. n = 2, rD = 6: остается 3 одноцветных ребра и 7 ребер, где по две Black вершины, а такие случаи уже умеем раскрашивать. n = 3: Раскрасить можно: 4 варианта покраски одной вершины в последнем ребре против двух потенциально возможных ребер, где по три Black вершины. n = 4 : Преположим наличие "3"и докажем возможность правильной раскраски при таком случае: