Συνδυαστικός σχεδιασμός

Η Συνδυαστική θεωρία του σχεδιασμού είναι το μέρος της συνδυαστικής των μαθηματικών που ασχολείται με την ύπαρξη, την κατασκευή και τις ιδιότητες πεπερασμένων συνόλων που ικανοποιούν κάποιες γενικευμένες έννοιες ισορροπίας και/ή συμμετρίας. Οι έννοιες αυτές δεν γίνονται ακριβείς, έτσι ώστε ένα ευρύ φάσμα μαθηματικών αντικειμένων να μπορεί να θεωρηθεί μέλος της ίδιας ευρύτερης οικογένειας. Μερικές φορές αυτό μπορεί να περιλαμβάνει αριθμητικά μεγέθη που σχετίζονται με τομές συνόλων, όπως στον σχεδιασμό των block, ενώ άλλες φορές την διάταξη των στοιχείων ενός πίνακα, όπως γίνεται στα sudoku.

Η συνδυαστική θεωρία του σχεδιασμού μπορεί να εφαρμοστεί στον σχεδιασμό πειραμάτων. Εξάλλου, ένα τμήμα της στοιχειώδους θεωρίας συνδιαστικού σχεδιασμού προέρχεται από τις εργασίες του στατιστικολόγου Ronald Fisher σχετικά με το σχεδιασμό βιολογικών πειραμάτων. Σύγχρονες εφαρμογές βρίσκονται σε ένα ευρύ φάσμα τομέων, συμπεριλαμβανομένων: της πεπερασμένης γεωμετρίας, του προγραμματισμού των τουρνουά, των λαχείων, της μαθηματικής βιολογίας, των αλγορίθμων σχεδιασμού και ανάλυσης, της δικτύωσης, του group testing και της κρυπτογραφίας.

Ένα παράδειγμα

Το προβολικό επίπεδο του Fano

Δοθέντος ενός πλήθους $n$ ανθρώπων, είναι δυνατόν να τους χωρίσετε σε ομάδες έτσι ώστε κάθε άτομο να ανήκει τουλάχιστον σε μια ομάδα, κάθε ζευγάρι ατόμων είναι μαζί σε ακριβώς μια ομάδα, κάθε δύο ομάδες να έχουν ακριβώς ένα κοινό άτομο, και καμμία ομάδα να μην τους περιέχει όλους ή όλους εκτός από ένα άτομο ή ένα άτομο μόνο του; Η απάντηση εξαρτάται από το $n$.

Το εν λόγω πρόβλημα έχει λύση μόνο αν το $n$ παίρνει τη μορφή $q^{2}+q+1$, για κάποιον φυσικό αριθμό $q$. Είναι λιγότερο απλό κανείς να δείξει ότι υπάρχει λύση αν το $q$ είναι δύναμη πρώτου και εικάζεται ότι οι προηγούμενες περιπτώσεις είναι οι μοναδικές λύσεις του προβλήματος. Επιπλέον έχει δειχθεί ότι, αν υπάρχει λύση όπου το $q$ είναι ισοϋπόλοιπο με $1$ ή $2\mod 4$, τότε το $q$ είναι άθροισμα δύο τέλειων τετραγώνων. Το τελευταίο αποτέλεσμα, το οποίο ανομάζεται θεώρημα των Bruck–Ryser, αποδεικνύεται με έναν συνδυασμό κατασκευαστικών μεθόδων που βασίζονται σε πεπερασμένα σώματα και σε μια εφαρμογή των τετραγωνικών μορφών.

Όταν μια τέτοια δομή υπάρχει, καλείται πεπερασμένο προβολικό επίπεδο. Αυτό είναι ένα παράδειγμα του πώς η πεπερασμένη γεωμετρία και η συνδυαστική σχετίζονται. Όταν το $q$ είναι $2$, το πεπερασμένο προβολικό επίπεδο ονομάζεται προβολικό επίπεδο του Fano.

Ιστορία

Η συνδυαστική σχεδίαση χρησιμοποιειται από την αρχαιότητα, με το τετράγωνο του Lo Shu να αποτελεί το πρώτο γνωστό παράδειγμα. Μια άλλη εφαρμογή, μάλιστα από τις παλαιότερες γνωστές εφαρμογές, βρέθηκε στην Ινδία, στο βιβλίο Brhat Samhita από τον Varahamira, το οποίο χρονολογείται περίπου το 587 μ.Χ. Στο βιβλίο περιγράφεται η παρασκευή αρωμάτων τα οποία κατασκευάζονται από τέσσερα υλικά, που έχουν επιλεγεί από δεκαέξι χρησιμοποιώντας ένα μαγικό τετράγωνο.

Η συνδιαστική σχεδίαση αναπτύχθηκε περαιτέρω μαζί με τη συνδιαστική του 18ο αιώνα. Παράδειγμα αποτελόυν τα λατινικά τετράγωνα (18ος) και τα συστήματα Steiner (19ος). Ο σχεδιασμός είναι επίσης δημοφιλής σε αναγεννησιακά μαθηματικά, όπως στο πρόβλημα της μαθήτριας Crickman (1850), και σε πρακτικά προβλήματα, όπως ο προγραμματισμός του τουρνουά round-robin (η λύση δημοσιεύθηκε τη δεκαετία του 1880). Στον 20ο αιώνα ο σχεδιασμός χρησιμοποιήθηκε για τον σχεδιασμό πειραμάτων, ευρέως στα λατινικά τετράγωνα, στην πεπερασμένη γεωμετρία, και στα association schemes, γεννώντας κατά μία έννοια το πεδίο της αλγεβρικής στατιστικής.

Θεμελιώδης συνδυαστικός σχεδιασμός

Το κύριο κομμάτι του συνδυαστικού σχεδίασμού έχει δομηθεί στα balanced incomplete block designs (BIBD), στους πίνακες Hadamard και στα σχέδια Hadamard, στα συμμετρικά BIBD, στα λατινικά τετράγωνα, στα resolvable BIBD, στα σύνολα διαφορών, και στα pairwise balanced designs (PBD). Άλλοι συνδυαστικοί σχεδιάσμοί σχετίζονται με τη μελέτη των προαναφερθέντων, ή έχουν προκύψει από τη μελέτη αυτών.

• Ένα balanced incomplete block design ή BIBD (συνήθως ονομάζεται για συντομία απλώς block design) είναι μια συλλογή $B$ με $b$ στο πλήθος υποσύνολα (που ονομάζονται block) ενός πεπερασμένου συνόλου $X$ με $\nu$ στοιχεία, τέτοια ώστε κάθε στοιχείο του $X$ περιέχεται σε ακριβώς $r$ block, κάθε block έχει τον ίδιο αριθμό $k$ στοιχείων, και κάθε δύο διακεκριμένα στοιχεία εμφανίζονται μαζί σε ίδιο πλήθος $\lambda$ block. Τα BIBD είναι επίσης γνωστά ως $2-$σχέδια και συχνά συμβολίζονται ως $2-(\nu ,k,\lambda )$. Ένα παράδειγμα αποτελεί το εξής: όταν $\lambda =1$ και $b=\nu$, έχουμε την περίπτωση ενός προβολικού επιπέδου. Το $X$ αποτελεί το σύνολο των σημείων του επιπέδου και τα block είναι οι ευθείες του.
• Ένα symmetric balanced incomplete block design ή SBIBD είναι ένα BIBD όπου $\nu =b$ (δηλαδή ο αριθμός των σημείων ισούται με τον πλήθος των block). Είναι η πιο σημαντική και ευρέως μελετημένη υποκατηγορία των BIBD. Τα προβολικά επίπεδα, τα διεπίπεδα (biplanes) και τα $2-$σχέδια Hadamard είναι όλα τους SBIBD. Έχουν ιδιαίτερο ενδιαφέρον, αφού αποτελούν 'ακραία' παράδειγμα στα οποία η ανισότητα Fisher ($b\geqslant \nu$) γίνεται ισότητα.
• Ένα resolvable BIBD είναι ένα BIBD του οποίου τα block μπορούν να χωριστούν σε σύνολα (που ονομάζονται παράλληλες τάξεις), καθένα εκ των οποίων αποτελεί μια διαμέριση του συνόλου των σημείων του BIBD. Το σύνολο των παράλληλων τάξεων ονομάζεται resοlution του σχεδιασμού. Μια λύση του διάσημου προβλήματος των 15 μαθητριών είναι ένα resolution ενός BIBD με $\nu =15$, $k=3$ και $\lambda =1$.
• Ένα λατινικό ορθογώνιο είναι ένας πίνακας $r\times n$, με $r\leqslant n$, που έχει τους αριθμούς $1,2,\cdots ,n$ ως στοιχεία του (ή οποιαδήποτε άλλα $n$ διακριτά σύμβολα) χωρίς επαναλήψεις στοιχείων σε οποιαδήποτε γραμμή ή στήλη. Ένα $n\times n$ λατινικό ορθογώνιο λέγεται λατινικό τετράγωνο. Αν $r<n$, τότε είναι δυνατόν να προσαρτήσετε $n-r$ σειρές σε ένα $r\times n$ λατινικό ορθογώνιο και να σχηματίσετε ένα λατινικό τετράγωνο, χρησιμοποιώντας επίσης το θεώρημα του γάμου. Δύο λατινικά τετράγωνα τάξης $n$ λέγεται ότι είναι ορθογώνια αν το σύνολο όλων των διατεταγμένων ζευγών που αποτελούνται από τα αντίστοιχα στοιχεία των δύο τετραγώνων, έχει $n^{2}$ διακεκριμένα μέλη (προκύπτουν δηλαδή όλα τα πιθανά διατεταγμένα ζεύγη). Ένα σύνολο λατινικών τετραγώνων της ίδιας τάξης αποτελεί ένα σύνολο απο mutualy ορθογώνια λατινικά τετράγωνα (MOLS) αν κάθε δύο λατινικά τετράγωνα του συνόλου είναι ορθογώνια. Μπορούν να υπάρχουν το πολύ $n-1$ τετράγωνα σε ένα σύνολο MOLS τάξης $n$. Ένα σύνολο από $n-1$ MOLS τάξης $n$ μπορεί να χρησιμοποιηθεί για την κατασκευή ενός προβολικού επιπέδου τάξεως $n$ (και αντιστρόφως).

• Ένα σύνολο διαφορών $(\nu ,k,\lambda )$ είναι ένα υποσύνολο $D$ μίας ομάδας $G$, της οποίας η τάξη είναι $\nu$, η πληθικότητα του $D$ είναι $k$, και κάθε μη μοναδιαίο στοιχείο της $G$ μπορεί να εκφραστεί ως ένα γινόμενο $d_{1}\cdot d_{2}^{-1}$στοιχείων $d_{1},d_{2}\in D$ με ακριβώς $\lambda$ τρόπους (όταν φυσικά η $G$ θεωρείται πολλαπλασιαστική ομάδα). Αν το $D$ είναι ένα σύνολο διαφορών και $g\in G$, τότε το σύνολο $g\cdot D:=\{g\cdot D~|~d\in D\}$ είναι επίσης σύνολο διαφορών, και ονομάζεται μεταφορά του $D$. Το σύνολο όλων των μεταφορών αποτελεί ένα symmetric block design. Σε έναν τέτοιο σχεδιασμό, υπάρχουν $\nu$ στοιχεία και $\nu$ block, κάθε block του σχεδιασμού αποτελείται από $k$ στοιχεία και κάθε στοιχείο περιέχεται σε $k$ block. Επίσης, κάθε δύο block έχουν ακριβώς $\lambda$ κοινά στοιχεία και δύο οποιαδήποτε στοιχεία εμφανίζονται μαζί σε $\lambda$ block. Αυτό το SBIBD ονομάζεται development της $D$. Ειδικότερα, αν $\lambda =1$, τότε το σύνολο διαφορών ουσιαστικά δημιουργεί ένα προβολικό επίπεδο. Ένα παράδειγμα ενός συνόλου διαφορών $(7,3,1)$ στην ομάδα $\mathbb {Z} /7\mathbb {Z}$ (η αβελιανή ομάδα εδώ θεωρείται προσθετική) είναι το υποσύνολο ${\big \{}[1/7\mathbb {Z} ],~[2/7\mathbb {Z} ],~[4/7\mathbb {Z} ]{\big \}}\subseteq \mathbb {Z} /7\mathbb {Z}$. Αυτό το σύνολο διαφορών δίνει το προβολικό επίπεδο του Fano. Δεδομένου ότι κάθε σύνολο διαφορών δίνει μια SBIBD, ο παραμετρικός χώρος πρέπει να ικανοποιεί το θεώρημα των Bruck–Ryser–Chowla, αλλά ας σημειωθεί ότι δεν δίνει οποιαδήποτε SBIBD ένα σύνολο διαφορών.
• Ένας πίνακας Hadamard τάξης $m$ είναι ένας πίνακας $m\times m$ (έστω $H$) του οποίου στοιχεία είναι τα $\pm 1$. Επιπλέον, $H\cdot H^{T}=m\cdot \mathrm {Id} _{m}$, όπου $H^{T}$ είναι ο ανάστροφος πίνακας του $H$ και $\mathrm {Id} _{m}$ είναι ο $m\times m$ ταυτοτικός πίνακας. Ένας πίνακας Hadamard μπορεί να τεθεί σε κλιμακωτή μορφή (δηλαδή, να μετατραπεί σε ισοδύναμο κλιμακωτό πίνακα Hadamard), όπου στην πρώτη γραμμή και στήλη τα στοιχεία είναι $1$. Αν η τάξη $m$ είναι γνήσια μεγαλύτερη του $2$, τότε το $m$ πρέπει να είναι ένα πολλαπλάσιο του $4$. Δoθέντος ενός πίνακα Hadamard τάξης $4$ σε κλιμακωτή μορφή, αφαιρέστε την πρώτη γραμμή και την πρώτη στήλη, και μετατρέψετε κάθε $-1$ σε $0$. Ο προκύπτον $0-1$ πίνακας $M$ είναι ο πίνακας προσπτώσεων ενός symmetric block design $2-(4a-1,~2a-a,~a-1)$, το οποίο ονομάζεται $2-$σχέδιο Hadamard. Αυτή η κατασκευή είναι αντιστρέψιμη, και ο πίνακας προσπτώσεων του symmetric block design με αυτές τις παραμέτρους μπορεί να χρησιμοποιηθεί για να σχηματίστεί ένας πίνακας Hadamard τάξης $4$. Όταν $a=2$, παίρνουμε το προβολικό επίπεδο του Fano ως 2-σχέδιο Hadamard.

• Ένα pairwise balanced design (ή PBD) είναι ένα σύνολο $X$ μαζί με μια οικογένεια υποσυνόλων του $X$ (τα οποία δεν χρειάζεται να ισοπληθή και μπορεί να υπάρχουν επαναλήψεις), τέτοια ώστε δύο διακεκριμένα στοιχεία του $X$ περιέχoνται ακριβώς σε $\lambda \in \mathbb {N} =\{1,2,3,\cdots \}$ υποσύνολα. Το σύνολο $X$ είναι επιτρέπεται να είναι ένα από τα υποσύνολα της οικογένειας - ειδικά, αν όλα τα υποσύνολα είναι αντίγραφα του $X$, το PBD ονομάζεται τετριμμένο. Η πληθικότητα του $X$ είναι $\nu$ και ο αριθμός των υποσυνόλων στην οικογένεια (υπολογίζοντας τις πολλαπλότητες) είναι $b$. Η ανισότητα Fisher ισχύει και για PBD: για κάθε μη-τετριμμένο PBD αληθεύει η ανισότητα $\nu \leqslant b$. Αυτό το αποτέλεσμα γενικεύει το περίφημο θεώρημα των Erdős–De Bruijn: για PBD με $\lambda =1$, χωρίς block πληθικότητας $1$ ή $\nu$, αληθεύει $\nu \leqslant b$. Η ισότητα ισχύει αν και μόνο αν το PBD είναι ένα προβολικό επίπεδο ή ένας γραμμικός χώρος με $\nu$ σημεία, που περιέχει ευθεία $\nu -1$ σημείων (near-pencil. Πρόχειρη μετάφραση: κοντινή δέσμη).

Μερικά παραδείγματα άλλων συνδυαστικών σχεδίων

Το εγχειρίδιο Handbool of Combinatorial Designs (Colbourn & Dinitz 2007) έχει, μεταξύ άλλων 65 κεφάλαια, το καθένα αφιερωμένο σε ένα συνδυαστικό σχεδιασμό διαφορετικό απ' όσους αναφέρθηκαν παραπάνω. Μια λίστα μερικών εξ αυτών, είναι η παρακάτω:

• Association schemes.
• Ένα τριαδικό balanced design $\mathrm {BTD} (V,B;~\rho _{1},\rho _{2};~K,\Lambda )$ είναι μια διάταξη με $V$ στοιχεία σε $B$ multiset (τα οποία είναι τα block), που έχουν πληθικότητα $K$ με $K\leqslant V$, και ικανοποιεί τις εξής ιδιότητες:

1. Κάθε στοιχείο εμφανίζεται $R=\rho _{1}+2\rho _{2}$ φορές συνολικά, με πολλαπλότητα $1$ σε ακριβώς $\rho _{1}$ block και $2$ σε ακριβώς $\rho _{2}$ block.
2. Κάθε ζεύγος διακεκριμένων στοιχείων εμφανίζεται $\Lambda$ φορές (υπολογίζοντας τις πολλαπλότητες). Δηλαδή, αν $m_{vb}$ είναι η πολλαπλότητα του στοιχείου $v$ στο block $b$, τότε για κάθε ζεύγος διακεκριμένων στοιχείων $v$ και $w$, $\sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda$.

Για παράδειγμα, ένα από τα δύο μοναδικά μη-ισόμορφα $\mathrm {BTD} (4,8;~2,3,8;~4,6)$ (τα block είναι οι στήλες) είναι το:

${\begin{matrix}1,&1,&1,&2,&2,&3,&1,&1;\\1,&1,&1,&2,&2,&3,&2,&2;\\2,&3,&4,&3,&4,&4,&4,&4\end{matrix}}$

Ο πίνακας προσπτώσεων ενός BTD (όπου τα στοιχεία του πίνακα είναι οι πολλαπλότητες των στοιχείων στα block) μπορεί να χρησιμοποιηθεί για να σχηματίστεί ένας τριαδικός κώδικας διόρθωσης σφαλμάτων, με τρόπο ανάλογο με το πώς δυαδικοί κώδικες σχηματίζονται από τους πίνακες προσπτώσεων των BIBD.

• Ένα balanced tournament design τάξης $n$ (δηλαδή ένα $\mathrm {BTD} (n)$) είναι μια διάταξη όλων των διακριτών, μη διατεταγμένων ζευγών ενός $2n-$συνόλου $V$, σε μία $n\times (2n-1)$ μορφή, τέτοια ώστε

1. κάθε στοιχείο του $V$ εμφανίζεται ακριβώς μια φορά σε κάθε στήλη,
2. κάθε στοιχείο του $V$ εμφανίζεται το πολύ δύο φορές σε κάθε σειρά.

Ένα παράδειγμα ενός $\mathrm {BTD} (3)$ δίνεται από το

${\begin{matrix}1~6,&3~5,&2~3,&4~5,&2~4;\\2~5,&4~6,&1~4,&1~3,&3~6;\\3~4,&1~2,&5~5,&2~6,&1~5\end{matrix}}$

Οι στήλες του $\mathrm {BTD} (3)$ δίνουν μία $1-$παραγοντοποίηση του πλήρους γραφήματος ($K_{2n}$) με $2n$ κορυφές. Τα $\mathrm {BTD} (n)$ μπορούν να χρησιμοποιηθούν για να προγραμματίστούν τουρνουά round-robin: οι σειρές αντιπροσωπεύουν τις θέσεις, οι στήλες τους γύρους του παιχνιδιού και τα στοιχεία είναι οι ανταγωνιστές παίκτες ή οι ομάδες.

• Συναρτήσεις bent (υποκατηγορία των συναρτήσεων Boolean)
• Διατάξεις Costas
• Παραγοντικά σχέδια
• Ένα τετράγωνο συχνότητας (F-square) είναι μια ανώτερης τάξης γενίκευση ενός λατινικού τετραγώνου. Ας είναι $S=\{s_{1},s_{2},\cdots ,s_{m}\}$ ένα σύνολο από διακριτά σύμβολα και $(\lambda _{1},\lambda _{2},\cdots ,\lambda _{m})$ ένα διάνυσμα συχνότητας, το οποίο αποτελείται από θετικούς ακέραιους. Ένα τετράγωνο συχνότητας τάξης $n$ είναι ένας $n\times n$ πίνακας στον οποίο κάθε σύμβολο $s_{i}$ παρουσιάζεται $\lambda _{i}$ φορές ($i\in \{1,2,\cdots m\}$) σε κάθε σειρά και στήλη. Η τάξη $n$ είναι ο αριθμός $n=\lambda _{1}+\lambda _{2}+\cdots +\lambda _{m}$. Ένα F-square είναι σε κλιμακωτή μορφή και αν στην πρώτη σειρά και στήλη, όλες τις εμφανίσεις του $s_{i}$ προηγούνται εκείνες του $s_{j}$_, όποτε $i<j$. Έστω ένα τετράγωνο συχνότητας $F_{1}$ τάξης $n$, με βάση το σύνολο $\{s_{1},s_{2},\cdots ,s_{m}\}$ και διάνυσμα συχνότητας $(\lambda _{1},\lambda _{2},\cdots ,\lambda _{m})$. Έστω επίσης τετράγωνο συχνότητας $F_{2}$ τάξης $n$, με βάση το σύνολο $\{t_{1},t_{2},\cdots ,t_{k}\}$ και διάνυσμα συχνότητας $(\mu _{1},\mu _{2},\cdots ,\mu _{k})$. Τα $F_{1}$ και $F_{2}$ καλούνται ορθογώνια αν κάθε διατεταγμένο ζεύγος $(s_{i},t_{j})$ εμφανίζεται ακριβώς $\lambda _{i}\mu _{j}$ φορές, όταν τα $F_{1}$ και $F_{2}$ είναι σε υπέρθεση.

• Τριπλά συστήματα Hall (HTS) είναι τριπλά συστήματα Steiner (STS) (αλλά τα block ονομάζονται εδώ καλούνται γραμμές) με την ιδιότητα ότι η υπο-δομή που δημιουργείται από δύο τεμνόμενες γραμμές είναι ισομορφική με το πεπερασμένο συσχετισμένο επίπεδο $\mathrm {AG} (2,3)$. Οποιοσδήποτε συσχετισμένος χώρος $\mathrm {AG} (n,3)$ δίνει ένα παράδειγμα ενός HTS. Κάθε τέτοιο HTS καλείται συσχετισμένο HTS. Μη συσχετισμένα HTS επίσης υπάρχουν. Ο αριθμός των σημείων ενός HTS είναι $3^{m}$ για κάποιον ακέραιο $m\geqslant 2$. Μη συσχετισμένα HTS υπάρχουν για κάθε $m\geqslant 4$ και δεν υπάρχουν για $m=2$ ή $3$. Κάθε τριπλό σύστημα Steiner είναι ισοδύναμο με μία ημιομάδα Steiner (ταυτοδύναμη, αντιμεταθετική και ικανοποίεί τη σχέση $(xy)y=x$ για όλα τα $x$ και $y$). Κάθε τριπλό σύστημα Hall είναι ισοδύναμο με μία ημιομάδα Steiner η οποία είναι επιμεριστική, δηλαδή ικανοποιεί τη σχέση $a(xy)=(ax)(ay)$ για όλα τα $a,x,y$ στην ημιομάδα.

• Έστω $S$ ένα σύνολο με $2n$ στοιχεία. Ένα σχέδιο Howell $H(s,2n)$ (σε σύνολο συμβόλων $S$) είναι μια διάταξη $s\times s$ για την οποία:

1. Κάθε κελί είναι είτε κενό ή περιέχει ένα μη διατεταγμένο ζεύγος του $S$,
2. Κάθε σύμβολο εμφανίζεται ακριβώς μία φορά σε κάθε σειρά και στήλη της διάταξης,
3. Κάθε μη διατεταγμένo ζεύγoς συμβόλων παρουσιάζεται το πολύ σε ένα κελί.

Ένα παράδειγμα ενός $H(4,6)$ είναι το ακόλουθο:

${\begin{matrix}0~4,&~~~~~,&1~3,&2~5;\\2~3,&1~4,&0~5,&~~~~~;\\~~~~~,&3~5,&2~4,&0~1;\\1~5,&0~2,&~~~~~,&3~4\end{matrix}}$

Ένα $H(2n-1,2n)$ αποτελεί επίσης τετράγωνο Room με πλευρά $2n-1$ - έτσι, τα σχέδια Howell γενικεύουν την έννοια των τετραγώνων Room. Τα ζεύγη συμβόλων στα κελιά του σχεδίου Howell μπορούν να θεωρηθούν ως ακμές ενός $s-$κανονικού γραφήματος $2n$ κορυφών, το οποίο ονομάζεται υποκείμενο γράφημα του σχεδίου Howell. Κυκλικοί σχεδιασμοί Howell χρησιμοποιούνται ως κινήσεις Howell σε διπλά τουρνουά bridge. Οι γραμμές του σχεδίου αντιπρσωπεύουν του γύρους, οι στήλες τους πίνακες και οι διαγώνιοι τα tables.

• Γραμμικοί χώροι
• Ένα $(n,k,p,t)-$σχέδιο lotto είναι ένα $n-$σύνολο $V$, το οποίο αποτελείται από κάποια στοιχεία μαζί με ένα σύνολο $\beta$, $k-$υποσυνόλων του $V$ (αυτά είναι τα block σε αυτήν την περίπτωση), έτσι ώστε για κάθε $p-$υποσύνολο $P$ του $V$, υπάρχει ένα block $B\in \beta$ για το οποίο $|P\cap B|\geqslant t$. Το σύμβολο $L(n,k,p,t)$ δηλώνει το μικρότερο αριθμό block κάθε $(n,k,p,t)-$σχεδίου lotto. Το παρακάτω παράδειγμα είναι ένα $(7,5,4,3)-$σχέδιο lotto με το ελάχιστο πλήθος block: $\{1,2,3,4,7\},~\{1,2,5,6,7\},~\{3,4,5,6,7\}$. Τα σχέδια lotto προσομοιάζουν κάθε κλήρωση που εκτελείται με τον ακόλουθο τρόπο: οι παίκτες αγοράζουν κλήρους που αποτελούνται από $k$ αριθμούς, που έχουν επιλεγεί από ένα σύνολο $n$ αριθμών. Κάποτε η πώληση των κλήρων σταματάει και ένα σύνολο $p$ αριθμών κατασκευάζεται τυχαία από τους $n$ αριθμούς. Αυτοί είναι οι αριθμοί που κερδίζουν. Εάν οποιοσδήποτε κλήρος που πωλείται περιέχει $t$ (ή περισσότερους) από τους αριθμούς που κερδίζουν, ένα βραβείο δίνεται στον κάτοχο του κλήρου. Τα μεγαλύτερα βραβεία είναι για τους κλήτους που έχουν τους περισσότερους αριθμούς που κληρώθηκαν. Η τιμή του $L(n,k,p,t)$ είναι προς το συμφέρον τόσο των παικτών όσο και των ερευνητών, καθώς αυτός είναι ο μικρότερος αριθμός των κλήρων που απαιτούνται να αγοραστούν προκειμένου να εξασφαλιστεί ένα βραβείο. Το ουγγρικό Λαχείο είναι ένα $(90,5,5,t)-$σχέδιο lotto και είναι γνωστό ότι $L(90,5,5,2)=100$. Λαχεία με παραμέτρους $(49,6,6,t)$ είναι επίσης δημοφιλή σε όλο τον κόσμο και είναι γνωστό ότι $L(49,6,6,2)=19$. Σε γενικές γραμμές όμως, οι αριθμοί είναι δύσκολο να υπολογισθούν και παραμένουν άγνωστοι. Μια γεωμετρική κατασκευή ενός τέτοιου σχεδίου είναι το λεγόμενο Λαχείο της Τρανσυλβανίας.

• Μαγικά τετράγωνα
• Ένα $(\nu ,k,\lambda )-$σχέδιο Mendelsohn (ή συμβολικά $\mathrm {MD} (\nu ,k,\lambda )$), είναι ένα $\nu -$σύνολο $V$ και μια συλλογή $\beta$, διατεταγμένων $k-$άδων διακεκριμένων στοιχείων του $V$ (που ονομάζονται block), τέτοια ώστε κάθε διατετεγμένο ζεύγος $(x,y)$ με $x\neq y$ στοιχείων του $V$ είναι κυκλικά εφαπτόμενο σε $\lambda$ block. Ένα διατεταγμένο ζεύγος $(x,y)$ από διακεκριμένα στοιχεία είναι κυκλικά εφαπτόμενο σε ένα block, αν τα στοιχεία εμφανίζονται στο block ως εξής: $(\cdots ,x,y,\cdots )$ ή $(y,\cdots ,x)$. Ένα $\mathrm {MD} (\nu ,3,\lambda )$ καλείται τριπλό σύστημα Mendelsohn, ή συμβολικά $\mathrm {MTS} (\nu ,\lambda )$. Ένα παράδειγμα ενός $\mathrm {MTS} (4,1)$ στο $V=\{0,1,2,3\}$ είναι το: $(0,1,2)~~(1,0,3)~~(2,1,3)~~(0,2,3)$. Κάθε τριπλό σύστημα μπορεί να γίνει ένα τριπλό σύστημα Mendelsohn με αντικατάσταση κάθε μη διατεταγμένης τριάδας $\{a,b,c\}$ από τις διατεταγμένες τριάδες $(a,b,c)$ και $(a,c,b)$, αλλά όπως δείχνει το ακόλουθο παράδειγμα, το αντίστροφο δεν είναι αληθές. Αν $(Q,*)$ είναι μία ταυτοδύναμη, ημισυμμετρική ημιομάδα - δηλαδή αν $x*x=x$ (ταυτοδυναμία) και $x*(y*x)=y$ (ημισυμμετρία) για όλα τα $x,y\in Q$ - θεωρούμε $\beta =\{(x,y,x*y)~|~x,y\in Q\}$. Παρατηρούμε τότε ότι το $(Q,\beta )$ είναι τριπλό σύστημα Mendelsohn $\mathrm {MTS} (|Q|,1)$. Αυτή η κατασκευή είναι αντιστρέψιμη.

• Ορθογώνιες διατάξεις.
• Ένα quasi-$3$ design είναι ένα symmetric design (SBIBD), στο οποίο κάθε τρία block τέμνονται σε $x$ είτε σε $y$ σημεία, για σταθερούς $x<y$ οι οποίοι ονομάζονται αριθμοί τριπλής τομής. Κάθε symmetric design με $\lambda \leqslant 2$ είναι ένα quasi-3 design με $x=0$ και $y=1$. Το σημειακό υπερεπίπεδο σχέδιο του $\mathrm {PG} (n,q)$ είναι ένα quasi-3 design με $x=(q^{n-2}-1)/(q-1)$ και $y=\lambda =(q^{n-1}-1)/(q-1)$. Αν σε ένα quasi-3 design αληθεύει $y=\lambda$, το εν λόγω σχέδιο είναι ισομορφικό με το $\mathrm {PG} (n,q)$ ή με ένα προβολικό επίπεδο.
• Ένα $t-(\nu ,k,\lambda )$ σχέδιο $D$ είναι quasi-συμμετρικό με αριθμούς τομής $x$ και $y>x$, αν κάθε δύο διαφορετικά μπλοκ τέμνονται είτε σε $x$, είτε σε $y$ σημεία. Αυτά τα σχέδια εμφανίζονται φυσικά, αν κανείς μελετήσει τα δυϊκά σχεδίων με $\lambda =1$. Ένα μη symmetric ($b>\nu$) design $2-(\nu ,k,1)$, είναι quasi-συμμετρικό με $x=0$ και $y=1$. Ένα γινόμενο ενός symmetric $2-(\nu ,k,\lambda )$ design (αυτό προκύπτει με επανάληψη των block ορισμένο πλήθος φορών) είναι quasi-συμμετρικό με $x=\lambda$ και $y=k$. Τα $3-$σχέδια Hadamard (τα οποία αποτελούν επέκταση των $2-$σχεδίων Hadamard) είναι quasi-συμμετρικά. Κάθε quasi-συμμετρικό σχέδιο δημιουργεί ένα ισχυρά κανονικό γράφημα (εννοείται γράφημα των block του), αλλά ας σημειωθεί ότι το αντίστροφο δεν αληθεύει - δεν προκύπτει κάθε ισχυρά κανονικό γράφημα μ' αυτόν τον τρόπο. Ο πίνακας προσπτώσεων του quasi-συμμετρικού $2-(\nu ,k,\lambda )$ σχεδίου με $k\equiv x\equiv y\mod 2$, δημιουργεί ένα δυαδικό αυτο-ορθογώνιο κώδικα.

• Τετράγωνα Room
• Ένα σφαιρικό σχέδιο είναι ένα πεπερασμένο σύνολο $X$ του οποίου τα σημεία βρίσκονται σε μία $(d-1)-$διαστάσεων σφαίρα, τέτοια ώστε (για κάποιον ακέραιο $t$) η μέση τιμή στο $X$ κάθε πολυωνύμου $f(x_{1},\cdots ,x_{d})$ με βαθμό το πολύ $t$, είναι ίση με την μέση τιμή του $f$ σε όλη τη σφαίρα. Δηλαδή, το ολοκλήρωμα του $f$ προς το εμβαδόν της σφαίρας ισούται με τη μέση τιμή στο $X$.

• Συστήματα Turán
• Ένα $r\times n$, $k-$ορθογώνιο Τοσκάνης με $n$ σύμβολα έχει $r$ γραμμές και $n$ στήλες, έτσι ώστε:

1. κάθε σειρά είναι μια μετάθεση των $n$ συμβόλων και
2. για κάθε δύο διαφορετικά σύμβολα $a$ και $b$ και για κάθε $m$ από $1$ έως $k$, υπάρχει το πολύ μία γραμμή στην οποία το $b$ είναι $m$ βήματα δεξιά του $a$.

Αν $r=n$ και $k=1$, τα ορθογώνια αυτά αναφέρονται ως τετράγωνα Τοσκάνης, ενώ αν $r=n$ και $k=n-1$ αναφέρονται ως τετράγωνα Φλορεντίας. Ένα ρωμαϊκο τετράγωνο είναι ένα τετράγωνο Τοσκάνης το οποίο είναι επίσης λατινικό τετράγωνο (Τα ρωμαϊκά τετράγωνα είναι επίσης γνωστά ως γραμμοπλήρη (row complete) λατινικά τετράγωνα). 'Ενα τετράγωνο Βατικανού είναι ένα τετράγωνο Φλορεντίας, το οποίο είναι επίσης ένα λατινικό τετράγωνο.

Το ακόλουθο είναι παράδειγμα ενός $1-$ορθογωνίου Τοσκάνης με $7$ σύμβολα, το οποίο δεν είναι $2-$ορθογώνιο Τοσκάνης:

${\begin{matrix}6,&1,&5,&2,&4,&3,&7;\\2,&6,&3,&5,&4,&7,&1;\\5,&7,&2,&3,&1,&4,&6;\\4,&2,&5,&1,&6,&7,&3;\\3,&6,&2,&1,&7,&4,&5;\\1,&3,&2,&7,&5,&6,&4;\\7,&6,&5,&3,&4,&1,&2\end{matrix}}$

Ένα τετράγωνο Τοσκάνης με $n$ σύμβολα είναι ισοδύναμο με μία αποσύνθεση του πλήρους γραφήματος με $n$ κορυφές, σε $n$ Hamiltonιανά κατευθυνόμενα μονοπάτια.

• Ένα t-wise balanced design (ή t BD) του τύπου $t-(\nu ,K,\lambda )$ είναι ένα $\nu -$σύνολο $X$ μαζί με μια οικογένεια υποσυνόλων του (που ονομάζονται block), των οποίων οι πληθάριθμοι είναι στο σύνολο $K$. Επιπλέον, κάθε $t-$υποσύνολο διακεκριμένων στοιχείων του $X$ περιέχεται ακριβώς σε $\lambda$ block. Αν K είναι ένα σύνολο θετικών ακεραίων, αυστηρά μεταξύ των $t$ και $\nu$, τότε το t BD καλείται proper. Αν όλα τα $k-$υποσύνολα του $X$ (για κάποιο $k$) είναι τετράγωνα, τo t BD καλείται τετριμμένο σχέδιο. Παρατηρούμε οτι στο παρακάτω παράδειγμα ενός $3-(12,\{4,6\},1)$σχεδίου στο σύνολο $X=\{1,2,3,\cdots ,12\}$, μερικά ζεύγη εμφανίζονται $4$ φορές (όπως τα $1,2$) ενω κάποια άλλα $5$ φόρες (όπως τα $6,12$).

1 2 3 4 5 6            1 2 7 8      1 2 9 11      1 2 10 12      3 5 7 8      3 5 9 11      3 5 10 12      4 6 7 8      4 6 9 11      4 6 10 12

7 8 9 10 11 12      2 3 8 9      2 3 10 7      2 3 11 12      4 1 8 9      4 1 10 7      4 1 11 12      5 6 8 9      5 6 10 7      5 6 11 12

                             3 4 9 10      3 4 11 8      3 4 7 12      5 2 9 10      5 2 11 8      5 2 7 12      1 6 9 10      1 6 11 8      1 6 7 12

                             4 5 10 11      4 5 7 9      4 5 8 12      1 3 10 11      1 3 7 9      1 3 8 12      2 6 10 11      2 6 7 9      2 6 8 12

                             5 1 11 7      5 1 8 10      5 1 9 12      2 4 11 7      2 4 8 10      2 4 9 12      3 6 11 7      3 6 8 10      3 6 9 12

• Οι πίνακες ζύγισης αποτελούν μια γενίκευση των πινάκων Hadamard, στους οποίους επιτρέπονται μηδενικά στοιχεία. Αυτού του είδους οι πίνακες χρησιμοποιούνται σε κάποια συνδιαστικά σχέδια, όπως στον σχεδιασμό πειραμάτων στα οποία εκτιμάται το βάρος καθενός αντεικειμένου, όταν ζυγίζονται πολλά αντικείμενα.

• Ένα τετράγωνο Youden είναι μία $k\times \nu$ ορθογώνια διάταξη ($k<\nu$) με $\nu$ σύμβολα, τέτοια ώστε κάθε σύμβολο εμφανίζεται ακριβώς μία φορά σε κάθε σειρά και τα σύμβολα που εμφανίζονται σε κάθε στήλη σχηματίζουν ένα block από ένα symmetric $(\nu ,k,\lambda )$ design, του οποίου τα block προκύπτουν όλα καθ' αυτόν τον τρόπο. Κάθε τετράγωνο Youden είναι λατινικό ορθογώνιο. Ο όρος "τετράγωνο" στο όνομα προέρχεται από ένα παλαιότερο ορισμό, στον οποίον χρησιμοποιούταν τετραγωνικός πίνακας. Ένα παράδειγμα ενός $4\times 7$ τετραγώνου Youden δίνεται παρακάτω:

${\begin{matrix}1,&2,&3,&4,&5,&6,&7;\\2,&3,&4,&5,&6,&7,&1;\\3,&4,&5,&6,&7,&1,&2;\\5,&6,&7,&1,&2,&3,&4\end{matrix}}$

Τα επτά block (στήλες) κατασκευάζουν ένα τάξης $2$ διεπίπεδο (biplane). Δηλαδή ένα symmetric $(7,4,2)-$design.

Ξενόγλωσσες σελίδες του ίδιου λήμματος

Το παρόν λήμμα αποτελεί μετάφραση του αντίστοιχου αγγλικού: Combinatorial design.

Δείτε επίσης

• Αλγεβρική στατιστική
• Θεωρία γραφημάτων
• Υπεργράφημα
• Η εικασία του Williamson

Βιβλιογραφία

• Assmus, E.F.; Key, J.D. (1992), Designs and Their Codes, Cambridge University Press, ISBN 0-521-41361-3 
• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge University Press . 2nd ed. (1999) (ISBN 978-0-521-44432-3).
• Bose, R. C. (1949). «A Note on Fisher's Inequality for Balanced Incomplete Block Designs». Annals of Mathematical Statistics 20 (4): 619–620. doi:10.1214/aoms/1177729958. https://archive.org/details/sim_annals-of-mathematical-statistics_1949-12_20_4/page/619. 
• Caliński, Tadeusz· Kageyama, Sanpei (2003). Block designs: A Randomization approach, Volume II: Design. Lecture Notes in Statistics. 170. Springer. ISBN 0-387-95470-8. 
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd έκδοση), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8, https://archive.org/details/handbookofcombin0000unse 
• Fisher, R. A. (1940). «An examination of the different possible solutions of a problem in incomplete blocks». Annals of Eugenics 10: 52–75. doi:10.1111/j.1469-1809.1940.tb02237.x. 
• Hall, Jr., Marshall (1986), Combinatorial Theory (2nd έκδοση), New York: Wiley-Interscience, ISBN 0-471-09138-3 
• Hughes, D.R.; Piper, E.C. (1985), Design theory, Cambridge University Press, ISBN 0-521-25754-9, https://archive.org/details/designtheory0000hugh 
• Lander, E. S. (1983), Symmetric Designs: An Algebraic Approach, Cambridge: Cambridge University Press 
• Lindner, C.C.; Rodger, C.A. (1997), Design Theory, Boca Raton: CRC Press, ISBN 0-8493-3986-3 
• Raghavarao, Damaraju· Padgett, Lakshmi V. (1988). Constructions and Combinatorial Problems in Design of Experiments. Dover. ISBN 978-0-486-65685-4. 
• Raghavarao, Damaraju· Padgett, Lakshmi V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific. ISBN 978-981-4480-23-9. 
• Ryser, Herbert John (1963), «8. Combinatorial Designs», Combinatorial Mathematics, Carus Monograph, 14, Mathematical Association of America, ISBN 978-0-88385-000-8, https://books.google.com/books?id=wOruAAAAMAAJ 
• Shrikhande, S.S.; Bhat-Nayak, Vasanti N. (1970), «Non-isomorphic solutions of some balanced incomplete block designs I», Journal of Combinatorial Theory 9 (2): 174–191, doi:10.1016/S0021-9800(70)80024-2 
• Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2 
• Street, Anne Penfold· Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. ISBN 0-19-853256-3. 
• van Lint, J.H.; Wilson, R.M. (1992), A Course in Combinatorics, Cambridge University Press, ISBN 978-0-521-41057-1, https://books.google.com/books?id=oO62swEACAAJ 

Εξωτερικοί σύνδεσμοι

• Design DB: Μια ολοκληρωμένη βάση δεδομένων, συνδυαστικής, στατιστικής και πειραματικών σχεδίων block.