기초과학연구원 이산수학그룹
Venue Gongju Hanok Vilage (공주한옥마을) Organizers Donggyu Kim (김동규), KAIST and IBS Discrete Mathematics Group Seokbeom Kim (김석범), KAIST and IBS Discrete Mathematics Group Seonghyuk Im (임성혁), KAIST and IBS Extremal Combinatorics and Probability Group Hyunwoo Lee (이현우), KAIST and IBS Extremal Combinatorics and Probability Group
For a family F of graphs, the F-Deletion Problem asks to remove the minimum number of vertices from a given graph G to ensure that G belongs to F. One of the most common ways to obtain an interesting family F is to fix another family H of graphs and let F be the set …
Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and the theory of sparsity. In this talk, we will survey structural and algorithmic results that concern width and …
For the past few years, I've been working on formalizing proofs in matroid theory using the Lean proof assistant. This has led me to many interesting and unexpected places. I'll talk about what formalization looks like in practice from the perspective of a combinatorialist.
The 2024 Workshop on (Mostly) Matroids will be held in-person at the Institute for Basic Science (IBS), Daejeon, South Korea, from August 19, 2024 to August 23, 2024. We expect that most people would arrive on Sunday, August 18 and leave on Saturday, August 24. Our hope is that this workshop will continue the tradition …
In some sense, matroids are generalisations of graphs. The idea of graph minors extends to matroids, and so does the idea of a minor-closed class. We can think of a minor-closed class of matroids as being an analogue to the class of graphs embeddable on a surface. Any such class of graphs has a corresponding …
Website: https://cw2024.combinatorics.kr/ Location Chungbuk National University, Cheongju, Korea. Advisory Committee Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Sang-il Oum, IBS Discrete Mathematics Group / KAIST) Sponsors IBS Discrete Mathematics Group. Korean Mathematical Society
In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} - \frac{k}{2} + 1$ by Addario-Berry et al. In this talk, we give the first subquadratic bound for Burr's …
An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors. An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in $G$ is rainbow. With this, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free, …