Thursday, 10th September 2020
14:00 Robert Samal, CUNI
Universality in Minor-Closed Graph Classes
Universal graph for a graph class is a member of the class that contains every other graph in the class as a subgraph. For instance, there is a universal graph for the class of countable trees, or for countable graphs of tree-width at most k. On the other hand, Pach showed, that there is no universal graph for countable planar graphs. We study what is the simplest possible graph that contains all countable planar graphs. We show that every such graph must have infinite complete minor (thus we find a new proof of Pach's results). On the positive side, we provide a construction of a graph containing all countable planar graphs and has favorable properties in terms of expansion. The construction is also remarkably explicit: strong product of an infinite path with a universal graph for graphs of tree-width at most 7.
14:30 Pavel Dvořák, CUNI
CoSP – Research Experience for Undergraduates 2019
The talk will survey CoSP-REU 2019 program. A group of ten students of Charles University attended the program in year 2019. They attended many scientific and additional skills lectures at DIMACS, Rutgers University and at Faculty of Mathematics and Physics, Charles University Prague. The students were divided into four groups and worked on the following topics:
1) Slowdown for the geodesic-biased random walk
2) Rainbow cycles in graphs - Aharoni conjecture
3) A graph game from extremal combinatorics
4) Time of Turing machines vs. depth of circuits
The results of the students will be presented.
15:00 Lenka Zdeborová, CNRS
Gradient descent algorithms analysis
Gradient descent algorithms and their noisy variants, such as the Langevin dynamics or multipass stochastic gradient descent, are at the center of attention in machine learning. Yet their behavior remains perplexing, in particular in the high-dimensional nonconvex setting. In this talk, I will present several high-dimensional and (mostly) nonconvex statistical learning problems in which the performance of gradient-based algorithms can be analyzed down to a constant. The common point of these settings is that the data come from a probabilistic generative model leading to problems for which, in the high-dimensional limit, statistical physics provides exact closed solutions for the performance of the gradient-based algorithms. The covered settings include the spiked mixed matrix-tensor model, the perceptron, and phase retrieval.
15:30 Michal Koucký, CUNI
Sorting Short Integers
Sorting is one of the fundamental algorithmic problems. It's precise complexity is still largely open in various models of computation. All known Boolean circuits for Sorting have super-linear size. We conjecture that there are no linear-size Boolean circuits for Sorting. We establish a connection between the circuit complexity of various computational problems, such as Sorting and Fast Fourier Transform, and certain data structure like problems.
16:00 Ron Aharoni, Technion
Cakes, matchings and topology
An r-partite hypergraph is called fractionally balanced if there exists a non-negative function on its edge set, that has constant degrees in each vertex side. Using a topological version of Hall's theorem we prove lower bounds on the matching number of such hypergraphs. Combined with an approach of Meunier and Su, this yields results on envy-free division and on rental harmony.
16:30 Michael Skotnica, CUNI
CoSP – Research Experience for Undergraduates 2020 (REMOTE)
In this talk, I will briefly summarize the programme of this year's remote COSP REU.
Then I will introduce four projects of the Czech group and their main results.
Namely Optimal starting state for a deterministic scan, Antipodal monochromatic paths-in hypercubes, Delta colouring in the graph streaming model and High school partitions.
17:00 Prof. Pavol Hell, Simon Fraser University
Graph Dichotomies
The proof of the celebrated Feder-Vardi Dichotomy Conjecture (independently by Bulatov and by Zhuk) has focused much recent attention on other homomorphism dichotomies. After a historical survey of the area, I will focus on the dichotomies that arise in graph theory, contrasting the results for homomorphisms and for list homomorphisms. In particular I will describe recent work on signed graphs, where uncharacteristically the classification seems harder to pin down for list homomorphisms.
17:30 Survey of research accomplished in CoSP 2019-2020
Martin Loebl, CUNI, coordinator
A survey of WP 1 – 4 research outcomes including Milestones and deliverables, dissemination, impact.
17:45 Discussion
Friday, 11th September 2020
9:00 – 9:30 CoSP financial report and management
Mgr. Eva Šauerová, M.Sc., project manager
use of resources, GANTT chart, number of secondments executed, project management
9:30 – 10:30 Risk management with focus on COVID pandemy
Proposed measures for adjusting to the risks
14:00 Jan Hubička, CUNI
Forbidden cycles in metrically homogeneous graphs
We discuss Cherlin catalogue of the metrically homogeneous graphs which
is conjectured to be complete. By introducing new methods motivated by
the connection to the structural Ramsey theory we give a new evidence
for this hypothesis showing that the list is complete for all strong
amalgamation classes with finitely many obstacles for completion.
Similarly we also show that the list is complete if all obstacles are
cycles and complete graphs.
15:00 Maria Chudnovsky, Princeton University
Induced Subgraphs and Tree Decompositions
Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction; the talk will be a survey of these results.
16:00 Ron Holzman, Technion – Princeton University
On convex Holes in d-dimensional Point Sets
Given a finite set P in R^d, points a_1,a_2,...,a_l of P form an l-hole in P if they are the vertices of a convex polytope which contains no points of P in its interior. We construct arbitrarily large point sets in general position in R^d having no holes of size 2^(7d) or more. This improves the previously known upper bound of order d^(d+o(d)) due to Valtr. Our construction uses a certain type of designs, originating from numerical analysis, known as ordered orthogonal arrays. Joint work with Boris Bukh and Ting-Wei Chao.
Posted on 2020-08-22