Семантические пределы плотных комбинаторных объектов

Autor: Leonardo Nagami Coregliano, Alexander Alexandrovich Razborov
Rok vydání: 2020
Předmět:
Zdroj: Uspekhi Matematicheskikh Nauk. 75:45-152
ISSN: 2305-2872
0042-1316
Popis: Теория пределов дискретных комбинаторных объектов успешно развивается в течение последнего десятилетия. Синтаксический, алгебраический подход к предмету широко известен как "алгебры флагов", тогда как семантический, геометрический подход часто именуется "пределами графов". Язык теории пределов графов в целом более наглядный и выразительный, но той ценой, что он лучше подходит для простых графов, чем для более общих комбинаторных объектов. Сообразно этому, из литературы известны несколько попыток (разной степени общности) определить предельные объекты для более сложных комбинаторных структур. Настоящая статья - еще одна попытка получить рабочую общую теорию плотных предельных объектов. В отличие от предыдущих усилий в этом направлении (за важным исключением работы А. Ароскара и Дж. Каммингса 2014 г.), наши построения основаны на тех же понятиях логики первого порядка и теории моделей, что используются в теории алгебр флагов. Показано, что наши определения естественным образом охватывают многие ранее рассматривавшиеся случаи (такие как графоны, гиперграфоны, направленные графоны, пермутоны, посетоны, раскрашенные графы и пр.), а фундаментальные свойства существования и единственности распространяются на этот более общий случай. Также приведено наглядное общее доказательство непрерывного варианта индуцированной леммы об удалении, основанное на теореме компактности для логики высказываний. Особо выделяется понятие открытой интерпретации, часто позволяющее переносить методы и результаты с одной ситуации на другую. И в этом случае показано, что некоторые ранее известные рассуждения можно довольно естественно выразить на таком языке. Библиография: 68 названий.
Databáze: OpenAIRE
Externí odkaz: