Оглавление
- 1 Неравенство Гротендика
- 1.1 Неравенство Гротендика
- 1.2 Мотивация и формулировка оператора
- 1.3 Вычисление нормы расхода
- 1.4 Неравенство Гротендика
- 1.5 Ограничения на константы
- 1.6 Приложения
- 1.7 Неравенство Гротендика для полуопределенных программ
- 1.8 Лемма Семереди о регулярности
- 1.9 Неравенство Гротендика для графов
- 1.10 Неравенство L^p Гротендика
- 1.11 Неравенство Пизье–Рингроуза
- 1.12 Формула Стирлинга
- 1.13 Применение неравенства
- 1.14 Рекомендации и внешние ссылки
- 1.15 Полный текст статьи:
- 2 Неравенство Гротендика
Неравенство Гротендика
-
Неравенство Гротендика
- Существует универсальная постоянная K_G, такая что для всех n × n матриц и векторов в единичном шаре, K_G не зависит от n.
- Для фиксированного гильбертова пространства размерности d, наименьшая постоянная K_G(d) называется постоянной Гротендика.
-
Мотивация и формулировка оператора
- Оператор A определяет линейный оператор между нормированными пространствами.
- Норма расхода A определяется как максимум x ∈ Rn: ‖x‖p = 1 ‖Ax‖q.
- Для p = q, норма обозначается как ‖A‖p.
-
Вычисление нормы расхода
- Норма расхода ‖A‖∞→1 может быть вычислена через квадратичную целочисленную программу.
- Программа может быть преобразована в полуопределенную программу.
-
Неравенство Гротендика
- Неравенство Гротендика утверждает, что существует фиксированная константа C, такая что для любого m, n и матрицы A, максимум x(i), y(i) ∈ H единичные векторы ∑i,jAij⟨x(i),y(j)⟩H ≤ C‖A‖∞→1.
-
Ограничения на константы
- Последовательности K_G(d) увеличиваются, но ограничены.
- Гротендик доказал, что 1.57 ≤ K_G ≤ 2.3.
- Кривин улучшил результат до 1.7822, но гипотеза была опровергнута.
-
Приложения
- Оценка нормы сокращения важна для разработки эффективных алгоритмов аппроксимации плотных графов и матриц.
- Неравенство Гротендика используется для аппроксимации нормы среза матрицы.
- Алгоритм аппроксимации использует полуопределенное программирование.
-
Неравенство Гротендика для полуопределенных программ
- Неравенство Гротендика утверждает, что оптимальное решение полуопределенной программы (СДП) приближается к норме сокращения матрицы.
- Неравенство позволяет оценить точность решения СДП с помощью полиномиального времени.
-
Лемма Семереди о регулярности
- Лемма Семереди утверждает, что любой граф можно разбить на контролируемое количество частей, взаимодействующих псевдослучайным образом.
- Неравенство Гротендика используется для создания разбиения множества вершин, удовлетворяющего лемме Семереди.
-
Неравенство Гротендика для графов
- Неравенство Гротендика для графа утверждает, что для каждого графа существует универсальная константа K, такая, что каждая матрица удовлетворяет определенному неравенству.
- Постоянная Гротендика графа K(G) определяется как наименьшая константа, удовлетворяющая этому неравенству.
-
Неравенство L^p Гротендика
- Неравенство L^p Гротендика обобщает неравенство Гротендика на выпуклые тела, отличные от единичного куба.
- Неравенство позволяет оценить точность оптимального решения СДП для выпуклых тел.
-
Неравенство Пизье–Рингроуза
- Неравенство связывает сумму произведений элементов матрицы на векторы с суммой квадратов модулей векторов.
- Неравенство утверждает, что сумма произведений элементов матрицы на векторы не может быть больше, чем произведение суммы квадратов модулей векторов на константу.
-
Формула Стирлинга
- Формула Стирлинга связывает константу γp с параметром p.
- Константа γp определяется как γp = 2(Γ((p+1)/2)π)1/p.
- Формула Стирлинга утверждает, что γp2 = p/e + O(1) при p → ∞.
-
Применение неравенства
- Неравенство используется в различных областях, таких как оптимизация и анализ данных.
- Оно помогает оценить сложность задач и найти оптимальные решения.
-
Рекомендации и внешние ссылки
- В статье упоминаются рекомендации и внешние ссылки для дальнейшего изучения.
- Приводится примечание о неточности исторической части статьи.