Personal tools
Document Actions

734. Αλγεβρική Συνδυαστική



1. Στόχοι

Αλγεβρική Συνδυαστική είναι η περιοχή των μαθηματικών η οποία είτε χρησιμοποιεί εργαλεία από την άλγεβρα ή συναφείς κλάδους των θεωρητικών μαθηματικών για να επιλύσει καθαρά συνδυαστικά προβλήματα, είτε χρησιμοποιεί συνδυαστικές τεχνικές για να επιλύσει προβλήματα αυτών των κλάδων. Στόχος του μαθήματος είναι να αναδείξει αυτή την αμφίδρομη σχέση μέσα από συγκεκριμένα παραδείγματα προβλημάτων, προϋποθέτοντας τις ελάχιστες δυνατές εξειδικευμένες γνώσεις άλγεβρας ή συνδυαστικής. Πιο συγκεκριμένα, στόχος είναι να εξοικειωθούν

(α) οι φοιτητές της θεωρητικής κατεύθυνσης με τις συνδυαστικές τεχνικές και τη σημασία τους στα θεωρητικά μαθηματικά και

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

2. Περιεχόμενο του μαθήματος

Επιλογή από τα παρακάτω θέματα:

  • Σύντομη μελέτη (επανάληψη) βασικών αρχών και τεχνικών απαρίθμησης, με έμφαση στις συνδυαστικές αποδείξεις (μέθοδος της 1-1 αντιστοιχίας) και τη μέθοδο των γεννητριών συναρτήσεων. Παραδείγματα (σύνολα, αναδιατάξεις, διαμερίσεις ακεραίων κλπ) (2 εβδομάδες).
  • Οι μεταθέσεις ως αναδιατάξεις, στοιχεία της συμμετρικής ομάδας, ενώσεις ξένων κύκλων (κυκλική δομή), 0-1 πίνακες, αύξοντα δένδρα κλπ. Απαρίθμηση μεταθέσεων (αντιστροφές, κύκλοι, κάθοδοι, υπερβάσεις, σταθερά σημεία, εναλλασόμενες μεταθέσεις, πρωτεύων δείκτης και το Θεώρημα του MacMahon. Μεταθέσεις συλλογών, αντιστροφές και οι q-διωνυμικοί συντελεστές. Young tableaux και ο τύπος hook-length, η αντιστοιχία Robinson-Schensted, κλάσεις ισοδυναμίας Knuth, το παιχνίδι jeu de taquin του Schutzenberger, εφαρμογές σε μονότονες υποακολουθίες μεταθέσεων, το tableau εκκένωσης και το Θεώρημα του Schutzenberger για την ανάστροφη και αντίστροφη μετάθεση. Η ασθενής διάταξη Bruhat και εφαρμογές στην απαρίθμηση reduced decompositions μεταθέσεων) (7 εβδομάδες).
  • Στοιχεία αλγεβρικής θεωρίας γραφημάτων, ο πίνακας της γειτονικότητας ενός (κατευθυνόμενου ή μη) γραφήματος, ιδιοτιμές και απαρίθμηση περιπάτων. Ο πίνακας Laplace, παράγοντα δένδρα και το Θεώρημα Πίνακα-Δένδρου, εφαρμογές σε πλήρη (τύπος του Cayley) και διμερή γραφήματα. Περίπατοι στο γράφημα (σύνδεσμο) του Young και διαφορικές μερικές διατάξεις. Εφαρμογές της γραμμικής άλγεβρας σε θέματα όπως: η μονοτροπία για τους q-διωνυμικούς συντελεστές, προβλήματα ύπαρξης για ζευγαρώματα γραφημάτων, το Θεώρημα του Sperner για υποσύνολα του {1, 2,...,n} και γενικεύσεις (4 εβδομάδες).

3. Βοηθήματα

Χ. Α. Αθανασιάδης, Εισαγωγή στην Αλγεβρική Συνδυαστική, Πανεπιστήμιο Αθηνών, 2008 (ps αρχείο, Κεφάλαια 1-2, 61 σελίδες).

4. Ενδεικτική βιβλιογραφία

  • N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974; second edition, 1993.
  • M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, London, New York, 2004.
  • W. Fulton, Young Tableaux, Student Texts, London Mathematical Society, Cambridge University Press, Cambridge, 1997.
  • C. D. Godsil, Algebraic Combinatorics, Chapman & Hall/CRC, New York, 1993.
  • B. E. Sagan, The symmetric group: Representations, Combinatorial Algorithms and Symmetric Functions, Graduate Texts in Mathematics 203, Springer-Verlag, New York, 2001.
  • R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge, 1998.
  • R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

5. Ηλεκτρονική σελίδα του μαθήματος

Περισσότερες πληροφορίες στην προσωπική σελίδα του διδάσκοντος.


Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: