기초과학연구원 이산수학그룹
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 …
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 …
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 …
Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every …
In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges …
Given a graph $G$, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ …
Let $F$ and $H$ be graphs. The subgraph counting function $\operatorname{ex}(n,H,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a …
Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In …
A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each …
A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in …