|
|
Alternující cesty v obarvených bodových množinách v konvexní poloze
Papáčková, Marie Guadalupe ; Valtr, Pavel (vedoucí práce) ; Soukup, Jan (oponent)
Tato práce se zabývá problémem nejdelších alternujících cest v obarve- ných bodových množinách v konvexní poloze, především v bodových množi- nách s n červenými a n modrými body. Cílem práce je shrnout hlavní výsledky dosažené v této oblasti a dát je do souvislostí. Nejprve uvedeme základní po- jmy a algoritmus pro hledání nejdelší alternující cesty na konkrétní bodové množině. Vyjádříme si l(n), největší číslo takové, že pro každé uspořádání 2n bodů s n červenými a n modrými body existuje alternující cesta o délce alespoň l(n). Ukážeme souvislost l(n) s problémem největšího separovaného párování. Uvedeme nejdůležitější dolní i horní odhady l(n), včetně nejlepších dosud publikovaných. Nakonec zobecníme problém pro více barev a ukážeme související problém o (anti)palindromech binárních cyklických slov.
|
|
|
On the structure and values of betweenness centrality in dense betweenness-uniform graphs
Ghanbari, B. ; Hartman, David ; Jelínek, V. ; Pokorná, Aneta ; Šámal, R. ; Valtr, P.
Betweenness centrality is a network centrality measure based on the amount of shortest paths passing through a given vertex. A graph is betweenness-uniform (BUG)if all vertices have an equal value of betweenness centrality. In this contribution, we focus on betweenness-uniform graphs with betweenness centrality below one. We disprove a conjecture about the existence of a BUG with betweenness value α for any rational numberαfrom the interval (3/4,∞) by showing that only very few betweenness centrality values below 6/7 are attained for at least one BUG. Furthermore, among graphs with diameter at least three, there are no betweenness-uniform graphs with a betweenness centrality smaller than one. In graphs of smaller diameter, the same can be shown under a uniformity condition on the components of the complement.
|
|
|
Konvexní mnohoúhelníky v hustotně omezených bodových množinách
Zálešák, Ondřej ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
Pro A, konečnou množinu bodů v Rd , nechť ∆(A) značí rozpětí A a je rovno poměru mezi maximální a minimální vzdáleností mezi dvěma body z A. Valtr (1992) dokázal, že pro množiny bodů v rovině a rozpětím rovným Θ(n 1 2 ) je veli- kost jejich největší podmnožiny v konvexní pozici Θ(n 1 3 ) v nejhorším případě. Ve stejném článku také uvádí rozšířený horní odhad na zaručenou velikost podmno- žiny v konvexní pozici pro množiny s asymptoticky vyšším rozpětím než n 1 2 , a stručnou konstrukci důkazu. Tato práce se věnuje konstrukci této detailně. Dále navazuje na nedávné výsledky pro množiny ve vyšších dimenzích, specificky pro- bírá, jestli by bylo možné rozšířit horní odhad v trojrozměrném prostoru pro vyšší rozpětí podobnou technikou, jako v rovinném případě. 1 Seznam použité literatury Valtr, P. (1992). Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2), 135-152. 2
|
|
| |
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent) ; Wood, David (oponent)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
|
Konvexně nezávislé podmnožiny konečných množin bodů
Zajíc, Vítězslav ; Valtr, Pavel (vedoucí práce) ; Cibulka, Josef (oponent)
Nech' fd(n), pro n > d ≥ 2, je nejmenší přirozené číslo takové, že každá množina fd(n) bod· v obecné poloze v Rd obsahuje n bod· v konvexní poloze. Nech' hd(n, k), pro n > d ≥ 2 a k ≥ 0, je nejmenší přirozené číslo takové, že v každé množině hd(n, k) bod· v obecné poloze v Rd existuje n bod· v konvexní poloze, uvnitř jejichž konvexního obalu je nejvýše k dalších bod·. Valtr ukázal, že h4(n, 0) neexistuje pro žádné n ≥ 249. V této práce předvedeme, že h4(n, 0) neexistuje pro žádné n ≥ 137. Ukážeme, že h3(8, k) ≤ f3(8) pro všechna k ≥ 26, h4(10, k) ≤ f4(10) pro všechna k ≥ 147 a h5(12, k) ≤ f5(12) pro všechna k ≥ 999. Dále nech' fd(k, n) je nejmenší číslo takové, že v každé množině fd(k, n) bod· v obecné poloze v Rd existuje n bod· jejichž konvexní obal má alespoň k vrchol·. Ukážeme, že pro n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , kde cd je konstanta závislá pouze na d.
|
|
| |
|
|
Extremal combinatorics of matrices, sequences and sets of permutations
Cibulka, Josef ; Valtr, Pavel (vedoucí práce) ; Füredi, Zoltán (oponent) ; Jelínek, Vít (oponent)
Název práce: Extremální kombinatorika matic, posloupností a množin permutací Autor: Josef Cibulka Katedra: Katedra aplikované matematiky Vedoucí disertační práce: Doc. RNDr. Pavel Valtr, Dr., Katedra aplikované ma- tematiky Abstrakt: V této práci se zabýváme oblastmi extremální teorie {0, 1}-matic, posloupností a množin permutací, které mají četná využití v oblasti kombina- torické a výpočetní geometrie. VC-dimenze množiny n-prvkových permutací P je největší celé číslo k takové, že množina zúžení permutací z P na některou k-tici pozic je množina všech k-prvkových permutací. Projdeme všemi třemi zmíněnými oblastmi extremální kombinatoriky, abychom dokázali horní a dolní meze, rostoucí kvaziexponenciálně v n, na maximální možnou velikost množiny n- permutací s VC-dimenzí shora omezenou konstantou. Tento výsledek využívá ve svém článku Jan Kynčl k výraznému snížení horního odhadu na počet tříd slabého izomorfismu úplného topologického grafu na n vrcholech. Dále pro některé, ze- jména permutační, matice M dokážeme nové meze na počet jedniček v M-prosté {0, 1}-matici velikosti n × n. Například pro každé k zkonstruujeme matici s k2 n/2 jedničkami prostou jedné konkrétní permutační matice velikosti k ×...
|
|
|
Problems in discrete geometry
Patáková, Zuzana ; Matoušek, Jiří (vedoucí práce) ; Bárány, Imre (oponent) ; Valtr, Pavel (oponent)
dizertační práce Problémy diskrétní geometrie Zuzana Patáková V této práci se věnujeme třem různým problémům z oblasti diskrétní geometrie. Společným pojítkem těchto problémů je, že jejich řešení využívá algebraické metody. První problém se zabývá tzv. polynomiální metodou, která konečnou množinu bodů rozdělí pomocí nulové množinu polynomu. Limitujícím fak- torem této metody je, co dělat s body, které leží v nulové množině získaného polynomu? V práci představujeme obecnou verzi, která řeší popsanou situaci, a jako aplikaci uvádíme nový algoritmus pro tzv. semialgebraický range searching problém. V druhé části práce se věnujeme studiu Ramseyových funkcí semialge- braických predikátů. Conlon, Fox, Pach, Sudakov a Suk zkonstruovali první příklady semialgebraických predikátů s Ramseyovou funkcí zespoda odhad- nutou věžovitou funkcí. My snížíme dimenzi příslušného prostoru v jejich konstrukci a jako důsledek ukážeme novou geometrickou větu Ramseyova typu s velkou Ramseyovou funkcí. V poslední části se zabýváme samodlážditelnými simplexy. Simplex S je k-samodlážditelný, pokud je sjednocením k navzájem shodných simplexů s disjunktními vnitřky, které jsou navíc podobné simplexu S. V...
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce) ; Valtr, Pavel (oponent)
Ramseyova teorie studuje vnitřní homogenitu matematických struktur (grafů, číselných oborů), jejichž části (podgrafy, podmnožiny) jsou libovolně obarveny. Často platí, že je-li studovaný objekt dostatečně velký, lze v něm najít určitý jednobarevný podobjekt. Kombinatorické hry jsou hry dvou hráčů s plnou informací, kde záleží pouze na jejich inteligenci. Teorie kombinatorických her studuje především otázky existence vyhrávajících či neprohrávajících strategií. Vezmeme-li ramseyovskou větu a necháme-li objekt, který tato věta studuje, střídavě barvit dvěma hráči, jejichž cílem je vytvořit určitý monochromatický podobjekt, dostaneme kombinatorickou hru. Předmětem našeho zájmu je jednak nejmenší velikost objektu, při které platí ramseyovská věta, tzv. ramseyovské číslo, a jednak nejmeněí velikost téhož objektu, při které má první hráč vyhrávající strategii v příslušné kombinatorické hře, tzv. herní číslo. V této práci popisujeme takové ramseyovské věty, u nichž je ramseyovské číslo podstatně větší než číslo herní. To znamená, že podáváme důkazy existence vyhrávajících strategií prvního hráče spolu s horními odhady na ramseyovská a herní čísla a obě čísla porovnáváme.
|
host ::
RSS.