Γράφημα Πέιλι

Στα μαθηματικά, τα γραφήματα Πέιλι είναι μη κατευθυνόμενα γραφήματα που κατασκευάζονται από τα μέλη ενός κατάλληλου πεπερασμένου σώματος συνδέοντας ζεύγη στοιχείων που διαφέρουν κατά ένα τετραγωνικό υπόλειμμα. Τα γραφήματα Πέιλι σχηματίζουν μια άπειρη οικογένεια γραφημάτων διασκέψεων (conference graph), τα οποία δίνουν μια άπειρη οικογένεια συμμετρικών πινάκων διασκέψεων. Τα γραφήματα Πέιλι επιτρέπουν την εφαρμογή γραφοθεωρητικών εργαλείων στη θεωρία αριθμών τετραγωνικών υπολοίπων και έχουν ενδιαφέρουσες ιδιότητες που τα καθιστούν χρήσιμα στη θεωρία γραφημάτων γενικότερα.

Τα γραφήματα Πέιλι πήραν το όνομά τους από τον Ρέιμοντ Πέιλι. Σχετίζονται στενά με την κατασκευή Πέιλι για την κατασκευή πινάκων Χαντάμαρντ από τετραγωνικά κατάλοιπα. Εισήχθησαν ως γραφήματα ανεξάρτητα από τους Σαχς () και Έρντος & Ρένι (). Ο Σαχς ενδιαφέρθηκε γι' αυτούς για τις ιδιότητες αυτοσυμπληρωματικότητας τους, ενώ οι Έρντος και Ρένι μελέτησαν τις συμμετρίες τους.

Τα διγράφηματα Πέιλι είναι κατευθυνόμενα ανάλογα των γραφημάτων Πέιλι που δημιουργούν αντισυμμετρικούς πίνακες διασκέψεων. Εισήχθησαν από τους Γκράχαμ & Σπένσερ () (ανεξάρτητα από τους Σαχς, Ερντό και Ρένι) ως ένας τρόπος κατασκευής τουρνουά με μια ιδιότητα που ήταν προηγουμένως γνωστό ότι είχαν μόνο τυχαία τουρνουά: σε ένα διγράφο Πέιλι, κάθε μικρό υποσύνολο κορυφών κυριαρχείται από κάποια άλλη κορυφή .

 Ορισμός 

Έστω q μια πρώτη δύναμη τέτοια ώστε q = 1 (mod 4). Δηλαδή, το  q πρέπει να είναι είτε μια τυχαία δύναμη ενός πυθαγόρειου πρώτου αριθμού (ένα πρώτο αριθμό συμβατό με το 1 mod 4) είτε μια ζυγή δύναμη ενός περιττού μη πυθαγόρειου πρώτου αριθμού. Αυτή η επιλογή του q συνεπάγεται ότι στο μοναδικό πεπερασμένο σώμα Fq τάξης q, το στοιχείο  −1 έχει τετραγωνική ρίζα.

Τώρα έστω  V = Fq και έστω 

.

Εάν ένα ζεύγος {a,b} περιλαμβάνεται στο E, περιλαμβάνεται κάτω από οποιαδήποτε διάταξη των δύο στοιχείων του. Για,
a − b = −(b − a), και  −1 είναι τετράγωνο, από το οποίο προκύπτει ότι a − b είναι τετράγωνο αν και μόνο αν  b − a είναι τετράγωνο.

Εξ ορισμού G = (V, E)  είναι το γράφημα Πέιλι  τάξης q.

 Παράδειγμα 

Για q = 13, το σώμα Fq είναι απλά ακέραιος αριθμητικός  modulo 13.  Οι αριθμοί με τετραγωνικές ρίζες mod 13 είναι:
 ±1 (τετραγωνικές ρίζες ±1 για +1, ±5 για −1)
 ±3 (τετραγωνικές ρίζες ±4 για +3, ±6 για −3)
 ±4 (τετραγωνικές ρίζες ±2 για +4, ±3 για −4).
Έτσι, στο γράφημα Πέιλι, σχηματίζουμε μια κορυφή για κάθε έναν από τους ακέραιους στην περιοχή [0,12] και συνδέουμε κάθε τέτοιο ακέραιο x με έξι γείτονες: x ± 1 (mod 13), x ± 3 (mod 13), και x ± 4 (mod 13).

 Ιδιότητες 
Τα γραφήματα Πέιλι είναι αυτοσυμπληρωματικά: το συμπλήρωμα οποιουδήποτε γραφήματος Πέιλι είναι ισόμορφο με αυτό.   Ένας ισομορφισμός είναι μέσω της απεικόνισης που παίρνει μια κορυφή  σε , όπου  είναι οποιοδήποτε μη υπολειμματικό .

Τα γραφήματα Πέιλι είναι ισχυρά κανονικά γραφήματα, με παραμέτρους

Αυτό στην πραγματικότητα προκύπτει από το γεγονός ότι το γράφημα είναι μεταβατικό και αυτοσυμπληρούμενο. Τα ισχυρά κανονικά γραφήματα με παραμέτρους αυτής της μορφής (για ένα αυθαίρετο ) ονομάζονται γραφήματα διάσκεψης, οπότε τα γραφήματα Πέιλι αποτελούν μια άπειρη οικογένεια γραφημάτων διάσκεψης. Ο πίνακας γειτνίασης ενός γραφήματος συνδιάσκεψης, όπως ένα γράφημα Πέιλι, μπορεί να χρησιμοποιηθεί για την κατασκευή ενός πίνακα συνδιάσκεψης, και αντίστροφα. Πρόκειται για πίνακες των οποίων οι συντελεστές είναι , με μηδέν στο διαγώνιο, που δίνουν ένα βαθμωτό πολλαπλάσιο του ταυτοτικού πίνακα όταν πολλαπλασιάζονται με τον ανάστροφό τους.

Οι ιδιοτιμές των γραφημάτων Πέιλι είναι   (με πολλαπλότητα 1) και (και οι δύο με πολλαπλότητα ).  Μπορούν να υπολογιστούν χρησιμοποιώντας το τετραγωνικό άθροισμα Γκάους ή χρησιμοποιώντας τη θεωρία των ισχυρά κανονικών γραφημάτων.

Εάν  είναι πρώτος αριθμός, ο ισοπεριμετρικός αριθμός  του γραφήματος Πέιλι ικανοποιεί τα ακόλουθα όρια:

Όταν  είναι πρώτος αριθμός, το σχετικό γράφημα Πέιλι είναι ένα Χαμιλτονιανό κυκλικό γράφημα.

Τα γραφήματα Πέιλι είναι οιονεί τυχαία: ο αριθμός των φορών που κάθε πιθανό γράφημα σταθερής τάξης εμφανίζεται ως υπογράφημα ενός γραφήματος Πέιλι είναι (στο όριο για μεγάλα ) ο ίδιος όπως και για τα τυχαία γραφήματα, και μεγάλα σύνολα κορυφών έχουν περίπου τον ίδιο αριθμό ακμών όπως και στα τυχαία γραφήματα.

 Το γράφημα Πέιλι τάξης 9 είναι ένα τοπικά γραμμικό γράφημα, ένα γράφημα πύργου και το γράφημα του ντουοπρίσματος 3-3.
 Το γράφημα Πέιλι τάξης 13 έχει πάχος βιβλίου 4 και αριθμό ουράς 3.
 Το γράφημα Πέιλι τάξης 17 είναι ο μοναδικός μεγαλύτερος γράφος G  τέτοιος ώστε ούτε ο G ούτε το συμπλήρωμα του να περιέχει έναν πλήρη υπογράφο 4 κορυφών.  Προκύπτει ότι ο αριθμός ΡάμσεϊR(4, 4) = 18.
 Το γράφημα Πέιλι τάξης 101 είναι προς το παρόν το μεγαλύτερο γνωστό γράφημα G τέτοιο ώστε ούτε το G ούτε το συμπλήρωμά του να περιέχει ένα πλήρες υπογράφημα 6 κορυφών.
 Οι Σασουκάρα κ.ά. (1993) χρησιμοποιούν γραφήματα Πέιλι για να γενικεύσουν την κατασκευή της δέσμης Χόροκς-Μάμφορντ.

Διγράφημα  Πέιλι

Έστω q μια πρώτη δύναμη τέτοια ώστε q = 3 (mod 4). Έτσι, το πεπερασμένο σώμα τάξης q, Fq, δεν έχει τετραγωνική ρίζα του −1. Συνεπώς, για κάθε ζεύγος (a,b) διαφορετικών στοιχείων του Fq, είτε το a − b είτε το b − a, αλλά όχι και τα δύο, είναι τετράγωνο.  Το διγράφημα Πέιλι είναι το κατευθυνόμενο γράφημα με σύνολο κορυφών V = Fq και σύνολο τόξων

Το διγράφημα Πέιλι είναι ένα τουρνουά επειδή κάθε ζεύγος διαφορετικών κορυφών συνδέεται με ένα τόξο προς μία και μόνο μία κατεύθυνση.

Το διγράφημα  Πέιλι οδηγεί στην κατασκευή μερικών αντισυμμετρικών πινάκων διασκέψεων και γεωμετριών διπλών επιπέδων.

 Γένος 


Οι έξι γείτονες κάθε κορυφής στο γράφημα Πέιλι τάξης 13 συνδέονται σε έναν κύκλο, δηλαδή το γράφημα είναι τοπικά κυκλικό. Επομένως, αυτό το γράφημα μπορεί να ενσωματωθεί ως τριγωνοποίηση Γουίτνει ενός τόρου, στην οποία κάθε όψη είναι ένα τρίγωνο και κάθε τρίγωνο είναι μια όψη.  Γενικότερα, αν οποιοδήποτε γράφημα Πέιλι τάξης q μπορούσε να ενσωματωθεί έτσι ώστε όλες οι επιφάνειές του να είναι τρίγωνα, θα μπορούσαμε να υπολογίσουμε το γένος της προκύπτουσας επιφάνειας μέσω της χαρακτηριστικής του Όιλερ ως εξής . Ο Μπόγιαν Μοχάρ εικάζει ότι το ελάχιστο γένος μιας επιφάνειας στην οποία μπορεί να ενσωματωθεί ένα γράφημα Πέιλι είναι κοντά σε αυτό το όριο στην περίπτωση που το q  είναι τετράγωνο, και διερωτάται αν ένα τέτοιο όριο μπορεί να ισχύει γενικότερα. Συγκεκριμένα, ο Μοχάρ εικάζει ότι τα γραφήματα Πέιλι τετραγωνικής τάξης μπορούν να ενσωματωθούν σε επιφάνειες με γένος

όπου ο όρος o(1) μπορεί να είναι οποιαδήποτε συνάρτηση του q που μηδενίζεται στο όριο καθώς το q πηγαίνει στο άπειρο.

Ο Γουάιτ ( βρίσκει ενσωματώσεις των γραφημάτων Πέιλι τάξης q ≡ 1 (mod 8) οι οποίες είναι εξαιρετικά συμμετρικές και αυτο-δυϊκές, γενικεύοντας μια φυσική ενσωμάτωση του γραφήματος Πέιλι τάξης 9 ως ένα τετραγωνικό πλέγμα 3×3 σε έναν τόρο. Ωστόσο, το γένος των ενσωματώσεων του Γουάιτ είναι υψηλότερο κατά περίπου έναν παράγοντα τρία από το εικαζόμενο όριο του Μοχάρ.

 Εξωτερικοί σύνδεσμοι 
English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
ΑΓΓΛΟΕΛΛΗΝΙΚΟ. ΛΕΞΙΚΟ. ΜΑΘΗΜΑΤΙΚΩΝ. ΟΡΩΝ Αριάδνη Καλογερόπουλου. Μίλτος Γκίκας — Δ. Καραπαννακης — Μ. Λάμπρου. 
 Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
 Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
 Θεωρία Αριθμών και Εφαρμογές
 Υπολογιστική Θεωρία Αριθμών
 Καμπυλότητες και γεωμετρία του Riemann σε διαφορίσιμες πολλαπλότητες Εθνικό Αρχείο Διδακτορικών Διατριβών
 Μέθοδοι μηχανικής μάθησης βασισμένες σε έλεγχο μονοτροπικότητας Εθνικό Αρχείο Διδακτορικών Διατριβών
  Παράμετροι και Στατιστικά. Διωνυμική και Κανονική Κατανομή
 Wolfram Mathematica Online Integrator
  A Table of Integrals of the Error Functions

 Δείτε επίσης 
 Απαγορευτική αρχή του Πάουλι
 Μορφοκλασματική διάσταση
 Ομοπαραλληλική γεωμετρία
 Αλγεβρική θεωρία αριθμών
 Άρθουρ Στάνλεϋ Έντινγκτον
 Μοναδιαία βηματική συνάρτηση
 Σουμπραμανιάν Τσαντρασεκάρ
 Ευκλείδειος χώρος
 Αρχιμήδεια ιδιότητα
 Βαθμός (γραμμική άλγεβρα)
 Εφαρμοσμένα μαθηματικά
 Υπολογιστική ρευστοδυναμική
 Καμπυλότητα Γκάους
 Καρτεσιανό σύστημα συντεταγμένων
 Θεμελιώδες θεώρημα αριθμητικής
 Αλγεβρική γεωμετρία
 Σώμα διασπάσεως
 Συνήθης διαφορική εξίσωση
 Γραμμική απεικόνιση
 Νοεροί υπολογισμοί

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











 Παραπομπές 

 Finite Groups of Lie Type: Conjugacy Classes and Complex Characters (Wiley Classics Library) by Roger W. Carter, John Wiley & Sons Inc; New Ed edition (August 1993) ISBN 0-471-94109-3
 ISBN 978-0-8218-1426-0

R. Steinberg,   Collected Papers, Amer. Math. Soc.  (1997) ISBN 0-8218-0576-2  pp. 580–586

 Πηγές 





 Wendelin Degen, Lothar Profke: Grundlagen der affinen und euklidischen Geometrie. Teubner, Stuttgart 1976, ISBN 3-519-02751-8.
 Hans Freudenthal: Mathematik als pädagogische Aufgabe. Band 1. Klett, Stuttgart 1973, ISBN 3-12-983220-3.
 Thomas W. Hungerford: Algebra (= Graduate Texts in Mathematics. Bd. 73). 5th printing. Springer, New York NY u. a. 1989, ISBN 0-387-90518-9.

Κατηγορία:Θεωρία σωμάτων
Κατηγορία:Θεωρία ομάδων
Κατηγορία:Αλγεβρική θεωρία αριθμών
Κατηγορία:Θεωρία δακτυλίων
Κατηγορία:Αφηρημένη άλγεβρα