Přednášky z online semináře ITI

Aproximační algoritmy ve třídách se sublearními oddělovači

podle Zdeněk Dvořák (Ústav výpočetní techniky Univerzity Karlovy v Praze)

^8. října 2020, 11:00 CEST ( join )

Abstraktní

Lipton a Tarjan dokázali, že každý rovinný graf n-vrcholů má vyvážený oddělovač řádu O (sqrt (n)), a poskytli řadu algoritmických aplikací tohoto výsledku. Ukázali zejména, že maximální velikost nezávislé množiny v grafech s touto vlastností lze v polynomiálním čase libovolně dobře přiblížit. Myšlenka jejich algoritmu platí pro jiné problémy, ale pouze s omezenými omezeními (optimální řešení musí mít lineární velikost a problém musí být definován hraničními omezeními).

V posledních několika letech bylo vyvinuto několik sofistikovanějších technik pro grafy se sublearními oddělovači; tyto techniky překonávají výše uvedená omezení a umožňují nám navrhnout aproximační algoritmy pro mnohem obecnější třídy problémů. Prozkoumám tento vývoj a vynikající výzvy.

Toroidní mřížka nezletilí a roztáhnout ve vložených grafech

podle Petr Hliněný (Masarykova univerzita, Brno)

^15. října 2020, 11:00 CEST ( join )

Abstraktní

Zkoumáme toroidní rozlohu vloženého grafu G, tj. Velikost největší toroidní mřížky obsažené v G jako vedlejší. V průběhu této práce představíme nový parametr hustoty vložení, úsek vloženého grafu G a použijeme jej k vázání toroidní rozlohy shora a zdola v konstantním faktoru závislém pouze na rodu a maximálním stupni. Ukážeme také, že tyto parametry úzce souvisejí s rovinným číslem křížení G. V důsledku našich hranic odvodíme efektivní algoritmus aproximace konstantního faktoru pro toroidní rozlohu a pro číslo křížení plošně vloženého grafu s omezeným maximem stupeň.

↪ slides

Limity latinských čtverců

podle Frederik Garbe (Matematický ústav AV ČR)

^22. 10. 2020, 11:00 SELČ ( join )

Abstraktní

Vyvíjíme teorii limitů pro latinské čtverce, paralelně s nedávnými teoriemi limitů hustých grafů a permutací. Zavádíme pojem hustoty, vhodnou verzi vzdálenosti řezu a prostor mezních objektů - takzvané latinky. Klíčovými výsledky naší teorie jsou kompaktnost mezního prostoru a ekvivalence topologií vyvolaných vzdáleností řezu a levou konvergencí. Nakonec pomocí nedávných výsledků Keevasha o kombinatorických vzorech dokazujeme, že každý Latinon lze aproximovat konečným latinským čtvercem.

Toto je společná práce s Robertem Hancockem, Janem Hladkým a Maryam Sharifzadeh.

↪ slides

Šest cyklů a perfektní párování snarků

podle Roman Nedela (Západočeská univerzita v Plzni)

^29. října 2020, 11:00 SEČ ( join )

Abstraktní

Každý 3barevný barevný kubický graf má sadu tří dokonalých shod, které pokrývají všechny jeho hrany. Naopak, pokud lze sadu okrajů kubického grafu pokrýt třemi dokonalými shody, musí být shody disjunktní a graf 3barevný. Z toho vyplývá, že pokud kubický graf není barevný na 3 hranách, pak jakákoli kolekce tří dokonalých shod, nazývaná 3balení, ponechá některé jeho hrany nezakryté. Minimální počet hran kubického grafu G, které zůstanou odkryty jakoukoli sadou tří dokonalých shody, se bude nazývat barevná vada, nebo krátce vada G, a bude označena df (G). V této přednášce rozumím snarkem bezbarvý kubický graf bez můstků. V důsledku Petersenovy věty je vada pro tyto grafy dobře definována, přičemž triviální horní mez df (G) ≤ v (G), kde v (G) označuje počet vrcholů G.

Koncept defektu kubického grafu představil Steffen (2017). Mimo jiné dokázal, že pokud graf není barevný na 3 hranách, musí být jeho vada minimálně 3. Další pozoruhodný výsledek uvádí, že vada snarku je alespoň tak velká jako polovina jeho obvodu. Protože existují snarky s libovolně velkým obvodem (Kochol 1996), existují snarky s libovolně velkým defektem. Na vadu snark G lze tedy pohlížet jako na míru nezbarvitelnosti G.

Indukovaný podgraf H snark G se nazývá neodstranitelný, pokud je G - H barevný. Jinak se H nazývá vyměnitelné. Připomeňme, že snark G je kritický, pokud je každá dvojice odlišných sousedních vrcholů v G neodstranitelná. Podobně řekneme, že G je kritická, pokud je každá dvojice odlišných nesousedících vrcholů neodstranitelná. Pokud je G kritické i kritické, říkáme, že G je bicritické. Snark G je neredukovatelný, pokud je každý indukovaný podgraf H s alespoň dvěma vrcholy neodstranitelný. Je známo, že snark je neredukovatelný právě tehdy, je-li dvoukritický. Snark G bude nazýván silným, pokud je každý pár sousedních vrcholů odnímatelný.

Ve své přednášce se zaměřím na snarks s defektem 3, což je minimální možná hodnota defektu snark. Je snadno vidět, že snark defektu 3 má 6 cyklů. Naší primární motivací k prozkoumání snarků defektu 3 je následující upravený obvodový dohad publikovaný v roce 1996.

Domněnka 1. (R. Nedela a M. Škoviera) Obvod neredukovatelných snarků je maximálně 6.

Měli jsme na paměti, že snarks defektu 3 obsahují 6 cyklů, které jsme chtěli dokázat

Domněnka 2. Vada neredukovatelné snarks je 3.

I když tento cíl nebyl plně dosažen, bylo získáno dílčí řešení. V důsledku toho jsme prokázali, že permutační snark má defekt 3 právě tehdy, když připouští 6-cyklus. Všimněte si, že není znám žádný permutační snark bez 6-cyklu (další pěkný problém k projednání). Na druhé straně mají silné snarky a snarky obvodu> 6 defekt> 3. Počítačem podporované experimenty ukazují, že mezi 25286953 cyklicky 4 připojenými snarky obvodu ≥ 5 a řádu ≤ 34 má defekt pouze 178> 3. To naznačuje že se může stát, že téměř všichni snarks mají defekt 3.

Dále jsme zkoumali vztah defektu k dalším invarianty snarků. Uvidíme, že několik důležitých invariantů snarků má na snarkech v této rodině své minimální hodnoty: jmenovitě zvláštnost, odpor, kompaktnost, index perfektní shody a další. Abychom přilákali posluchače, oznamujeme následující výsledek.

Teorém. Každý kubický graf bez můstku s defektem 3 má kryt Berge.

Připomeňme, že Bergeova obálka kubického grafu G je množina {M ₁ , M ₂ , M ₃ , M ₄ , M ₅ } pěti dokonalých shody, které nemusí být nutně odlišné, které společně pokrývají všechny hrany G. Dlouhodobě Otevřená Bergeova domněnka uvádí, že každý kubický graf bez můstku připouští Bergeovu obálku.

Jedná se o společnou práci s J. Karabášem, E. Máčajovou a M. Škovierou.

Bibliografie:

1. G. Brinkmann, J. Goedgebeur, J. Hgglund, K. Markstrm, Generace a vlastnosti snarků, J. Combin. Theory Ser. B 103 (2013), 468–488.

2. PJ Cameron, AG Chetwynd a JJ Watkins, Decomposition of snarks, J. Graph Theory 11 (1987), 13–19.

3. G. Fan a A. Raspaud, Fulkersonova domněnka a kryty obvodů, J. Combin. Theory Ser. B 61 (1994), 133–138.

4. MA Fiol, G. Mazzuoccolo, E. Steffen, Measures of edge-uncolorability of cubic graphs, Elecron. J. Combin. 25 (2018), # P4.54.

5. L. Jin, E. Steffen, Petersenova jádra a zvláštnost kubických grafů, J. Teorie grafů 84 (2017), 109–120.

6. L. Jin, E. Steffen a G. Mazzuoccolo Cores, spojení a domněnky o Fano-flow, diskutovat. Matematika. Teorie grafů 38, 165–175.

7. J. Karabáš, E. Máčajová, R. Nedela, 6-rozklad snarků, evropský J. Combin. 34 (2013), 111–122.

8. M. Kochol, Snarks bez malých cyklů, J. Combin. Theory Ser. B 61 (1996), 34–47.

9. R. Lukot'ka, E. Máčajová, J. Mazák, M. Škoviera, Malé snarky s velkou podivností, elektron. J. Combin. 22 (2015), # P1.51.

10. E. Máčajová, A. Raspaud, O silné kruhové domněnce 5 toků, J. Grap Theory 52 (2006), 307–316.

11. E. Máčajová, M. Škoviera, Fano zbarvení a Fulkersonova hypotéza, Theoret. Comput. Sci. 349 (2005), 112–120.

12. E. Máčajová, M. Škoviera, Řídce protínající dokonalé shody v kubických grafech, Combinatorica 34 (2014), 61–94.

13. R. Nedela a M. Škoviera, Dekompozice a redukce snarků, J. Teorie grafů 22 (1996), 253–279.

14. E. Steffen, Klasifikace a charakterizace snarků, Diskrétní matematika. 188 (1998), 183–203.

15. E. Steffen, 1-faktor a obaly cyklů kubických grafů, J. Teorie grafů 78 (2015), 195–206.

16. E. Steffen, Protínající se 1-faktory a nikde nula 5-toků, Combinatorica 35 (2015), 633–640.

Schémata polynomiálního přibližování času pro shlukování v grafech dimenzí nízké dálnice

podle Andreas Feldmann (Matematicko-fyzikální fakulta Univerzity Karlovy v Praze)

^5. listopadu 2020, 11:00 SEČ ( join )

Abstraktní

Studujeme problémy s klastrováním jako k-Median, k-Means a Location Facility v grafech nízké dimenze dálnice, což je grafový parametr modelování přepravních sítí. Dříve se ukázalo, že pro tyto problémy existují aproximační schémata, která probíhají buď v kvazi-polynomiálním čase (za předpokladu konstantní dimenze dálnice) [Feldmann et al. SICOMP 2018] nebo běží v čase FPT (parametrizováno počtem klastrů k, dimenzí dálnice a aproximačním faktorem) [Becker et al. ESA 2018, Braverman et al. 2020]. V tomto článku ukážeme, že existuje polynomiálně-časové aproximační schéma (PTAS) (za předpokladu konstantní dimenze dálnice). Ukážeme také, že uvažované problémy jsou NP-těžké na grafech dálniční dimenze 1. Toto je společná práce s Davidem Saulpicem. Verzi arxiv najdete na arXiv .

Littlewood-Offordova teorie pro libovolné distribuce

podle Tomáš Juskevicius (Matematický ústav AV ČR)

^12. listopadu 2020, 11:00 SEČ ( join )

Abstraktní

Klasický Littlewood-Offordův problém vyžaduje maximální pravděpodobnost, že vážený součet nezávislých náhodných znaků zasáhne bod nebo kouli daného poloměru. Ostrý výsledek při jednání se skutečnými váhami skvěle poskytl Erdős, který použil Spernerovu větu. Toto později Kleitman zobecnil na vysoké dimenze. V této přednášce budeme uvažovat o stejném problému pro libovolné distribuce. Ukazuje se, že možná překvapivě existuje jedinečný výběr optimálních vah, bez ohledu na uvažované rozdělení. Náš výsledek aplikovaný na Bernoulliho distribuce odpovídá na nedávnou otázku Foxe, Kwana a Sauermanna. Důležitým rysem našeho přístupu je, že nepoužíváme harmonickou analýzu nebo extrémní kombinatoriku, které jsou převládajícími nástroji v této oblasti. Nakonec budu diskutovat o aplikacích metod vyvinutých na jiné problémy.

Přednáška je založena na společné práci s Valentasem Kurauskasem (Vilnius University) a předtisk našeho příspěvku najdete na arXiv .

Problém izomorfismu pro S _d -grafy

podle Deniz Agaoglu (Masarykova univerzita, Brno)

^19. listopadu 2020, 11:00 SEČ ( join )

Abstraktní

H-graf je průsečíkový graf připojených podgrafů vhodného rozdělení pevného grafu H, který zavedli Biró, Hujter a Tuza (1992). Zaměřujeme se na S _d -grafy jako speciální případ zobecňující intervalové grafy. Graf G je S _d -graf právě tehdy, je-li průsečíkem spojených podgrafů dělení hvězdy S _d s paprsky d. Dali jsme algoritmus FPT k řešení problému izomorfismu pro S _d -grafy s parametrem d. Tím se řeší otevřený problém Chaplicka, Töpfera, Voborníka a Zemana (2016). V průběhu našeho důkazu také ukazujeme, že problém izomorfismu S _d- grafů je výpočetně přinejmenším stejně tvrdý jako problém izomorfismu poloh omezené šířky.

Dokonce i mapy, počet Colin de Verdière a reprezentace grafů

podle Martin Tancer (Katedra aplikované matematiky Univerzity Karlovy v Praze)

^26. listopadu 2020, 11:00 SEČ ( join )

Abstraktní

Van der Holst a Pendavingh představili parametr grafu σ, který se shoduje se slavnějším parametrem grafu μ Colina de Verdièra μ pro malé hodnoty. Definice σ je však mnohem více geometrická / topologická, která přímo odráží vlastnosti grafu vložitelnosti. Ukázali μ (G) ≤σ (G) +2 a předpokládali μ (G) ≤σ (G) pro jakýkoli graf G. Tuto domněnku potvrzujeme. Pokud víme, jedná se o první topologickou horní hranici na μ (G), která je obecně těsná. Rovnost mezi μ a σ obecně neplatí, protože van der Holst a Pendavingh ukázali, že existuje graf G s μ (G) ≤18 a σ (G) ≥20. Ukázali jsme, že se mezera objevuje na mnohem menších hodnotách, konkrétně vykazujeme graf H, pro který μ (H) ≤7 a σ (H) ≥8. Rovněž dokážeme, že mezera může být obecně velká: Grafy dopadu H_q konečných projektivních rovin řádu q uspokojí μ (H_q) je řádu q ^ (3/2), zatímco σ (H_q) je v q kvadratické. Během přednášky plánuji vysvětlit výsledky a načrtnout hlavní myšlenky důkazů.

Toto je společné dílo s Vojtěchem Kalužou.

Horní hranice složitosti rozšíření pomocí orientačních cyklů: Tři sjednocené výsledky

podle Hans Raj Tiwary (Matematicko-fyzikální fakulta Univerzity Karlovy v Praze)

^3. 12. 2020, 11:00 SEČ ( join )

Abstraktní

Při dokazování, že daný (velký) polytop lze získat jako projekci malého polytopu, často používáme specializované argumenty, které jsou specifické pro daný problém. V této přednášce představím jednoduché důkazy o třech známých výsledcích, které ukazují složitost polynomiálního rozšíření pro nerovnosti Subtour Elimination pro TSP, vrcholový tvar Matching polytop a nerovnosti lichého cyklu pro nezávislou množinu. Naše důkazy používají (málo využívané) spojení mezi složitostí rozšíření a existencí určitých protokolů dvou stran, které počítají uvolněnou matici polytopu. Přednáška bude obsahovat také přehled tohoto spojení.

Cykly dané délky v turnajích

podle Jan Volec (České vysoké učení technické, Praha)

^10. prosince 2020, 11:00 SEČ ( join )

Abstraktní

Studujeme asymptotické chování maximálního počtu řízených cyklů dané délky k ve velkých turnajích. Je dobře známo, že v případě trojúhelníku je maximum dosaženo pravidelným turnajem a v případě 4-cyklů je maximum dosaženo takzvaným kolotočovým turnajem - vrcholem-přechodným turnajem na množině vrcholů { 0,1,2,…, 2k} s oblouky od vrcholu i k vrcholům i + 1, i + 2,…, i + k (mod 2k + 1).

V této přednášce ukážeme, že pro každé l, které není násobkem 4, je počet l-cyklů asymptoticky maximalizován náhodným turnajem. Navíc pro každé kladné celé číslo z dokazujeme, že velký turnaj T maximalizuje počet (4z + 2) -cyklů a (2z + 1) -cyklů právě tehdy, když T je kvazi náhodný a regulární. U délek cyklů, které jsou dělitelné 4, ukážeme, že turnaj v kolotoči asymptoticky maximalizuje počet 8 cyklů a najdeme přibližné řešení pro dostatečně dlouhé cykly.

Jedná se o společnou práci s Andrzejem Grzesikem, Danem Kráľom a Laszlem M. Lovászem.

Ramseyova horní hustota nekonečných grafů

podle Ander Lamaison (Masarykova univerzita, Brno)

^17. prosince 2020, 11:00 SEČ ( join )

Abstraktní

Nechť H je nekonečný graf. Ve dvoubarevném provedení okrajů celého grafu na přirozených číslech, jaký je nejhustší monochromatický podgraf izomorfní s H, který zaručeně najdeme? Měříme hustotu podgrafu podle horní hustoty jeho sady vrcholů. Tuto otázku, zejména v případě nekonečné cesty, představili Erdős a Galvin. Po nedávném výsledku pro nekonečnou cestu uvádíme hranice maximální hustoty pro další volby H, včetně přesných hodnot pro široké třídy bipartitních grafů a nekonečných faktorů.