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

Δεκέμβριος 1, 2010

Πόσες μοναδιαίες αποστάσεις;

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 9:30 μμ

Άμεσα συνδεδεμένο με το προηγούμενο πρόβλημα είναι το εξής:
Δείξτε ότι το πλήθος των ζευγαριών σημείων τού E τα οποία έχουν μεταξύ τους απόσταση 1 είναι μικρότερο από CN^{3/2}.

Advertisements

4 Σχόλια »

  1. «Ρίχνω» μια ιδέα που δίδει ένα άνω φράγμα που είναι κοντά στο ζητούμενο.
    Ελπίζω να μη σκοτώνω μύγα με ατομική βόμβα. Θα χρησιμοποιήσω το θεώρημα του Turan.

    http://en.wikipedia.org/wiki/Turán's_theorem

    Το θεώρημα του Turan λέει ότι το μέγιστο πλήθος ακμών σε ένα γράφημα που αποτελείται
    από n κορυφές και δεν περιέχει πλήρες υπογράφημα r+1 κορυφών είναι
    \displaystyle (1-\frac{1}{r}) \frac{n^2}{2}

    Δοθέντος συνόλου Ε με n σημεία, φτιάξτε γράφημα G ως εξής:
    Για κάθε σημείο του Ε τοποθετήστε μια κορυφή και ενώστε δυο κορυφές με μια ακμή αν και
    μόνον αν η απόσταση των αντίστοιχων σημείων του Ε ισούται με 1.
    Παρατηρήστε ότι το πλήθος των ζευγών του Ε που έχουν απόσταση 1 ισούται με τον αριθμό
    των ακμών του G. Επίσης, το G δεν δύναται να περιέχει πλήρες υπογράφημα με 4 κορυφές.
    Το θεώρημα του Turan δίδει ότι το πλήθος των ακμών του G είναι το πολύ \frac{n^2}{3}.

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιουνίου 25, 2013 @ 8:36 μμ

  2. Σωστά, εδώ όμως μας ενδιαφέρει η τάξη μεγέθους δηλαδή ο εκθέτης, όχι η σταθερά.
    Σαν τάξη μεγέθους, το n^2 είναι η προφανής απάντηση όταν μιλάμε για πλήθος ζευγαριών με οποιαδήποτε ιδιότητα.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Ιουνίου 26, 2013 @ 9:46 πμ

  3. Θα ρίξω μία ακόμη ατομική. Την τελευταία..
    Θα χρησιμοποιήσω το θεώρημα των Kovari-Sos-Turan.

    http://www.math.bgu.ac.il/~shakhar/teaching/combinatorial_geometry_files/Lecture11.pdf

    Το θεώρημα αυτό λέει ότι το μέγιστο πλήθος ακμών, σε ένα γράφημα που έχει n κορυφές και δεν
    περιέχει πλήρες διμερές υπογράφημα K_{r,s}, 1\leq r\leq s, είναι τάξεως O(n^{2-\frac{1}{r}}).

    Δοθέντος συνόλου Ε, φτιάξτε γράφημα G όπως στο σχόλιο 1.
    Αν το G δεν περιέχει K_{2,3}, τότε το ζητούμενο έπεται απο το θεώρημα KST.

    Έστω ότι το G περιέχει ένα K_{2,3}.
    Έστω Α={α,β} το μέρος του G που έχει τις δύο κορυφές και Β το μέρος με τις 3 κορυφές.
    Αν πάμε στο Ε και φέρουμε κύκλους ακτινας 1 με κέντρο τα σημεια που αντιστοιχουν στις κορυφές α και β,
    τότε οι κύκλοι αυτοί είναι διαφορετικοί και τέμνονται σε 3 σημεία, άτοπο!

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιουνίου 28, 2013 @ 1:23 πμ

  4. Σωστά. Ίσως μπορούμε να αποφύγουμε τη ραδιενέργεια.
    Αν E=\{x_i:1\leq i\leq N\} θέτουμε
    \mathcal A=\{(i,j,k):|x_i-x_k|=|x_j-x_k|=1\} και
    A_i=\{j:|x_i-x_j|=1\}. Τότε η ζητούμενη τάξη μεγέθους είναι
    \displaystyle \sum_{i}|A_i|\leq \sqrt N\left(\sum_i|A_i|^2\right)^{1/2}=\sqrt N|\mathcal A|^{1/2}\lesssim \sqrt N\cdot N=N^{3/2}.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Ιουνίου 28, 2013 @ 7:45 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: