RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. МИАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. МИАН, 2011, том 274, страницы 269–290 (Mi tm3324)  

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана

А. А. Разборовab

a Чикагский университет, Чикаго, США
b Математический институт им. В. А. Стеклова РАН, Москва, Россия

Аннотация: Фон-Дер-Флаасс (1988) предложил общую конструкцию, позволяющую превратить произвольный ориентированный граф $\Gamma$ без индуцированных циклов $\vec C_4$ в $(3,4)$-граф Турана. Им было замечено, что все примеры Турана–Брауна–Косточки можно получить с помощью его конструкции, а также была доказана нижняя оценка $\frac37(1-o(1))$ на реберную плотность любого $(3,4)$-графа Турана, получаемого таким образом. В настоящей работе мы доказываем оптимальную нижнюю оценку $\frac49(1-o(1))$ на реберную плотность любого $(3,4)$-графа Турана, строящегося с помощью конструкции Фон-Дер-Флаасса, при выполнении любого из следующих двух ограничений на неориентированный остов $G$ ориентированного графа $\Gamma $: (i) $G$ является полным многодольным графом; (ii) $G$ имеет плотность ребер не ниже $\frac23-\epsilon$, где $\epsilon>0$ – некоторая абсолютная константа. Без дополнительных ограничений на $\Gamma$ мы в состоянии усилить оценку Фон-Дер-Флаасса до значения $\frac7{16}(1-o(1))$.

Полный текст: PDF файл (341 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 247–266

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.176+519.179.1
Поступило в октябре 2010 г.

Образец цитирования: А. А. Разборов, “Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 269–290; Proc. Steklov Inst. Math., 274 (2011), 247–266

Цитирование в формате AMSBIB
\RBibitem{Raz11}
\by А.~А.~Разборов
\paper Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана
\inbook Алгоритмические вопросы алгебры и логики
\bookinfo Сборник статей. К~80-летию со дня рождения академика Сергея Ивановича Адяна
\serial Тр. МИАН
\yr 2011
\vol 274
\pages 269--290
\publ МАИК «Наука/Интерпериодика»
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm3324}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2962945}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 247--266
\crossref{https://doi.org/10.1134/S0081543811060150}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000295983200014}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84870915108}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tm3324
  • http://mi.mathnet.ru/rus/tm/v274/p269

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Hatami H., Hladky J., Kral D., Norine S., Razborov A., “On the Number of Pentagons in Triangle-Free Graphs”, J. Comb. Theory Ser. A, 120:3 (2013), 722–732  crossref  mathscinet  zmath  isi  elib
    2. Falgas-Ravry V., Vaughan E.R., “Applications of the Semi-Definite Method to the Turan Density Problem for 3-Graphs”, Comb. Probab. Comput., 22:1 (2013), 21–54  crossref  mathscinet  zmath  isi  elib
    3. Razborov A.A., “On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs”, J. Graph Theory, 74:2 (2013), 236–248  crossref  mathscinet  zmath  isi  elib
    4. А. А. Разборов, “О $(3,4)$-проблеме Турана с запрещенными подграфами”, Матем. заметки, 95:2 (2014), 271–281  mathnet  crossref  mathscinet  elib; A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254  crossref  isi  elib
    5. Glebov R., Kral D., Volec J., “A problem of Erdős and Sós on 3-graphs”, Isr. J. Math., 211:1 (2016), 349–366  crossref  mathscinet  zmath  isi  elib  scopus
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Просмотров:
    Эта страница:192
    Полный текст:5
    Литература:35

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018