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

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

Определение

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

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

Примеры

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

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

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

Проективная триада δ стороны m — это набор из 3 m — 2 точек, m из которых лежат на каждой из трех совпадающих прямых, таких, что точка совмещения C находится в δ и выполняется следующее условие: если точка P на одной прямых и точка 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]

Размер

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

Блокировочные наборы Redei

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

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

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

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

Примечания

^ Хиршфельд 1979 , с. 366
^ Хиршфельд 1979 , с. 376, Теорема 13.4.1.
^ Хиршфельд 1979 , с. 377, Теорема 13.4.2.
^ Jump up to: ^а ^б Блокхуис, Аарт (1994), «О размере блокирующего множества в PG(2,p)», Combinatorica , 14 : 111–114, doi : 10.1007/bf01305953
^ Хиршфельд 1979 , с. 376, Теорема 13.3.3.
^ Барвик и Эберт 2008 , с. 30, теорема 2.15.
^ Барвик и Эберт 2008 , с. 30, теорема 2.16.
^ Холдер 2001 , с. 45
^ Ричардсон, Моисей (1956), «О конечных проективных играх», Труды Американского математического общества , 7 (3): 458–465, doi : 10.2307/2032754 , JSTOR 2032754
^ Исбелл, младший (1958), «Класс простых игр», Duke Mathematical Journal , 25 (3): 425–436, doi : 10.1215/s0012-7094-58-02537-7
^ ДиПаола, Джейн В. (1969), «О минимальных блокирующих коалициях в играх на малых проективных плоскостях», SIAM Journal on Applied Mathematics , 17 (2): 378–392, doi : 10.1137/0117036
^ Хиршфельд 1979 , с. 366, Теорема 13.1.2.
^ Сёньи, Тамаш (1997), «Блокирующие множества в дезарговых аффинных и проективных плоскостях», Конечные поля и их приложения , 3 (3): 187–202, doi : 10.1006/ffta.1996.0176
^ Сёньи, Тамаш (1999), «Вокруг теоремы Редеи», Discrete Mathematics , 208/209: 557–575, doi : 10.1016/s0012-365x(99)00097-7
^ Джеймисон, Роберт Э. (1977), «Покрытие конечных полей смежными классами подпространств», Журнал комбинаторной теории , серия A, 22 (3): 253–266, doi : 10.1016/0097-3165(77)90001-2
^ Брауэр, Андриес; Шрийвер, Александр (1978), «Блокирующее число аффинного пространства», Журнал комбинаторной теории , серия A, 24 (2): 251–253, doi : 10.1016/0097-3165(78)90013-4

Ссылки

Барвик, Сьюзен; Эберт, Гэри (2008), Юнитали в проективных плоскостях , Нью-Йорк: Springer, doi : 10.1007/978-0-387-76366-8 , ISBN 978-0-387-76364-4 , ISSN 1439-7382
К. Берге , Графы и гиперграфы, Северная Голландия, Амстердам, 1973. (Определяет $\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 г.

[1] Хиршфельд 1979 , с. 366

[2] Хиршфельд 1979 , с. 376, Теорема 13.4.1.

[3] Хиршфельд 1979 , с. 377, Теорема 13.4.2.

[Blokhuis1994-4] Jump up to: ^а ^б Блокхуис, Аарт (1994), «О размере блокирующего множества в PG(2,p)», Combinatorica , 14 : 111–114, doi : 10.1007/bf01305953

[5] Хиршфельд 1979 , с. 376, Теорема 13.3.3.

[6] Барвик и Эберт 2008 , с. 30, теорема 2.15.

[7] Барвик и Эберт 2008 , с. 30, теорема 2.16.

[8] Холдер 2001 , с. 45

[9] Ричардсон, Моисей (1956), «О конечных проективных играх», Труды Американского математического общества , 7 (3): 458–465, doi : 10.2307/2032754 , JSTOR 2032754

[10] Исбелл, младший (1958), «Класс простых игр», Duke Mathematical Journal , 25 (3): 425–436, doi : 10.1215/s0012-7094-58-02537-7

[11] ДиПаола, Джейн В. (1969), «О минимальных блокирующих коалициях в играх на малых проективных плоскостях», SIAM Journal on Applied Mathematics , 17 (2): 378–392, doi : 10.1137/0117036

[12] Хиршфельд 1979 , с. 366, Теорема 13.1.2.

[13] Сёньи, Тамаш (1997), «Блокирующие множества в дезарговых аффинных и проективных плоскостях», Конечные поля и их приложения , 3 (3): 187–202, doi : 10.1006/ffta.1996.0176

[14] Сёньи, Тамаш (1999), «Вокруг теоремы Редеи», Discrete Mathematics , 208/209: 557–575, doi : 10.1016/s0012-365x(99)00097-7

[15] Джеймисон, Роберт Э. (1977), «Покрытие конечных полей смежными классами подпространств», Журнал комбинаторной теории , серия A, 22 (3): 253–266, doi : 10.1016/0097-3165(77)90001-2

[16] Брауэр, Андриес; Шрийвер, Александр (1978), «Блокирующее число аффинного пространства», Журнал комбинаторной теории , серия A, 24 (2): 251–253, doi : 10.1016/0097-3165(78)90013-4

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]