Jozef Skokan, Separating the edges of a graph by a linear number of paths

Room B332 IBS (기초과학연구원)

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 a path in P which contains e but not f. We improve this upper bound to 19n, thus answering a question of Katona and confirming

Oliver Janzer, Small subgraphs with large average degree

Room B332 IBS (기초과학연구원)

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 at least $d$ contains a subgraph of average degree at least $s$ on at most $nd^{-\frac{s}{s-2}}(\log d)^{O_s(1)}$ vertices. This is optimal up to the polylogarithmic

Suyun Jiang (江素云), How connectivity affects the extremal number of trees

Room B332 IBS (기초과학연구원)

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 unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree

Minho Cho (조민호), Strong Erdős-Hajnal property on chordal graphs and its variants

Room B332 IBS (기초과학연구원)

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 complement has $K_{m, m}$ as a subgraph where $m \geq \left\lfloor c|V(G)| \right\rfloor$. We prove that the class of chordal graphs satisfies SEH-property with constant

Guanghui Wang (王光辉), Embeddings in uniformly dense hypergraphs

Room B332 IBS (기초과학연구원)

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. In precise, we will mention the uniform Turan density of some hypergraphs.

Chong Shangguan (上官冲), The hat guessing number of graphs

Room B332 IBS (기초과학연구원)

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

Tuan Tran, Complexity of null dynamical systems

Room B109 IBS (기초과학연구원)

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

Xuding Zhu (朱緒鼎), List version of 1-2-3 conjecture

Room B109 IBS (기초과학연구원)

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

Andrzej Grzesik, Rainbow Turán problems

Room S221 IBS (기초과학연구원) Science Culture Center

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

Dong Yeap Kang (강동엽), Hamilton cycles and optimal matchings in a random subgraph of uniform Dirac hypergraphs

Room B332 IBS (기초과학연구원)

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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.