기초과학연구원 이산수학그룹
In a rainbow variant of the Turán problem, we consider $k$ graphs on the same set of vertices and want to determine the smallest possible number of edges in each graph, which guarantees the existence of a copy of a given graph $F$ containing at most one edge from each graph. In other words, we …
A loose cycle is a cyclic ordering of edges such that every two consecutive edges share exactly one vertex. A cycle is Hamilton if it spans all vertices. A codegree of a $k$-uniform hypergraph is the minimum nonnegative integer $t$ such that every subset of vertices of size $k-1$ is contained in $t$ distinct edges. …
Ramsey's Theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. As probabilistic constructions often provide good bounds on quantities in extremal combinatorics, we say that a graph H is common if the random 2-edge-coloring asymptotically minimizes the number of monochromatic copies of H. …
2023 Mini-Workshop on Discrete Geometry will be held on August 9th at Room B332, Institute for Basic Science (IBS), Daejeon, Republic of Korea. The workshop consists of three presentations on recent results and an open problem session. Researchers who are highly interested in this field are welcome to attend. Tentative schedule 10:00-10:50 Michael Dobbins (SUNY …
How can one arrange a collection of convex sets in d-dimensional Euclidean space? This guiding question is fundamental in discrete geometry, and can be made concrete in a variety of ways, for example the study of hyperplane arrangements, embeddability of simplicial complexes, Helly-type theorems, and more. This talk will focus on the classical topic of d-representable …
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such …
Take a prime power $q$, an integer $n\geq 2$, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper, we …
In 1986, Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minor if and only if it is planar. In particular, for every non-planar graph $H$ they gave examples showing that the Erdős-Pósa property does …
The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Wegner's conjecture (1977) states that for a planar graph $G$, the chromatic number $\chi(G^2)$ of $G^2$ is at most 7 if $\Delta(G) …
Even delta-matroids generalize matroids, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field $K$, and we say such an even delta-matroid is representable over the field $K$. Interestingly, a matroid is representable over $K$ …