Seokbeom Kim (김석범), The structure of △(1, 2, 2)-free tournaments
Given a tournament $S$, a tournament is $S$-free if it has no subtournament isomorphic to $S$. Until now, there have been only a small number of tournaments $S$ such that …
10 events found.
Discrete Math Seminar
Events
-
-
Room B332 IBS (기초과학연구원)
-
Meike Hatzel, Counterexample to Babai’s lonely colour conjecture
Room B332 IBS (기초과학연구원)Motivated by colouring minimal Cayley graphs, in 1978 Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large …
-
-
Denys Bulavka, Strict Erdős-Ko-Rado Theorems for Simplicial Complexes
Room B332 IBS (기초과학연구원)The now classical theorem of Erdős, Ko and Rado establishes the size of a maximal uniform family of pairwise-intersecting sets as well as a characterization of the families attaining such …
-
On-Hei Solomon Lo, Minors of non-hamiltonian graphs
Room B332 IBS (기초과학연구원)A seminal result of Tutte asserts that every 4-connected planar graph is hamiltonian. By Wagner's theorem, Tutte's result can be restated as: every 4-connected graph with no $K_{3,3}$ minor is …
-
Attila Jung, The Quantitative Fractional Helly Theorem
Room B332 IBS (기초과학연구원)Two celebrated extensions of Helly's theorem are the Fractional Helly theorem of Katchalski and Liu (1979) and the Quantitative Volume theorem of Barany, Katchalski, and Pach (1982). Improving on several …
-
Roohani Sharma, Uniform and Constructive Polynomial Kernel for Deletion to $K_{2,p}$ Minor-Free Graphs
Room B332 IBS (기초과학연구원)Let $\mathcal F$ be a fixed, finite family of graphs. In the $\mathcal F$-Deletion problem, the input is a graph G and a positive integer k, and the goal is …
-
-
Sergey Norin, Asymptotic dimension of intersection graphs
Room B332 IBS (기초과학연구원)The notion of asymptotic dimension of metric spaces, introduced by Gromov, describes their large-scale behaviour. Asymptotic dimension of graph families has been recently studied, in particular, by Bonamy et al. …
-
Mihyun Kang (강미현), Phase transitions in a random subgraph of the hypercube
Room B332 IBS (기초과학연구원)We will discuss classical and recent results about phase transitions in random subgraphs of the hypercube and beyond. The focus will be on the giant component, long cycles, large matchings, …
-
Linda Cook, A tight algorithmic meta-theorem for distributed certification within bounded treewidth graphs
Room B332 IBS (기초과학연구원)A local certification of a graph property is a protocol in which nodes are given “certificates of a graph property” that allow the nodes to check whether their network has this …
-
Colin Geniet, Merge-width
Room B332 IBS (기초과학연구원)This talk is an introduction to the recent notion of merge-width, proposed by Jan Dreier and Szymon Torúnczyk. I will give an overview of the context and motivations for merge-width, …