Μονοχρωματικό k-πλευρο

[miltosk]

Έστω δοσμένος θετικός ακέραιος. Έστω ακόμη σημεία στο επίπεδο ανά 3 μη συνευθειακά. Φέρνουμε όλα τα ευθύγραμμα τμήματα που τα ενώνουν και τα βάφουμε με χρώματα. Να βρεθεί ο ελάχιστος ώστε ανεξάρτητα από τον χρωματισμό που έγινε να υπάρχει -πλευρο, κυρτό ή μη κυρτό, του οποίου οι πλευρές έχουν όλες το ίδιο χρώμα.
ΔΕΝ ΕΧΩ ΛΥΣΗ Edit: ΔΕΝ ΞΕΡΩ ΑΝ ΕΙΝΑΙ ΕΠΙΛΥΣΙΜΟ (αν πράγματι δεν είναι χίλια συγγνώμη σε όσους ταλαιπώρησα άδικα)
Ίσως πρόκειται για γνωστό πρόβλημα. Ασχολούμουν με την περίπτωση που (όπου νομίζω προκύπτει ) σε συγκεκριμένο πρόβλημα και έπεσα πάνω στον Ramsey και σκέφτηκα αν υπάρχει γενίκευση (ο Ramsey μίλαγε για πλήρης υπογράφο αν κατάλαβα καλά, νομίζω αυτό που ζητάω είναι πιο απλό).

[Demetres]

Ουσιαστικά ζητάς το όπου το εμφανίζεται φορές. (Χρησιμοποίησα τον συμβολισμό της τρίτης παραγράφου εδώ.)

Για προκύπτει . Υπάρχει απόδειξη στην παραπομπή. Δεν νομίζω να είναι γνωστοί οι αριθμοί για . Π.χ. στο άρθρο εδώ (σελίδα 39) λέει ότι οπότε είμαστε ακόμη αρκετά μακριά από το .

[Demetres]

Όπως με ενημέρωσε ο Μίνος σε π.μ. δεν διάβασα σωστά το ζητούμενο. Ουσιαστικά ζητείται το όπου το γράφημα (κύκλος μήκους ) εμφανίζεται φορές.

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

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