기초과학연구원 이산수학그룹
In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models …
An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved …
What is the largest subset of $Z_{2^n}$ that doesn't contain a projective d-cube? In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain …
Courcelle's Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed …
We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, …
A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by …
Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, \ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ …
Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called …
Our problem can be described in terms of a two player game, played with the set $\mathcal{S}_n$ of permutations on $\{1,2,\dots,n\}$. First, Player 1 selects a subset $S$ of $\mathcal{S}_n$ and shows …
The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two. In this talk, we …