Mehtaab Sawhney, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture

Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]

An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e., if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One

Alexander Clifton, Ramsey Theory for Diffsequences

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

Van der Waerden's theorem states that any coloring of $\mathbb{N}$ with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number $W(r,k)$ which is the smallest $n$ such that any $r$-coloring of $\{1,2,\cdots,n\}$ guarantees the presence of a monochromatic arithmetic progression of length

Santiago Guzmán-Pro, Local expressions of graphs classes

Zoom ID: 869 4632 6610 (ibsdimag)

A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes, the set of minimal obstructions might be infinite, or too complicated to describe. For instance, for any $k\ge 3$, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$

Zixiang Xu (徐子翔), On the degenerate Turán problems

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

For a graph $F$, the Turán number is the maximum number of edges in an $n$-vertex simple graph not containing $F$. The celebrated Erdős-Stone-Simonovits Theorem gives that \ where $\chi(F)$ is the chromatic number of $H$. This theorem asymptotically solves the problem when $\chi(F)\geqslant 3$. In case of bipartite graphs $F$, not even the order of magnitude

Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube

Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]

A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper, we show that $r(Q_n)=O(2^{2n−cn})$ for a universal constant $c>0$, improving upon the previous best-known bound $r(Q_n)=O(2^{2n})$, due to Conlon, Fox, and Sudakov.

Nika Salia, Exact results for generalized extremal problems forbidding an even cycle

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

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

Xavier Goaoc, Order types and their symmetries

Room 1501, Bldg. E6-1, KAIST

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.

Florent Koechlin, Uniform random expressions lack expressivity

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

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

Dabeen Lee (이다빈), Non-smooth and Hölder-smooth submodular optimization

Room 1501, Bldg. E6-1, KAIST

We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an guarantee when the function is monotone and Hölder-smooth, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that

Jungho Ahn (안정호), Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

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

Let $\mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers. The $(p,r,\mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^p\setminus N_G^r$ has no induced subgraph isomorphic to a graph in $\mathcal{F}$, where

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.