פונקציית דן – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 1:
'''פונקציית דן''' של [[חבורה נוצרת סופית]] היא פונקציה המתארת את אי-השוויון האיזופרימטרי בגרףב[[גרף קיילי]] של החבורה, ומודדת את הסיבוכיות של פתרון [[בעיית המילה]] בחבורה זו.
 
תהי G חבורה הנוצרת על ידי קבוצה X עם [[ייצוג של חבורה|קבוצת יחסים]] R. כל מילה w המייצגת את איבר היחידה אפשר להציג כמכפלה של צמודים <math>\ w = (p_1 r_1 p_1^{-1})\cdots (p_t r_t p_t^{-1})</math>, כאשר <math>\ r_1,\dots,r_t \in R^{\pm 1}</math> הם יחסים. המספר המינימלי של יחסים כאלה הוא ה'''שטח''' של w. פונקציית דן המתאימה ל-X מוגדרת כך ש-<math>\ f(n)</math> הוא השטח הגדול ביותר של מילים באורך n.