기초과학연구원 이산수학그룹
We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in $\mathbb{R}^d$ to admit a $k$-transversal (a $k$-dimensional affine subspace that intersects each set) for any $0 \le k \le d-1$. This result is a common generalization of …
A rooted spanning tree of a graph $G$ is called normal if the endvertices of all edges of $G$ are comparable in the tree order. It is well known that every finite connected graph has a normal spanning tree (also known as depth-first search tree). Also, all countable graphs have normal spanning trees, but uncountable …
What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of \(\chi\)-bounded classes of graphs --- classes where a large clique is essentially the only reason for large chromatic number. Unfortunately, many interesting graph classes are not …
Modern practical software libraries that are designed for isomorphism tests and symmetry computation rely on combinatorial techniques combined with techniques from algorithmic group theory. The Weisfeiler-Leman algorithm is such a combinatorial technique. When taking a certain view from descriptive complexity theory, the algorithm is universal. After an introduction to problems arising in symmetry computation and …
Let S and T be two sets of points in a metric space with a total of n points. Each point in S and T has an associated value that specifies an upper limit on how many points it can be matched with from the other set. A multimatching between S and T is a way of pairing points such that each point in S is matched with at least as many …
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 the complete structure of $S$-free tournaments is known. Let $\triangle(1, 2, 2)$ be a tournament obtained from the cyclic triangle by substituting two-vertex tournaments for …
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 girth and chromatic number that have a proper edge colouring in which each cycle contains no colour exactly once. The result presented is the joint …
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 upper bound. One natural extension of this theorem is that of restricting the possiblechoices for the sets. That is, given a simplicial complex, what is …
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 hamiltonian. In 2018, Ding and Marshall posed the problem of characterizing the minor-minimal 3-connected non-hamiltonian graphs. They conjectured that every 3-connected non-hamiltonian graph contains a …
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 recent works, we prove an optimal combination of these two results. We show that given a family $F$ of $n$ convex sets in $\mathbb{R}^d$ such …