# Upcoming Events › Discrete Math Seminar

## June 2019

### Speaker

Jinyoung Park (박진영)
Department of Mathematics, Rutgers University, USA

Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$, as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them "stability" results for maximal independent set counts and old…

Find out more »

### Speaker

Suil O (오수일)
Department of Applied Mathematics and Statistics, SUNY-Korea
https://you.stonybrook.edu/suilo/

An odd -factor of a graph is a spanning subgraph $H$ such that for every vertex $v \in V(G)$, $1 \le d_H(v) \le b$, and $d_H(v)$ is odd. For positive integers $r \ge 3$ and $b \le r$, Lu, Wu, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of vertices to guarantee the existence of an odd -factor. In this talk, we improve their bound.

Find out more »

### Patrice Ossona de Mendez, A model theoretical approach to sparsity

We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity, and give some example of applications, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes, characterization of transductions of classes with bounded pathwidth, decompositions of graphs with bounded rank-width into cographs.

Find out more »
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
Discrete Mathematics Group (DIMAG)
Center for Mathematical and Computational Sciences
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr