Loading Events

Upcoming Events › Discrete Math Seminar

Events Search and Views Navigation

Event Views Navigation

June 2019


Jinyoung Park (박진영), The number of maximal independent sets in the Hamming cube


Jinyoung Park (박진영)
Department of Mathematics, Rutgers University, USA
June 3 Monday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

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 »

Suil O (오수일), An odd [1,b]-factor in regular graphs from eigenvalues


Suil O (오수일)
Department of Applied Mathematics and Statistics, SUNY-Korea
June 19 Wednesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

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

June 25 Tuesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

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 »
+ Export Events
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright (c) IBS 2018. All rights reserved.