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

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

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



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






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


УМН, 2016, том 71, выпуск 1(427), страницы 85–116 (Mi umn9688)  

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

Структурная разреженность

Я. Нешетрилab, П. Оссона де Мендезac

a Computer Science Institute of Charles University (IUUK), Praha, Czech Republic
b Computer Science Institute of Charles University (ITI), Prague, Czech Republic
c Centre d'Analyse et de Mathèmatiques Sociales (CNRS, UMR 8557), Paris, France

Аннотация: В работе обсуждается понятие структурной разреженности, а также отношение этого понятия к введенной авторами для классов графов дихотомии “нигде не плотный / где-то плотный”. Рассматриваются многочисленные проявления этой дихотомии и ее связь с такими понятиями, как устойчивость, независимость, VC-размерность, регулярные разбиения, энтропия, скорость класса, разложение с малой древесной глубиной, квазиширота, покрытие окрестностями, статистика подграфов и др., а также такие аспекты алгоритмической сложности, как разрешимость проверки модели первого порядка при фиксированном параметре.
Библиография: 78 названий.

Ключевые слова: реляционные структуры, теория графов, нигде не плотный класс, разреженность, VC-размерность, устойчивость, свойство независимости, неглубокий минор, случайно-свободный предел, структурный предел, борелевская структура, моделировка, разложение с малой древесной глубиной, проверка моделей.

Финансовая поддержка Номер гранта
European Research Council ERCCZ LL-1201
Agence Nationale de la Recherche ANR-13-BS02-0007
Czech Science Foundation CE-ITI P202/12/G061
Работа первого автора выполнена при поддержке грантов ERCCZ LL-1201 и CE-ITI P202/12/G061, а также Европейской объединенной лаборатории “Structures in Combinatorics” (LEA STRUCO). Работа второго автора выполнена при поддержке гранта ERCCZ LL-1201 и Европейской объединенной лаборатории “Structures in Combinatorics” (LEA STRUCO), а также при частичной поддержке проекта Stint ANR за номером ANR-13-BS02-0007.


DOI: https://doi.org/10.4213/rm9688

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

Англоязычная версия:
Russian Mathematical Surveys, 2016, 71:1, 79–107

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

Тип публикации: Статья
УДК: 512.56+519.71+519.17
MSC: 03C13, 03C98, 05C99
Поступила в редакцию: 02.06.2015

Образец цитирования: Я. Нешетрил, П. Оссона де Мендез, “Структурная разреженность”, УМН, 71:1(427) (2016), 85–116; Russian Math. Surveys, 71:1 (2016), 79–107

Цитирование в формате AMSBIB
\RBibitem{NesOss16}
\by Я.~Нешетрил, П.~Оссона де Мендез
\paper Структурная разреженность
\jour УМН
\yr 2016
\vol 71
\issue 1(427)
\pages 85--116
\mathnet{http://mi.mathnet.ru/umn9688}
\crossref{https://doi.org/10.4213/rm9688}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3507464}
\zmath{https://zbmath.org/?q=an:06599755}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2016RuMaS..71...79N}
\elib{http://elibrary.ru/item.asp?id=25707791}
\transl
\jour Russian Math. Surveys
\yr 2016
\vol 71
\issue 1
\pages 79--107
\crossref{https://doi.org/10.1070/RM9688}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000376511100002}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84973523453}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn9688
  • https://doi.org/10.4213/rm9688
  • http://mi.mathnet.ru/rus/umn/v71/i1/p85

    ОТПРАВИТЬ: 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. J. Nešetřil, P. Ossona de Mendez, “Towards a characterization of universal categories”, J. Pure Appl. Algebra, 221:8 (2017), 1899–1905  crossref  mathscinet  isi  scopus
    2. Martin A.J., Batty R., Thompson A., Kuchar R., Pancoska P., “An Examination of Children'S Motives For Triathlon Participation as a Function of Age”, Ann. Leis. Res., 22:2 (2019), 183–201  crossref  isi  scopus
    3. Nesetril J., de Mendez P.O., “Local-Global Convergence, An Analytic and Structural Approach”, Comment. Math. Univ. Carol., 60:1 (2019), 97–129  crossref  mathscinet  isi  scopus
    4. Nesetril J., De Mendez P.O., “Existence of Modeling Limits For Sequences of Sparse Structures”, J. Symb. Log., 84:2 (2019), 452–472  crossref  isi
  • Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:347
    Полный текст:39
    Литература:61
    Первая стр.:61
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019