Новый тип блок-дизайна

Tatjana Piontkovskaja

НОВЫЙ ТИП БЛОК-ДИЗАЙНА

ВВЕДЕНИЕ

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

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

Сперва, мы даем формальное определение - дизайна. Пусть S – множество , и пусть T состоит из k элементов подмножества S и . Мы называем элементы множества S объектами или точками и элементы из T блоками или прямыми.

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

Мы выделим два типа примеров "естественных" -дизайнов.

Тип 1. Пусть P – проективное пространство размерности n над конечным полем K. Пусть r – фиксированное натуральное число, такое что . Пусть S – множество всех r-мерных подпространств в P и пусть T – множество всех -мерных подпространства в P, это понимаем так, что точки -мерного подпространства из P являются r мерными подпространствами, содержавшимися в P. Потребуем, чтобы . Пусть является числом таких блоков из T, которые содержат некоторое r подпространство из P. Для любых двух r-подпространств (то есть, двух элементов из S), наименьшее, содержащее их обоих подпространство является размерным. Следовательно, любые два элемента из S лежат в блоках, где зависит только от размерности содержащего их подпространства. Такой дизайн имеет тип . Эти дизайны имеют высокую степень симметрии, так как каждая коллинеация пространства P вызывает автоморфизм дизайна. Эти дизайны не будут далее изучены в этой статье. Однако, это построение приводит к следующей теореме:

Теорема 1.1. Пусть m – фиксированное натуральное число. Тогда существует бесконечно много -дизайнов с .

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

Тип 2. Этот пример построил Bose [1]. Jungnickel в теореме 4.1 дает для аффинной геометрии более общий результат.

Пусть P – проективное пространство размерности n. Удалите одну линию и точки на ней, чтобы получить аффинную плоскость, которая является - дизайном. Теперь удалите любую точку и прямые через эту точку так, чтобы получить -дизайн. В этом дизайне, число точек на всех прямых одного параллельного класса равно . Осталось точка. Эти точки образуют максимальное множество точек, никакие две из которых не лежат на одной прямой. Теперь мы определяем две точки “параллельными”, если они не лежат вместе ни на одной прямой, такие точки формируют максимальный параллельный класс. Фактически, все точки дизайна разделяются на n параллельные классы. Мы отмечаем полную двойственность между параллельными классами точек и параллельными классами прямых. Такой дизайн называют двойственной аффинной плоскостью. Этот дизайн является основным примером для типа дизайнов, которые будут изучены.

ПОСТРОЕНИЯ РАЗНОСТНОГО МНОЖЕСТВА

Пусть v – некоторое фиксированное натуральное число. Пусть S – последовательность k различных целых чисел , которые являются наименьшими неотрицательными остатками по модулю v. Порядок их расположения не важен, поэтому мы считаем, что . Мультимножество разностей, связанное с множеством S состоит из остатков , где и .

Определение 2.1. Пусть является последовательностью k различных остатков по модулю v. Мы говорим, что-разностное множество, если

(1) Для любого существует точно упорядоченных пар , , таких, что .

(2) Для любого существует хотя бы один такой, что существует точно упорядоченных пар , , удовлетворяющих условию .

Пусть является разностным множеством. Мы построим -дизайн следующим образом. За точки дизайна берем числа 0, 1, …, v – 1 и блоками дизайна являются , где блок состоит из k точек по модулю v. Пусть будет числом остатков по модулю v, которые появляются раз как разность по модулю v. Тогда,

(1)

и

(2)

Если разность, появляется раз, то точки i и j находятся на блоках и блоки и пересекаются в точках. Это так, потому что каждое появление как разность соответствует некоторому блоку, который содержит точки i и j и еще одну точку, которая содержится в пересечении блоков и . Поэтому, мы имеем:

Теорема 2.1. Пусть является разностным -множеством и – множества: , где . Если и , то следующие три утверждения эквивалентны:

(1) появляется раз как разность элементов множества S;

(2) и имеют общих чисел точек;

(3) точки i и j появляются вместе в блоках.

Дизайн, построенный выше называется –дизайном, произведенным разностным -множеством S, и S называют основным множеством этого дизайна.

Из этого также следует, что для является корреляцией этого дизайна.

Следствие 2.1. Для разностного -множества выполняется для r = 1; 2; ...; m.

Доказательство. Два множества и не могут иметь больше чем k общих объектов. Значит, утверждение верно в виду Теоремы 2.1. o

Определение 2.2. Два дизайна и называются изоморфными, если существует взаимнооднозначное отображение объектов и блоков на объекты и блоки из , удовлетворяющее следующему условию: если - объект в блоке из , то

объект из ,

блок из ,

Тогда тогда и только тогда, когда

Определение 2.3. Два разностных множества S и T называют изоморфными, если они производят изоморфные дизайны. И обозначим .

Теорема 2.2. Если является разностным -множеством, то , где а положительное целое число, тоже является разностным множеством.

Доказательство. Эта теорема следует из факта что, при мы имеем , тогда и только тогда, когда , где являются целыми числами. o

Определение 2.4. Согласно Теореме 2.2, разностное множество T в Теореме 2.2 называется кратным S.

Теорема 2.3. Если является множеством различий , тогда

,

где a, b –целые числа и является также множетвом различий, и .

Доказательство. Первый результат может быть получен из факта, что при мы имеем , тогда и только тогда, когда , где являются целыми числами. Легко показать . o

Эта теорема, обычно рассматривает только случай .

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

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

Один подход к построениям дизанов состоял бы в том, чтобы построить дизайн с фиксированным числом основанный на множествах различий.

В литературе нет никакого исследования дизайнов или множеств различий со значениями три и больше. О дизайнах с двумя значениями есть немного информации относительно -дизайнов под названием около множеств различия (near difference sets). Другие примеры множеств различий или значений с двумя значениями также появляются в литературе. Один такой пример - квадратные остатки в , где . Есть важные классы дизайнов с двумя значениями, которые не появляются в литературе. Один такой класс примеров выходит от понятия строго регулярного графа. Пусть G строго регулярный граф со следующими параметрами. Число вершин графа равно v; каждая вершина имеет степень k; каждая смежная пара вершин смежна с другими вершинами; и каждая несмежная пара вершин смежна с другими вершинами. Если вершины G помечены , тогда к вершине i берется как блок множество всех вершин, смежных с i, где . Тогда блоки являются блоки -дизайна. Эти дизайны представляют много интереса, но не изучены в этой статье с тех пор, вообще, они не основаны на множествах различий на циклических группах. В дальнейшем, мы определим понятие – эквивалентность, которая является главным инструментом, используемым в этой статье. Этот инструмент используется, чтобы проанализировать наши дизайны. Однако, эквивалентность поставляет полезную информацию только для дизайнов, построенных из множеств различий на циклических группах.

Хороший пример -дизайна, основанные на множествее различий, заключается в следующем. Пусть m и n различные положительные целые числа каждый больше или равный 2. Представьте элементы , где группа целых чисел по модулю n, пары . Постройте граф с этими парами вершин и и являются смежными, если и или и . Дизайн сформирован, взяв как блок все вершины, смежные с фиксированной вершиной. Такой дизайн имеет параметры , где и Секунда такой дизайн получен, взяв как блок вершину со смежной вершиной . Для этого дизайна и . Важный специальный случай то, когда m и n являются относительно простыми. В этом случае, мы можем рассмотреть точки дизайна как элементы , где элементы mapped в элементы mapping производитель к 1. В этом случае, первый дизайн имеет как основное множество , примыкая к 0 к этому множеству приводит к основному множеству для второго дизайна. Мы обсудим больше на этом примере позже в этой статье.

ТЕОРЕМЫ НЕСУЩЕСТВОВАНИЯ

Определение 3.1. Пусть является множеством из k отличный остатков по модулю v. Мы говорим, что D является множеством различий, если какое-нибудь различие появляется или 0 раз.

Пример 3.1. – с 2-множеством различия, так как мультимножество различий

и и такие образом.

Теорема 3.1. Если является -множеством различий, тогда , где а положительное целое число, является также -множеством различий.

Доказательство. Эта теорема следует из факта что, когда , мы имеем , тогда и только тогда, когда , где являются целыми числами. ¨

Определение 3.2. Согласно теореме 3.1, множество различий T в Теореме 3.1 называется кратным множеству S.

Теорема 3.2. Если является разностным -множеством, тогда , где a, b – целые числа и является также разностным -множеством, и T является изоморфизмом к S.

Доказательство. Эта теорема может быть получена из факта, когда , мы имеем , тогда и только тогда, когда , где являются целыми числами. ¨

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

Пример 3.2. и являются разностными 2-множествами.

Из в Примере 3.1, по теореме 3.2, пусть a = 3 и b = 0, мы получаем . Из , пусть a = 2 и b = 0, мы получаем .

Пример 3.3. является разностными 2-множествами.

Из , по теореме 3.2, пусть a = –1 и b = 2, мы получаем .

Заключение 3.1. Если является разностным -множествоми, тогда также является разностным -множеством.

Доказательство. По теоремой 3.2, пусть a = –1 и b = 0, мы получаем, что

Является разностным -множеством. ¨

Пример 3.4. является разностными 2-множествами.

По Заключению 3.1 на T1, мы получаем T4.

Теорема 3.3. Для k = 4, upto кратное число и изоморфизм, есть только одно разностное 2-множество, которые являются как показано в Примере 3.1.

Доказательство. Пусть является разностным 2-множеством. По заключению 3.1, мы можем предположить, что , где – наибольшее целое число, которое не больше чем . С тех пор есть difference a из , второе difference a из или . Это приводит к пяти случаям:

Случай I. Если второе difference a из , тогда очевидно это невозможно, с тех пор во-первых, и во вторых, , так как .

Случай II. Если второе difference a из , тогда, начиная , мы имеем и 2-множества различий должны быть . Мультимножество его различий является

Второе difference b могло быть из, или , и это приводит к трем подслучаям:

(1) Это будет из . Тогда начиная с мы имеем . Из этого следует, что , который противоречит .

(2) Это будет из . Если , тогда , что означает a больше двух раз в мультимножестве различий, и таким образом это приводит к противоречию. Если , тогда . Таким образом, также a появляется больше двух раз в мультимножестве различий, что является невозможным.

(3) Это будет из . Если , тогда . Мы имеем . Теперь, рассматривая остающееся различие , мы имеем или . Для прежнего, мы получаем . Таким образом ; невозможно. Для последнего, мы имеем . Так и . Поэтому, , которое является кратным к .

Случай III. Если второе difference a будет от , то подобно случаю II, мы можем доказать, что , которое является кратным к .

Случай IV. Если второе difference a будет от , то мы можем доказать, что это приводит к , которре является кратным к .

Случай V. Если второе difference a будет от , то легко показать, что это вызывает противоречие.

Это заканчивает наше доказательство. ¨

Так как в Примере 3.1 не допускает никакого остатка отличного от нуля как различие, это не -множество различий. Мы имеем:

Заключение 3.2. Там не существует никакого -множества различий , если .

Точно так же, но более легко, мы можем доказать:

Теорема 3.4. Там не существует никакой - множества различий , если .

ПОНЯТИЕ - ЭКВИВАЛЕНТНОСТИ

Определение 4.1. -множество различий S называют - множеством различий, если для каждого , есть точно остатков отличные от нуля, появляющиеся точно раз в мультимножестве различий S. -дизайн, построенный из - множества различий называют - дизайном. - множество различий определен, как множество различий с . - дизайн может быть определен подобным образом.

Вообще в -дизайне, если i и j находятся вместе в блоках и j и k находятся вместе в блоках, это не верно, т. к. i и k находятся также вместе в блоках, где . Например, рассмотрите -дизайн, построенный из множества различий . Точки 0 и 4 находятся вместе в 0 блоках, и 4 и 8 находятся вместе в 0 блоках, но 0 и 8 - оба в блоке [5].

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