|
|
Fractionally Isomorphic Graphs and Graphons
Hladký, Jan ; Hng, Eng Keat
Fractional isomorphism is a well-studied relaxation of graph isomorphism with a very rich theory. Grebík and Rocha [Combinatorica 42, pp 365–404 (2022)] developed a concept of fractional isomorphism for graphons and proved that it enjoys an analogous theory. In particular, they proved that if two sequences of graphs that are fractionally isomorphic converge to two graphons, then these graphons are fractionally isomorphism. Answering the main question from ibid, we prove the converse of the statement above: If we have two fractionally isomorphic graphons, then there exist sequences of graphs that are fractionally isomorphic converge and converge to these respective graphons. As an easy but convenient corollary of our methods, we get that every regular graphon can be approximated by regular graphs.
|
|
|
Permutation Flip Processes
Hladký, Jan ; Řada, Hanka
We introduce a broad class of stochastic processes on permutations which we call flip processes. A single step in these processes is given by a local change on a randomly chosen fixed-sized tuple of the domain. We use the theory of permutons to describe the typical evolution of any such flip process started from any initial permutation. More specifically, we construct trajectories in the space of permutons with the property that if a finite permutation is close to a permuton then for any time it stays with high probability is close to this predicted trajectory. This view allows to study various questions inspired by dynamical systems.
|
|
| |
|
| |
|
|
Structural properties of graphs---probabilistic and deterministic point of view
Hladký, Jan ; Šámal, Robert (vedoucí práce) ; Pawlas, Zbyněk (oponent)
V práci zkoumáme bipartitní podgrafy náhodného kubického grafu. Ukážeme, že hranově maximální bipartitní podgraf náhodného kubického grafu na n vrcholech má asymptoticky skoro jistě méně než 3 2 ·0.9351n hran. Dále ukážeme, že počet vrcholů vrcholově maximálního indukovaného bipartitnho podgrafu náhodného kubického grafu asymptoticky skoro jistě leží v intervalu [0.75n; 0.9082n]. K získání dolního odhadu zkonstruujeme randomizovaný algoritmus na hledání velkého indukovaného biparitního podgrafu v náhodném kubickém grafu. V závěru práce diskutujeme důsledky pro grafové homomorfismy, zejména pro Nešetřilovu Pětiúhelníkovou domněnku.
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Keevash, Peter (oponent) ; Krivelevich, Michael (oponent)
disertační práce Structural graph theory Jan Hladký V práci se zabýváme domněnkou Loebla, Komlóse a Sósové, která je kla- sickým problémem extremální teorie grafů. Dokážeme následující slabou verzi domněnky: pro libovolné α > 0 existuje číslo k0 takové, že pro každé k > k0 a každý n-vrcholový graf G obsahující alespoň (1 2 + α)n vrcholů stupně ale- spoň (1 + α)k platí, že G obsahuje každý strom T na k vrcholech jako podgraf. Důkaz tohoto výsledku sleduje strategii běžnou v přístupech využívajících Szemerédiho regularity lemma: nejdřív je graf G rozložen a v tomto rozkladu je nalezena kombinatorická struktura s vhodnými vlastnostmi. V posledním kroku je strom T vnořen do G pomocí této struktury. Rozklad zaručený původním regularity lemmatem je ovšem triviálni pokud je G řídký. Abychom obešli toto omezení, vyvineme rozkladovou techniku která umožňuje postihnout i strukturu řídkých grafů: každý graf může být rozložen do vrcholů s velkým stupněm, regulárních párů (ve smyslu regularity lemmatu) a dvou dalších částí, které mají jisté expandující vlastnosti. Výsledky v této práci byly dosaženy s následujícími spolupracovníky: János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein,...
|
|
|
Tomaszewski's conjecture
Toufar, Tomáš ; Šámal, Robert (vedoucí práce) ; Hladký, Jan (oponent)
V roce 1986 Boguslaw Tomaszewski zformuloval následující otázku: Mějme n reálných čísel a1, . . . , an takových, že součet jejich druhých mocnin je 1. Uvážíme-li 2n výrazů tvaru |ε1a1 +· · ·+εnan|, kde εi = ±1, může se stát, že výrazů s hodnotou ostře větší než 1 bude více než výrazů s hodnotou nejvýše 1? Kromě toho, že tato otázka je zajímavá z pohledu pravděpodobnosti, odpověď na tuto otázku by měla také aplikace například v kvadratickém programování. Otázka je ale po třiceti letech stále otevřená. V této práci vyřešíme speciální případ této domněnky. Dokážeme, že domněnka platí pro vektory tvaru (α, δ, . . . , δ) dostatečně velké dimenze. To zobecňuje předešlý výsledek dokazující, že domněnka platí pro vektory tvaru (δ, . . . , δ). 1
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Keevash, Peter (oponent) ; Krivelevich, Michael (oponent)
disertační práce Structural graph theory Jan Hladký V práci se zabýváme domněnkou Loebla, Komlóse a Sósové, která je kla- sickým problémem extremální teorie grafů. Dokážeme následující slabou verzi domněnky: pro libovolné α > 0 existuje číslo k0 takové, že pro každé k > k0 a každý n-vrcholový graf G obsahující alespoň (1 2 + α)n vrcholů stupně ale- spoň (1 + α)k platí, že G obsahuje každý strom T na k vrcholech jako podgraf. Důkaz tohoto výsledku sleduje strategii běžnou v přístupech využívajících Szemerédiho regularity lemma: nejdřív je graf G rozložen a v tomto rozkladu je nalezena kombinatorická struktura s vhodnými vlastnostmi. V posledním kroku je strom T vnořen do G pomocí této struktury. Rozklad zaručený původním regularity lemmatem je ovšem triviálni pokud je G řídký. Abychom obešli toto omezení, vyvineme rozkladovou techniku která umožňuje postihnout i strukturu řídkých grafů: každý graf může být rozložen do vrcholů s velkým stupněm, regulárních párů (ve smyslu regularity lemmatu) a dvou dalších částí, které mají jisté expandující vlastnosti. Výsledky v této práci byly dosaženy s následujícími spolupracovníky: János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein,...
|
|
|
Szemerédi Regularity Lemma a jeho aplikace v kombinatorice
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Dvořák, Zdeněk (oponent)
V práci podáme důkaz domněnky Loebla, Komlóse a Sósové (1995) pro husté grafy. Dokážeme následující tvrzení. Pro libovolné q > 0 existuje číslo n0 takové, že pokud má libovolný graf G řadu n > n0 alespoň polovinu vrcholů se stupněm alespoň k > qn, pak G obsahuje každý strom na k+1 vrcholech jako podgraf. Tím vylepšujeme předchozí výsledky autorů Zhao (2002) a Piguet a Stein (2007). Ukážeme, že v jistých případech lze předpoklady věty oslabit. Je diskutována dolní mez k problému. Jako důsledek hlavní věty dostaneme těsný odhad Ramseyova čísla dvou stromů. Důkaz hlavní věty kombinuje vnořovací techniku založenou na Regularity Lemmatu s Metodou stability. Výsledku bylo dosaženo ve společné práci s Dianou Piguet.
|
|
|
Structural properties of graphs---probabilistic and deterministic point of view
Hladký, Jan ; Pawlas, Zbyněk (oponent) ; Šámal, Robert (vedoucí práce)
V práci zkoumáme bipartitní podgrafy náhodného kubického grafu. Ukážeme, že hranově maximální bipartitní podgraf náhodného kubického grafu na n vrcholech má asymptoticky skoro jistě méně než 3 2 ·0.9351n hran. Dále ukážeme, že počet vrcholů vrcholově maximálního indukovaného bipartitnho podgrafu náhodného kubického grafu asymptoticky skoro jistě leží v intervalu [0.75n; 0.9082n]. K získání dolního odhadu zkonstruujeme randomizovaný algoritmus na hledání velkého indukovaného biparitního podgrafu v náhodném kubickém grafu. V závěru práce diskutujeme důsledky pro grafové homomorfismy, zejména pro Nešetřilovu Pětiúhelníkovou domněnku.
|
host ::
RSS.