Задачи непрерывной и полиномиальной комбинаторики тема диссертации и автореферата по ВАК РФ 01.01.01, кандидат наук Петров, Федор Владимирович

• Петров, Федор Владимирович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Петров, Федор Владимирович

Оглавление

Введение

1 Непрерывная комбинаторика

1.1 Непрерывные графы и гиперграфы. Меры на счетных графах

1.2 Исправление непрерывных гиперграфов

1.3 Метрики

1.4 Виртуальная непрерывность: основные понятия

1.5 Толщина. Метрика и норма на пространстве виртуально непрерывных функций

1.6 Виртуальная непрерывность и транспортная задача

1.7 Виртуальная непрерывность. Приложения

2 Полиномиальная комбинаторика

2.1 Комбинаторная теорема о нулях как формула

2.2 Тождества для коэффициентов

2.3 Пути в градуированных графах

2.4 Приложения к аддитивной комбинаторике

2.5 Приложения к теории графов

2.6 Частичная симметризация

2.7 Групповые кольца

Заключение

Список используемой литературы

Введение диссертации (часть автореферата) на тему «Задачи непрерывной и полиномиальной комбинаторики»

Введение

Диссертация относится к двум бурно развивающимся областям современного комбинаторного анализа.

В первой части речь идёт о так называемой непрерывной комбинаторике, которую можно определить в нескольких словах как теорию измеримых функций нескольких переменных ("обычная", дискретная комбинаторика соответствует случаю конечного пространства с мерой). Этот взгляд и его приложения систематически изложен, например, в недавней книге Л. Ловаса [47]. К этому параллелизму относится и знаменитое соответствие Г. Фюрстен-берга [15] между аддитивными свойствами циклической группы и эргодической теорией. Основные работы первой части основаны на предложенным А. М. Вершиком подходе к изучению действия групп через изучение динамики функций нескольких переменных, в первую очередь метрик.

Вторая часть относится к приложениям полиномиального метода в перечислительной и аддитивной комбинаторике, а также теории графов. Кроме того, представлен ряд приложений метода групповых колец, который предлагается понимать как некоммутативный (точнее, не обязательно коммутативный) аналог полиномиального метода. Основным инструментом является явная форма комбинаторной теоремы о нулях Н. Алона, а также идео-

логия её доказательства. Метод групповых колец восходит к работам Дж. Олсона.

Актуальность вопросов, изучаемых в диссертации, подтверждается их встроенностью в широкий математический контекст (теория моделей, функциональный анализ, эргодическая теория, теория меры, транспортная задача; перечислительная комбинаторика, интегралы Сельберга, симметрические функции, теория представлений, аддитивная комбинаторика, групповые кольца, алгебраическая геометрия) и высоким интересом специалистов, — некоторые из них упомянуты выше, ещё многие, но далеко не все, — в тексте диссертации.

Я считаю темы исследований обеих глав разработанными в достаточной степени, чтобы представлять работу к защите. Получен ряд как общих результатов, так и их приложений. Конечно, это не означает ни в коей степени, что темы исчерпаны, — напротив, остаётся ряд важных вопросов, некоторые из которых сформулированы в заключении.

Целью работы является получение и изложение новых конкретных математических результатов и разработка общих методов, позволяющих получать новые результаты в дальнейшем и расширяющих понимание.

Большинство результатов работы — новые, что подтверждается их публикацией в рецензируемых изданиях. Некоторые результаты состоят в новых подходах к доказательствам уже известных теорем, что также представляет интерес.

Работа носит теоретический характер, её результаты могут применяться — и уже применяются — в математических исследованиях в указанных выше областях, а также в теоретической физике (последнее относится в первую очередь к тожде-

ствам типа Дайсона, Морриса, Аомото, Форрестера, возникающим в квантовой электродинамике.)

В первой главе используются известные и новые методы функционального анализа, теории меры, эргодической теории, комбинаторики, вторая глава посвящена развитию полиномиального метода комбинаторики и рассматриваемого как его обобщения метода групповых колец. В целом я считаю, что именно разработанные методы являются главным результатом работы.

В тексте диссертации содержатся определения, пояснения, исторические справки, формулировки вспомогательных утверждений и теорем 1 - 46, каковые выносятся на защиту.

Результаты диссертации опубликованы в 14 статьях в рецензируемых журналах и одном препринте. Они неоднократно докладывались на международных научных конференциях и исследовательских семинарах. Это свидетельствует об их достоверности.

Доказательства теорем не приводятся в основном тексте, они содержатся в прилагаемых статьях [71-85]. Определяемые понятия выделяются полужирным.

Я глубоко благодарен моему учителю Анатолию Моисеевичу Вершику за постоянную поддержку и множество замечательных вопросов; всем моим соавторам, особенно — младшим коллегам Павлу Затицкому и Владиславу Волкову, без которых я бы, определённо, сделал много меньше; Даниле Черкашину, любезно взявшему на себя труд исправить много неточностей.

Перейдем к изложению результатов.

Глава 1. Непрерывная комбинаторика

1.1. Непрерывные графы и гиперграфы. Меры на

счетных графах.

т-однородным гиперграфом на множестве вершин V называют семейство его т-элементных подмножеств (рёбер), при т = 2 говорят о графе. Если заменить подмножества на упорядоченные наборы (ы,..., ут) € Vт, получим ориентированный гиперграф. Гиперграф называют конечным, соответственно счетным, если таково множество вершин.

Удалением вершин и/или рёбер из данного гиперграфа получаем его подграф. Удаляя только ребра получаем остовный подграф, только вершины — индуцированный подграф.

Гомоморфизмом гиперграфа С\ на множестве VI в гиперграф С2 на множестве V2 называют отображение f : VI ^ V2, переводящее ребро в ребро. Гомоморфизм, являющийся биекци-ей, называется изоморфизмом, если обратное отображение — тоже гомоморфизм.

Если в качестве V выступает пространство с вероятностной мерой ¡, измеримый т-однородный гиперграф естественно было бы понимать как измеримую функцию из т-ой симметрической степени пространства (V, в {0,1} (для ориентированных гиперграфов — обычной степени Vm). Вместо функции на

симметрической степени нам удобнее говорить о симметрической функции на Vт. В действительности часто удобнее рассматривать более широкий класс функций — со значениями в [0,1]. Причина в том, что этот класс устойчив относительно взятия слабых пределов в подходящем смысле.

Измеримые функции нескольких переменных со значениями в сепарабельном метрическом пространстве во многом похожи на измеримые гиперграфы. С такой функцией f (х\,... ,Хк) связана мера на конечных или счетных к-тензорах: выбирая точки х\,х2,... случайно по мере строим тензор, у которого коэффициент при вгх ® вг2 ® ■ ■■ ® вгк равен f (г^ , ..., ггк) (здесь в\,... — стандартный базис пространства, тензорная степень которого рассматривается). При к = 2 тензоры канонически изоморфны матрицам и мы получаем так называемое матричное распределение функции f(х\,х2). Для двух не изоморфных (в естественном понимании изоморфизма функций двух переменных) f, д матричные распределения могу совпадать. Именно, если на V задано измеримое отношение эквивалентности, и функция f (х,у) зависит только от классов х и у по этому отношению, матричное распределение функции f такое же, как у фактор-функции на пространстве классов (которое может снова быть стандартным пространством). Однако это по существу единственный пример, что было установлено для компактных метрик М. Л. Громовым [28] и в общем случае для так называемых чистых функций А. М. Вершиком [29]. То же верно и при к> 2.

Каждому измеримому гиперграфу ф : Vm ^ [0,1] соответствует мера на множестве гиперграфов на фиксированном множестве М: выбирая для каждой вершины V € М случайно по

мере л точку Г (у) € М, ребро {у\,... ,ут} возьмём с вероятностью ф(Г(у\),...,Г(ут)). Эти события независимы. Очевидно, эта мера определяется тензорным распределением функции ф. Обратное тоже верно, но нетривиально, см. теорему 13.10 в [47] (при к = 2).

При т = 2, ф = р € (0,1) получаем модель случайного графа Эрдёша - Реньи. Для счетного М при любом р € (0,1) случайный граф Эрдёша - Реньи с вероятностью 1 изоморфен универсальному графу Радо. Характеристические свойства универсального графа Я:

и1) Любой конечный граф изоморфен некоторому индуцированному подграфу Я;

и2) Если подграфы, индуцированные на конечных подмножествах VI ,У2 С М изоморфны посредством отображения f : VI ^ V2 (такое отображение называют частичным изоморфизмом), то f продолжается до автоморфизма всего графа Я.

Общие соображения позволяют ослабить свойство И2: достаточно потребовать, что для любого конечного надмножества V3 Э VI найдется надмножество V4 Э V2 и продолжение f до частичного изоморфизма с Vз на Р4. Кроме того, достаточно требовать этого при дополнительном условии | У3 \ VI | = 1.

Пусть К — некоторый класс конечных графов. Рассмотрим счетные графы, все конечные индуцированные подграфы которых принадлежат классу К. Счетный граф С назовем К-универсальным, если выполняется условие

и1') Любой конечный граф в классе К изоморфен некоторому индуцированному подграфу С, а также условие и2.

Несложно доказать, что если К-универсальный граф суще-

ствует, то он единственен с точностью до изоморфизма.

Таким образом, граф Радо является универсальным в классе всех графов, и случайный граф Эрдёша - Реньи даёт пример инвариантной (относительно перестановок вершин) вероятностной меры на классе счетных графов, для которой почти любой граф есть граф Радо.

Важным примером класса графов, для которых существует универсальный граф, является класс графов без треугольников или, более общо, класс графов без клик (полных подграфов) на й вершинах, где с1 > 2 — фиксированное натуральное число. В этом случае вопрос о (борелевской в естественном смысле) инвариантной вероятностной мере на классе всех счетных графов, для которой почти любой граф будет ^-универсальным, оставался открытым. Эта задача была решена в [71]. Именно, справедлива следующая

Теорема 1. Пусть й ^ 3 и Ка — класс конечных графов, не содержащих клик на й вершинах. Существует симметричная функция ф : [0,1]2 ^ {0,1}, для которой соответствующая мера на счётных графах сосредоточена на множестве Ка-универсальных графов.

Доказательство теоремы основано на идее построения не измеримого, а топологического универсального графа — открытого множества в М2, обладающего определенными свойствами — отсутствия клик на й вершинах и топологическим аналогом универсальности.

Отметим, что то свойство, что функция ф действует в {0,1}, а не просто в отрезок [0,1], является необходимым для того, чтобы соответствующая мера была сосредоточена на Ка-универсальных графах. Это также доказано в [71].

1.2. Исправление непрерывных гиперграфов

Широко известна лемма Семереди об удалении треугольника:

если граф на п вершинах содержит о(п3) треугольников, то можно удалить о(п2) рёбер так, чтобы треугольников не осталось.

Обобщение этой леммы на случай гиперграфов влечет, в частности, теорему Семереди об арифметических прогрессиях

[37].

Измеримой версией леммы об удалении треугольника является следующая теорема:

если измеримая симметричная функция f (х, у) на [0,1] удовлетворяет равенству

f (x,y)f (y,z)f (г,х)=0 (1.1)

при почти всех х,у^ € [0,1], то функцию f можно заменить на эквивалентную (то есть изменить ее значения на множестве меры 0 на квадрате [0,1]2) так, что условие (1.1) будет выполняться при всех х,у, z € [0,1].

Отметим, что можно вывести дискретную лемму об удалении треугольника из измеримой с помощью перехода к пределу по ультрафильтру и взятия сепарабельного фактора [46].

Для каких условий, кроме (1.1), верно аналогичное утверждение?

При исследовании измеримых метрик (см. далее) оказалась полезной следующая теорема [72]:

Теорема 2. Пусть измеримая функция р(х,у) : [0,1]2 ^ [0, те) удовлетворяет при почти всех х,у, z € [0,1] равенству р(х, у) = р(у,х) и неравенству р(х,у)+р(у, z) ^ р(х^). Тогда существует

функция, эквивалентная р, удовлетворяющая этим условиям при всех х,у, г € [0,1].

Иными словами, измеримая почти полуметрика эквивалентна измеримой полуметрике.

Отметим, что дискретный аналог, по крайней мере наивный, не имеет места. Именно, пусть X — большое конечное множество, на котором задана функция й(х, у) : X х X — [0, те) ("почти метрика"), удовлетворяющая условиям

(1) й(х, у) = 0 тогда и только тогда когда х = у;

(п) й(х,у) = й(у,х) при всех х,у € X;

(ш) й(х, у) + й(у, г) ^ й(х, г) для всех троек (х, у, г) € X3 кроме o(\X|3) троек.

Следует ли из этих свойств, что

(гу) й совпадает с некоторой полуметрикой й, заданной на X, на всех парах (х,у) € X2 кроме о(^\2) пар?

Ответ отрицательный, контрпример приведён в [80].

Там же приведена измеримая версия леммы об удалении гиперграфа. Сформулируем ее. Введем необходимые обозначения. Пусть К — компактное метрическое пространство, X — стандартное непрерывное пространство с мерой (скажем, отрезок [0,1] с мерой Лебега). Пусть, далее, к — натуральное число, функция f (х1,х2,... ,хк): Xк — К измерима относительно бо-релевской сигма-алгебры на К. Обозначим через Мк множество всех упорядоченных к-наборов I = (г1,...,гк) попарно различных натуральных чисел. Для I € Мк и точек у\,у2,... в X обозначим Ц (у1,у2, ...):= f (у^,..., у1к). Таким образом, f индуцирует отображение / из Xк в тихоновский компакт К-^к: точке (у1,у2,...) € Xк соответствует функция I — fI(у1,у2,...,) на

Мк.

Теорема 3. 1. Пусть М — фиксированное замкнутое подмножество К^к. Предположим, что при почти всех у!,у2,... в X отображение ¡'(у!,у2,...) принадлежит М. Тогда существует измеримая функция д на Xк, эквивалентная f, такая, что д(у\,у2,...) принадлежит М для всех попарно различных У!,У2, ... в х.

2. Предположим дополнительно, что "почти симметрична", то есть

(х!,...,хк) = I' (хЖ1 ,...,хЖк) (1.2)

для почти всех х!,...,хк в X и любой перестановки п множества {1, 2,...,к}. Тогда существует измеримая симметричная функция д на Xк, эквивалентная f, такая, 'что д(у!,у2,...) принадлежит М для всех (не обязательно различных) у!,у2,... в X.

Доказательство теоремы 3 основано на теореме Лебега о точках плотности, а пункта 2 также на теореме Рамсея.

1.3. Метрики

Пусть (X, л) — стандартное вероятностное пространство. Допустимая полуметрика р на X это измеримая функция р(х, у) : [0,1]2 ^ [0, те), которая удовлетворяет при почти всех х,у^ € [0,1] равенству р(х, у) = р(у, х) и неравенству р(х, у) + р(у, z) ^ р(х^), такая что при почти всех х все шары В(х,Я) = {у : р(х,у) ^ Я},Я > 0, с центром х имеют положительную меру. Тройка (X, л, р) называется допустимой полуметрической тройкой.

Исследование метрических троек (метрических пространств с мерой) было инициировано М. Громовым [28]. В работах Вер-

шика [26, 31] был предложен альтернативный взгляд на метрические тройки: вместо рассмотрения различных мер на топологическом пространстве (например, метрическом компакте) рассматриваются метрики на фиксированном стандартном пространстве с мерой. Этот подход естественно возникает при изучении динамики метрики под действием группы.

Теорема 2 позволяет считать, что р — полуметрика на X. Хотя выбор такой полуметрики не однозначен, любые две эквивалентные допустимые полуметрики совпадают на некотором подмножестве Xi С X полной меры.

Допустимая метрика — это допустимая полуметрика, эквивалентная на множестве полной меры некоторой метрике.

Имеется несколько равносильных приведенному определений допустимости. Прежде чем их формулировать, введём несколько определений.

Существенным диаметром essdiam^(Xi) множества Xi D X назовем существенный супремум функции p(x,y) на Xi х Xi. Диаметром diam^(Xi), как обычно, будем называть супремум р(х, у) на Xi х Xi. Существенный диаметр, в отличие от диаметра, не меняется при замене функции р на эквивалентную.

Пусть е е (0,1) — фиксированное число. Рассмотрим наименьшее натуральное к, для которого X можно представить как объединение множеств Xo,Xi,...,Xk таких, что ¡(Xq) < е и diam^(Xj) < е for j = 1,...,к. е-энтропия допустимой тройки (X, ¡, р) определяется как

Ш£(р,ц.) = logk

(логарифм по основанию 2). Если такого к не существует, полагаем И£(р, ¡) = те.

Полуметрика р задает полуметрику Канторовича Кр на пространстве борелевских вероятностных мер на X: расстояние между двумя такими мерами ¡1,^2 определяется как супремум выражения J f (х)й(л! — ¡2), где f — 1-липшицева относительно полуметрики р функция.

В [74] дается характеристика допустимости:

Теорема 4. Пусть р — измеримая полуметрика на стандартном вероятностном пространстве (X, ¡). Следующие свойства 'равносильны:

1) Тройка (X, л, р) допустима, то есть почти все шары имеют положительную меру.

2) Найдется множество полной меры X! С X, сужение полуметрики р на которое — сепарабельное полуметрическое пространство.

3) Мера л аппроксимируется мерами с конечным носителем в полуметрике Канторовича Кр.

4) Для любого е > 0 полуметрика р имеет конечную е-энтропию.

5) Для всякого е > 0 пространство X является объединением множеств Xo,X!,...Хк таких, что 11X0) < е и существенный диаметр в88ё1ашр (Xj) < е при всех ] = 1,...,к.

6) Для любого множества А положительной меры существенный инфимум метрики р на А х А равен 0.

Теорема классификации [28, 32] говорит, что метрика с точностью до изоморфизма определяется распределением матриц

расстояний р(хг,х^)1<г^<п (по всем п). Таким образом, эти распределения должны определять и допустимость метрики. Вот один из возможных критериев.

Теорема 5. 1) Если метрика р не допустима, то существует с > 0, для которого вероятность следующего события стремится к 1 с ростом п:

(Рс) найдется множество индексов I С {1, 2,...,п} мощности хотя бы сп такое, что р(xг,xj) > с для всех различных

г,3 € I.

2) Если метрика р допустима, то при любом с > 0 вероятность события Рс стремится к 0.

В обоих случаях скорость сходимости к 1 или 0 как минимум экспоненциальна по п.

Для изучения конуса Аёш (X) допустимых полуметрик полезна следующая топология. т-нормой ^\\т измеримой функции f (х,у) на X х X будем называть (конечный или бесконечный) инфимум выражения /ххх р(х,у)й^(х)й^(у) по всем измеримым полуметрикам р на X, удовлетворяющим при почти всех х,у неравенству ^(х, у)\ ^ р(х,у). Ценность соответствующего этой норме расстояния на конусе Аёш (X) в том, что сходимость по т-норме позволяет контролировать е-энтропию, и, следовательно, допустимость: множество Аёш (X) замкнуто по т-норме. С другой стороны, если последовательность полуметрик сходится в Ь1 к допустимой полуметрике, то сходимость имеет место и в т-норме. В частности, компактность некоторого множества допустимых полуметрик по норме Ь1 равносильна компактности по т-норме. Эти утверждения доказаны в [74], там же приведены критерии предкомпактности множе-

ства М С Аёш (X) по т-норме. Сформулируем критерий пред-компактности выпуклого множества:

Теорема 6. Равномерно интегрируемое семейство М допустимых полуметрик предкомпактно по т-норме тогда и только тогда, когда при всяком е > 0 е-энтропии полуметрик из множества М равномерно ограничены.

Этот критерий может быть сформулирован для не обязательно выпуклых множеств, поскольку предкомпактность множества равносильна предкомпактности его выпуклой оболочки. Таким образом, т-предкомпактность произвольного равномерно интегрируемого семейства М С Аёш (X) равносильна равномерной ограниченности е-энтропий выпуклых комбинаций полуметрик семейства М.

В следующем важном частном случае оказывается, что достаточно рассматривать даже не все выпуклые комбинации.

Теорема 7. Пусть Т — сохраняющее меру преобразование стандартного пространства с мерой Х,л), р — суммируемая допустимая полуметрика на X. Предположим, что при всяком е > 0 е-энтропии полуметрик рп(х, у) := П П-0 р(Тгх, Тгу) равномерно ограничены. Тогда орбита метрики р под действием Т предкомпактна в т-норме.

Эта теорема является ключевой при установлении следующего критерия дискретности (чистой точечности) спектра автоморфизма Т на X:

Теорема 8. 1) Если спектр автоморфизма Т — чисто точечный, то при всяком е > 0 для любой суммируемой полуметрики р е-энтропии полуметрик рп равномерно ограничены.

2) Если хотя бы для одной допустимой метрики р е-энтропии полуметрик рп равномерно ограничены, то спектр автоморфизма Т — чисто точечный.

В этой теореме проявляется общий феномен независимости от выбора допустимой метрики. Причина кроется в следующем наблюдении [75]:

Теорема 9. Пусть р! и р2 — две допустимые метрики на пространстве Лебега (X, л). Тогда для любого е > 0 существует множество К С X, такое что л(К) > 1 — е и топологии, задаваемые метриками р! и р2 на К, совпадают.

Из теоремы 9 немедленно вытекает теорема Лузина: измеримая на (X, л) функция f непрерывна по допустимой метрике р на некотором множестве К меры л(К) > 1 — е. Для доказательства достаточно рассмотреть допустимую метрику р!(х, у) = р(х,у) + \!(х) — (у)|, по которой f, очевидно, непрерывна, и применить теорему 9.

1.4. Виртуальная непрерывность: основные понятия

Для измеримых функций f (■, ■) на произведении X х У стандартных вероятностных пространств (X, л), (У, V) двух переменных аналог теоремы Лузина — непрерывность на произведении X' х У' множеств меры более 1 — е относительно заданной метрики вида р[(х!,ух), (х2,у2)] = рх(х!,х2) + ру(у!,у2), уже выполняется не всегда. Это приводит к следующему понятию.

Измеримая функция f (■, ■) на произведении пространств с мерой (X, л) х (У, V) называется собственно виртуально непрерывной, если для любого е > 0 найдутся множества X' С X,

У' С У меры хотя бы 1 — е каждое, и допустимые полуметрики рх, ру на X', У' соответственно, такие что функция f непрерывна на (X' х У', рх х ру). Функция, совпадающая с собственно виртуально непрерывной на множестве полной меры в X х У, называется виртуально непрерывной. Виртуально непрерывные функции большего числа аргументов определяются точно так же.

В этом определении существенно, что метрика, относительно которой функция должна быть непрерывной, не произвольна, а учитывает структуру прямого произведения (более общо, наличие фиксированных подалгебр). Нетрудно убедиться, что не существует универсальной метрики такого типа, т.е. такой метрики, непрерывность в которой равносильна виртуальной непрерывности; это объясняет нетривиальность введенного понятия.

Ясно, что всякая допустимая метрика — как измеримая функция двух переменных — виртуально непрерывна. Функция, непрерывная по какой-либо допустимой метрике указанного вида на произведении пространств, разумеется, виртуально непрерывна. Вырожденные функции (или "функции конечного ранга") f (х, у) = ЕИ1 <£г(х)фг(у), где &(•),&(•), г = 1,...,п, — произвольные измеримые функции, также виртуально непрерывны. Достаточно воспользоваться теоремой Лузина для всех функций ^(•), г = 1,...,п, и фг( ), г = 1,...,п.

Менее тривиальные примеры виртуально непрерывных функций дают (см. далее) функции из некоторых классов Соболева, а также ядра ядерных операторов.

Простым примером измеримой функции на квадрате [0,1]2, не являющейся виртуально непрерывной, может служить характеристическая функция треугольника {х > у}. Вообще, в слу-

чае функций двух переменных на группе, которые зависят от частного двух аргументов, критерий виртуальной непрерывности прост:

Предложение 1. Пусть С — метризуемая компактная группа, — измеримая по мере Хаара функция на С. Тогда функция Г(х, у) := f (ху-!) на СхС виртуально непрерывна если и только если функция эквивалентна непрерывной.

Виртуально непрерывные функции автоматически обладают более сильными свойствами, чем это требуется по определению.

Во-первых, пользуясь теоремой 9, немедленно получаем, что метрики можно считать наперед заданными:

Теорема 10. Пусть функция (■, ■) собственно виртуально непрерывна. Тогда для любого е > 0 и любых допустимых метрик рх, ру на X, У найдутся множества X' С X, У' С У меры хотя бы 1 — е каждое, такие что функция непрерывна на (X' х У', рх х ру).

С другой стороны, выбирая подходящим образом метрики, можно добиться того, чтобы множества X',У' из определения имели полную меру:

Теорема 11. Пусть функция (■, ■) собственно виртуально непрерывна. Тогда найдутся множества X' С X, У' С У полной меры каждое и допустимые полуметрики рх, ру на X', У' соответственно, такие что функция непрерывна на (X' х У' ,рх х ру).

Функцию двух переменных на X х У полезно рассматривать, как отображение из X в пространство функций на У, (т.е.

f (х,у) = ¡'х(у)). Более подробно о том, как использовать это для классификации измеримых функций, см. статью А. М. Вершика [49]. Виртуальная непрерывность описывается в этих терминах следующим равносильным определением:

Теорема 12. Следующие свойства функции (•, •) 'равносильны: (1) f виртуально непрерывна;

(п) для любого е > 0 найдутся множества X' С X,У' С У меры хотя бы 1 — е каждое и допустимая полуметрика ру на У', такие что функция Д(-) эквивалентна непрерывной на (У', ру) при почти каждом х € X';

(ш) для любого е > 0 найдутся множества X' С X, У' С У меры хотя бы 1 — е каждое, такие что множество функций вида Д(-) на У' (переменная х пробегает X') образует вполне ограниченное (предкомпактное) метрическое подпространство в Ь^ (У');

(гу) для любого е > 0 найдутся множества X' С X, У' С У меры хотя бы 1 — е каждое, такие что множество функций вида Д(-) на У' (переменная х пробегает X') образует сепарабельное метрическое подпространство в Ь^(У').

Как известно, функция непрерывна, если прообраз любого открытого множества открыт. Виртуальная непрерывность функции двух переменных также может быть характеризована подобным образом. Измеримое множество 2 С X х У называется виртуально открытым, если для некоторых множеств X' С X, У' С У полной меры множество 2 П (X' х У') есть счетное объединение измеримых прямоугольников Кг = Аг х Вг,

г = 1, 2,.... Множество называется виртуально замкнутым, если его дополнение виртуально открыто.

Теорема 13. Измеримая функция (х, у) на X х У собственно виртуально непрерывна если и только если -прообраз любого открытого множества на прямой виртуально открыт.

Измеримые функции f (■, ■), как уже обсуждалось, классифицируются матричными распределениями, т.е. мерами на пространстве бесконечных матриц (ац)^-=1, индуцируемых отображением f ^ (агц = ! (хг ,у])), точки хг в X и уг в У, г = 1, 2,..., выбираются независимо. В этих терминах можно охарактеризовать свойство виртуальной непрерывности:

Теорема 14. Пусть точки х\,х2,..., выбираются случайно и независимо в X, у\,у2,..., случайно и независимо в У. Виртуальная непрерывность функции (х,у) равносильна каждому из двух следующих свойств:

Список литературы диссертационного исследования кандидат наук Петров, Федор Владимирович, 2018 год

Литература

[1] K. G. Jacobi. Theoremata nova algebraica circa systema duarum aequationum inter duas variabiles propositarum. J. Reine Angew. Math. 14 (1835), 281-288.

[2] F. Carlson. Sur une Classe de Series de Taylor, Ph.D. Thesis, Uppsala Univ., 1914.

[3] Л. В. Канторович. О перемещении масс. ДАН СССР 37 (1942), вып. 7-8, 227-229.

[4] A. Selberg. Bemerkninger om et multipelt integral, Norsk Mat. Tidsskr. 26 (1944), 71-78.

[5] J. S. Frame, G. de B. Robinson, and R. M. Thrall. The hook graphs of the symmetric group. Canad. J. Math. 6 (1954), 316325.

[6] P. Scherk. Distinct elements in a set of sums (solution to Problem 4466). American Math. Monthly 62 (1955), no. 1, 4647.

[7] J. H. B. Kemperman. On complexes in a semigroup. Indag. Math. 18 (1956), 247-254.

[8] Л. В. Канторович, Г. Ш. Рубинштейн. Пространство вполне аддитивных функций. Вестник Ленинградского университета 13, вып. 7 (1958), 52-59.

[9] J. H. B. Kemperman. On small sumsets in an abelian group. Acta Math. 103 (1960), 63-88.

[10] F. J. Dyson. Statistical theory of energy levels of complex systems. I, J. Math. Phys. 3 (1962), 140-156.

[11] K. G. Wilson. Proof of a conjecture by Dyson, J. Math. Phys. 3 (1962), 1040-1043.

[12] J. E. Olson. A Combinatorial Problem on Finite Abelian Groups I, Journ. of Numb. Th. 1 (1969), no. 1, 8-10.

[13] I. J. Good. Short proof of a conjecture by Dyson, J. Math. Phys. 11 (1970), 1884.

[14] G. E. Andrews. Problems and prospects for basic hypergeometric functions, in: R.A. Askey (Ed.), Theory and Application of Special Functions, Academic Press (New York, 1975), 191-224.

[15] H. Furstenberg. Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions. J. D'Analyse Math. 31 (1977), 204-256.

[16] W. G. Morris. Constant Term Identities for Finite and Affine Root Systems: Conjectures and Theorems, Ph.D. Thesis, Univ. Wisconsin-Madison, 1982.

[17] H. G. Kellerer. Duality theorems for marginal problems. Z.

Wahrcheinlichkeitstheorie Verw. Geb. 67 (1984), 399-432.

[18] D. Zeilberger, D. M. Bressoud, A proof of Andrews' g-Dyson conjecture, Discrete Math. 54 (1985), 201-224.

[19] E. Kunz, M. Kreuzer. Traces in strict Frobenius algebras and strict complete intersections. J. Reine Angew. Math. 381 (1987), 181-204.

[20] N. Alon, M. Tarsi. Colorings and orientations of graphs. Combinatorica 12 (1992), 125-134.

[21] H. Fleishner, M. Stiebitz. A solution to a colouring problem of P. Erdos. Discrete Mathematics 101 (1992), 39-48.

[22] N. Alon and Z. Furedi. Covering the cube by affine hyperplanes. Eur. J. Comb. 14 (1993), 79-83.

[23] А. Ю. Окуньков, Г. И. Ольшанский. Сдвинутые функции Шура. Алгебра и анализ 9(1997), вып. 2, 73-146.

[24] В. Н. Иванов. Размерность косых сдвинутых диаграмм Юнга и проективные характеры бесконечной симметрической группы. Зап. научн. сем. ПОМИ 240 (1997), 115-135.

[25] A. Okounkov. On Newton Interpolation of Symmetric Functions: A Characterization of Interpolation Macdonald Polynomials. Adv. in Appl. Math. 20 (1998), no. 4, 395-428.

[26] A. Vershik. The universal Urysohn space, Gromov's metric triples, and random metrics on the series of natural numbers, Russian Math. Surveys 53 (1998), no. 5, 921-928.

[27] N. Alon. Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 (1999), 7-29.

[28] M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Birkhauser, Boston, 1999.

[29] A. Vershik. Classification of measurable functions of several variables and invariantly distributed random matrices, Funct. Anal. Appl. 36 (2002), no. 2, 93-105.

[30] G. Olshanski, A. Regev, A. Vershik. Frobenius-Schur Functions, with appendix by V. Ivanov. Studies in Memory of Issai Schur. Vol. 210 (2003), ser. Progress in Mathematics, 251-299.

[31] A. Vershik. Random and universal metric spaces, in: Fundamental Mathematics Today (S. K. Lando and

0. K. Sheinman, eds.), Independent University of Moscow, 2003, 54-88.

[32] A. Vershik. Random metric spaces and universality, Russian Math. Surveys 59 (2004), no. 2, 259-295.

[33] G. Karolyi. The Erdo's-Heilbronn problem in abelian groups. Israel J. Math. 139 (2004), no. 1, 349-359.

[34] V. Lev. Restricted set addition in abelian groups: results and conjectures, J. Th. Nombres. Bordeaux 17 (2005), no. 1, 181193.

[35] J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. Int. J. Number Theory 1 (2005), no.

1, 1-32.

[36] H. Pan, Z.-W. Sun. Restricted sumsets and a conjecture of Lev. Israel J. Math. 154 (2006), no. 1, 21-28.

[37] W. T. Gowers. Hypergraph regularity and the multidimensional Szemeredi theorem. Ann. of Math. 166 (2007), 897-946.

[38] U. Schauz. Algebraically solvable problems: describing polynomials as equivalent to explicit solutions. Electron. J. Combin. 15 (2008) #R10, 35 p.

[39] V. H. Vu. Sum-product estimates via directed expanders. Math. Res. Lett. 15 (2008), no. 2, 375-388.

[40] P. J. Forrester, S. O. Warnaar. The importance of the Selberg integral, Bull. Amer. Math. Soc. (N.S.) 45 (2008), 489-534.

[41] N. Hegyvari, F. Hennecart. Explicit constructions of extractors and expanders. Acta Arith. 140 (2009), 233-249.

[42] A. Postnikov. Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 2009.6 (2009), 1026-1106.

[43] M. Lason. A generalization of Combinatorial Nullstellensatz, Electron. J. Combin. 17 (2010) #N32, 6 pages.

[44] I. D. Shkredov. On monochromatic solutions of some nonlinear equations in Z/pZ. Math. Notes 88 (2010), no. 3-4, 603-611.

[45] S. Janson. Quasi-random graphs and graph limits. Europ. J. Comb. 32 (2011), 1054-1083.

[46] G. Elek, B. Szegedy. A measure-theoretic approach to the theory of dense hypergraphs. Adv. Math. 231 (2012), no. 3-4, 17311772.

[47] L. Lovasz. Large networks and graph limits. Colloquium Publications, Vol. 60. (2012)

[48] L. Lovasz. Coupling measure concentrated on a given set. http://www.cs.elte.hu/ lovasz/book/homnotes-A-3-4b.pdf

[49] А. Вершик. О классификации измеримых функций нескольких переменных. Зап. научн. сем. ПОМИ. 403 (2012), 35-57.

[50] E. Balandraud. An addition theorem and maximal zero-sum free sets in Z/pZ. Israel J. Math. 188 (2012), 405-429. Also Erratum in 192 (2012), 1009-1010.

[51] A. Vershik. Long History of Monge-Kantorovich transportation problem. Mathem. Intellegencer, 35 (2013), no. 4, 1-9.

[52] D. Hart, L. Li and C.-Y. Shen. Fourier analysis and expanding phenomena in finite fields. Proc. Amer. Math. Soc. 141 (2013), 461-473.

[53] D. Ostrovsky. Selberg integral as a meromorphic function. Int. Math. Res. Not. (2013), 3988-4028.

[54] Gy. Karolyi, Z. L. Nagy. A simple proof of the Zeilberger-Bressoud q-Dyson theorem, Proc. Amer. Math. Soc. 142 (2014), no. 6, 3007-3011.

[55] M. Denker, M. Gordin. Limit theorem for von Mises statistics of a measure preserving transformations. Probab. Theory Relat. Fields 160 (2014), 1-45.

[56] М. Ш. Бирман. Простая теорема вложения для ядер интегральных операторов следового класса в L2(Rm). Применение к формуле Фредгольма для следа. Алгебра и Анализ, 27 (2015), вып. 2, 211-217.

[57] T. Tao. Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets.

Contributions to Discrete Mathemtaics 10 (2015), no. 1.

[58] P. L. Clark. Fattening Up Warning's Second Theorem, arXiv:1506.06743.

[59] A. Bishnoi, P. L. Clark, A. Potukuchi, J. R. Schmitt. On Zeros of a Polynomial in a Finite Grid. Combinatorics, Probability and Computing (2018), published online.

[60] T. Amdeberhan. Explicit computations with the divided symmetrization operator. Proc. Amer. Math. Soc. 144 (2016), 2799-2810.

[61] E. Naslund, W. Sawin. Upper Bounds for Sunflower-Free Sets in URL:https://goo.gl/Tc5V6I

[62] R. Kleinberg, W. Sawin, D. Speyer. The Growth Rate of Tri-Colored Sum-Free Sets, arXiv preprint arXiv:1607.00047 (2016).

[63] S. Norin. A distribution on triples with maximum entropy marginal, arXiv preprint arXiv:1608.00243 (2016).

[64] L. Pebody. Proof of a Conjecture of Kleinberg-Sawin-Speyer, arXiv preprint arXiv:1608.05740 (2016).

[65] J. Ellenberg. Sumsets as unions of sumsets of subsets, arXiv preprint arXiv:1612.01929 (2016).

[66] D. Speyer, blog post. URL:https://sbseminar.wordpress.com /2016/07/08/bounds-for-sum-free-sets-in-prime-power-cyclic-groups-three-ways/

[67] S. Janson. Graph limits and hereditary properties. Europ. J. Comb. 52 (2016), part B, 321-337.

[68] E. Croot, V. Lev, and P. Pach. Progression-free sets in ZJ are exponentially small. Ann. of Math. 185 (2017), no. 1, 331-337.

[69] J. Ellenberg, D. Gijswijt. On large subsets of FMra with no three-term arithmetic progression.Ann. of Math. 185 (2017), no. 1, 339-343.

[70] W. Sawin. Bounds for Matchings in Nonabelian Groups. arXiv:1702.00905 (2017).

[71] F. Petrov, A. Vershik. Uncountable Graphs and Invariant Measures on the Set of Universal Countable Graphs. Random Structures and Algorithms, 37 (2010), no. 3, 389-406.

[72] П. Б. Затицкий, Ф. В. Петров. Об исправлении метрик. Зап. научн. сем. ПОМИ 390 (2011), 201-209.

[73] R. N. Karasev, F. V. Petrov. Partitions of nonzero elements of a finite field into pairs, Israel J. Math. 192 (2012), 143-156.

[74] A. M. Vershik, P. B. Zatitskiy, F. V. Petrov. Geometry and dynamics of admissible metrics in measure spaces, Cent. Eur. J. Math. 11 (2013), no. 3, 379-400.

[75] А. М. Вершик, П. Б. Затицкий, Ф. В. Петров. Виртуальная непрерывность измеримых функций многих переменных и ее приложения. Усп. мат. наук 69 (2014), вып. 6, 81-114.

[76] F. Petrov. Combinatorial Nullstellensatz approach to polynomial expansion. Acta Arith. 165 (2014), 279-282.

[77] А. М. Вершик, П. Б. Затицкий, Ф. В. Петров. Интегрирование виртуально непрерывных функций по бистохастиче-ским мерам и формула следа ядерных операторов. Алгебра и Анализ, 27 (2015), вып. 3, 66-74.

[78] G. Karolyi, Z.-L. Nagy, F. V. Petrov, V. Volkov. A new approach to constant term identities and Selberg-type integrals. Adv. Math. 277 (2015), 252-282.

[79] В. В. Волков, Ф. В. Петров. Некоторые обобщения теоремы Коши-Дэвенпорта. Зап. научн. сем. ПОМИ 432 (2015), 105110.

[80] Ф. В. Петров. Исправление непрерывных гиперграфов. Алгебра и Анализ, 28 (2016), вып. 6, 84-90.

[81] F. Petrov. Polynomial approach to explicit formulae for generalized binomial coefficients. Europ. J. of Math. 2 (2016), no. 2, 444-458.

[82] F. Petrov. Restricted product sets under unique representability, Mosc. J. Comb. Numb. Th. 7 (2017), no. 1, 73-78.

[83] F. Petrov. General parity result and cycle-plus-triangles graphs. J. Graph Th. 85 (2017), no. 4, 803-807.

[84] F. Petrov. Combinatorial and Probabilistic Formulae for Divided Symmetrization. Discr. Math. 341 (2018), no. 2, 336340.

[85] F. Petrov. Combinatorial results implied by many zero divisors in a group ring. arXiv:1606.03256 (2016).

ST. PETERSBURG STATE UNIVERSITY ST. PETERSBURG DEPARTMENT of V. A. STEKLOV INSTITUTE of mathematics ras

manuscript

FEDOR PETROV

PROBLEMS OF CONTINUOUS AND POLYNOMIAL COMBINATORICS

01.01.01 - REAL, complex AND FUNCTIONAL ANALYsis

HABILITATION THESIS

SCIENTIFIC CONSULTANT professor A. M. Vershik

ST. PETERSBURG 2018

Contents

Introduction 91

1 Continuous combinatorics 95

1.1 Continuous graphs and hypergraphs. Measures on countable graphs..........................................95

1.2 Correcting continuous hypergraphs....................98

1.3 Metrics ..................................................100

1.4 Virtual continuity: main notions ......................105

1.5 Thickness. Measure and norm on the space of virtually continuous functions................................109

1.6 Virtual continuity and optimal transportation .... 115

1.7 Virtual continuity. Applications........................119

2 Polynomial combinatorics 123

2.1 Combinatorial Nullstellensatz as a formula............123

2.2 Identities for coefficients................................126

2.3 Paths in graded graphs..................................132

2.4 Applications to additive combinatorics................142

2.5 Applications to graph theory..........................147

2.6 Partial symmetrization..................................148

2.7 Group rings..............................................152

Conclusion

159

References

161

Introduction

The thesis is devoted to two intensively developing areas of a modern combinatorial analysis.

In the first part the so called continuous combinatorics is considered. In few words it may be defined as a theory of measurable functions of several variables ("usual", discrete combinatorics corresponds to a finite measure space.) This viewpoint is systematically presented, for example, in a recent book of L. Lovasz [47]. The famous H. Furstenberg's correspondence between additive properties of a cyclic group and ergodic theory [15] also refers to this parallelism. Main works of the first part are based on the A. M. Vershik's approach to studying group actions via the dynamics of functions of several variables, first of all metrics.

The second part relates to applications of the polynomial method in enumerative and additive combinatorics and in graph theory. Also we give several applications of the group rings method, which is suggested to be viewed as a non-commutative (more precisely, not necessarily commutative) analogue of the polynomial method. The main tool is the explicit form of the Combinatorial Nullstellensatz of N. Alon, as well as the ideology of its proof. The method of group rings goes back to the works of J. Olson.

The topics studied in the thesis is included in a wide mathe-

matical context (model theory, functional analysis, ergodic theory, measure theory, transport problem; enumerative combinatorics, Sel-berg integrals , symmetric functions, representation theory, additive combinatorics, group rings, algebraic geometry). They attract a high interest of specialists — some of them are mentioned above; below in the text many more, but not all are also mentioned. This confirms the relevance of the thesis.

I consider the topics of both chapters being developed sufficiently for the defense. A number both of general results and their applications is obtained. Of course, this does not mean in any way that the topics are exhausted, — on the contrary, there remain a number of important questions, few of which are formulated in the conclusion.

The purpose of the work are new concrete mathematical results and the development of general methods, which allow to obtain new results in the future and expand the understanding of things.

Most of the results of the thesis are new, which is confirmed by their publication in peer-reviewed publications. Some results consist of new approaches to the already known theorems, which is also of interest.

The nature of the work is theoretical, its results can be applied — and are already applied — in the mathematical research in the aforementioned areas, as well as in theoretical physics (the latter refers primarily to identities like those of Dyson, Morris, Aomoto, Forrester, arising in quantum electrodynamics.)

The first chapter uses the well-known and new methods of the functional analysis, measure theory, ergodic theory, combinatorics. The second chapter is devoted to the development of the polynomial method in combinatorics and the method of group rings, which is

considered as its generalization. In general, I believe that the developed methods are the main result of the work.

The thesis contains definitions, explanations, historical references, the formulations of auxiliary statements and Theorems from 1 to 46, which are presented to defense.

Thesis results are published in 14 articles in peer-reviewed journals and one preprint. Many talks on international scientific conferences and research seminars based on these results have been given. This confirms their reliability.

The proofs of the theorems are not given in the main text. They are contained in the attached articles [71-85]. The newly defined notions are typed bold.

I am deeply grateful to my teacher Anatoly Moiseevich Vershik for the permanent support and asking so many good questions; to all my coauthors, especially to my younger colleagues Pavel Zatiskiy and Vladislav Volkov, without whom I would do much less; to Danila Cherkashin, who kindly helped to fix a lot of inaccuracies.

Now pass to the presentation of the results.

Chapter 1. Continuous combinatorics

1.1. Continuous graphs and hypergraphs. Measures on

countable graphs.

m-homogeneous hypergraph on the ground set V of vertices is a family of the m-element subsets of V (edges). For m = 2 we say simply graph. If we replace subsets to ordered arrays (v\,...,vm) <E Vm, we get directed hypergraph. Hypergraph is called finite, respectively countable, if so is a vertex set V.

Removing vertices and/or edges from a given hypergraph we get its subgraph. Removing only edges we get a spanning subgraph, removing only vertices we get an induced subgraph.

A homomorphism of a hypergraph G\ on a vertex set V\ to a hypergraph G2 on a set V2 is a map f : V\ ^ V2 which maps edges to edges. A bijective homomorphism is called isomorphism, if an inverse map is homomorphism as well.

If V is a probability space with measure ¡, it looks natural to understand a measurable m-homogeneous hypergraph as a measurable function from the m-th symmetric power of the space (V, ¡) to {0,1} (for directed hypergraphs — from the usual power Vm). It is more convenient to consider symmetric functions on Vm instead of functions on the symmetric power. But actually it appear that often wider class of functions with the values in [0,1] is more suit-

able. The reason is that this class is closed under taking appropriate weak limits.

Measurable functions of several variables with values in a separable metric space are similar to measurable hypergraphs. To any such function f (xi,..., xk) we may assign a measure on finite or countable fc-tensors: choose the points zi,z2,... ^-randomly and take a tensor with coefficient of eil ® ei2 eik equal to f (zil ,...,zik)

(here ei,... is a standard base of the tensor-powered space). For fc = 2 the tensors are canonically isomorphic to matrices and we get a so called matrix distribution of the function f (xi,x2). For two non-isomorphic (in natural sense of isomorphism of functions of two variables) functions f,g their matrix distributions may coincide. Namely, if we have a measurable equivalence relation on V, and the function f (x, y) depends only on the classes of x and y, the matrix distribution of f is the same as that of a factor-function on the factorspace (which may be a standard space again). But this is essentially the only example, that was established for compact metrics by M. L. Gromov [28] and in general case for so called pure functions by A. M. Vershik [29]. The same holds for fc > 2.

Note that for any homogeneous hypergraph p : Vm — [0,1] and any fixed set M we get a measure on the set of hypergraphs on M: for any vertex v £ M choose a point F(v) £ M ^-randomly, and take an edge {vi,..., vm} with probability p(F(vi),..., F(vm)). These events are independent. This measure is obviously defined by the tensor distribution of the function p. The converse is also true, but non-trivial, see Theorem 13.10 in [47] (for fc = 2).

For m = 2, p = p £ (0,1) we get an Erdos-Renyi random graph model. For countable M for any p £ (0,1), with probability 1 a random Erdos-Renyi graph is isomorphic to a universal Rado graph

R. The latter is characterized by the following properties:

U1) Any finite graph is isomorphic to a certain induced subgraph of R;

U2) If two subgraphs induced on finite subsets V\ ,V2 C M are isomorphic by a map f : V\ ^ V2 (such a map is called a partial isomorphism), then f may be extended to an automorphism of the whole graph R.

General "back and force" arguments allow to weaken the condition U2: it suffices to require that for any finite superset V3 D V\ there exists a superset V4 D V2 and an extension of f to a partial isomorphism from V3 to V4. Moreover, it suffices to require this for |Vs \ V!\ = 1.

Let K be a certain class of finite graphs. Consider countable graphs with all induced finite subgraphs belonging to K. A countable graph G is called K-universal, if the following conditions holds:

U1') Any finite graph from K is isomorphic to an induced subgraph of G, and U2.

It is easy to prove that when a K-universal graph exists, it is unique up to isomorphism.

Thus, Rado graph is universal in the class of all graphs and a random Erdos-Renyi graph gives an invariant (under permutations of vertices) probabilistic measure on the set of countable graphs, for which almost any graph is a Rado graph.

An important class of graphs, for which there exists a universal graph, is a class of triangle-free graphs, or, more generally, of Kd-free graphs, where d > 2 is a fixed positive integer. In this case the question of the existence of a Borel (in a natural sense) invariant probability measure on the class of all countable graphs, which

is concentrated on the set of K-universal graphs, was open. This question was solved in [71]. Namely, the following claim holds.

Theorem 1. Assume that d ^ 3 and is a class of finite graphs without cliques on d vertices. There exists a symmetric function p : [0,1]2 ^ {0,1} for which the corresponding measure on countable graphs is concentrated on the set of Kd-universal graphs.

The proof is based on the idea of building not measurable, but topological universal graph — an open subset in R2, satisfying certain conditions (Kd-free and topological analog of universality).

Note that the property that p maps to {0,1}, not just to [0,1], is necessary for the corresponding measure to be concentrated on Kd-universal graphs. This is also proved in [71].

1.2. Correcting continuous hypergraphs

Szemeredi triangle removal lemma is well known:

if a graph on n vertices contains o(n3) triangles, than we may remove o(n2) edges so that all triangles disappear.

A generalization of this lemma to the hypergraphs case includes, in particular, Szemeredi's theorem on arithmetic progressions [37].

A measurable version of the triangle removal lemma is the following claim:

if a measurable symmetric function f (x, y) on [0,1] satisfies the equality

f (x,y)f (y,z)f (z, x) = 0 (1.1)

for almost all x,y,z G [0,1], then f may replaced to an equivalent function (i.e., to a function coinciding with f almost everywhere on [0,1]2) so that condition (1.1) holds for all x,y,z G [0,1].

Note that the discrete lemma may be deduced from a continuous one using ultrafilters limit and a separable factor [46].

For which conditions apart (1.1) an analogous claim holds?

For studying measurable metrics (see further), the following theorem [72] appeared to be useful:

Theorem 2. Assume that a measurable function p(x,y) : [0,1]2 — [0, to) satisfies for almost all x,y,z e [0,1] the equality p(x, y) = p(y, x) and the inequality p(x,y) + p(y,z) ^ p(x,z). Then there exists a function, equivalent to p, satisfying these properties for all x,y,z e [0,1].

In other words, a measurable almost semimetric is equivalent to a measurable semimetric. Note that a naive discrete version does not hold. Namely, consider large finite set X equipped by a function d(x,y) : X x X — [0, to) ("almost metric") satisfying:

(i) d(x, y) = 0 if and only if x = y;

(ii) d(x,y) = d(y,x) for all x,y e X;

(iii) d(x,y) + d(y,z) ^ d(x,z) for all but o(|X|3) triples (x,y,z) e X3.

Do these properties imply that

(iv) d coincides with a semimetric d on X for all but o(|X|2) pairs (x, y) e X2?

The answer is negative, a counterexample is given in [80].

In the same paper a measurable version on hypergraph removal lemma is stated and proved. For formulating it, we need some notations.

Let K be a metric compact space, X be a standard continuous measure space (say, X = [0,1] with Lebesgue measure). Let, further, k be a positive integer and let f (x\,x2,..., xk) : Xk — K be a

measurable (with respect to the Borel sigma-algebra on K) function. Denote by Nk the set of all ordered fc-tuples I = (ii,...,ik) of mutually distinct positive integers. For any such fc-tuple I and any points yi,y2,... in X denote fi (yby2,...) := f (yh ,...,yik). So, f induces a map f from XN to the Tychonoff's compact set KNk, which maps a point (yi,y2,...) £ XN to the function I — fI(yi,y2,...,) on Nk.

Theorem 3. 1. Let M be a fixed closed subset of KNk. Assume that for almost all yi,y2,... in X the value f(yi,y2,...) belongs to M. Then there exists a measurable function g on Xk, equivalent to f, such that g(yi,y2,...) belongs to M for all mutually different yi,y2,... in X.

2. Assume additionally that f is "almost symmetric", i.e.

f (xi,...,xk) = f (xni ,...,xnk) (1.2)

for almost all xi,...,xk in X and any permutation n of the set {1,2,..., fc}. Then there exists a measurable symmetric function g on Xk, equivalent to f, such that g(yi,y2,...) belongs to M for all (not necessarily different) yi,y2,... in X.

A proof of Theorem 3 is based on Lebesgue density theorem, and for p.2 also on Ramsey theorem.

1.3. Metrics

Let (X, ¡j) be a standard probabilistic space. An admissible semi-metric p on X is a measurable function p(x,y) : [0,1]2 — [0, to), satisfying for almost all x,y,z £ [0,1] the equality p(x, y) = p(y, x) and the inequality p(x,y) + p(y,z) ^ p(x,z), such that for almost all points x £ X all balls B(x,R) = {y : p(x,y) 4 R},R > 0,

centered in x have positive measure. A triple (X, ¡, p) is called an admissible semimetric triple.

A studying of metric triples (metric measure spaces) was initiated by M. Gromov [28]. Vershik [26, 31] an alternative view on metric triples was suggested: in contrast to the classical approach, where one fixes a topological space (for instance, a metric compact space) and considers various Borel measures on it, here, on the contrary, one fixes a a-algebra and a measure and varies admissible metrics on this measure space. This approach naturally arises in studying the dynamics of metric under group action.

Theorem 2 allows to think that p is a semimetric on X. Although the choice of such semimetric is not unique, any two equivalent admissible semimetrics coincide on a certain subset X1 c X with full measure.

An admissible metric is an admissible semimetric, which is equivalent to a metric on a set of full measure.

There are several equivalent definitions of admissibility. Before formulating them, we give several definitions.

Essential diameter essdiamp(Xi) of a set X1 D X is an essential supremum of the function p(x,y) on X1 x X1 .A diameter diamp(X1) is, as usual, a supremum of p(x,y) on X1 x X1. Essential diameter, in contrast to diameter, does not change when the function p is replaced to an equivalent function.

Fix a number e <E (0,1). Consider the smallest positive integer k for which X can be represented as the union of sets X0, X1,...,Xk such that ¡(X0) < e and diamp(Xj) < e for j = 1,...,k. The e-entropy of the admissible triple (X, ¡, p) is

H£(p,i) = logk

(the logarithm is binary). If such k does not exist, we set H£(p, j) = то.

A semimetric p defines a Kantorovich semimetric Kp on the space of Borel probability measures on X: the distance between two such measures j1, is defined as a supremum of / f (x)d(j1 — j2), where a varied function f is 1-Lipschitz with respect to semimetric p.

In [74] the following criterion of admissibility is given:

Theorem 4. Let p be a measurable semimetric on (X,j). Then the following conditions are equivalent:

1) The triple (X,j,p) is admissible, i.e., almost all balls have positive measure.

2) There exist a set X1 с X of full measure such that a semi-metric space (X1,p) is separable.

3) The measure j can be approximated in the Kantorovich metric Kp by finitely supported measures.

4) For every e > 0, the semimetric p has a finite e-entropy

5) For every e > 0, the space X can be represented as the union of sets X0,X1,...,Xk such that j(X0) < e and essdiamp(Xj) < e for j = 1,...,k.

6) For every measurable set A of positive measure, the essential infimum of the function p on A x A is zero.

The classification theorem [28, 32] says that a metric triple is determined up to isomorphism by the corresponding distribution of the distance matrices p(xi,xj)i<i,j<n (for all n). Therefore, the

admissibility of a metric must also be expressible in terms of this distribution. Here is a possible criterion.

Theorem 5. 1) If a metric p is not admissible, then there exists c > 0 such that the probability of the following event tends to one as n tends to infinity:

(Pc) there is a set of indices I C {1,2,...,n} of cardinality at least cn such that p(xi, Xj) > c for all distinct i,j G I.

2) If a metric p is admissible, then for every c > 0 the probability of Pc tends to zero.

In both cases, the rate of convergence to 1 or 0 is at least exponential in n.

When working with admissible semimetrics, the following topology is useful. Define an m-norm \\f \\m of a measurable function f (x, y) on X x X as a finite or infinite infimum of the expression fxxx p(x,yW(x)dv(y) taken over all admissible semimetrics p on X which satisfy the inequality \ f (x,y)\ 4 p(x,y) for almost all x,y. The feature of the corresponding distance on cone Adm (X) is that convergence in m-norm allows to control e-entropy, and therefore admissibility: set Adm (X) is m-closed. On the other hand, if a sequence of semimetrics tends in L1 to an admissible semimetric, the convergence automatically takes place in m-norm. In particular, a compactness of a set of admissible semimetrics in L1 norm is equivalent to the compactness of the same set in m-norm. These statements are proved in [74], and the criteria of m-precompactness of a set M C Adm (X) are also given. Here is a precompactness criterion for a convex set:

Theorem 6. A uniformly integrable set M of admissible semimetrics is precompact in m-norm if and only if the e-entropies of semi-

metrics in M are uniformly (with respect to semimetric) bounded for every fixed e > 0.

Note that the criterion may be rephrased for not necessarily convex family of semimetrics, since the set in Banach space is precompact if and only if its convex hull is precompact. That is, m-precompactness of an arbitrary uniformly integrable set M с Adm(X) is equivalent to the uniform boundedness of e-entropies of the convex combinations of semimetrics from M.

In the following important special case we see that not even all convex combinations are necessary for assuring in precompactness.

Theorem 7. Let T be a measure-preserving transform of a standard measure space (X,y) (not necessarily invertible), let p be a summable admissible semimetric. Assume that for any e > 0, e-entropies of semimetrics pn(x,y) := П En-о p(T%x,T%y) are uniformly bounded.. Then the orbit of p under the action of T is m-precompact.

This theorem is a key step in the proof of the following discreteness criterion for the spectrum of an automorphism T of X:

Theorem 8. 1) If the spectrum of an automorphism T is discrete (purely point), then for any e > 0 and any admissible semimetric p, e-entropies of semimetrics pn are uniformly bounded.

2) If there exists at least one metric p such that e-entropies of semimetrics pn are uniformly bounded, then the spectrum of T is discrete.

In this theorem a general phenomenon of independence on the choice of admissible metric arises. The reason is the following observation [75]:

Theorem 9. Let pi and p2 be two admissible metrics on the Lebesgue space (X, ¡). Then for any e > 0 there exists a set K С X, such that ¡(K) > 1 — e and topologies defined by the metrics pi and p2 on K coincide.

The theorem 9 immediately yields Luzin's theorem: a measurable function f on (X, ¡) is continuous with respect to an admissible metric p on a certain set K of measure ¡(K) > 1 — e. For the proof it suffices to consider an admissible metric pi(x,y) = p(x,y) + \f (x) — f (y)|, for which f is, of course, pi-continuous, and apply Theorem 9.

1.4. Virtual continuity: main notions

Let f (■, ■) be a measurable function of two variables. Then Luzin's theorem analogue (continuity on the product X' x Y' of sets of measure > 1 — e with respect to given metric p[(xi,yi), (Х2,У2)] = px(xi,X2)+ pY(yi,y2)) is not in general true. This leads to the following notion.

Measurable function f (■, ■) on the product (X, ¡) x (Y, v) of standard spaces is called properly virtually continuous , if for any e > 0 there exist sets X' С X, Y' С Y each of which having measure at least 1 — e, and admissible semimetrics px, pY on X', Y' respectivelysuch that function f is continuous on (X' x Y', px x pY).

Function which coincides with a properly virtually continuous function on the set of full measure in X x Y is called virtually continuous. Virtually continuous functions of several variables are defined in the same way.

It is essential that admissible metric with respect to which function becomes continuous is not arbitrary, but respects the structure

of direct product (in more general setting, it respects selected subal-gebras). It is easy to verify that there does not exist universal metric of such type (i.e. such a metric that virtual continuity implies continuity in this metric). It explains the non-trivial properties of defined notion.

It is clear that any admissible metric (considered as a function of two variables) is virtually continuous. So is any function, which is continuous with the respect to product of admissible metrics. Degenerated functions (or "finite rank functions") f (x,y) = Y%=i <Pi(x)&(y), where &(•),& (•), i = 1,...n are arbitrary measurable functions, are also virtually continuous. For the proof just use Luzin's theorem for all functions ^i( ), i = 1 ...n, and ■0i(-), i = 1 ...n.

Less trivial examples of virtually continuous functions are given (see further) by functions from some Sobolev spaces and kernels of trace class operators.

An easy example of not virtually continuous measurable function on [0, 1]2 is provided by the characteristic function of the triangle {x > y}. In general, for functions on the square of a compact group depending of the ratio of variables the criterion of virtual continuity is simple:

Proposition 1. Let G be a metrizable compact group, f be a Haar measurable function on G. Then the function F(x,y) := f (xy-1) on G x G is virtually continuous if and only if f is equivalent to a continuous function.

Virtually continuous functions automatically satisfy stronger properties than are required by the definition.

At first, using Theorem 9 we immediately see that metrics may be fixed a priori:

Theorem 10. Let the function f (■, ■) be properly virtually continuous. Then for any admissible semimetrics px,py on X,Y and for any e > 0 there exist sets X' c X,Y' c Y, each of which having measure at least 1 — e, such that the function f is continuous on (X' x Y' ,px x py).

On the other hand choosing metrics in a special way we may force sets X', Y' from the definition to have the full measure:

Theorem 11. Let function f (■, ■) be virtually continuous. Then there exist sets X' c X, Y' c Y of full measure and admissible semimetrics px, py on X', Y' respectively such that f is continuous on (X' x Y', px x py).

It is useful to think about a function of two variables on X x Y as a map from X to the space of functions on Y (i.e. f (x,y) = fx(y)). See details on using this viewpoint for classification of measurable functions in Vershik's paper [49]. Virtual continuity may be expressed in these terms by the following equivalent definition:

Theorem 12. The following properties of a function f (■, ■) are equivalent:

(i) f is virtually continuous;

(ii) for any e > 0 there exist sets X' c X,Y' c Y having measure not less than 1 — e and a semimetric py on Y', so that the function fx(^) is equivalent to a continuous function on (Y', py) for almost all x £ X';

(iii) for anye > 0 there exist sets X' c X, Y' c Y having measure not less then 1 — e such that the set of functions fx() on Y' (where variable x runs over X') is totally bounded (precom-pact) as a metric subspace in L^(Y');

(iv) for any e > 0 there exist sets X' c X, Y' c Y having measure not less then 1 — e such that the set of functions fx(^) on Y' (where variable x runs over X') is separable as a metric subspace in Li(Y').

function is measurable if and only if for any open set its preimage is open. Virtual continuity of a function of two variables admits a similar definition. A measurable set Z c X x Y is called virtually open, if for some subsets X' c X, Y' c Y of full measure the set Z n (X' x Y') is a countable union of measurable rectangles Ri = Ai x Bi, i = 1, 2,.... Set is called virtually closed if its complement is virtually open.

Theorem 13. A measurable function f (x,y) on X x Y is properly virtually continuous if and only if f -preimage of any open set on the real line is virtually open.

Measurable functions f (•, •), as we have seen, are classified by matrix distributions, i. e. by measures on the space of infinite matrices (aij)ij=1, induced by the map f — (aj = f (xi,yj)), where points xi in X and yi in Y, i = 1,2,..., are chosen independently. Virtual continuity also may be characterized on this manner:

Theorem 14. Let x1,x2,... (resp. y1,y2,...) be independent random points in X (resp. in Y). Virtual continuity of the measurable function f (x, y) is equivalent to each of two following conditions:

(i) For any e > 0 there exists a positive integer N such that the probability of the following event tends 1 when n grows: if points xi,..., xn are chosen independently at random in X, y1,...,yn are chosen independently at random in Y, then there

exist partitions {1,...,n} = UN=0Ai = UN=0Bi such that \Ao\ <en, |Bo| <en, \f(xs,yt) — f(xr,yP)| <e n > i,j> 0, s,r £ Ai,p,t £ Bj.

(ii) For any e > 0 there exists a positive integer N, for which the probability of the following event equals 1:

if points xi,x2,... are chosen independently at random in X, y1,y2,... are chosen independently at random in Y, then there exist two partitions of the naturals {1, 2,...,} = UN=0Ai = UN=0Bi, so that upper density of the set A0UB0 is less than e (i.e. limsup |(A0UB0)n [1,n]|/n < e) and \f (xs,yt) — f (xr,yp)| < e for i,j > 0, s,r £ Ai,p,t £ Bj.

For studying virtual continuity it is useful to introduce a topology such that convergence preserves virtual continuity.

1.5. Thickness. Measure and norm on the space of virtually continuous functions

We write Am0d°B if A,B c X x Y and j x v(B \ A) = 0. Also, we write m<d0 or m>d0, if the corresponding inequality holds j x v—almost everywhere.

For a measurable set Z c X x Y define its proper thickness

as

sth(Z) = inf {¡(X )+v (Y): X c X,Y c Y, Z c (X xY) U(X xF)}.

(1.3)

The thickness of a set Z is defined as

th(Z) = inf {^(X)+v (f): X c X,Y c Y, Zm^0(X xY)U(X x f)}. In other words,

th(Z) = min{sth(Z'): ZmocA0Z'}. (1.4)

Minimum in (1.4) is always attained, because we may intersect a minimizing sequence of sets.

The sets X x Y, X x Y are just sets from chosen subalgebras, so we may extend our definition to other choices of selected subalgebras in a standard space.

The following properties of thickness are immediate:

• thickness of a set does not exceed 1 and equals 0 for and only for sets of measure 0;

• thickness of a subset does not exceed a thickness of a set;

• thickness of a set is not less than its measure;

• thickness of a finite or countable union of sets does not exceed sum of thicknesses.

The following lemma is not hard too:

Lemma 1. If a set Z c X x Y is virtually open, then th(Z) = sth(Z).

The following lemma provides an equivalent and sometimes more useful definition of the thickness.

Lemma 2. For any Z c X x Y consider pairs of measurable functions f: X ^ [0,1], g: Y ^ [0,1], for which f (x) + g(y) > xz(x,y) (resp. f (x) + g(y)m>d°Xz(x,y)). Then the proper thickness (resp. thickness) of the set Z is the infimum of fx fdj + Jy gdv. Moreover, this infimum is realized as well as infimum in (1.3).

Using lemma 2 we may establish "continuity of thickness from below":

Lemma 3. Let {Zn} be an increasing sequence of measurable sets, Z = UnZn. Then th(Z) = limth(Zn), sth(Z) = limsth(Zn).

Now we define a convergence of functions "in thickness" analogously to convergence "in measure". This is a convergence in the following metrizable topology: define a distance t(f (■, ),g(■, ■)) between two arbitrary measurable functions as infimum of such e > 0, for which

th({(x,y): \f(x,y) — g(x,y^ > e}) < e.

Convergence in this T-metrics implies convergence in measure (but not vice versa).

Let £x : X = Lin=1 Xi, £y : Y = um=1Yi be finite partitions of the spaces X, Y respectively onto measurable subsets of positive measure. Functions which are constant mod 0 on each product Xix Yj are called step functions. Finite linear combinations Ei=1 ai(x)bi(y) are called functions of finite rank.

The following theorem connects finite rank functions and virtual continuity.

Theorem 15. The t-closure of the set of step functions (or the set of finite rank functions) is exactly the set of virtually continuous functions. In other words, a function f is virtually continuous

on X x Y if and only if for any e > 0 there exist such families of disjoint measurable sets A1,...,An c X, B1,...,Bn c Y, and numbers Cj, 1 < i,j < n, that E j(Aj) > 1 — e^v(B;) > 1 — e, |F(x, y) — Cj| < e for almost all x <E Ai, y <E Bj.

Convergence in r-metric defined above generalizes convergence in measure for virtually continuous functions. There are analogues of known Banach spaces of measurable functions.

A measurable function h(•, •) on the space (X x Y,jx v) is called subbistochastic, if the measure with j x v-density |h(•, •) is sub-bistochastic (that is, the measure of any measurable set Z c X x Y does not exceed the measure of its projection on X, and does not exceed the measure of its projection on Y). Denote by S the set of subbistochastic functions. A signed measure which has a bounded density with respect to some subbistochastic measure is called qua-sibistochastic.

Call a function f (x, y) = a(x) + b(y) separate. The following construction defines a norm (so called regulator norm) of a function of two variables, where regulator is separate function and norm is taken in L1. Define a finite or infinite norm of a measurable function f (•, •) as

Connection between SR1-norm and r-metric is established in the following

\\f\\SRi :=inf{ / a(x)d/(x)+ b(y)dv(y):

•J X J Y

a(x) > 0,b(y) > 0, f (x,yTt0a(x)+ b(y)}.

Y

Lemma 4. For any function f we have r(0, f) <

Corollary. Convergence in SR1-norm implies convergence in t-metric.

Note that for X = Y the SR1 norm is equivalent to m-norm defined earlier for studying admissible metrics. Indeed, each metric p(x,y) is majorized by a sum of one variable functions a(x) + a(y) = p(z,x) + p(z,y), and averaging over z allows to estimate m-norm via SR1-norm. The reverse inequality follows from the fact that |a(x)| + |a(y)| + |b(x)| + |b(y)| is always a semimetric.

Next theorem is an analogue of known L. V. Kantorovich's duality theorem [3] in the mass transportation problem (concretely, of duality between measures space with Kantorovich distance and and the space of Lipschitz functions, see also [51]).

Theorem 16.

\\f llSRi =sup| J \f(x,y)\h(x,y)dj(x)dv(y): h . (1.5)

lx xY )

An SR1 norm allows to construct a Banach space consisting of virtually continuous functions.

Theorem 17. The closure of step functions in SR1 -norm consists exactly of all virtually continuous functions having finite norm (in particular, each bounded virtually continuous function belongs to this closure).

Denote by VC1 the space of all virtually continuous functions with finite SR1-norm. It is an analogue of the space L1 for virtually continuous functions and is a pre-dual for the space of polymorphisms with bounded densities of projections.

Theorem 18. The space dual to VC1 is a space QB^ of quasibis-toshastic signed measures n on X x Y with finite norm

iiniu = maJi|dPXM|| \\dPM II

mqb = max|ll dj IIl^X,^ II dv Wl^(Yv)

where Px and Py are projections onto X and Y respectively and n is a full variation of a signed measure n. A coupling between n G QB^ and f (x,y) G VC1 is defined as f fdn, where f is a properly virtually continuous function equivalent to f (a function f is automatically n-measurable, and the value of integral does not depend on choice of f for fixed f.)

So, virtually continuous functions admit integration against qua-sibistochastic measures, which may be not continuous with respect to the product measure. For example, if X = Y, the diagonal measure is bistochastic, that is, an integral / f (x,x)dj1x is defined for virtually continuous f, where dj1 is any measure with bounded density with respect to dj. For arbitrary measurable functions on Xx X such expressions have no sense.

For applications in the theory of trace class operators [77] we need the following statement on *-weak convergence of polymorphisms to a diagonal measure.

Proposition 2. Let (X,p,j) be a separable metric space with sigma-compact Borel measure j. Let n be a measure on the diagonal diag = {(x,x): x G X} c X x X defined as a push-forward of the measure j under the map x — (x,x). Now assume that a sequence of bistochastic measures nn on X x X is such that nn(K) — 0 for any compact subset K c X2 \ diag. Then a sequence of measures nn converges to the measure n in QB^ = (VC1 )* in *-weak topology.

In other words, for any function f £ VC1 the following convergence holds: fx2 fdr/n ^ fx2 fdnn

It should be noted that the thickness convergence and the space VC1 were introduced (without connection to continuity in admissible metrics) by Kellerer [17].

1.6. Virtual continuity and optimal transportation

We connect Theorem 18 on the space of quasipolymorphisms QB^ which is dual to the space VC1 of virtually continuous functions, and the classical theorem of L. V. Kantorovich on duality in continuous linear transportation problem. Recall it.

Consider a metric space (X, p) 1 and two probabilistic Borel measures j1,j2 on it. The following infimum is to be found:

where QBS™.is a set of measures on X x X with projections (marginal) equal to j1 ,j2 (another name for such measures ^ — polymorphism from (X,j1) into (X, j2), or transportation plan, or coupling, or joining, or Young measure etc.)

Main facts known by general name duality theorem claim the following (we use our terminology):

1) above infimum is attained on some non-negative element of the set QB^ (and is not attained, in general, on the set of absolutely continuous measures like d^ = p(x,y)dj1(x)dj2(y), where p is a measurable summable function);

1in the classical work [3] this space is compact, but we further need only that it is complete separable metric (=Polish) space

2) this infimum may be considered as a norm of a signed measure \\/1 — j2\\ in a certain space of signed Borel measures on the space (X, p) with finite variation. 2

3) there is a dual definition of the norm

where Lip1(p) is a unit ball in Lipschitz functions space with usual Lipschitz norm. Supremum is also realized on some Lipschitz function u0 and we have u(x) — u(y) = p(x, y) -almost everywhere.

Main sense of above claims is that a norm of an element in Banach space may be calculated using a functional from the dual space, and this reduces the problem to finding a dual space.

Above claim is known as duality theorem (or optimality criterion) in the optimal transportation problem and was formulated in the pioneering paper [3]. At fact what is used is that Lipschitz space is Banach dual to the Kantorovich-Rubinstein space. Let us outline that it is a duality theorem for functions of "one variable", and we "cover" it by a duality for functions of two variables.

Below we show how to apply Theorem 18, which is a claim on dual space for the space VC1 of virtually continuous functions, to Kantorovich duality. It is more convenient to tell about transportation between two different spaces (of course, this is equivalent to above problem on the transportation in the same space).

So we get yet another proof of duality theorem, and the main feature is that our scheme includes spaces of metrics and plans, unlike original approach of Kantorovich. Choice of spaces VC1 and

2this observation made in [8] originates a tradition to call this norm the Kantorovich-Rubinstein norm, and metric the Kantorovich metric.

QB™ is natural in the sense that smaller spaces are not enough (see remark above) and admissible metrics are virtually continuous functions.

Two-level duality theorem in our specific situation leads, in turn, to following general two-level duality. We hope that it has another applications. This is why we start with our general statement and later explain how to apply it to optimal transportation.

Theorem 19. Let X be a real vector space ordered by a convex cone K, let Y = X* be a dual space. Denote by W and Z = W* two other linear real spaces. Let A : W ^ X be a linear operator and B = A* : Y ^ Z be a conjugate operator:

W A X X* W*

Fix a positive element p G K c X and define (finite or infinite) quasinorm on Z as follows:

\\z\\p = inf{(y,p) : By = z,y > 0}.

Assume the following condition: the space X is the sum of the cone K and the space A(W). Then

\\z\\P = \\z\\P := sup{(z,u) : Au < p}.

Moreover, if \\z\\p < <x>, then there exist non-negative continuous functional y G X* such that (y,p) = \\z\\p.

Remark. In the case when X is a Banach space and cone K is closed and generating (K — K = X), classical Kakutani theorem says that a non-negative functional y on X is automatically norm bounded on X.

In our situation X = VCx Q2), Y D QB~(^1 x Q2), where (Qi,^i),i = 1,2 are standard probabilistic spaces, W = L1(Qi) © L1(Q2), Z = L~(Qi) © L~(^2), operator A maps a pair of functions u = (w1(t),w2(t)) G W into w1(t1) + w2(t2) := (Au)(t1,t2) G X, restriction of B on QB^ maps quasibistochastic sign measure n into pair of its projections on X, Y:

L1 (Qi) x L1(Q2) Д VC 1(Qi, Q2) QB~(fib Q2) & L^(Q1) x L~(Q2)

A A*

(Wi(x),W2(y)) ^ Wi(x) + W2(y) /Л ^ (Prni^,Prn2/)

Element p(t1,t2) is understood as a price of transporting from t1 G Q1 into t2 G Q2, take element z G Z equal to a pair of constant functions (1,1) (we do not lose a generality: for other functions just change measures /1, /2 onto equivalent). Note that by definition of the space VC1 each function in this space may be represented as a sum of non-negative function and a separate function w1(t1)+w2(t2). Thus condition of Theorem 19 holds. Remark to this theorem (cone of non-negative functions is clearly closed and generating in VC1) guarantees that this functional is norm bounded, hence it corresponds to some polymorphism from QB^. Norm ||(1,1)||p is infi-mum of plan prices of transportation / 1 into / 2 with price function p. So, Theorem 19 implies existence of optimal plan.

If we try to replace VC 1(Q1 x Q2) onto space L1(Q1 x Q2), then both assumption and conclusion of Theorem 19 fail. In this case nonnegative bounded functional corresponds to bounded function (not just to polymorphism), and optimal plan may easily not exist.

1.7. Virtual continuity. Applications

As it have been already noted, virtually continuous functions have well defined traces on certain subsets of measure 0 (for example, on the diagonal). The following theorem connects this fact and the Sobolev traces theorems.

Theorem 20. Let Q1, Q2 be domains of dimensions d1,d2 respectively, suppose that pl > d2 or p = 1 ,l = d2. Then functions from the Sobolev space W,(Q1 xQ2) (l-th generalized derivatives are summable with power p) are virtually continuous as functions of two variables x G Q1, y G Q2. Embedding W,(Q1 x Q2) into VC 1(Q1,K) is continuous for any compact subset K of the domain Q2.

It is well known that the space of nuclear operators in the Hilbert space L2 is a projective tensor product of Hilbert spaces. Their kernels are measurable functions of two variables, which can hardly be described directly. the following theorem claims that kernels of nuclear operators are virtually continuous as functions of two variables. Note that kernels of Hilbert-Schmidt operators are not in general virtually continuous.

Theorem 21. Let (X,y), (Y,v) be standard spaces. the space of kernels of nuclear operators from L2(X) to L2(Y) (with Schatten-von Neumann norm) embeds continuously into VC1.

It implies that such kernels may be integrated not only over diagonal when X = Y, which is well known, but by bistochastic measures. But the space VC1 is wider than kernels of nuclear operators. If we look at VC1 as to the space of kernels of integral operators, it is not unitary invariant, on the contrast to Schatten-von Neumann spaces. indeed, the definition of VC1 essentially uses

known sigma-subalgebras, which do not have necessary invariance. Close question is considered in [55].

Let K £ S1 be a nuclear operator in the Hilbert space L2(X, ¡); and K is its kernel. Define a regular kernel corresponding to the operator K following [56].

A measurable function K0, defined on a square X' x X' of some subset X' d X of full measure is called a regular kernel corresponding to the operator K £ S1 if there exist two Hilbert-Schmidt operators L,M £ S2 with kernels L, M£ L2(X x x,s x ¡) respectively such that K = LM and

for all x,y G X'.

Functions K and clearly coincide a.e. on X x X. Note that in general regular kernel for a nuclear operator is not unique, since there may be different factorizations to two Hilbert-Schmidt operators. But any two regular kernels coincide on a square of a set of full measure. It follows from the fact that a regular kernel K0 of a nuclear operator K is a properly virtually continuous function, and a kernel K is virtually continuous.

Birman interprets integral of the kernel K of the nuclear operator K as integral of regular kernel K0.

Birman suggests to calculate a trace of nuclear operator as a limit of averages over the neighborhood of diagonal. Namely, if (X, j) is Rm with the Lebesgue measure, and K is a regular kernel of a nuclear operator in L2(X, j), then for the integral over diagonal the

(1.6)

following formula holds:

. K,(x,x)d^(x) = lim —1— 11 K,(x,y)d^(x)d^(y), X Kmhm J J

\x-y\<h

where Km is the Lebesgue measure of a unit ball in Rm.

This result immediately follows from Theorem 21 and proposition 2.

As a combinatorial application of Theorem 18 we give a variant of continuous Hall lemma, Borel version of which is given in appendix [48] to the book [47]:

Theorem 22. Let Z C X x Y be virtually closed set. Then two following conditions are equivalent:

(i) There exists a bistochastic measure X such that X(Z) = 1;

(ii) Proper thickness sth(Z) of the set Z equals 1.

It is not hard to deduce a

Corollary. For virtually closed Z we always have maxA(Z) = sth(Z), where maximum is taken over all bistochastic measures A.

Chapter 2. Polynomial combinatorics

2.1. Combinatorial Nullstellensatz as a formula

We start with certain abstract algebraic observations (our exposition follows the lines of [78], a similar view was suggested by Uwe Schauz [38]).

Let V1,..., Vn be vector spaces over the field F. For each i we choose a basis Bi in Vi, then ®Bi is a basis in a tensor product ®Vi. Let Ai C Bj be non-empty subsets, ai £ Ai be chosen vectors and linear functionals ni £ Hom(Vi, F) satisfy the conditions ni(ai) = 1 and ni(b) = 0 for all b £ Ai V^}. The following lemma is obvious

Lemma 5. Assume that the tensor F £ ®Vi satisfies the following condition: if bi £ Bi and the coordinate of F at ®bi does not vanish, then either bi = ai for every i or bi £ Ai \ {ai} for at least one index i. Then the coordinate of F at ®ai equals (®ni)(F).

We will apply this lemma in the following situation:

Vi = F[xi], Bi = {1 ,xi,xi , ... }, Ai = {1,xi,...,xi }, ai = xd .

Moreover we will assume that the value of n £ Hom(Vi, F) at f £ F[xi] is the same as the coefficient of xdi in f if deg(f) < di. A main example of such a functional is provided by Lagrange

interpolation formula. Denote x = xi, d = di, n = Vi, choose a set C c F of the size \C\ = d + 1. For a polynomial f (x) G F[x] denote

V(f ) = E K(C,c)f (c), c e c

where we denote k(C,c) = nxeC\{c}(c — x)_1. Note that the functional n depends on the choice of set C, but its restriction to polynomials of degree at most d always gives a coefficient of xd.

Now F[x1,..., xn], as a vector space over F, can be identified with via the unique isomorphism, which extends the correspondence

x^ ... xn <—> xk1 , ki G {0,1, 2 ... }.

An important feature of this identification is the following.

Lemma 6. Assume that linear functionals §i G Hom(Vi, F) are given in the form §i(f) = f(mi)(ci) for some elements ci G F and non-negative integers mi. Then for any polynomial G G F[x1,.. .,x,n],

Qmi +-----+m„ G

(®tfi)(G) = ^mi gxmn (c1, . ..,cn).

Let F G F[x1, ...,xn]. We say that no monomial majorizes Hxdi in F if every monomial J} xki with a non-zero coefficient in F satisfies either ki = di for every i or ki < di for some i. This is certainly the

case if deg(F) ^ d1 +-----hdn. Such a polynomial F obviously satisfies

the condition in Lemma 5. Lemma 5 and one-dimensional Lagrange interpolation formula lead to the following formula, which expresses a coefficient of a polynomial via its values on the grid direct product of finite sets).

Theorem 23. [Combinatorial Nullstellensatz]

Let F £ F[x1, ...,xn] be a polynomial such that no monomial majorizes M = xdi in F. Let C1, ...,Cn be arbitrary subsets of F such that \Ci\ = di + 1 for every i. Then the coefficient of M in F can be evaluated as

n

[M]F = £ E UK(Ci,Ci)F(c1,c2,...,cn), (2.1)

ci€Ci 02eC2 cneon i=1

where K(Ci,ci) = ceC.\{c.}(ci — c)j . Consequently, if the above coefficient is not zero, then there exists a system of representatives ci £ Ci such that F(c1, c2,..., cn) = 0.

The last corollary is an original Alon's Combinatorial Nullstellensatz [27].

Formula (2.1) have been reinvented recently in several combinatorial papers [38, 43, 73]. The first of them, by Uwe Schauz, contains many interesting generalizations and corollaries.

But from algebraic point of view, (2.1) is just a specialization of the so called Euler-Jacobi formula for full intersections [1] (a grid A x B is a full intersection of the manifolds HaeA(x — a) = 0, Ilfees(y — b) = 0). See a modern exposition and generalizations, for example, in [19]. I have not seen this specialization stated explicitly in algebraic papers, but I am not aware of them so much to make any strong statements.

In some applications we need a Combinatorial Nullstellensatz for multisets. A finite multiset C in a field F is understood as a multiplicity function w : F ^{0,1, 2,...} with finite sum \C \ := e xe f w(x). We denote by supp(C) := {c £ F \ w(c) = 0} the supporting set of C and, with a slight abuse of notation, write c £ C if c £ supp(C).

A finite union of multisets is understood as the sum of the corresponding multiplicity functions. An appropriate generalization of Theorem 23 for multisets can be formulated as follows [78].