Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles
Fix $r \ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded …
10 events found.
Events
-
-
Zoom ID: 224 221 2686 (ibsecopro)
-
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 …
-
-
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 …
-
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 …
-
Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins
Room B332 IBS (기초과학연구원)We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply, delineated) if for every hereditary closure $\mathcal D$ of a subclass of …
-
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 …
-
Jan Hladký, Invitation to graphons
Zoom ID: 224 221 2686 (ibsecopro)The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very …
-
Abhishek Methuku, A proof of the Erdős–Faber–Lovász conjecture
Room B332 IBS (기초과학연구원)The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof …
-
-
Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width
Zoom ID: 869 4632 6610 (ibsdimag)We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches …
-
Raphael Steiner, Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs
Room B332 IBS (기초과학연구원)Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all …