기초과학연구원 이산수학그룹
By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial of an $n$-vertex $k$-uniform hypergraph from the multiset of all induced sub-hypergraphs on $\lfloor \frac{k-1}{k}n \rfloor + 1$ vertices. This generalizes the well-known result 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 …
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 …
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 …