- Видео 111
- Просмотров 14 371
TCS Group at Jagiellonian
Добавлен 16 мар 2021
Theoretical Computer Science Department of Jagiellonian University
We post here the recordings of our weekly research seminar and other random recordings (workshop, minicourses).
The channel is maintained by Piotr Micek & Lech Duraj.
We post here the recordings of our weekly research seminar and other random recordings (workshop, minicourses).
The channel is maintained by Piotr Micek & Lech Duraj.
Bartosz Walczak - "Excluding a Burling graph"
A talk by Bartosz Walczak, Jagiellonian University given on November 27, 2024.
A class of graphs 𝒢 is χ-bounded if there is a function f:ℕ→ℕ such that every graph in 𝒢 with chromatic number greater than f(k) contains a k-clique. Several important classes of graphs, including the class of string graphs and, more generally, every class of graphs excluding induced subdivisions of a fixed graph, are not χ-bounded because they contain a specific infinite family {Bℓ:ℓ∈ℕ} of triangle-free graphs with unbounded chromatic number, first constructed by Burling in 1965. We show that if 𝒢 is the class of string graphs or any 2-controlled class of graphs excluding induced subdivisions of a fixed graph, ...
A class of graphs 𝒢 is χ-bounded if there is a function f:ℕ→ℕ such that every graph in 𝒢 with chromatic number greater than f(k) contains a k-clique. Several important classes of graphs, including the class of string graphs and, more generally, every class of graphs excluding induced subdivisions of a fixed graph, are not χ-bounded because they contain a specific infinite family {Bℓ:ℓ∈ℕ} of triangle-free graphs with unbounded chromatic number, first constructed by Burling in 1965. We show that if 𝒢 is the class of string graphs or any 2-controlled class of graphs excluding induced subdivisions of a fixed graph, ...
Просмотров: 49
Видео
Marcin Briański - "On Erdős-Pósa properties of tripods in directed graphs"
Просмотров 68День назад
A talk by Marcin Pilipczuk, Jagiellonian University given on December 11, 2024. A seminal result of Erdős and Pósa from 1965 states that every graph either contains k pairwise vertex disjoint cycles or a set of O(k log k) vertices intersecting every cycle. In modern terminology we would say that cycles have the Erdős-Pósa property (EP for short). This result led to many developments in structur...
Andrzej Ruciński - "Homogeneous Substructures in Ordered Uniform (Random) Matchings"
Просмотров 63Месяц назад
A talk by Andrzej Ruciński, Adam Mickiewicz University given on December 04, 2024. An ordered r-uniform matching is an r-uniform hypergraph on a linearly ordered set of vertices which consists exclusively of vertex-disjoint edges (and no isolated vertices). In the first part of my talk, I will present recent Erdős-Szekeres type results, including the almost optimal theorem of Sauermann and Zakh...
Marcin Pilipczuk - "Bounding ε-scatter dimension via metric sparsity"
Просмотров 24Месяц назад
A talk by Marcin Pilipczuk, Jagiellonian University given on November 06, 2024. A recent work of Abbasi et al. [FOCS 2023] introduced the notion of ε-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range of clustering problems in classes of metric spaces that admit a bound on the ε-scatter dimensi...
Tara Abrishami - "Locally chordal graphs"
Просмотров 203Месяц назад
A talk by Tara Abrishami, Universität Hamburg given on November 20, 2024. In this talk, I will discuss recent results concerning graphs which behave locally like chordal graphs. A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs have interesting properties and many equivalent characterizations. They also have algorithmic applications, for example to the...
Giannos Stamoulis - "Finding irrelevant vertices in linear time on bounded-genus graphs"
Просмотров 57Месяц назад
A talk by Giannos Stamoulis, University of Warsaw given on November 13, 2024. The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these problems, permitting the application of this technique on surface-embedded graphs, is the fact that every graph of large enough treewidth contai...
Clément Legrand-Duchesne - "Kempe recoloring of sparse graphs"
Просмотров 682 месяца назад
A talk by Clément Legrand-Duchesne, Jagiellonian University given on October 23, 2024. Kempe changes are a recoloring operation introduced in 1879 by Kempe. They are decisive in the proofs of the Four Color Theorem and of Vizing's edge coloring theorem. We say that two k-colorings are equivalent if they are connected by a series of Kempe changes, and that a graph is k-recolorable if all its k-c...
Jędrzej Hodor - Weak coloring numbers of minor-closed graph classes
Просмотров 582 месяца назад
A talk by Jędrzej Hodor, Jagiellonian University given on October 16, 2024. Weak coloring numbers are a family of graph parameters studied extensively in structural and algorithmic graph theory. We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. showed that for a fixed graph X, the maximum r-th weak coloring number of X-minor-fr...
Zdeněk Dvořák - Random thoughts on Borodin-Kostochka conjecture
Просмотров 493 месяца назад
A talk by Zdeněk Dvořák, Charles University given on October 9, 2024. Borodin-Kostochka conjecture proposes the following variation on Brooks theorem: For every ∆≥9, every graph of maximum degree ∆ and clique number less than ∆ is (∆-1)-colorable. We discuss the known results towards this conjecture, as well as other problems motivated by it (for fractional coloring, other forbidden subgraphs, ...
Michał Seweryn - Polynomial Bounds for the Graph Minor Structure Theorem
Просмотров 1223 месяца назад
A talk by Michał Seweryn, Charles University given on October 2, 2024. Graph Minor Structure Theorem is the cornerstone result of the series of papers "Graph Minors" by Robertson and Seymour, and one of the deepest results in the whole graph theory. Originally it was developed as a tool for proving Wagner's conjecture, but has since found numerous applications in various branches of mathematics...
António Girão - Induced C_4-free subgraphs with high average degree
Просмотров 903 месяца назад
"Induced C_4-free subgraphs with high average degree" by António Girão, University of Oxford. The talk was given on June 12, 2024.
Alexander Wolff - Eliminating Crossings in Ordered Graphs
Просмотров 303 месяца назад
"Eliminating Crossings in Ordered Graphs" by Alexander Wolff, Universität Würzburg. The talk was given on May 29, 2024.
Marta Kwiatkowska - Strategy synthesis for stochastic games with neural perception mechanisms
Просмотров 1123 месяца назад
"Strategy synthesis for partially observable stochastic games with neural perception mechanisms" by Marta Kwiatkowska, University of Oxford. The talk was given on May 15, 2024.
Michał Pilipczuk - Minor testing in almost linear time
Просмотров 1423 месяца назад
"Minor testing in almost linear time" by Michał Pilipczuk, University of Warsaw. The talk was given on May 8, 2024.
Hoang La - Graph reconstruction with connectivity queries
Просмотров 393 месяца назад
"Graph reconstruction with connectivity queries" by Hoang La, Université Paris-Saclay. The talk was given on April 17, 2024.
Jean Cardinal - A rectangulation is a decomposition of a rectangle into finitely many rectangles
Просмотров 1767 месяцев назад
Jean Cardinal - A rectangulation is a decomposition of a rectangle into finitely many rectangles
David Conlon - Additive combinatorics without (much) addition
Просмотров 1327 месяцев назад
David Conlon - Additive combinatorics without (much) addition
Clément Rambaud - Inversions in oriented graphs
Просмотров 457 месяцев назад
Clément Rambaud - Inversions in oriented graphs
Jacob Fox - Structure theorems for intersection patterns of geometric objects
Просмотров 1659 месяцев назад
Jacob Fox - Structure theorems for intersection patterns of geometric objects
Gábor Tardos - Forbidden acyclic patterns in 0-1 matrices
Просмотров 869 месяцев назад
Gábor Tardos - Forbidden acyclic patterns in 0-1 matrices
Sergio Cabello - Packing d-dimensional balls into a (d+1)-dimensional container
Просмотров 4410 месяцев назад
Sergio Cabello - Packing d-dimensional balls into a (d 1)-dimensional container
Peter Allen - Universality for degenerate graphs
Просмотров 4010 месяцев назад
Peter Allen - Universality for degenerate graphs
Paul Bastide - Skipless chain decompositions and improved poset saturation bounds
Просмотров 54Год назад
Paul Bastide - Skipless chain decompositions and improved poset saturation bounds
Matthieu Rosenfeld - A simple counting argument applied to graph colorings
Просмотров 103Год назад
Matthieu Rosenfeld - A simple counting argument applied to graph colorings
Gábor Damásdi - Monochromatic configurations on the circle
Просмотров 23Год назад
Gábor Damásdi - Monochromatic configurations on the circle
Torsten Mütze - A book proof of the middle levels theorem
Просмотров 280Год назад
Torsten Mütze - A book proof of the middle levels theorem
Piotr Micek - Tight bound for the Erdős-Pósa property of tree minors
Просмотров 104Год назад
Piotr Micek - Tight bound for the Erdős-Pósa property of tree minors
Torsten Ueckerdt - When Surrounding is not Catching in Cops and Robber
Просмотров 110Год назад
Torsten Ueckerdt - When Surrounding is not Catching in Cops and Robber
Marcelo Campos - An exponential improvement for diagonal Ramsey
Просмотров 454Год назад
Marcelo Campos - An exponential improvement for diagonal Ramsey
at 28:03 5:45-8:34;
Thank you very much for sharing your seminars on RUclips and thank to Michal Pilipcszuk for this presentation and the interesting background explanation.
Now I want to make a Hex Flower version of the Cops & Robber game 😬
Great content, looking forward to seeing more uploads! This deserves more views, I think you should use promosm to grow your channel!