Wzajemnie ortogonalne kwadraty łacińskie

W kombinatoryce mówi się , że dwa kwadraty łacińskie tego samego rozmiaru ( rządu ) są ortogonalne , jeśli po nałożeniu uporządkowane sparowane wpisy na pozycjach są różne. Zbiór kwadratów łacińskich, wszystkie tego samego rzędu, których wszystkie pary są ortogonalne, nazywamy zbiorem wzajemnie ortogonalnych kwadratów łacińskich . Ta koncepcja ortogonalności w kombinatoryce jest silnie związana z koncepcją blokowania w statystyce , co gwarantuje, że zmienne niezależne są naprawdę niezależne, bez ukrytych zakłócających korelacji. „Ortogonalny” jest zatem synonimem „niezależnego”, ponieważ znajomość wartości jednej zmiennej nie daje dalszych informacji o prawdopodobnej wartości innej zmiennej.

Przestarzałym terminem określającym parę ortogonalnych kwadratów łacińskich jest kwadrat grecko-łaciński , występujący w starszej literaturze.

Kwadraty grecko-łacińskie

Kwadrat grecko-łaciński lub kwadrat Eulera lub para ortogonalnych kwadratów łacińskich rzędu n nad dwoma zbiorami S i T (które mogą być takie same), z których każdy składa się z n symboli, jest układem komórek n × n , z których każda zawiera uporządkowana para ( s , t ) , gdzie s jest w S i t jest w T , tak, że każdy wiersz i każda kolumna zawiera każdy element S i każdy element T dokładnie raz oraz że żadne dwie komórki nie zawierają tej samej uporządkowanej pary.

Układ współrzędnych s (które można traktować jako znaki łacińskie) i współrzędnych t (znaki greckie) tworzy kwadrat łaciński . Kwadrat grecko-łaciński można zatem rozłożyć na dwa ortogonalne kwadraty łacińskie. Ortogonalność oznacza tutaj, że każda para ( s , t ) z iloczynu kartezjańskiego S × T występuje dokładnie raz.

Ortogonalne kwadraty łacińskie zostały szczegółowo zbadane przez Leonharda Eulera , który przyjął dwa zestawy jako S = { A , B , C , ... }, pierwsze n wielkich liter alfabetu łacińskiego i T = {α , β, γ, ... }, pierwszych n małych liter alfabetu greckiego — stąd nazwa grecko-łacińskiego kwadratu.

Istnienie

Kiedy kwadrat grecko-łaciński jest postrzegany jako para ortogonalnych kwadratów łacińskich, mówi się, że każdy z kwadratów łacińskich ma ortogonalnego mata . W dowolnym kwadracie łacińskim wybór pozycji, po jednej w każdym rzędzie i po jednej w każdej kolumnie, których wpisy są różne, nazywany jest poprzecznym tego kwadratu. Rozważmy jeden symbol w kwadracie grecko-łacińskim. Pozycje zawierające ten symbol muszą znajdować się w różnych rzędach i kolumnach, a ponadto inne symbole w tych pozycjach muszą być różne. Stąd, patrząc jako para kwadratów łacińskich, pozycje zawierające jeden symbol w pierwszym kwadracie odpowiadają poprzecznemu w drugim kwadracie (i odwrotnie).

Dany kwadrat łaciński rzędu n ma ortogonalnego mate wtedy i tylko wtedy, gdy ma n rozłącznych poprzecznych.

Stół Cayleya (bez granic) dowolnej grupy o nieparzystym porządku tworzy kwadrat łaciński, który ma ortogonalnego mata.

Tak więc kwadraty grecko-łacińskie istnieją dla wszystkich porządków nieparzystych, ponieważ istnieją grupy tych rzędów. Mówi się, że takie grecko-łacińskie kwadraty są oparte na grupach .

Euler był w stanie skonstruować grecko-łacińskie kwadraty rzędów, które są wielokrotnościami czterech, i wydawał się być świadomy następującego wyniku.

Żadne grecko-łacińskie kwadraty oparte na grupach nie mogą istnieć, jeśli porządek jest nieparzystą wielokrotnością dwóch (to znaczy równy 4 k + 2 dla pewnej dodatniej liczby całkowitej k ).

Historia

Chociaż ortogonalne kwadraty łacińskie są znane z jego oryginalnego matematycznego podejścia do tematu, są starsze niż Euler. W formie starej układanki z kartami do gry , konstrukcja zestawu 4 x 4 została opublikowana przez Jacquesa Ozanama w 1725 roku. Problemem było wzięcie wszystkich asów, królów, dam i waletów ze standardowej talii kart i ułożenie ich w siatce 4 x 4 w taki sposób, że każdy wiersz i każda kolumna zawierały wszystkie cztery kolory, a także po jednym z każdego nominału. Ten problem ma kilka rozwiązań.

Częstym wariantem tego problemu było ułożenie 16 kart w taki sposób, aby oprócz ograniczeń związanych z rzędami i kolumnami, każda przekątna zawierała wszystkie cztery nominały i wszystkie cztery kolory.

Według Martina Gardnera , który przedstawił ten wariant problemu w swojej kolumnie Mathematical Games z listopada 1959 r., Rouse Ball błędnie podał liczbę różnych rozwiązań na 72 . Ten błąd utrzymywał się przez wiele lat, dopóki Kathleen Ollerenshaw nie znalazła prawidłowej wartości 144 . Każde ze 144 rozwiązań ma osiem odbić i obrotów, co daje w sumie 1152 rozwiązań. Rozwiązania 144 × 8 można podzielić na następujące dwie klasy równoważności :

Rozwiązanie Normalna forma
Rozwiązanie nr 1


A♠ K♥ Q♦ J♣ Q♣ J♦ A♥ K J ♥ Q ♠ K♣ A♦ K♦ A♣ J♠ Q♥
Rozwiązanie nr 2


A♠ K♥ Q♦ J♣ J♦ Q♣ K♠ A♥ K ♣ A♦ J♥ Q♠ Q♥ J♠ A♣ K♦

Dla każdego z dwóch rozwiązań można wyprowadzić rozwiązania 24 × 24 = 576, permutując niezależnie cztery kolory i cztery wartości nominalne. Żadna permutacja nie zamieni tych dwóch rozwiązań na siebie, ponieważ kolory i wartości nominalne są różne.


Problem trzydziestu sześciu oficerów

Uogólnienie układanki 36 oficerów na stopnie od 1 do 8 (szachy) i pułki (kolory) – przypadki 2 i 6 nie mają rozwiązań

Problem podobny do powyższego problemu z kartami krążył w Petersburgu pod koniec XVIII wieku i zgodnie z folklorem Katarzyna Wielka poprosiła Eulera o jego rozwiązanie, ponieważ przebywał on wówczas na jej dworze. Ten problem jest znany jako problem trzydziestu sześciu oficerów i Euler przedstawił go w następujący sposób:

Bardzo ciekawe pytanie, które przez pewien czas wykazywało pomysłowość wielu ludzi, wciągnęło mnie w następujące badania, które wydają się otwierać nowe pole analizy, w szczególności badanie kombinacji. Pytanie obraca się wokół wylosowania 36 oficerów z 6 różnych pułków, tak aby byli ustawieni w kwadracie, tak aby w każdej linii (zarówno poziomej, jak i pionowej) było 6 oficerów różnych stopni i różnych pułków.

Leonharda Eulera

Przypuszczenie i obalenie Eulera

Przerysowanie zamówienia Scientific American z listopada 1959 r. – 10 grecko-łacińskich kwadratów – w pliku SVG najedź kursorem na litery, aby ukryć tło i odwrotnie

Euler nie był w stanie rozwiązać tego problemu, ale w tej pracy zademonstrował metody konstruowania grecko-łacińskich kwadratów, gdzie n jest nieparzyste lub wielokrotnością 4. Zauważając, że nie istnieje rząd dwóch kwadratów i nie będąc w stanie skonstruować rzędu sześciu kwadratów, przypuszczał że żaden nie istnieje dla jakiejkolwiek dziwnie parzystej liczby n ≡ 2 ( mod 4). Nieistnienie rzędu sześciu kwadratów zostało potwierdzone w 1901 roku przez Gastona Tarry'ego poprzez dowód wyczerpania . Jednak hipoteza Eulera opierała się rozwiązaniu aż do późnych lat pięćdziesiątych XX wieku, ale problem doprowadził do ważnych prac w kombinatoryce .

W 1959 roku RC Bose i SS Shrikhande skonstruowali kilka kontrprzykładów (nazwanych spojlerami Eulera ) rzędu 22, używając spostrzeżeń matematycznych. Następnie ET Parker znalazł kontrprzykład zamówienia 10, korzystając z jednogodzinnego wyszukiwania komputera na komputerze wojskowym UNIVAC 1206 podczas pracy w oddziale UNIVAC firmy Remington Rand (był to jeden z najwcześniejszych problemów kombinatoryki rozwiązanych na komputerze cyfrowym ).

W kwietniu 1959 roku Parker, Bose i Shrikhande przedstawili swój artykuł pokazujący, że hipoteza Eulera jest fałszywa dla wszystkich n ≥ 10. Zatem kwadraty grecko-łacińskie istnieją dla wszystkich rzędów n > 1 z wyjątkiem n = 2, 6. W wydaniu z listopada 1959 r. z Scientific American, Martin Gardner opublikował ten wynik. Przednia okładka to obalenie hipotezy Eulera 10 × 10.

Problem trzydziestu sześciu splątanych oficerów

Kwantowe rozwiązanie klasycznie niemożliwego problemu. Jeśli figury szachowe są stanami kwantowymi w superpozycji, to istnieje para ortogonalnych kwantowych kwadratów łacińskich o rozmiarze 6. Względne rozmiary figur szachowych oznaczają udział odpowiednich stanów kwantowych.

Rozszerzenia wzajemnie ortogonalnych kwadratów łacińskich do domeny kwantowej są badane od 2017 roku. W tych projektach zamiast wyjątkowości symboli elementami tablicy są stany kwantowe, które muszą być do siebie ortogonalne w wierszach i kolumnach. W 2021 r. indyjsko-polski zespół fizyków (Rather, Burchardt, Bruzda, Rajchel-Mieldzioć, Lakshminarayan i Życzkowski ) znaleźli tablicę stanów kwantowych, która stanowi przykład wzajemnie ortogonalnych kwantowych kwadratów łacińskich o rozmiarze 6; lub, równoważnie, układ 36 funkcjonariuszy, którzy są uwikłani. Ta konfiguracja rozwiązuje uogólnienie problemu 36 oficerów Eulera, a także zapewnia nowy kwantowy kod wykrywania błędów, pozwalający zakodować 6-poziomowy system w trzy 6-poziomowy system, który poświadcza wystąpienie jednego błędu.

Przykłady wzajemnie ortogonalnych kwadratów łacińskich (MOLS)

Zbiór kwadratów łacińskich tego samego rzędu, w którym każda para kwadratów jest ortogonalna (to znaczy tworzy grecko-łaciński kwadrat) nazywany jest zbiorem wzajemnie ortogonalnych kwadratów łacińskich ( lub parami ortogonalnych kwadratów łacińskich ) i zwykle oznaczany skrótem MOLS lub MOLS( n ) , gdy kolejność jest wyraźna.

Na przykład zestaw MOLS(4) jest określony przez:

I zestaw MOLS(5):

Chociaż możliwe jest przedstawienie MOLS w postaci „złożonej” macierzy, podobnej na przykład do grecko-łacińskich kwadratów,

1,1,1,1 2,2,2,2 3,3,3,3 4,4,4,4 5,5,5,5
2,3,5,4 3,4,1,5 4,5,2,1 5,1,3,2 1,2,4,3
3,5,4,2 4,1,5,3 5,2,1,4 1,3,2,5 2,4,3,1
4,2,3,5 5,3,4,1 1,4,5,2 2,5,1,3 3,1,2,4
5,4,2,3 1,5,3,4 2,1,4,5 3,2,5,1 4,3,1,2

w powyższym przykładzie MOLS (5) bardziej typowe jest zwarte przedstawienie MOLS jako tablicy ortogonalnej (patrz poniżej ).

W dotychczas podanych przykładach MOLS ten sam alfabet (zestaw symboli) był używany dla każdego kwadratu, ale nie jest to konieczne, jak pokazują kwadraty grecko-łacińskie. W rzeczywistości dla każdego kwadratu zestawu MOLS można użyć zupełnie różnych zestawów symboli. Na przykład,

Dowolne dwa elementy tekstu, koloru pierwszego planu, koloru tła i kroju pisma tworzą parę ortogonalnych kwadratów łacińskich:
fiordy szczęka flegma qiviut cynkowy
cynkowy fiordy szczęka flegma qiviut
qiviut cynkowy fiordy szczęka flegma
flegma qiviut cynkowy fiordy szczęka
szczęka flegma qiviut cynkowy fiordy

jest reprezentacją złożonego przykładu MOLS (5) powyżej, w którym cztery MOLS mają odpowiednio następujące alfabety:

Liczba wzajemnie ortogonalnych kwadratów łacińskich

Na właściwość wzajemnej ortogonalności zbioru MOLS nie ma wpływu

  • Permutując rzędy wszystkich kwadratów jednocześnie,
  • Permutowanie kolumn wszystkich kwadratów jednocześnie i
  • Permutowanie wpisów w dowolnym kwadracie, niezależnie.

Korzystając z tych operacji, dowolny zestaw MOLS można przekształcić w postać standardową , co oznacza, że ​​pierwszy wiersz każdego kwadratu jest identyczny i normalnie ułożony w jakimś naturalnym porządku, a jeden kwadrat ma swoją pierwszą kolumnę również w tej kolejności. Przykłady MOLS(4) i MOLS(5) na początku tej sekcji zostały podane w standardowej formie.

Umieszczając zbiór MOLS( n ) w postaci standardowej i badając wpisy w drugim rzędzie i pierwszej kolumnie każdego kwadratu, można zauważyć, że może istnieć nie więcej niż n − 1 kwadratów. Zbiór n − 1 MOLS( n ) nazywamy zbiorem pełnym MOLS . Wiadomo, że kompletne zestawy istnieją, gdy n jest liczbą pierwszą lub potęgą liczby pierwszej (patrz konstrukcja pola skończonego poniżej ). Jednak liczba MOLS, które mogą istnieć dla danego zamówienia n nie jest znany dla ogólnego n i jest obszarem badań w kombinatoryce .

Płaszczyzny rzutowe

Zbiór n − 1 MOLS( n ) jest równoważny skończonej płaszczyźnie afinicznej rzędu n (patrz Sieci poniżej). Ponieważ każda skończona płaszczyzna afiniczna jest jednoznacznie rozciągliwa na skończoną płaszczyznę rzutową tego samego rzędu, równoważność tę można również wyrazić w kategoriach istnienia tych płaszczyzn rzutowych.

Jak wspomniano powyżej, kompletne zestawy MOLS( n ) istnieją, jeśli n jest liczbą pierwszą lub potęgą pierwszą, więc istnieją płaszczyzny rzutowe takich rzędów. Nie wiadomo, czy istnieją skończone płaszczyzny rzutowe o innym rzędzie, a zatem kompletne zestawy MOLS takich rzędów.

Jedynym ogólnym wynikiem dotyczącym nieistnienia skończonych płaszczyzn rzutowych jest twierdzenie Brucka-Rysera , które mówi, że jeśli istnieje płaszczyzna rzutowa rzędu n i n ≡ 1 (mod 4) lub n ≡ 2 (mod 4), to n musi być sumą dwóch (całkowitych) kwadratów. Wyklucza to na przykład płaszczyzny rzutowe rzędów 6 i 14, ale nie gwarantuje istnienia płaszczyzny, gdy n spełnia warunek. W szczególności n = 10 spełnia warunki, ale nie istnieje żadna płaszczyzna rzutowa rzędu 10, jak wykazały bardzo długie poszukiwania komputerowe, co z kolei implikuje, że nie istnieje dziewięć MOLS rzędu 10.

Żadne inne wyniki istnienia nie są znane. Od 2020 r. Najmniejsze zamówienie, dla którego istnienie pełnego zestawu MOLS jest nieokreślone, wynosi zatem 12.

Twierdzenie McNeisha

, że minimalna liczba MOLS( n ) wynosi 2 dla wszystkich n z wyjątkiem n = 2 lub 6, gdzie wynosi 1. Można jednak powiedzieć więcej, a mianowicie:

Twierdzenie MacNeisha : Jeśli to faktoryzacja liczby całkowitej n na potęgi różnych liczb pierwszych wtedy

minimalna liczba MOLS ( n )

Twierdzenie MacNeisha nie daje bardzo dobrej dolnej granicy, na przykład jeśli n ≡ 2 (mod 4), to znaczy, że w rozkładzie na czynniki pierwsze jest jedna 2, twierdzenie daje dolną granicę 1, która jest pokonana, jeśli n > 6. Z drugiej strony daje prawidłową wartość, gdy n jest potęgą liczby pierwszej.

W przypadku ogólnych liczb złożonych liczba MOLS nie jest znana. Kilka pierwszych wartości zaczynających się od n = 2, 3, 4... to 1, 2, 3, 4, 1, 6, 7, 8, ... (sekwencja A001438 w OEIS ).

Najmniejszy przypadek, dla którego nie jest znana dokładna liczba MOLS( n ), to n = 10. Z grecko-łacińskiej konstrukcji kwadratowej musi być co najmniej dwa, a z nieistnienia płaszczyzny rzutowej rzędu 10 jest jest mniej niż dziewięć. Jednak nigdy nie znaleziono żadnego zestawu trzech MOLS (10), mimo że wielu badaczy próbowało odkryć taki zestaw.

Dla wystarczająco dużych n liczba MOLS jest większa niż , więc dla każdego k istnieje tylko skończona liczba n taka, że ​​liczba MOLS jest k . Co więcej, minimum to 6 dla wszystkich n > 90.

Skończona konstrukcja pola

Pełny zestaw MOLS( q ) istnieje zawsze, gdy q jest liczbą pierwszą lub potęgą pierwszą. Wynika to z konstrukcji opartej na skończonym polu GF ( q ), które istnieje tylko wtedy, gdy q jest liczbą pierwszą lub potęgą pierwszą. Grupa multiplikatywna GF ( q ) jest grupą cykliczną , a więc ma generator λ, co oznacza, że ​​wszystkie niezerowe elementy pola można wyrazić jako odrębne potęgi λ. Nazwij q elementy GF ( q ) w następujący sposób:

0 α = 0, α 1 = 1, α 2 = λ, α 3 = λ 2 , ..., α q -1 = λ q -2 .

Teraz λ q -1 = 1, a reguła iloczynu w odniesieniu do α to α i α j = α t , gdzie t = i + j -1 (mod q -1). Kwadraty łacińskie są zbudowane w następujący sposób: ( i, j )-ty wpis w kwadracie łacińskim L r (gdzie r ≠ 0) to L r ( i,j ) = α i + α r α j , gdzie wszystkie operacje występują w GF ( q ). W przypadku, gdy pole jest polem pierwszym ( q = p a prime), w którym elementy pola są reprezentowane w zwykły sposób, jako liczby całkowite modulo p , powyższa konwencja nazewnictwa może zostać porzucona, a reguła konstrukcyjna może zostać uproszczona do L r ( i,j ) = i + rj , gdzie r ≠ 0 oraz i , j oraz r są elementami GF ( p ) i wszystkie operacje są w GF ( p ). Powyższe przykłady MOLS (4) i MOLS (5) powstały z tej konstrukcji, chociaż ze zmianą alfabetu.

Nie wszystkie kompletne zestawy MOLS wynikają z tej konstrukcji. Płaszczyzna rzutowa, która jest powiązana z pełnym zestawem MOLS uzyskanym z tej konstrukcji pola, jest specjalnym typem, płaszczyzną rzutową Desarguesa . Istnieją niedesarguezowskie płaszczyzny rzutowe , a odpowiadających im kompletnych zestawów MOLS nie można uzyskać ze skończonych pól.

Tablica ortogonalna

Tablica ortogonalna , OA( k,n ), o sile dwa i indeksie jeden, jest tablicą n 2 × k A ( k 2 i n ≥ 1, liczby całkowite) z wpisami ze zbioru o rozmiarze n takim, że w dowolnych dwóch kolumnach A ( siła ), każda uporządkowana para symboli pojawia się dokładnie w jednym rzędzie A ( indeks ) .

OA( s + 2, n ) jest równoważne z s MOLS ( n ). Na przykład przykład MOLS(4) podany powyżej i powtórzony tutaj,

można użyć do utworzenia OA (5,4):

R C L 1 L 2 L 3
1 1 1 1 1
1 2 2 2 2
1 3 3 3 3
1 4 4 4 4
2 1 2 4 3
2 2 1 3 4
2 3 4 2 1
2 4 3 1 2
3 1 3 2 4
3 2 4 1 3
3 3 1 4 2
3 4 2 3 1
4 1 4 3 2
4 2 3 4 1
4 3 2 1 4
4 4 1 2 3

gdzie wpisy w kolumnach oznaczonych r i c oznaczają wiersz i kolumnę pozycji w kwadracie, a pozostała część wiersza dla stałych wartości r i c jest wypełniona wpisem na tej pozycji w każdym z kwadratów łacińskich. Ten proces jest odwracalny; biorąc pod uwagę OA( s , n ) z s ≥ 3, wybierz dowolne dwie kolumny, aby odgrywały role r i c , a następnie wypełnij łacińskie kwadraty wpisami z pozostałych kolumn.

Bardziej ogólne tablice ortogonalne reprezentują uogólnienia koncepcji MOLS, takie jak wzajemnie ortogonalne kostki łacińskie.

Sieci

A (geometryczna) ( k,n )-net jest zbiorem n 2 elementów zwanych punktami i zbiorem kn podzbiorów zwanych liniami lub blokami, każdy o rozmiarze n , z tą właściwością, że dwie różne proste przecinają się co najwyżej w jednym punkcie. Ponadto proste można podzielić na k równoległych klas (nie spotykają się żadne dwie jego proste), z których każda zawiera n prostych.

An ( n + 1, n )-net jest płaszczyzną afiniczną rzędu n .

Zbiór k MOLS( n ) jest równoważny a ( k + 2, n )-netto.

Aby skonstruować a ( k + 2, n )-net z k MOLS ( n ), przedstaw MOLS jako tablicę ortogonalną OA ( k + 2, n ) (patrz wyżej ). Uporządkowane pary wpisów w każdym rzędzie tablicy ortogonalnej w kolumnach oznaczonych r i c będą uważane za współrzędne n 2 punktów sieci. Każda inna kolumna (czyli kwadrat łaciński) zostanie użyta do zdefiniowania linii w klasie równoległej. rz _ linie wyznaczone przez kolumnę oznaczoną L i będą oznaczane przez l ij . Punkty na l ij będą punktami o współrzędnych odpowiadających wierszom, w których wpis w kolumnie Li to j . Istnieją dwie dodatkowe klasy równoległe, odpowiadające r i c . Linie r j i c j składają się z punktów, których pierwsze współrzędne to j , lub drugie współrzędne to j odpowiednio. Ta konstrukcja jest odwracalna.

Na przykład OA(5,4) w powyższej sekcji można użyć do skonstruowania sieci (5,4) (płaszczyzna afiniczna rzędu 4). Punkty na każdej linii są podane przez (każdy wiersz poniżej to równoległa klasa linii):

11 : _ (1,1) (2,2) (3,3) (4,4) 12 : _ (1,2) (2,1) (3,4) (4,3) 13 : _ (1,3) (2,4) (3,1) (4,2) 14 : _ (1,4) (2,3) (3,2) (4,1)
l 21 : (1,1) (2,4) (3,2) (4,3) 22 : _ (1,2) (2,3) (3,1) (4,4) 23 : _ (1,3) (2,2) (3,4) (4,1) 24 : _ (1,4) (2,1) (3,3) (4,2)
31 : _ (1,1) (2,3) (3,4) (4,2) 32 : _ (1,2) (2,4) (3,3) (4,1) 33 : _ (1,3) (2,1) (3,2) (4,4) 34 : _ (1,4) (2,2) (3,1) (4,3)
r 1 : (1,1) (1,2) (1,3) (1,4) r 2 : (2,1) (2,2) (2,3) (2,4) r 3 : (3,1) (3,2) (3,3) (3,4) r 4 : (4,1) (4,2) (4,3) (4,4)
do 1 : (1,1) (2,1) (3,1) (4,1) do 2 : (1,2) (2,2) (3,2) (4,2) do 3 : (1,3) (2,3) (3,3) (4,3) do 4 : (1,4) (2,4) (3,4) (4,4)

Projekty poprzeczne

Projekt poprzeczny z k grupami o rozmiarze n i indeksie λ, oznaczony T [ k , λ; n ], jest trójką ( X, G, B ) gdzie:

  • X to zbiór kn odmian;
  • G = { G 1 , G 2 , ..., G k } jest rodziną kn -zbiorów (nazywanych grupami , ale nie w sensie algebraicznym), które tworzą podział X ;
  • B jest rodziną k -zbiorów (zwanych blokami ) rozmaitości takich, że każdy k -zbiór w B przecina każdą grupę G i w dokładnie jednej rozmaitości, a każda para rozmaitości należących do różnych grup występuje razem w dokładnie λ blokach w B .

Istnienie T[ k ,1; n ] projekt jest równoważny z istnieniem k -2 MOLS( n ).

Projekt poprzeczny T[ k ,1; n ] jest strukturą o podwójnym incydencie an ( k, n )-net. Oznacza to, że ma nk punktów i n 2 bloków. Każdy punkt jest w n blokach; każdy blok zawiera k punktów. Punkty dzielą się na k klas (grup) równoważności o rozmiarze n , tak że dwa punkty z tej samej grupy nie należą do bloku, podczas gdy dwa punkty z różnych grup należą dokładnie do jednego bloku.

Na przykład, używając (5,4)-net z poprzedniej sekcji, możemy skonstruować plan poprzeczny T[5,1;4]. Blok związany z punktem ( i, j ) sieci będzie oznaczony jako bij . Punkty obliczeń otrzymamy z następującego schematu: r i i , c j ↔ 5 j , oraz l ij ↔ 5 i + j . Punkty projektu są zatem oznaczone liczbami całkowitymi 1, ..., 20. Bloki projektu to:

b 11 : 6 11 16 1 5 b 22 : 6 13 19 2 10 b 33 : 6 14 17 3 15 b 44 : 6 12 18 4 20
b 12 : 7 12 17 1 10 b 21 : 7 14 18 2 5 b 34 : 7 13 16 3 20 b 43 : 7 11 19 4 15
b 13 : 8 13 18 1 15 b 24 : 8 11 17 2 20 b 31 : 8 12 19 3 5 b 42 : 8 14 16 4 10
b 14 : 9 14 19 1 20 b 23 : 9 12 16 2 15 b 32 : 9 11 18 3 10 b 41 : 9 13 17 4 5

Pięć „grup” to:

6 7 8 9
11 12 13 14
16 17 18 19
1 2 3 4
5 10 15 20

Teoria grafów

Zbiór k MOLS( n ) jest równoważny podziałowi brzegowemu pełnego ( k + 2)-częściowego grafu K n ,..., n na pełne podgrafy rzędu k + 2.

Aplikacje

Wzajemnie ortogonalne kwadraty łacińskie mają wiele zastosowań. Są one używane jako punkt wyjścia do konstrukcji w statystycznym projektowaniu eksperymentów , planowaniu turniejów oraz poprawianiu błędów i wykrywaniu kodów . Zainteresowanie Eulera kwadratami grecko-łacińskimi wynikało z jego chęci konstruowania magicznych kwadratów . Francuski pisarz Georges Perec zbudował swoją powieść Life: A User's Manual z 1978 roku wokół grecko-łacińskiego kwadratu 10 × 10.

Zobacz też

Notatki

Linki zewnętrzne