סידור ישרים
בגאומטריה קומבינטורית, סידור ישרים הוא מערכת מסומנת של ישרים במישור האוקלידי או הפרויקטיבי, שכל שניים מהם נחתכים. מערכות כאלה נלמדות באמצעות מודלים קומבינטוריים כגון סידורים של פסאודו-ישרים (ראו להלן). ההכללה לסידור של על-מישורים מופיעה בהקשרים שונים בגאומטריה אלגברית ובתורת החבורות, למשל בהצגות של חבורות קוקסטר. משפט Folkman-Lawrence מספק קשר בין סידורי ישרים (ופסאודו-ישרים) לבין מטרואידים.
פסאודו-ישרים עריכה
פסאודו-ישר הוא מסילה חלקה ופשוטה במישור, המשיקה באינסוף ובמינוס אינסוף לשני ישרים מקבילים. פסאודו-ישרים מאפשרים ללמוד את התכונות הקומבינטוריות של סידור ישרים, תוך הרפיה של אילוצים גאומטריים. כמה מהשאלות העיקריות בתחום זה נוגעות למידה שבה אפשר לממש סידור של פסאודו-ישרים באמצעות ישרים.
סידור של פסאודו-ישרים הוא מערכת מסומנת של פסאודו-ישרים, שבה כל זוג פסאודו-ישרים נפגש בדיוק פעם אחת, ובה הם חוצים זה את זה. סידור שבו כל הפסאודו-ישרים נפגשים בנקודה אחת נקרא עפרון (pencil), והוא נחשב לטריוויאלי. סידור של פסאודו-ישרים משרה קומפלקס תאי שהקודקודים שלו הם התחומים המתקבלים מהוצאת הסידור מן המישור, והקשתות שלו מחברות תחומים שיש להם שפה משותפת (שאינה נקודה). שני סידורים שהקומפלקסים שלהם איזומורפיים נקראים איזומורפיים. נקודות החיתוך הן קודקודים של הסידור. קודקוד שנפגשים בו בדיוק שני פסאודו-ישרים הוא קודקוד פשוט; קודקוד שאינו פשוט הוא קודקוד מרובה. סידור שכל הקודקודים שלו פשוטים הוא סידור פשוט. ידוע שהלוגריתם של מספר הסידורים האפשריים של n פסאודו-ישרים חסום בין שתי כפולות חיוביות של n^2.
סידור שבו כל אחד מהפסאודו-ישרים הוא מונוטוני בציר ה-x נקרא סידור אוקלידי.
סידור אוקלידי שבו כל אחד מן הפסאודו-ישרים מקביל לציר ה-x בכל מקום פרט לסביבה של הקודקודים נקרא דיאגרמת תיילים (wiring diagram) או רשת מיון פרימיטיבית. כל סידור של פסאודו-ישרים איזומורפי לדיאגרמת תיילים.
סידור של פסאודו-ישרים הוא בר-מתיחה (stretchable) אם הוא איזומורפי לסידור ישרים. כל סידור של עד 8 ישרים ניתן למתיחה, אבל יש סידור פשוט ב-9 פסאודו-ישרים שאינו כזה. כל סידור שהתאים שלו משולשים ומרובעים (ואפילו אם יש תא אחד גדול יותר -[1]) הוא ניתן למתיחה. ההכרעה האם סידור פשוט ניתן למתיחה היא NP-קשה.
תמורות עריכה
כאשר מטילים סידור של פסאודו-ישרים על ישר קבוע, מתקבלת בכל נקודה של הישר תמורה של המסילות, המתארת את מרחקן המכוון מן הישר. התמורה משתנה על ידי החלפה של כמה מסילות סמוכות בכל קודקוד. התמורות המתקבלות באינסוף ובמינוס אינסוף מנוגדות זו לזו. הסתכלות פרויקטיבית מאפשרת להשלים את סדרת התמורות על ידי תמורות מנוגדות, והמעבר בחזרה למישור האוקלידי, הכרוך בבחירת "הנקודה באינסוף", משמעו חיתוך של מעגל התמורות במקום כלשהו. סדרה כזו של תמורות נקראת סדרה מותרת (allowable sequence).
תחומים קמורים עריכה
תהי p נקודה מחוץ לפסאודו-ישרים המרכיבים סידור A. ה-p-קמור של תת-סידור B כולל את הישרים ש-B מפריד ביניהם לבין p. משפט Helly ומשפט Tverberg עוסקים בהרחבת סידור פסאודו-ישרים נתון על-ידי פסאודו-ישר הנמצא ב-p-קמור של נקודה נתונה.
הערות שוליים עריכה
- ^ Euclidean arrangements of n pseudolines with one n-gon are stretchable, 2011