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

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

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


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




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

Успехи математических наук, 2016, том 71, выпуск 1(427), страницы 85–116
DOI: https://doi.org/10.4213/rm9688 (Mi rm9688) 		 
Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)

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

Я. Нешетрил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
PDF полного текста (1344 kB) PDF английской версии (1055 kB) Список цитирования (14)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/rm9688
Аннотация: В работе обсуждается понятие структурной разреженности, а также отношение этого понятия к введенной авторами для классов графов дихотомии “нигде не плотный / где-то плотный”. Рассматриваются многочисленные проявления этой дихотомии и ее связь с такими понятиями, как устойчивость, независимость, 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.
Поступила в редакцию: 02.06.2015
Англоязычная версия:
Russian Mathematical Surveys, 2016, Volume 71, Issue 1, Pages 79–107
DOI: https://doi.org/10.1070/RM9688
Реферативные базы данных:
Тип публикации: Статья
УДК: 512.56+519.71+519.17
MSC: 03C13, 03C98, 05C99
Образец цитирования: Я. Нешетрил, П. Оссона де Мендез, “Структурная разреженность”, УМН, 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/rm9688}
\crossref{https://doi.org/10.4213/rm9688}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3507464}
\zmath{https://zbmath.org/?q=an:06599755}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2016RuMaS..71...79N}
\elib{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000376511100002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84973523453}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm9688
  • https://doi.org/10.4213/rm9688
  • https://www.mathnet.ru/rus/rm/v71/i1/p85
    • Эта публикация цитируется в следующих 14 статьяx:
    1. Gwenaël Joret, Clément Rambaud, “Neighborhood Complexity of Planar Graphs”, Combinatorica, 2024  crossref
    2. Jan Dobrowolski, Rosario Mennuni, “The Amalgamation Property for automorphisms of ordered abelian groups”, Trans. Amer. Math. Soc., 2024  crossref
    3. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, 567  crossref
    4. Sam Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz, “Decomposition horizons: from graph sparsity to model-theoretic dividing lines”, EUROCOMB, 2023, 216  crossref
    5. Guillaume Ducoffe, Michel Habib, Laurent Viennot, “Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension”, SIAM J. Comput., 51:5 (2022), 1506  crossref
    6. J. Nesetril, P. O. de Mendez, R. Rabinovich, S. Siebertz, “Classes of graphs with low complexity: the case of classes with bounded linear rankwidth”, Eur. J. Comb., 91 (2021), 103223  crossref  mathscinet  zmath  isi  scopus
    7. Y. Jiang, J. Nesetril, P. Ossona de Mendez, S. Siebertz, “Regular partitions of gentle graphs”, Acta Math. Hung., 161:2, SI (2020), 719–755  crossref  mathscinet  zmath  isi
    8. G. Ducoffe, M. Habib, L. Viennot, “Diameter computation on h-minor free graphs and graphs of bounded (distance) vc-dimension”, Proceedings of the Thirty-First Annual Acm-SIAM Symposium on Discrete Algorithms (Soda'20), Assoc Computing Machinery, 2020, 1905–1922  mathscinet  zmath  isi
    9. J. Nesetril, P. O. de Mendez, “A unified approach to structural limits and limits of graphs with bounded tree-depth”, Mem. Am. Math. Soc., 263:1272 (2020), 1+  crossref  mathscinet  isi
    10. A. J. Martin, R. Batty, A. Thompson, R. Kuchar, P. Pancoska, “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
    11. J. Nesetril, P. O. de Mendez, “Local-global convergence, an analytic and structural approach”, Comment. Math. Univ. Carol., 60:1 (2019), 97–129  crossref  mathscinet  isi  scopus
    12. J. Nesetril, P. O. De Mendez, “Existence of modeling limits for sequences of sparse structures”, J. Symb. Log., 84:2 (2019), 452–472  crossref  mathscinet  isi  scopus
    13. Joret G., Micek P., de Mendez P.O., Wiechert V., “Nowhere Dense Graph Classes and Dimension”, Combinatorica, 39:5 (2019), 1055–1079  crossref  mathscinet  isi
    14. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:798
    PDF русской версии:162
    PDF английской версии:92
    Список литературы:130
    Первая страница:61
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025