Chong Shangguan (上官冲), On the sparse hypergraph problem of Brown, Erdős and Sós
Zoom ID: 224 221 2686 (ibsecopro)For fixed integers
10 events found.
Seminars and Colloquiums
Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
Room B332 IBS (기초과학연구원)A linear
Cosmin Pohoata, Convex polytopes from fewer points
Zoom ID: 224 221 2686 (ibsecopro)Finding the smallest integer
Giannos Stamoulis, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
Room B332 IBS (기초과학연구원)The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate
Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles
Zoom ID: 224 221 2686 (ibsecopro)Fix
Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets
Room B332 IBS (기초과학연구원)Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs, it becomes less trivial and one discovers some surprising …
Youngho Yoo (유영호), Approximating TSP walks in subcubic graphs
Room B332 IBS (기초과학연구원)The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous
Mamadou Moustapha Kanté, MSOL-Definable decompositions
Room B332 IBS (기초과학연구원)I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain how to define in MSOL branch-decompositions for finitely …
Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins
Room B332 IBS (기초과학연구원)We introduce the notion of delineation. A graph class
Pedro Montealegre, A Meta-Theorem for Distributed Certification
Zoom ID: 869 4632 6610 (ibsdimag)Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two …