Discrete Math Seminar
Euiwoong Lee (이의웅), The Karger-Stein algorithm is optimal for k-cut
Room B232 IBS (기초과학연구원)In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is …
Duksang Lee (이덕상), Intertwining connectivities for vertex-minors and pivot-minors
Room B232 IBS (기초과학연구원)We show that for pairs (Q,R) and (S,T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such …
Linda Cook, Two results on graphs with holes of restricted lengths
Room B232 IBS (기초과학연구원)We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph …
Eun Jung Kim (김은정), A Constant-factor Approximation for Weighted Bond Cover
Room B232 IBS (기초과학연구원)The Weighted
Cheolwon Heo (허철원), Representations of even-cycle matroids
Room B232 IBS (기초과학연구원)A signed graph is a pair
Dabeen Lee (이다빈), Mixing sets, submodularity, and chance-constrained optimization
Room B232 IBS (기초과학연구원)A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly …
Kevin Hendrey, Extremal functions for sparse minors
Room B232 IBS (기초과학연구원)The extremal function
Eunjin Oh (오은진), Feedback Vertex Set on Geometric Intersection Graphs
Room B232 IBS (기초과학연구원)I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time $2^{O(\sqrt{k})}(n + …
Joonkyung Lee (이준경), Majority dynamics on sparse random graphs
Room B232 IBS (기초과학연구원)Majority dynamics on a graph