기초과학연구원 이산수학그룹
Website: https://www.matrix-inst.org.au/events/structural-graph-theory-downunder-iii/ Program Description: This program, jointly organised by MATRIX and the Discrete Mathematics Group of the Korean Institute for Basic Science (IBS), builds on the “Structural Graph Theory Downunder” …
In 2006, Tao established the Gaussian counterpart of the celebrated Green-Tao theorem on arithmetic progressions of primes. In this talk, I will explain the extension of Tao's theorem and the …
For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of …
In many different areas of mathematics (such as number theory, discrete geometry, and combinatorics), one is often presented with a large "unstructured" object, and asked to find a smaller "structured" …
The Ramsey number $R(k)$ is the minimum n such that every red-blue colouring of the edges of the complete graph on n vertices contains a monochromatic copy of $K_k$. It …
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 …
Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition …
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 …
We define new graph parameters, called flip-width, that generalize treewidth, degeneracy, and generalized coloring numbers for sparse graphs, and clique-width and twin-width for dense graphs. The flip-width parameters are defined …
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 …