Вероятностные методы решения экстремальных задач о раскраске равномерных гиперграфов

Открытие того, что детерминированные утверждения могут быть доказаны с помощью вероятностных соображений, позволило уже в первой половине XX в. установить ряд замечательных фактов из анализа, теории чисел, комбинаторики и теории информации. Вскоре стало ясно, что метод, который сейчас называется вероятностным, является весьма мощным инструментом получения результатов в дискретной математике. Ранние результаты такого сорта основывались на сочетании комбинаторных соображений с элементарной вероятностной техникой, однако развитие метода в последние годы потребовало применения все более изощренных инструментов теории вероятностей. Еще одной причиной столь интенсивного развития вероятностного метода стало осознание важности роли, которую играет этот метод-в теории компьютерных вычислений, являющейся источником многих задач комбинаторики. В связи с этим, интересен также алгоритмический подход к изучению вероятностного метода в комбинаторике.

Одним из главных инициаторов применения вероятностного метода в дискретной математике выступил в 50-е годы XX века П. Эрдеш, который впоследствии внес в развитие метода очень значительный вклад. Его достижения, гипотезы и проблемы в существенной степени стимулировали исследования в этой области. Отныне результаты, получаемые вероятностным методом, можно разделить условно на две группы. К первой группе относятся те результаты, которые связаны с изучением определенных классов комбинаторных объектов, таких, как случайные графы или случайные матрицы (см. [13], [30], [31], [32], [33] и др.). Эти результаты являются по существу теоретико-вероятностными, хотя большинство из них мотивировано задачами комбинаторики. Вторая группа состоит из тех фактов, которые формулируются в терминах существования комбинаторных структур, обладающих рядом предписанных свойств. Основная идея доказательства подобных фактов может быть описана следующим образом: мы строим вероятностное пространство, в котором роль элементарных событий играют некоторые комбинаторные структуры, и затем показываем, что такие структуры обладают необходимыми свойствами с положительной вероятностью. Как правило, главная тонкость здесь в выборе подходящей вероятностной меры. Доказательства существования такого типа приводят к решениям различных эктре-мальных задач дискретной математики.

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

В задачах теории раскрасок гиперграфов вероятностный метод был впервые применен П. Эрдешем (см. [1], [2]) для отыскания величины m (n, 2), равной минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных1 двухцветных раскрасок. Дальнейшее развитие метод Эрдеша, в рамках которого вершинам гиперграфа цвета присваивались случайным образом, получил в работах Й. Бека (см. [3]) и Дж. Спенсера (см. [4]). Указанными авторами был предложен подход, основанный на построении рандомизированного алгоритма перекраски вершин гиперграфа, и этот подход идейно и технически гораздо сложнее метода Эрдеша. Позднее, Дж. Радхакришнан и А. Сринивазан (см. [5]) усовершенствовали алгоритм Бека — Спенсера и получили наилучший, на сегодняшний день, результат в задаче о величине т (п, 2).

Диссертация состоит из шести глав. В первой главе обсуждается история наиболее известных задач о нахождении минимального числа ребер гиперграфов, принадлежащих различным классам, даются необходимые определения, а также приводятся формулировки большинства полученных соискателем результатов. Во второй и третьей главах доказываются, соответственно, нижняя и верхняя оценки величины m&(n), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не допускающих такую двухцветную раскраску, в которой все ребра гиперграфа содержат не менее к вершин каждого цвета. Теорема о нижней оценке является центральным результатом работы. Доказательство этой теоремы основано на построении нового нетривиального рандомизированного алгоритма раскраски вершин гиперграфа. Четвертая глава посвящена доказательству результатов в.

Раскраска (вершин) гиперграфа называется правильной, если в ней все ребра неодноцветны. задачах с дополнительными ограничениями на пересечения ребер гиперграфов. Эти задачи близки к проблемам, связанным с теоремой Эрдеша — КоРадо (подробнее см. [18], [19], [20], [21]). В пятой главе изложены доказательства теорем об оценках экстремальных характеристик гиперграфов в случае раскрасок в три цвета. Шестая глава связана с различными задачами о под-гиперграфах.

Автор глубоко признателен научному руководителю А. М. Райгородскому за постановку задач, постоянное внимание и интерес к работе.

Общая характеристика работы.

Актуальность темы

диссертации.

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

Подобные задачи впервые были рассмотрены в работах П. Эрдеша. Так, в 1960;х гг. Эрдешем была предложена (см. [1], [2]) следующая проблема: найти величину т (п, 2), равную минимальному числу ребер гиперграфа, принадлежащего классу п-равномерных гиперграфов, которые не допускают правильных двухцветных раскрасок, или, как ewte говорят, не обладают свойством В. Дальнейшее развитие данная проблема получила в работах таких замечательных специалистов в области вероятностной комбинаторики, как Й. Бек, Дж. Спенсер, Дж. Радхакришанан и А. Сринивазан (см. [3], [4], [5]). Ими были разработаны так называемые рандомизированные алгоритмы раскрасок вершин гиперграфа, с помощью которых и были получены наилучшие известные оценки величины га (п, 2).

Задача о величине m (n, 2) имеет важные обобщения в случае г-цветных раскрасок. Первое обобщение связано с понятием хроматического числа гиперграфа. Через m (n, г) обозначим минимальное число ребер гиперграфа в классе п-равномерных гиперграфов, не допускающих правильных г-цветных раскрасок (т.е. имеющих хроматическое число, большее г). Изучению этой величины при различных соотношениях между параметрами п и г посвящены работы таких известных математиков, как Н. Алон и А. Косточка (см.

7], И).

Второе обобщение связано с рассмотрением радужных раскрасок. Различные экстремальные свойства равномерных гиперграфов, обладающих радужными2 r-раскрасками, изучались П. Эрдешем, JI. Ловасом, А. Косточкой, Д.

2Раскраска вершин гиперграфа в г цветов называется радужной r-раскраской, если в этой раскраске любое ребро содержит вершины всех г цветов.

Вудоллом и др. (см. [14], [34]). Обозначим через р (п, г) минимальное число ребер гиперграфа в классе n-равномерных гиперграфов, не допускающих радужных r-раскрасок. Ясно, что р (п, 2) = т (п, 2). В работах [14], [24] были получены общие оценки величины р (п, г). С помощью вероятностного метода в диссертации доказываются улучшенные оценки величины р (п, 3).

При изучении раскрасок равномерных гиперграфов особый интерес представляют задачи с дополнительными условиями на пересечения ребер гиперграфа. Например, хорошо известна задача (см. [14], [16], [17]) о величине т*(п, г), равной минимальному числу ребер гиперграфа в классе п-равномерных простых гиперграфов (т.е. таких гиперграфов, у которых любые два ребра имеют не более одной общей вершины), не допускающих правильных r-цветных раскрасок. В диссертации рассматриваются также задачи о раскрасках гиперграфов в случае, когда совокупности их ребер удовлетворяют некоторым условиям, которые тесно связаны с проблемами пересечений множеств и, в частности, с классической теоремой Эрдеша — Ко — Радо (см. [18], [19], [20], [21]).

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

Цель и задачи исследования

.

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

Научная новизна полученных результатов.

Все результаты диссертации являются новыми.

Практическая значимость полученных результатов.

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

Основные положения диссертации, выносимые на защиту.

1. Для величины т^(п), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Bk (т.е. не допускающих двухцветных раскрасок, в которых любое ребро гиперграфа содержит не менее к вершин каждого цвета), при параметре к = к (п), удовлетворяющем условию к <С Inn, выполняется оценка где фукция ф (п) 1 при п —у оо (теорема 3).

3. Для величины га&^п), равной минимальному количеству ребер гиперграфа в классе n-равномерных гиперграфов, обладающих свойством Ад (ребра таких гиперграфов не имеют общих вершин, либо имеют не менее h общих вершин), но не обладающих свойством Впри некоторых ограничениях, наложенных на параметры к и Я, выполняются оценки теорема 1).

2. Для величины m^(n) при условии к = о (j^) имеет место оценка.

4 к-1 ' ЕСтеоремы 5 и 6). 4. Для величины р (п, 3) имеют место оценки п теоремы 8 и 9).

5. Для величины т^)?(п), равной минимальному числу ребер гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством Bk)? (гиперграф обладает свойством Bk,?, если из него можно так удалить е долю ребер, чтобы оставшиеся ребра образовывали гиперграф, обладающий свойством Bfc), при условиях к — 1 |1п (сА)| < Inn — 3 In Inn выполнена оценка.

An e~k 2n-2fc «| ln (cA) 12к — 1.

2-J 71 i=0 где с — некоторая константа из интервала (0,1), а, А = ^ (теорема 12). i—0.

6. Для величины /?г (п)> равной минимальному числу вершин гиперграфа в классе n-равномерных гиперграфов, не обладающих свойством F^i (гиперграф обладает свойством .F^/, если из него можно так удалить I ребер, чтобы оставшиеся ребра образовывали гиперграф, обладающий свойством Bk), найдено точное значение (теорема 14).

Личный вклад соискателя.

Все результаты диссертации получены соискателем самостоятельно.

Апробация результатов.

Результаты диссертации докладывались на международной конференции «Дискретный анализ и исследование операций» (г. Новосибирск, 2004 г.), на международной конференции «Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложениям» в Праге (Чехия, 2006 г.), на международной конференции «Горизонты Комбинаторики» в Ба-латональмади (Венгрия, 2006 г.), на IX международном семинаре «Дискретная математика и ее приложения», посвященном 75-летию со дня рождения академика О. Б. Лупанова (Москва, 2007 г.), на международной конференции «Европейская Комбинаторика» в Севилье (Испания, 2007 г.) — на Ломоносовских чтениях в Московском Государственном Университете в 2004 г., а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на Большом семинаре кафедры теории вероятностей механико-математического факультета.

МГУ под руководством чл.-корр. РАН А. Н. Ширяева, на семинаре д.ф.-м.н. А. М. Зубкова в МИРАН, на семинаре проф. С. В. Конягина в МГУ, на семинаре проф. Н. Г. Мощевитина в МГУ и др.

Опубликованность результатов.

Результаты диссертации опубликованы в работах [35] - [43] списка литературы. Всего по теме диссертации опубликовано 9 работ.

Структура и объем диссертации

.

В диссертации имеется введение, общая характеристика работы, шесть глав, список литературы. Полный объем 97 страниц, из них 4 страницы занимает список литературы (43 наименования).

1. P. Erdos, On a combinatorial problem, 1. Nordisk Mat. Tidskrift, 11(1963), 5−10.

2. P. Erdos, On a combinatorial problem, II, Acta Mathematica of the Academy of Sciences, Hungary, 15(1964), 445−447.

3. J. Beck, On 3-chromatic hypergraphs, Discrete Mathematics, 24(1978), 127 137.

4. J.H. Spencer, Coloring n-sets red and blue, J. Combinatorial Theory, Series A, 30(1981), 112−113.

5. J. Radhakrishnan and A. Srinivasan, Improved bounds and algorithms for hypergraph two-coloring, Random Structures and Algorithms, 16(2000), 4−32.

6. A. V. Kostochka, Color-Critical Graphs and Hypergraphs with Few Edges: A Survey, In More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15(2006), 175−198.

7. N. Alon, Hypergraphs with high chromatic number, Graphs and Combinatorics, 1(1985), 387−389.

8. A. V. Kostochka, Coloring uniform hypergraphs with few colors, Random Structures and Algorithms, 44(2003), 166−177.

9. F. Bernstein, Zur Theorie der trigonometrische Reihen, Leipz. Ber., 60(1908), 325−328.

10. E.W. Miller, On a property of families of sets, C. R. Soc. Sci. Varsovie, 30(1937), 31−38.

11. T. R. Jensen and B. Toft, Graph coloring problems, A Wiley-Interscience (1995).

12. J.H. Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289(1985), 679−706.

Список литературы

.

13. P. Erdos, On a combinatorial problem, I, Nordisk Mat. Tidskrift, 11(1963), 5−10.

14. P. Erdos, On a combinatorial problem, II, Acta Mathematica of the Academy of Sciences, Hungary, 15(1964), 445−447.

15. J. Beck, On 3-chromatic hypergraphs, Discrete Mathematics, 24(1978), 127 137.

16. J.H. Spencer, Coloring n-sets red and blue, J. Combinatorial Theory, Series A, 30(1981), 112−113.

17. J. Radhakrishnan and A. Srinivasan, Improved bounds and algorithms for hypergraph two-coloring, Random Structures and Algorithms, 16(2000), 4−32.

18. A. V. Kostochka, Color-Critical Graphs and Hypergraphs with Few Edges: A Survey, In More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, 15(2006), 175−198.

19. N. Alon, Hypergraphs with high chromatic number, Graphs and Combinatorics, 1(1985), 387−389.

20. A. V. Kostochka, Coloring uniform hypergraphs with few colors, Random Structures and Algorithms, 44(2003), 166−177.

21. F. Bernstein, Zur Theorie der trigonometrische Reihen, Leipz. Ber., 60(1908), 325−328.

22. E.W. Miller, On a property of families of sets, C. R. Soc. Sci. Varsovie, 30(1937), 31−38.

23. T. R. Jensen and B. Toft, Graph coloring problems, A Wiley-Interscience (1995).

24. J.H. Spencer, Six standard deviations suffice, Trans. Amer. Math. Soc. 289(1985), 679−706.

25. Н. Алон и Дж. Спенсер, Вероятностный метод, М.: Бином. Лаборатория знаний, 2007.

26. P. Erdos and L. Lovasz, Problems and results on 3-chromatic hypergraphs and some related questions, In Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, 11(1975), North Holland, Amsterdam, 609−627.

27. T. Tao and V. Vu, Additive Combinatorics, Cambridge University Press, Cambridge, 2006.

28. Z. Szabo, An application of Lovasz Local Lemma a new lower bound for the van der Waerden number, Random Structures and Algorithms, 1(1990), 344−360.

29. D. Grable, K. Phelps and V. Rodl, The minimum independence number for designs, Combinatorica, 15(1995), 175−185.

30. P. Erdos, Ch. Ко, R. Rado, Intersection theorems for systems of finite sets, J. Math. Oxford, Sec. 12(48)(1961), 313−320.

31. R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Th. Ser. A 76(1996), 121−138.

32. R. Ahlswede, L.H. Khachatrian, The complete intersection theorem for systems of finite sets, Europ. J. Combin. 18(1997), 125−136.

33. M. Deza, P. Frankl, Erdos Ко — Rado theorem — 22 years later, SIAM J. Alg. Disc. Methods 4(1983), 419−431.

34. A. M. Райгородский, Линейно-алгебраичекий метод в комбинаторике, М.: МЦНМО, 2007.

35. P. Erdos, A. L. Rubin and Н. Taylor, Choosability in graphs, In. Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Areata, 1979, Congr. Numer., 26(1980), 125−157.

36. A. V. Kostochka, On a theorem by Erdos, Rubin and Taylor, Electronic Journal of Combinatorics, 9(2002).

37. N. Alon, Choice number of graphs: a probabilistic approach, Combinatorics, Probability and Computing, 1(1992), 107−114.

38. В. Феллер, Введение в теорию вероятностей и ее приложения, T. l, М.: Мир, 1984.

39. А. М. Райгородский, Системы общих представителей, Фундам. и при-кл. мат., Т.5, Вып. 3(1999), 851−860.

40. Н. Алон и Дж. Спенсер, Вероятностный метод, М.: Бином. Лаборатория знаний, 2007.

41. P. Erdos and L. Lovasz, Problems and results on 3-chromatic hypergraphs and some related questions, In Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai, 11(1975), North Holland, Amsterdam, 609−627.

42. T. Tao and V. Vu, Additive Combinatorics, Cambridge University Press, Cambridge, 2006.

43. Z. Szabo, An application of Lovasz Local Lemma a new lower bound for the van der Waerden number, Random Structures and Algorithms, 1(1990), 344−360.

44. D. Grable, K. Phelps and V. Rodl, The minimum independence number for designs, Combinatorica, 15(1995), 175−185.

45. P. Erdos, Ch. Ко, R. Rado, Intersection theorems for systems of finite sets, J. Math. Oxford, Sec. 12(48)(1961), 313−320.

46. R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Th. Ser. A 76(1996), 121−138.

47. R. Ahlswede, L.H. Khachatrian, The complete intersection theorem for systems of finite sets, Europ. J. Combin. 18(1997), 125−136.

48. M. Deza, P. Frankl, Erdos Ко — Rado theorem — 22 years later, SIAM J. Alg. Disc. Methods 4(1983), 419−431.

49. A. M. Райгородский, Линейно-алгебраичекий метод в комбинаторике, М.: МЦНМО, 2007.

50. P. Erdos, A. L. Rubin and Н. Taylor, Choosability in graphs, In. Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Areata, 1979, Congr. Numer26(1980), 125−157.

51. A. V. Kostochka, On a theorem by Erdos, Rubin and Taylor, Electronic Journal of Combinatorics, 9(2002).

52. N. Alon, Choice number of graphs: a probabilistic approach, Combinatorics, Probability and Computing, 1(1992), 107−114.

53. В. Феллер, Введение в теорию вероятностей и ее приложения, T. l, М.: Мир, 1984.

54. А. М. Райгородский, Системы общих представителей, Фундам. и при-кл. мат., Т.5, Вып. 3(1999), 851−860.

55. Н. Н. Кузюрин, Асимптотическое исследование задачи о покрытии, Проблемы кибернетики, Вып. 37(1980), 19−56.

56. Г. П. Гаврилов и А. А. Сапоженко, Задачи и упражнения по дискретной математике, М.: Физматлит, 2005.

57. П. Эрдеш и Дж. Спенсер, Вероятностные методы в комбинаторике, М.: Мир, 1976.

58. В. Bollobas, Random Graphs, Cambridge University Press, Cambridge, 2001.

59. T. Luczak, S. Janson and A. Rucinski, Random Graphs, A Wiley-Interscience, New York, 2000.

60. В. Ф. Колчин, Случайные графы, M.: Физматлит, 2000.

61. А. V. Kostochka and D. R. Woodall, Density conditions for panchromatic colourings of hypergraphs, Combinatorics, 21(2001), 515−541.

62. Д. А. Шабанов, Об одной комбинаторной задаче Эрдеша, Доклады Академии Наук, 396 N2(2004), 166−169.

63. Д. А. Шабанов, О раскрасках гиперграфов, Доклады Академии Наук, 402 N5(2005), 605−608.

64. Д. А. Шабанов, О числе вершин в гиперграфах близких к двудольным, Доклады Академии Наук, 412 N1(2007), 31−34.

65. Д. А. Шабанов, Экстремальные задачи для раскрасок равномерных гиперграфов, Известия РАН Серия математическая, 71 N6(2007), 183−222.

66. D. A. Shabanov, On some extremal properties of hypergraphs colorings, Electronic Notes in Discrete Mathematics, 29(2007), 97−100.

67. Д. А. Шабанов, Об одной комбинаторной задаче Эрдеша, Материалы международной конференции «Дискретный анализ и исследование операций», Новосибирск: изд-во института математики (2004), стр. 91.

68. D. A. Shabanov, On В Property of Hypergraphs, Abstracts of the talks at «Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications», ITI Series, Prague (2006), p. 114.

69. D. A. Shabanov, On Some Properties of Hypergraphs, Abstracts of the talks at «EMS Conference on Horizon of Combinatorics», изд-во Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest (2006), p. 59.

70. Н. Н. Кузюрин, Асимптотическое исследование задачи о покрытии, Проблемы кибернетики, Вып. 37(1980), 19−56.

71. Г. П. Гаврилов и А. А. Сапоженко, Задачи и упражнения по дискретной математике, М.: Физматлит, 2005.

72. П. Эрдеш и Дж. Спенсер, Вероятностные методы в комбинаторике, М.: Мир, 1976.

73. В. Bollobas, Random Graphs, Cambridge University Press, Cambridge, 2001.

74. T. Luczak, S. Janson and A. Rucinski, Random Graphs, A Wiley-Interscience, New York, 2000.

75. В. Ф. Колчин, Случайные графы, M.: Физматлит, 2000.

76. А. V. Kostochka and D. R. Woodall, Density conditions for panchromatic colourings о j hyper graphs, Combinatorics, 21(2001), 515−541.

77. Д. А. Шабанов, Об одной комбинаторной задаче Эрдеша, Доклады Академии Наук, 396 N2(2004), 166−169.

78. Д. А. Шабанов, О раскрасках гиперграфов, Доклады Академии Наук, 402 N5(2005), 605−608.

79. Д. А. Шабанов, О числе вершин в гиперграфах близких к двудольным, Доклады Академии Наук, 412 N1(2007), 31−34.

80. Д. А. Шабанов, Экстремальные задачи для раскрасок равномерных гиперграфов, Известия РАН Серия математическая, 71 N6(2007), 183−222.

81. D. A. Shabanov, On some extremal properties of hypergraphs colorings, Electronic Notes in Discrete Mathematics, 29(2007), 97−100.

82. Д. А. Шабанов, Об одной комбинаторной задаче Эрдеша, Материалы международной конференции «Дискретный анализ и исследование операций», Новосибирск: изд-во института математики (2004), стр. 91.

83. D. A. Shabanov, On В Property of Hypergraphs, Abstracts of the talks at «Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications», ITI Series, Prague (2006), p. 114.

84. D. A. Shabanov, On Some Properties of Hypergraphs, Abstracts of the talks at «EMS Conference on Horizon of Combinatorics», изд-во Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest (2006), p. 59.