기초과학연구원 이산수학그룹
Consider the following hat guessing game: $n$ players are placed on $n$ vertices of a graph, each wearing a hat whose color is arbitrarily chosen from a set of $q$ possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to …
A theoretical dynamical system is a pair (X,T) where X is a compact metric space and T is a self homeomorphism of X. The topological entropy of a theoretical dynamical system (X,T), first introduced in 1965 by Adler, Konheim and McAndrew, is a nonnegative real number that measures the complexity of the system. Systems with positive …
The well-known 1-2-3 Conjecture by Karoński, Łuczak and Thomason states that the edges of any connected graph with at least three vertices can be assigned weights 1, 2 or 3 so that for each edge $uv$ the sums of the weights at $u$ and at $v$ are distinct. The list version of the 1-2-3 Conjecture …
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. …
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 …