Математическая энциклопедия - комбинаторная геометрия

раздел математики, объединяющий круг задач, в к-рых исследуются экстремальные свойства комбинаторного характера для систем фигур. Эти задачи связаны, в первую очередь, с оптимальным в нек-ром смысле расположением выпуклых множеств. Примером одной из старейших задач такого рода может служить задача о 13 шарах: каково максимальное число равных материальных шаров, к-рые можно приложить к равному всем им шару в евклидовом пространстве? И. Кеплер (J. Kepler, 1611) указал число 12, но строгое решение этой задачи было дано в сер. 20 в. Б. Л. Ван дер Варденом (В. L. Van der Waerden) и К. Шютте (К. Schutte).

Термин "К. г.", по-видимому, впервые появился в 1955 (см. [1]). Обычно с этим годом связывают возникновение К. г. как направления в математике, хотя к ней можно отнести и боЛее ранние результаты (см., напр., [2]). Для К. г. характерна наглядность ее задач. В К. г. широко используются комбинаторные соображения и сочетания приемов из различных областей математики (топологии, функционального анализа, геометрии в целом, теории графов и др.).

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

Большую группу задач К. г. составляют . задачи о покрытиях, в к-рых исследуется возможность покрытия заданного множества фигурами специального вида (см., напр., Хадвигера гипотезу о покрытии выпуклого тела минимальным числом меньших гомотетичных ему тел с коэффициентом гомотетии k,0<k<1); освещения задачи о минимальном числе направлений пучков параллельных лучей или источников, освещающих границу выпуклого тела и др.

К. г. родственна дискретной геометрии, см., напр., определенным образом связанную с гипотезой Хадвигера и задачами освещения Эрдёша задачу о нахождении максимального числа точек евклидова пространства Rⁿ, любые три из к-рых образуют треугольник с углами, нe превосходящими p/2.

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

Лит.:[1] Нadwiger Н., "J. reine angew. Math.", 1955, Bd 194, S. 101 10; [2] Alexandrоff P., Hopl H., Topologie, Bd 1, В., 1935; [3] Xадвигер Г., Дебруннер Г., Комбинаторная геометрия плоскости, пер. с нем., М., 1965; [4] Грюнбаум Б., Этюды по комбинаторной геометрии и теории выпуклых тел, пер. с англ., М., 1971; [5] Нadwiger H., Debrunner H., Combinatorial Geometry in the Plane, N. Y., 1964; [6] Яглом И. М., О комбинаторной геометрии, М., 1971; [7] Болтянский В. Г., Солтан П. С, Комбинаторная геометрия различных классов выпуклых множеств, Киш., 1978. П. С. Солтан.

КОМБИНАТОРНАЯ ГЕОМЕТРИЯ конечное множество Sвместе с отношением замыкания определенным для всех подмножеств Аиз S(т. е. влечет и но не обязательно = удовлетворяющим условиям: 1) для пустого множества 2)для каждого элемента 3) если и и если но то (свойство замены). Замкнутые множества, или плоскости образуют геометрическую решетку. Подмножество независимо, если для всех все максимальные независимые множества, или базисы, имеют одинаковую мощность. Обычным образом определяются прямая сумма К. г. и сужение К. г. на подмножество А. Мощность базисов сужения К. г. на Аназ. рангом (А)множества А. Ранг удовлетворяет условию:

Множество для к-рого r(А)<|А|, наз. зависимым; минимальные зависимые множества К. г. наз. циклами. Опуская условия 1) и 2) в определении К. г., получают определение предгеометрии, или матроида. Рассматриваются также бесконечные К. г., при этом требуется конечность базисов.

Пример К. г.подмножество Sвекторного пространства Vс отношением

определенным для всех где sр(A) линейная оболочка, натянутая на Ав V.

Одной из основных проблем в теории К. г. является так наз. критическая проблема. Для К. г., заданной множеством Sв проективном пространстве размерности пнад полем Галуа, эта проблема состоит в том, чтобы найти наименьшее положительное целое число k (критическую экспоненту), для к-рого существует семейство гиперплоскостей H1, ..., Hk, различающих S(семейство гиперплоскостей различает множество S, если для всякого tОSсуществует хотя бы одна гиперплоскость, не содержащая t).

Лит.:[1] Whitney H., "Amer. J. Math.", 1935 V. 57 р. 509-33; [2] Сrаро Н. Н., Rota G. С, On the foundations of combinatorial theory: combinatorial geometries, Camb.L., 1970; [3] Tutte W. Т., Introduction to the theory of matroids, N. Y., 1971; [4] Уилсон Р., Введение в теорию графов, пер. с англ., М., 1977; [5] Рыбников К. А., Введение в комбинаторный анализ, М., 1972.

А. М. Рееякин.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985