השערת צ'רני

בתורת האוטומטים הסופיים, השערת צ'רני (באנגלית: Černý conjecture; על שם יאן צ'רני) היא השערה על האורך המקסימלי של מלה מסנכרנת, באוטומט שיש בו מלה כזו. ההשערה קובעת שאם X היא משפחה של פונקציות מקבוצה בת n נקודות לעצמה, ואפשר להרכיב מ-X באמצעות הרכבה פונקציה קבועה, אז יש הרכבה כזו באורך שאינו עולה על $\ (n-1)^2$ ‏‏.

את החסם שההשערה מציעה אי-אפשר לשפר. לדוגמה, מן התמורה $\ a=(1 2 \cdots n)$ והפונקציה b המעבירה כל נקודה לעצמה, פרט לכך ש- $\ b(1)=2$, אפשר להגיע לערך קבוע באמצעות הסדרה $\ b(a^{n-1}b)^{n-2}$, ולא בשום דרך קצרה יותר.

ידוע שההשערה נכונה אם הקבוצה X כוללת מחזור באורך n. החסם העליון הטוב ביותר הידוע כיום הוא $\ (n^3-n)/6$.

ראו גם

• בעיית צביעת הדרכים