TBA

Chair: Pavel Pudlak, Neil Thapen, Jan Krajíček

More information on the old seminar web page. The programme is announced via the mailing list.

IM CAS

Monday, 26. September 2022 - 16:00 to 17:30

(Joint seminar with set theory group)

The study of compactness phenomena at uncountable cardinals has been a central line of research in combinatorial set theory since the mid-twentieth century. In the first part of this talk, we will give a broad overview of this area of research and survey some of its most prominent results. We will then look at a few recent results concerning compactness phenomena for uncountable graphs. We first look at possible generalizations of the de Bruijn-Erdos compactness theorem for chromatic numbers to uncountable cardinalities, in particular showing that consistently there are large uncountable graphs witnessing extreme failures of compactness for, e.g., the property of having a countable chromatic number. We then turn to the study of the structure of the collections of finite subgraphs of uncountably chromatic graphs, answering a question of Erdos, Hajnal, and Szemeredi about the growth rates of chromatic numbers in such collections of... more

The study of compactness phenomena at uncountable cardinals has been a central line of research in combinatorial set theory since the mid-twentieth century. In the first part of this talk, we will give a broad overview of this area of research and survey some of its most prominent results. We will then look at a few recent results concerning compactness phenomena for uncountable graphs. We first look at possible generalizations of the de Bruijn-Erdos compactness theorem for chromatic numbers to uncountable cardinalities, in particular showing that consistently there are large uncountable graphs witnessing extreme failures of compactness for, e.g., the property of having a countable chromatic number. We then turn to the study of the structure of the collections of finite subgraphs of uncountably chromatic graphs, answering a question of Erdos, Hajnal, and Szemeredi about the growth rates of chromatic numbers in such collections of... more

University of Oxford

Monday, 23. May 2022 - 16:00 to 17:30

We say that Rudich's Conjecture holds for a propositional proof system Q if there are no efficient Q-proofs of random truth table tautologies. We say that Razborov's Conjecture holds for a propositional proof system Q if there are no efficient Q-proofs of *any* truth table tautologies. A fundamental task in proof complexity and the meta-mathematics of circuit lower bounds is to understand for which Q these conjectures hold. We show various results about these conjectures, including evidence for their difficulty.

Based on joint work with Jan Pich.