Προβλήματα Μαθηματικών

Απριλίου 6, 2008

Το πεπερασμένο και το άπειρο

Κατηγορίες: Άλυτα Προβλήματα, Με υπόδειξη — Mihalis Kolountzakis @ 3:27 μμ

Ένα γράφημα G είναι ένα σύνολο V από κορυφές οι οποίες μπορεί ανά δύο να συνδέονται με μια ακμή. (Αυτό κωδικοποιείται στο σύνολο E των ακμών που είναι ένα σύνολο από διμελή υποσύνολα του V.)

Ένα απλό γράφημα

Ένας χρωματισμός ενός γραφήματος με {r} χρώματα είναι μια απεικόνιση

\displaystyle \chi:V \to \{1,\ldots,r\}

τέτοια ώστε αν οι κορυφές u, v \in V συνδέονται με ακμή στο γράφημα (αν δηλ. \{u,v\}\in E) τότε \chi(u) \neq \chi(v). Κορυφές δηλ. που συνδέονται με ακμή πρέπει να έχουν διαφορετικό χρώμα.

Τέλος, ένα υπογράφημα ενός γραφήματος G προκύπτει αν κρατήσουμε ένα υποσύνολο μόνο των κορυφών του και τις ακμές που υπάρχουν στο G.

Σας δίδεται ένα γράφημα G με άπειρο σύνολο κορυφών V=\{1,2,3,\ldots\} και με την ιδιότητα ότι όλα τα πεπερασμένα υπογραφήματά του μπορούν να χρωματιστούν με 10 χρώματα. Δείξτε ότι το ίδιο ισχύει και για το άπειρο γράφημα G.

2 σχόλια »

  1. Υπόδειξη:

    Το πρόβλημα αυτό είναι πολύ πιο σημαντικό και πολύ πιο γενικό απ’ ό,τι ίσως φαίνεται σε πρώτη ανάγνωση. Θα δείτε ότι η λύση μπορεί να προσαρμοστεί σε πολλές περιπτώσεις όπου υπάρχει λύση για “οσοδήποτε μεγάλα πεπερασμένα κομμάτια” και επιθυμούμε λύση “για το άπειρο”.

    Προσπαθείστε να βρείτε ένα χρωματισμό του άπειρου γραφήματος ως εξής: ας είναι {G_n} το πεπερασμένο υπογράφημα του {G} που ορίζεται από τις κορυφές {1,2,\ldots,n} και τις ακμές του {G} που τις ενώνουν μεταξύ τους, και ας είναι

    {\chi_n:\{1,2,\ldots,n\} \to \{1,2,\ldots,r\}}

    ένας καλός χρωματισμός του {G_n} (που αντιστοιχεί δηλ. διαφορετικά χρώματα σε κορυφές που συνδέονται με ακμή στο {G_n}).

    Τα στοιχεία της άπειρης ακολουθίας

    { \chi_1(1), \chi_2(1), \ldots, \chi_n(1), \ldots }

    παίρνουν το πολύ {r < \infty} διαφορετικές τιμές, άρα υπάρχει κάποιο χρώμα {c_1 \in \{1,2,\ldots r \}} που εμφανίζεται σε αυτή την ακολουθία άπειρες φορές. Επιλέξτε το {c_1} ως χρώμα της κορυφής 1.

    Σχόλιο από Mihalis Kolountzakis — Απριλίου 20, 2008 @ 11:04 μμ

  2. Υπόδειξη:

    Έχοντας επιλέξει το c_1 ως το χρώμα της κορυφής 1, “πετάξτε” από το σύνολο των φυσικών αριθμών n όλα εκείνα τα n για τα οποία ο χρωματισμός \chi_n δίνει στην κορυφή 1 χρώμα διαφορετικό από το c_1. Από τον τρόπο επιλογής του χρώματος c_1 (δείτε αμέσως προηγούμενο σχόλιο-υπόδειξη) προκύπτει ότι απομένουν άπειρα ακόμη n. Από δω και πέρα δουλεύετε μόνο με αυτά τα n.

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 8, 2009 @ 10:19 μμ


Κανάλι RSS για τα σχόλια του άρθρου. TrackBack URI

Γράψτε ένα σχόλιο

Για να σχολιάσετε πρέπει να συνδεθείτε.

Blog στο WordPress.com.