Блокирующий набор

В геометрии , в частности, в проективной геометрии , блокирующий набор - это набор точек на проективной плоскости, которые пересекаются каждой прямой и которые не содержат целую линию. Эту концепцию можно обобщить по-разному. Вместо того, чтобы говорить о точках и линиях, можно было бы иметь дело с n -мерными подпространствами и m -мерными подпространствами, или, в более общем смысле, с объектами типа 1 и объектами типа 2, когда некоторая концепция пересечения имеет смысл для этих объектов. Второй способ обобщения - это перейти к более абстрактным параметрам, чем проективная геометрия. Блокирующее множество гиперграфа можно определить как множество, которое встречает все ребра гиперграфа.

Определение

В конечной проективной плоскости π порядка n блокирующее множество - это набор точек из π, которые пересекаются каждой прямой и которые полностью не содержат прямой. Согласно этому определению, если B - блокирующее множество, то дополнительный набор точек, π \ B также является блокирующим множеством. Блокирующее множество B является минимальным, если удаление любой точки B оставляет множество, которое не является блокирующим множеством. Блокирующий набор наименьшего размера называется комитетом . Каждый комитет представляет собой минимальный блокирующий набор, но не все минимальные блокирующие наборы являются комитетами. Блокирующие множества существуют во всех проективных плоскостях, кроме наименьшей проективной плоскости порядка 2, плоскости Фано.. ^[1]

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

Примеры

В любой проективной плоскости порядка n (каждая прямая содержит n + 1 точку) точки на прямых, образующих треугольник без вершин треугольника (3 ( n - 1) точки), образуют минимальное блокирующее множество (если n = 2 этот блокирующий набор тривиален), который, как правило, не является комитетом.

Другая общая конструкция в произвольной проективной плоскости порядка n состоит в том, чтобы взять все, кроме одной точки, скажем P , на данной прямой, а затем по одной точке на каждой из других прямых, проходящих через P , убедившись, что эти точки не все коллинеарны (это последнее условие не может быть выполнено, если n = 2.) Это дает минимальный блокирующий набор размера 2 n .

Проективное треугольника β на боковые м в PG (2, д ) состоит из 3 ( м - 1) точек, м на каждой стороне треугольника, таким образом, что вершины , B и C треугольника находятся в р, и выполняется следующее условие: если точка P на прямой AB и точка Q на прямой BC находятся в β, то точка пересечения PQ и AC находится в β.

Проективные триады δ бокового м представляет собой набор 3 м - 2 балла, м которых лежат на каждом из трех параллельных линий таким образом, что точка параллелизма C находится в б , и выполняется следующее условие: Если точка Р на одном прямых и точка Q на другой прямой лежат в δ, то точка пересечения PQ с третьей прямой находится в δ.

Теорема : В PG (2, q ) с нечетным q существует проективный треугольник со стороной ( q + 3) / 2, который является блокирующим множеством размера 3 ( q + 1) / 2. ^[2]

Используя однородные координаты , пусть вершины треугольника равны A = (1,0,0), B = (0,1,0) и C = (0,0,1). Точки, кроме вершин, на стороне AB имеют координаты вида (- c , 1, 0), точки на BC имеют координаты (0,1, a ), а точки на AC имеют координаты (1,0, b ) где a , b и c - элементы конечного поля GF ( q ). Три точки, по одной на каждой из этих сторон, коллинеарны тогда и только тогда, когда a = bc. Выбирая все точки, где a , b и c являются ненулевыми квадратами GF ( q ), условие определения проективного треугольника выполняется.

Теорема : в PG (2, q ) с четным q существует проективная триада стороны ( q + 2) / 2, которая является блокирующим множеством размера (3 q + 2) / 2. ^[3]

Конструкция аналогична описанной выше, но поскольку поле имеет характеристику 2 , квадраты и неквадраты должны быть заменены элементами абсолютного следа 0 и абсолютного следа 1. В частности, пусть C = (0,0,1). Точки на прямой X = 0 имеют координаты вида (0,1, a ), а точки на прямой Y = 0 имеют координаты вида (1,0, b ). Точки прямой X = Y имеют координаты, которые можно записать как (1,1, c ). Три точки, по одной на каждой из этих прямых, коллинеарны тогда и только тогда, когда a = b + c. Выбирая все точки на этих линиях, где a , b и c - элементы поля с абсолютным следом 0, условие определения проективной триады выполняется.

Теорема : в PG (2, p ), где p - простое число, существует проективная триада стороны ( p + 1) / 2, которая является блокирующим множеством размера (3 p + 1) / 2. ^[4]

Размер

Обычно ищут небольшие блоки блокировки. Называется минимальный размер блокирующего набора .${\ displaystyle H}$${\ Displaystyle \ тау (Н)}$

В дезарговой проективной плоскости порядка q , PG (2, q ), размер блокирующего множества B ограничен: ^[5]

${\ displaystyle q + {\ sqrt {q}} + 1 \ leq | B | \ leq q ^ {2} - {\ sqrt {q}}.}$

Когда q - квадрат, нижняя граница достигается любой подплоскостью Бэра, а верхняя граница получается дополнением подплоскости Бэра.

Можно доказать более общий результат ^[6].

Любое блокирующее множество на проективной плоскости π порядка n имеет не менее точек. Более того, если эта нижняя граница соблюдается, то n обязательно является квадратом, а блокирующее множество состоит из точек некоторой подплоскости Бэра в π.${\ displaystyle n + {\ sqrt {n}} + 1}$

Верхняя граница размера минимального блокирующего множества имеет тот же вкус ^[7].

Любое минимальное блокирующее множество на проективной плоскости π порядка n имеет не более чем точки. Более того, если эта верхняя граница достигается, то n обязательно является квадратом, а блокирующее множество состоит из точек некоторой единицы, вложенной в π.${\ displaystyle n {\ sqrt {n}} + 1}$

Когда n не равно квадрату, можно сказать меньше о нетривиальных блокирующих наборах наименьшего размера. Один хорошо известный результат Аарта Блокхейса: ^[8]

Теорема : Нетривиальное блокирующее множество в PG (2, p ), p простое, имеет размер не менее 3 ( p + 1) / 2.

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

История

Блокирующие множества возникли ^[9] в контексте экономической теории игр в статье Мозеса Ричардсона 1956 года. ^[10] Игроки отождествлялись с точками на конечной проективной плоскости, а минимальные выигрышные коалиции - с линиями. Блокировании коалиция была определена как набор точек , не содержащих линии , но пересекающихся каждую строку. В 1958 г. Исбелл ^[11] изучил эти игры с негеометрической точки зрения. Джейн В. ДиПаола изучала минимальные блокирующие коалиции во всех проективных плоскостях порядка в 1969 году ^[12].${\ displaystyle \ leq 9}$

В гиперграфах

Позвольте быть гиперграфом, так что это набор элементов и является набором подмножеств , называемых (гипер) ребрами. Блокирующий набор является подмножество из который имеет непустое пересечение с каждым гиперребро.${\ Displaystyle H = (X, E)}$${\ displaystyle X}$${\ displaystyle E}$${\ displaystyle X}$${\ displaystyle H}$${\displaystyle S}$${\displaystyle X}$

Блокирующие множества иногда также называют « множеством попаданий » или « вершинными покрытиями ». Кроме того, термин « трансверсально » используются, но в некоторых контекстах трансверсалий является подмножество в том , что каждый отвечает гиперребро ровно в одной точке.${\displaystyle H}$${\displaystyle T}$${\displaystyle X}$

А « два-раскраски » из разбиение на на два подмножества (цветовые классы) таких , что ни одно ребро не является монохроматическим, т.е., ни одно ребро не содержится полностью в пределах или в пределах . Теперь оба и являются блокирующими наборами.${\displaystyle H}$${\displaystyle \{C,D\}}$${\displaystyle X}$${\displaystyle C}$${\displaystyle D}$${\displaystyle C}$${\displaystyle D}$

Полные k-дуги

В проективной плоскости полная к -arc представляет собой набор K точек, никаких три коллинеарно , которые не могут быть распространены на большую дугу (таким образом, каждая точка не на дуге не находится на секущую линии дуги встречи линии дуга в двух точках.)

Теорема : Пусть K - полная k -дуга в = PG (2, q ) с k < q + 2. Двойственное в множество секущих прямых K является блокирующим множеством B размера k ( k - 1) / 2. ^[13]

Блокирующие наборы Rédei

В любой проективной плоскости порядка q для любого нетривиального блокирующего множества B (с b = | B |, размер блокирующего множества) рассмотрим прямую, пересекающую B в n точках. Так как ни одна строка не содержится в B , должна быть точка, P , на этой линии , которая не находится в B . В Q другие линии , хотя Р каждый из них должен содержать по крайней мере одну точку B , с тем , чтобы быть блокирован. Таким образом, если для некоторой строки в этом отношении выполняется равенство, блокирующий набор называется блокирующим набором типа Редеи, а линия - линией Редеи.${\displaystyle b\geq n+q.}$блокирующего множества (обратите внимание, что n будет наибольшим количеством коллинеарных точек в B ). ^[14] Не все блокирующие множества относятся к типу Редеи, но многие из более мелких. Эти множества названы в честь Ласло Редеи, чья монография о лакунарных полиномах над конечными полями оказала влияние на изучение этих множеств. ^[15]

Наборы аффинных блокировок

Множество точек в конечном дезарговом аффинном пространстве, которое нетривиально пересекает каждую гиперплоскость, т. Е. Каждая гиперплоскость инцидентна некоторой точке этого множества, называется аффинным блокирующим множеством. Определите пространство с помощью фиксации системы координат. Тогда легко показать, что множество точек, лежащих на осях координат, образуют блокирующий набор размеров . Жан Дуайен на конференции в Обервольфахе в 1976 году предположил, что это наименьший возможный размер блокирующего множества. Это было доказано Р. Е. Джемисоном в 1977 г. ^[16] и независимо А. Е. Брауэром , А. Шрайвером в 1978 г. ^[17] с использованием так называемого полиномиального метода${\displaystyle AG(n,q)}$${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle 1+n(q-1)}$. Джемисон доказал следующий общий результат о покрытии, из которого следует оценка аффинных блокирующих множеств с использованием двойственности:

Позвольте быть размерным векторным пространством над . Тогда количество -мерных смежных классов, необходимых для покрытия всех векторов, кроме нулевого вектора, будет не менее . Более того, эта оценка точна.${\displaystyle V}$${\displaystyle n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle k}$${\displaystyle q^{n-k}-1+k(q-1)}$

Примечания

использованная литература

• Барвик, Сьюзен; Эберт, Гэри (2008), Униталы в проективных плоскостях , Нью-Йорк: Спрингер, DOI : 10.1007 / 978-0-387-76366-8 , ISBN 978-0-387-76364-4, ISSN  1439-7382
• К. Берге , Графы и гиперграфы, Северная Голландия, Амстердам, 1973 г. (Определения ).${\displaystyle \tau (H)}$
• П. Дюше, Гиперграфы, Глава 7 в: Справочник по комбинаторике, Северная Голландия, Амстердам, 1995.
• Хиршфельд, JWP (1979), Проективные геометрии над конечными полями , Оксфорд: Oxford University Press, ISBN 978-0-19-853526-3
• Холдер, Линн Д. (2001), Блокирующие множества коник, доктор философии. дипломная работа , Колорадский университет в Денвере
• Де Бёль, Ян; Сторм, Лео (2011), Текущие темы исследований в геометрии Галуа , Nova Science Publishers, ISBN 978-1-61209-523-3, заархивировано из оригинала 29 января 2016 г. , извлечено 23 января 2016 г.