Combinatorial group
We are shocked by the aggression happening to Ukraine. As citizens we try to help her people with our private means.
As professional mathematicians, we welcome suggestions that might help our fellow Ukrainian colleagues (students or researchers) in any way.
Do not hesitate to contact us!
Programme
Friday 31.05.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Pedro Campos Araújo (Czech Technical University in Prague): TBA
Abstract: TBA
Wednesday 17.04.2024 at 10:30 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Petr Savický (ICS CAS): On CNF formulas irredundant with respect to unit clause propagation
Abstract: Unit clause propagation (UCP) is a simple incomplete deduction rule on formulas in conjunctive normal form (CNF formulas). The algorithm used in most recent SAT solvers is based on clause learning. Such a SAT solver derives and includes into the formula new clauses which do not change the represented function, but make UCP stronger and this is repeated until UCP is able to derive a contradiction or a satisfying assignment. Since the learned clauses have to be stored in the memory, it is interesting to try to minimize the original formula together with the learned clauses while preserving its behavior with respect to UCP. It appears that already irredundancy with respect to UCP is sufficient to guarantee that the size of the formula is larger than the minimum possible only by a polynomial factor. The presentation will demonstrate an upper bound n^2 and a lower bound of order n/log(n) on this factor where n is the number of the variables. The upper bound is simple and the hard part of the proof is the lower bound which uses probabilistic method and known results on covering numbers for hypergraphs. The main result is available in an arXiv preprint.
Past Seminars
Friday 22.03.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Jan Hladký (ICS CAS): Tower-type lower bound for a "Degularity lemma"
Abstract: The Szemeredi regularity lemma asserts that each graph can be partitioned into a finite number, say M(epsilon), of clusters so that almost all the pairs of these clusters are "epsilon-regular", a notion with convenient properties. Szemeredi's proof gives M(epsilon)<2^2^2^2...^2 for a tower of height roughly epsilon^{-5}. Strikingly, Gowers showed that this is quite tight when he gave a tower-type lower bound of height roughly epsilon^{-1/16}.
It is an easy observation that in an epsilon-regular pair, almost all the vertices have almost the same degree into the partnering cluster. This property, which we call "epsilon-degularity" is in fact much weaker than "epsilon-regularity". We show that, despite substantial decrease in strength, in general epsilon-degular partititions require also a tower-type number of clusters. Joint work with Frederik Garbe.
Friday 08.03.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Jan Volec (Czech Technical University in Prague): Subgraphs with a positive minimum semidegree in digraphs with large outdegree
Abstract:
We show that every d-out-regular directed graph G has a subgraph that has the
minimum semidegree at least d(d+1)/(2*|V(G)|). On the other hand, for every
c > 0 we construct infinitely many tournaments T with the minimum outdegree d
and the property that every subgraph of T has the minimum semidegree at most
(1+c)*d(d+1)/(2*|V(T)|).
This is a joint work with Andrzej Grzesik and Vojta Rödl.
Friday 23.02.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Tomáš Hons (Charles University): First-order limits and rooted inverse problems
|
Abstract: The main goal of graph limit theory is to assign to a given well-behaved sequence of graphs a certain limit object capturing significant properties of the sequence. When seeking the right definition of the limit object, we consider the inverse problem asking which objects can actually arise as a limit. This seems to be very difficult for some notions of convergence. A simplified problem of a similar nature is approximation of vertices of the limit object, which we call rooted inverse problem. In this talk, we introduce the rooted inverse problem in the context of first-order limit theory. We describe the current state-of-the-art, discuss some open problems and possible approaches.
|
Friday 16.02.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Denys Bulavka (Charles University): A Hilton-Milner theorem for exterior algebras
Abstract: A set family F is pairwise-intersecting if every pair of its members intersect. In 1960, Erdős, Ko, and Rado gave an upper-bound on the size of a pairwise-intersecting family of k-sets coming from a ground set of size n. Moreover, they characterized the families achieving the upper-bound. These are families whose members all share exactly one element, so called trivial families. Later, Hilton and Milner provided the next best upper-bound for pairwise-intersecting families that are not trivial.
There are several generalizations of the above results. We will focus on the case when the set family is replaced with a subspace of the exterior algebra. In this scenario intersection is replaced with the wedge product, being pairwise-intersecting with self-annihilating and being trivial with being annihilated by a 1-form. Scott and Wilmer, and Woodroofe gave an upper-bound on the dimension of self-annihilating subspaces of the exterior algebra. In the current work we show that the better upper-bound coming from Hilton and Milner's theorem holds for non-trivial self-annihilating subspaces.
This talk is based on a joint work with Francesca Gandini and Russ Woodroofe.
Friday 02.02.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Martin Balko (Charles University): The Erdős--Szekeres Theorem for Split Polygons
Abstract: The famous and still open Erdős--Szekeres Conjecture (1935) states that every set of at least 2k-2+1 points in the plane with no three being collinear contains k points in convex position, that is, k points that are vertices of a convex polygon. We prove several new results around this conjecture. In particular, we prove a relaxed version of the Erdős--Szekeres Conjecture where the value 2k-2+1 is exactly the right threshold. This is a joint work with Jineon Baek.
Friday 19.01.2024 at 14:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Gorav Jindal (Max Planck Institute for Software Systems): Sign Me Up: PosSLP, Sign Testing, and Polynomials
Abstract: Given an integer, deciding its positivity may appear trivial initially. However, this problem becomes more compelling when the integer is presented in a compact form, as opposed to being explicitly represented as a bit string. One such compact representation involves utilizing straight line programs and arithmetic circuits. In this talk, I introduce the concept of straight line programs and subsequently delve into the PosSLP problem, which is the problem of testing the positivity of integers represented by straight line programs. Furthermore, I provide a brief survey of how PosSLP is intricately connected to the Blum–Shub–Smale (BSS) model of computations over reals, numerical analysis, and other intriguing problems in complexity theory. To conclude the talk, I discuss our recent and ongoing research on the PosSLP problem.
Wednesday 17.01.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Samuel Braunfeld (Charles University): Automorphism-invariant measures on countable structures
Abstract: We discuss the classification of automorphism-invariant measures on certain highly symmetric countable structures. The tools include model theory, exchangeability, and probabilistic constructions. This is joint work with Colin Jahel and Paolo Marimon.
Monday 15.01.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Václav Rozhoň (ETH Zürich): Network decompositions in distributed computing and beyond
|
Abstract:
I will talk about so-called network decompositions and their applications in distributed computing and beyond. In particular, Bernshteyn and Yu recently proved a lemma about the existence of network decompositions in graphs of polynomial growth and used that lemma to prove results about so-called measurable graphs. I plan to present a simple proof of their lemma. Joint work with Jan Grebík, Andrew Marks, Forte Shinko
|