Activities This Week

We show how to decompose the moduli-space of shapes of polyhedra and how such a decomposition can be used to solve geometric realization problems.

In 1975, S. Kakutani introduced a splitting procedure which generates a sequence of partitions of the unit interval [0,1], and showed that this sequence is uniformly distributed in [0,1]. We present generalizations of this procedure in higher dimensions, which correspond to constructions used when defining substitution and multiscale substitution tilings of Euclidean space. We prove uniform distribution of these sequences of partitions using new path counting results on graphs and establish Kakutani’s result as a special case.

סדרת דה ברויין מסדר $n$ מעל אלפבית $[k]$ היא סדרה באורך $k^n$ אשר מכילה כל מחרוזת באורך $n$ מהאלפבית כתת-מילה בדיוק פעם אחת.

בהרצאה נתמקד בסדרת בסדרת דה ברויין הנקראת “העדף מקסימום” שהיא הראשונה בסדר הלקסיקוגרפי. נתמקד בבעיית החישוב היעיל של הסדרה: בהנתן מילה באורך $n$, נראה כיצד לבנות את האות הבאה בסדרה אחרי המקום (היחיד) שבו מופיעה המילה באופן יעיל (בלי זיכרון נוסף ורק במעבר יחיד על הקלט).

הטריק המעניין בהרצאה יהיה שנראה איך לפתור את הבעיה שהוצגה למעלה באמצעות משחק קומבינטורי. נתאר את המשחק (שלדעתנו מעניין גם בפני עצמו) ונראה כי המהלך האופיטמלי למשחק יוצר את סדרת דה ברויין העדף-מקסימום. בנוסף, נראה איך האסטרטגיות ה”לא-מפסידות” ניתנות לחישוב בצורה יעילה (באמצעות אסטרטגיות חסרות-זכרון), מה שמניב עבורינו פתרון לבעיית החישוב היעיל של הסדרה.

ההרצאה מיועדת למי שמתעניין בפתרון משחקים קומבינטוריים בסגנון שח-מט, איקס-עיגול או גו, למי שמתעניין בתורת הקידוד ובקומבינטוריקה של סדרות ולמי שרוצה לשמוע על קשר מעניין בין השניים. לא נדרש ידע קודם, מעבר למושגים בסיסיים במתמטיקה.