# Upcoming Events › Discrete Math Seminar

## October 2019

### Speaker

For a graph $H$ and an integer $k\ge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4$ vertices. For odd cycles, Bondy and Erd\H{o}s in 1973 conjectured that for all $k\ge1$ and $n\ge2$, $R_k(C_{2n+1})=n\cdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large…

Find out more »

### Speaker

Joonkyung Lee (이준경)
Department of Mathematics, University of Hamburg, Germany

For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $p\geq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is a norm. We obtain some results that contribute to the theory of (weakly) norming graphs. Firstly, we show that 'twisted' blow-ups of cycles, which include…

Find out more »

## November 2019

### Speaker

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a…

Find out more »

### Speaker

Ruth Luo
University of California, San Diego
https://faculty.math.illinois.edu/~ruthluo2/

Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$, $f(xy) \cap V(F) = \{x,y\}$. In this talk, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular, this function is strongly related to the generalized Turán function $ex(n,K_r, F)$, i.e., the…

Find out more »

## December 2019

### Speaker

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low…

Find out more »
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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