- 109
- 13 633
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.
Andrzej Ruciński - "Homogeneous Substructures in Ordered Uniform (Random) Matchings"
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 Zakharov [2025+], guaranteeing in every ordered r-uniform matching the presence of a large homogeneous sub-matching of one of several prescribed types. In the second part, we will address a similar question with respect to uniformly random ordered r-uniform matchings, where so far only partial results have been obtained.
This is joint work with Andrzej Dudek, Jarek Grytczuk, and, for the second part, Jakub Przybyło.
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 Zakharov [2025+], guaranteeing in every ordered r-uniform matching the presence of a large homogeneous sub-matching of one of several prescribed types. In the second part, we will address a similar question with respect to uniformly random ordered r-uniform matchings, where so far only partial results have been obtained.
This is joint work with Andrzej Dudek, Jarek Grytczuk, and, for the second part, Jakub Przybyło.
Переглядів: 9
Відео
Marcin Pilipczuk - "Bounding ε-scatter dimension via metric sparsity"
Переглядів 518 годин тому
A talk by Marcin Pilipczuk, University of Warsaw given on November 27, 2024.
Tara Abrishami - "Locally chordal graphs"
Переглядів 15121 день тому
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"
Переглядів 4821 день тому
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"
Переглядів 59Місяць тому
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
Переглядів 50Місяць тому
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
Переглядів 452 місяці тому
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
Переглядів 1142 місяці тому
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
Переглядів 842 місяці тому
"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
Переглядів 282 місяці тому
"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
Переглядів 1092 місяці тому
"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
Переглядів 1342 місяці тому
"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
Переглядів 392 місяці тому
"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
Переглядів 1746 місяців тому
"A rectangulation is a decomposition of a rectangle into finitely many rectangles" by Jean Cardinal, Université Libre de Bruxelles. The talk was given on April 10, 2024.
David Conlon - Additive combinatorics without (much) addition
Переглядів 1196 місяців тому
"Additive combinatorics without (much) addition" by David Conlon, California Institute of Technology. The talk was given on April 3, 2024.
Clément Rambaud - Inversions in oriented graphs
Переглядів 446 місяців тому
Clément Rambaud - Inversions in oriented graphs
Jacob Fox - Structure theorems for intersection patterns of geometric objects
Переглядів 1638 місяців тому
Jacob Fox - Structure theorems for intersection patterns of geometric objects
Gábor Tardos - Forbidden acyclic patterns in 0-1 matrices
Переглядів 798 місяців тому
Gábor Tardos - Forbidden acyclic patterns in 0-1 matrices
Sergio Cabello - Packing d-dimensional balls into a (d+1)-dimensional container
Переглядів 449 місяців тому
Sergio Cabello - Packing d-dimensional balls into a (d 1)-dimensional container
Peter Allen - Universality for degenerate graphs
Переглядів 379 місяців тому
Peter Allen - Universality for degenerate graphs
Paul Bastide - Skipless chain decompositions and improved poset saturation bounds
Переглядів 5411 місяців тому
Paul Bastide - Skipless chain decompositions and improved poset saturation bounds
Matthieu Rosenfeld - A simple counting argument applied to graph colorings
Переглядів 9911 місяців тому
Matthieu Rosenfeld - A simple counting argument applied to graph colorings
Gábor Damásdi - Monochromatic configurations on the circle
Переглядів 2311 місяців тому
Gábor Damásdi - Monochromatic configurations on the circle
Torsten Mütze - A book proof of the middle levels theorem
Переглядів 276Рік тому
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
Переглядів 103Рік тому
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
Переглядів 107Рік тому
Torsten Ueckerdt - When Surrounding is not Catching in Cops and Robber
Marcelo Campos - An exponential improvement for diagonal Ramsey
Переглядів 438Рік тому
Marcelo Campos - An exponential improvement for diagonal Ramsey
Krzysztof Potępa - Better Diameter Algorithms for Bounded VC-dimension and Geom. Intersection Graphs
Переглядів 88Рік тому
Krzysztof Potępa - Better Diameter Algorithms for Bounded VC-dimension and Geom. Intersection Graphs
Avi Widgerson - The Value of Errors in Proofs
Переглядів 147Рік тому
Avi Widgerson - The Value of Errors in Proofs
at 28:03 5:45-8:34;
Thank you very much for sharing your seminars on UA-cam 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!