기초과학연구원 이산수학그룹
We determine the maximum number of copies of $K_{s,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s \ge 2$ and sufficiently large $n$. Moreover, for $s\in\{2,3\}$ and any integer $n$ we obtain the maximum number of cycles of length $2s$ in an $n$-vertex $C_{2s+2}$-free bipartite graph. This is joint work with Ervin Győri (Renyi …
Order types are a combinatorial classification of finite point sets used in discrete and computational geometry. This talk will give an introduction to these objects and their analogue for the projective plane, with an emphasis on their symmetry groups. This is joint work with Emo Welzl.
In computer science, random expressions are commonly used to analyze algorithms, either to study their average complexity, or to generate benchmarks to test them experimentally. In general, these approaches only consider the expressions as purely syntactic trees, and completely ignore their semantics — i.e. the mathematical object represented by the expression. However, two different expressions …
The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every …