기초과학연구원 이산수학그룹
Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists …
We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number $s>2$, we prove that every graph on $n$ vertices with average degree …
The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains …
A graph class $\mathcal{G}$ has the strong Erdős-Hajnal property (SEH-property) if there is a constant $c=c(\mathcal{G}) > 0$ such that for every member $G$ of $\mathcal{G}$, either $G$ or its …
An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in uniformly dense hypergraphs. …
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$ …
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 …
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 …
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 …
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 …