Thrackl
Thrackle to osadzenie wykresu na płaszczyźnie w taki sposób, że każda krawędź jest łukiem Jordana , a każda para krawędzi spotyka się dokładnie raz . Krawędzie mogą stykać się we wspólnym punkcie końcowym lub, jeśli nie mają wspólnych punktów końcowych, w punkcie w ich wnętrzach. W tym drugim przypadku skrzyżowanie musi być poprzeczne .
Liniowe dreszcze
Trakla liniowa to kaczka narysowana w taki sposób, że jej krawędzie są odcinkami linii prostych. Jak Paul Erdős , każdy liniowy drań ma co najwyżej tyle krawędzi, ile wierzchołków. Jeśli wierzchołek v jest połączony z trzema lub więcej krawędziami vw , vx i vy , przynajmniej jedna z tych krawędzi (powiedzmy vw ) leży na linii oddzielającej dwie inne krawędzie. Wtedy w musi mieć stopień jeden, ponieważ żaden odcinek liniowy kończący się na w , inny niż vw , może dotykać zarówno vx, jak i vy . Usunięcie w i vw daje mniejsze drżenie, bez zmiany różnicy między liczbą krawędzi i wierzchołków. Po usunięciach takich jak to prowadzimy do pułapki, w której każdy wierzchołek ma co najwyżej dwóch sąsiadów, zgodnie z lematem o uzgadnianiu liczba krawędzi jest co najwyżej liczbą wierzchołków. Na podstawie dowodu Erdősa można wywnioskować, że każdy liniowy trop jest pseudolasem . Każdy cykl o nieparzystej długości można ułożyć tak, aby tworzył liniową pętlę, ale nie jest to możliwe w przypadku cyklu o parzystej długości, ponieważ jeśli jedna krawędź cyklu jest wybrana arbitralnie, to pozostałe wierzchołki cyklu muszą leżeć naprzemiennie po przeciwnych stronach linii przez tę krawędź.
Micha Perles przedstawił kolejny prosty dowód na to, że kajdany liniowe mają co najwyżej n krawędzi, opierając się na fakcie, że w kajdankach liniowych każda krawędź ma punkt końcowy, w którym krawędzie rozciągają się pod kątem co najwyżej 180 ° i dla którego jest to najbardziej zgodne z ruchem wskazówek zegara krawędź w tej rozpiętości. W przeciwnym razie istniałyby dwie krawędzie, padające na przeciwne punkty końcowe krawędzi i leżące po przeciwnych stronach linii przechodzącej przez krawędź, które nie mogłyby się przecinać. Ale każdy wierzchołek może mieć tę właściwość tylko w odniesieniu do pojedynczej krawędzi, więc liczba krawędzi jest co najwyżej równa liczbie wierzchołków.
Jak zauważył również Erdős, zbiór par punktów realizujących średnicę zbioru punktowego musi tworzyć liniowy łańcuch: żadne dwie średnice nie mogą być od siebie rozłączne, ponieważ gdyby tak było, to ich cztery punkty końcowe miałyby parę w większej odległości od siebie niż dwie rozłączne krawędzie. Z tego powodu każdy zbiór n punktów na płaszczyźnie może mieć co najwyżej n par diametralnych, odpowiadając na pytanie postawione w 1934 roku przez Heinza Hopfa i Erikę Pannwitz . Andrew Vázsonyi przypuszczał ograniczenia liczby par średnic w wyższych wymiarach, uogólniając ten problem.
W geometrii obliczeniowej metodę obracania suwmiarki można wykorzystać do utworzenia liniowego mostka z dowolnego zestawu punktów w położeniu wypukłym , łącząc pary punktów, które wspierają równoległe linie styczne do wypukłej otoczki punktów. Ten wykres zawiera jako podwykres pary średnic.
Średnice wielokątów Reinhardta tworzą ścieżki liniowe. Wyliczenie liniowych kajdanek może być użyte do rozwiązania największego problemu małego wielokąta , polegającego na znalezieniu n -kąta o maksymalnym polu w stosunku do jego średnicy.
Przypuszczenie Thrackla
Czy thrackle może mieć więcej krawędzi niż wierzchołków?
John H. Conway wywnioskował, że w każdym fragmencie liczba krawędzi jest co najwyżej równa liczbie wierzchołków. Sam Conway użył terminologii ścieżki i plamy (odpowiednio dla krawędzi i wierzchołków ), więc hipoteza Conwaya dotycząca thrackle'a została pierwotnie wyrażona w postaci, że każdy thrackle ma co najmniej tyle samo punktów, co ścieżek. Conway zaoferował nagrodę w wysokości 1000 dolarów za udowodnienie lub obalenie tej hipotezy, jako część zestawu problemów z nagrodami, w tym również problem 99-wykresów Conwaya , minimalny odstęp między Danzer ustawia , a zwycięzca monety Sylver po ruchu 16.
Równoważnie, hipotezę thrackle można sformułować, ponieważ każdy thrackle jest pseudolasem . Mówiąc dokładniej, jeśli hipoteza thrackla jest prawdziwa, thrackle można dokładnie scharakteryzować na podstawie wyniku Woodalla: są to pseudolasy, w których nie ma cyklu o długości czterech i co najwyżej jednego cyklu nieparzystego.
Udowodniono, że każdy wykres cykli inny niż C4 ma osadzenie thrackle'a, co pokazuje, że przypuszczenie jest ostre . Oznacza to, że istnieją kajdany mające taką samą liczbę plamek jak ścieżki. Z drugiej strony najgorszy scenariusz jest taki, że liczba miejsc jest dwukrotnie większa niż liczba ścieżek; jest to również osiągalne.
Wiadomo, że hipoteza thrackle'a jest prawdziwa dla thrackles narysowanych w taki sposób, że każda krawędź jest krzywą x -monotoniczną, przecinaną co najwyżej raz przez każdą pionową linię.
Znane granice
Lovász, Pach i Szegedy (1997) udowodnili, że każdy dwudzielny thrackle jest grafem planarnym , chociaż nie jest rysowany w sposób planarny. W konsekwencji pokazują, że każdy graf z n wierzchołkami ma co najwyżej 2 n - 3 krawędzie. Od tego czasu granica ta była kilkakrotnie poprawiana. Po pierwsze, został poprawiony do 3 ( n - 1)/2, a kolejna poprawa doprowadziła do granicy około 1,428 n . Co więcej, metoda zastosowana do udowodnienia tego ostatniego wyniku daje dla dowolnego ε > 0 skończony algorytm, który albo poprawia wiązanie z (1 + ε) n lub obala przypuszczenie. Obecny rekord należy do Fulka i Pacha (2017) , którzy pobili 1,3984 n .
Jeśli przypuszczenie jest fałszywe, minimalny kontrprzykład miałby postać dwóch parzystych cykli o wspólnym wierzchołku. Dlatego, aby udowodnić hipotezę, wystarczyłoby udowodnić, że grafów tego typu nie można narysować jako drzazg.
Linki zewnętrzne
- thrackle.org — strona internetowa poświęcona problemowi