Принудительный график
В теории графов — форсирующий граф это граф, плотность которого определяет, является ли последовательность графов квазислучайной. Этот термин был впервые введен Чангом, Грэмом и Уилсоном в 1989 году. [ 1 ] Форсинг-графы играют важную роль в изучении псевдослучайности в последовательностях графов.
Гипотеза о форсинге утверждает, что форсинг-графы представляют собой в точности циклические двудольные графы. Ее описывают как «одну из основных открытых проблем экстремальной комбинаторики ». [ 2 ]
Определения
[ редактировать ]Пусть т ( Ч , G ) = # помеченных копий H в G / v ( G ) v ( Ч ) , известная как плотность подграфа (в частности, t ( K 2 , G ) — плотность ребер G ). Последовательность графов { Gn приближается к } называется квазислучайной, если для всех графов плотность ребер t ( K2 H , Gn ) ( некоторому p а t приближается H , Gn ) , к p. е(Н) по мере увеличения n , где e ( H ) — количество ребер в H . Интуитивно это означает, что последовательность графов с заданной плотностью ребер имеет такое количество гомоморфизмов графа, которое можно было бы ожидать от случайной последовательности графов. Граф F называется форсирующим, если для всех последовательностей графов { G n } , где t ( K 2 , G n ) приближается к p, когда n стремится к бесконечности, { G n } является квазислучайным, если t ( F , G n ) приближается к p е ( F ) . Другими словами, можно проверить, что последовательность графов является квазислучайной, просто проверив плотность гомоморфизма одного графа. [ 3 ]
Существует второе определение форсирования графов, использующее язык графонов . Формально граф называется форсирующим, если каждый графон W такой, что t ( F , W ) = t ( K 2 , W ) е ( F ) является постоянным. Интуитивно понятно, что эти определения связаны. Константный графон W ( x , y ) = p представляет случайный граф Эрдеша – Реньи G ( n , p ) , поэтому можно ожидать, что он будет иметь тесную связь с квазислучайными графами. На самом деле эти определения эквивалентны. [ нужна ссылка ]
Примеры
[ редактировать ]Первым графом воздействия, который следует рассмотреть, является 4-цикл C 4 , поскольку он тесно связан с другими условиями квазислучайности. В той же статье Чанг, Грэм и Уилсон показали, что каждый четный цикл C 2 t и полные двудольные графы вида K 2, t с t ≥ 2 являются форсирующими. [ 1 ] Конлон, Фокс и Судаков расширили этот последний результат, включив в него все двудольные графы с двумя вершинами в одной части, полные до другой части. [ 3 ]
Принуждение семей
[ редактировать ]Семейства принуждения обеспечивают естественное обобщение графов принуждения. Семейство графов F заставляет { G n } быть квазислучайным всякий раз, когда t ( F , G n ) приближается к p е ( F ) для всех F ∈ F . Охарактеризовать семейства воздействий гораздо сложнее, чем охарактеризовать графики воздействий, поэтому известно немногое. Известные семьи выгонки включают:
- { K 2 , C 2 t } , где t - целое положительное число;
- { C 2 s , C 2 t } , где s и t — положительные целые числа, причем s ≠ t ;
- { К 2 , К 2, т } , где т ≥ 2 ; и
- { K 2, s , K 2, t } , где s ≠ t и s , t ≥ 2 . [ 1 ]
Формирование гипотезы
[ редактировать ]Гипотеза о вынуждении была выдвинута Скоканом и Томой в 2004 году. [ 4 ] и официально оформлен Конлоном, Фоксом и Судаковым в 2010 году. [ 3 ] Он дает характеристику графов принуждения, формализованную следующим образом:
Граф является форсирующим тогда и только тогда, когда он двудольный и содержит цикл.
Одно направление этого утверждения хорошо известно. Чанг, Грэм и Уилсон показали, что если граф имеет нечетный цикл, он не может быть принудительным, [ 1 ] поэтому, если граф является форсирующим, то он должен быть двудольным. Кроме того, Конлон, Фокс и Судаков утверждали, что t ( H , G n ) приближается к p е ( Ч ) для любого леса H, когда { G n } является почти регулярной (и не обязательно квазислучайной) последовательностью графов. [ 3 ] Таким образом, граф принуждения должен быть двудольным и иметь хотя бы один цикл. Другое направление еще предстоит доказать, но не найден ни один граф взаимодействия, который не обладал бы обоими этими свойствами.
Гипотеза о вынуждении также подразумевает гипотезу Сидоренко , давнюю гипотезу в этой области. Известно, что все форсинг-графы являются Сидоренко, поэтому, если гипотеза форсинга верна, то все двудольные графы хотя бы с одним циклом будут Сидоренко. [ 3 ] Поскольку деревья Сидоренко, [ 5 ] все двудольные графы были бы Сидоренко.
Ссылки
[ редактировать ]- ^ Jump up to: а б с д Чанг, Франция; Грэм, РЛ; Уилсон, Р.М. (1 декабря 1989 г.). «Квазислучайные графики» . Комбинаторика . 9 (4): 345–362. дои : 10.1007/BF02125347 . ISSN 1439-6912 . S2CID 17166765 .
- ^ Хэнкок, Роберт; Кабела, Адам; Краль, Даниэль; Мартинс, Таиса; Паренте, Роберто; Скерман, Фиона; Воец, Ян (2023). «Никакие дополнительные турниры не являются квазислучайными». Европейский журнал комбинаторики . 108 : Статья № 103632, 10. arXiv : 1912.04243 . дои : 10.1016/j.ejc.2022.103632 . МР 4502205 .
- ^ Jump up to: а б с д и Конлон, Дэвид; Фокс, Джейкоб; Судаков, Бенни (20 октября 2010 г.). «Приблизительная версия гипотезы Сидоренко» . Геометрический и функциональный анализ . 20 (6): 1354–1366. arXiv : 1004.4236 . дои : 10.1007/s00039-010-0097-0 . ISSN 1016-443X . S2CID 1872674 .
- ^ Скокан, Йозеф; Тома, Любош (1 июня 2004 г.). «Двудольные подграфы и квазислучайность» . Графы и комбинаторика . 20 (2): 255–262. дои : 10.1007/s00373-004-0556-1 . ISSN 0911-0119 . S2CID 2154492 .
- ^ СИДОРЕНКО А.Ф. (1992). «Неравенства для функционалов, порожденных двудольными графами» . Дискретная математика и приложения . 2 (5). дои : 10.1515/dma.1992.2.5.489 . ISSN 0924-9265 . S2CID 117471984 .