기초과학연구원 이산수학그룹
Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning …
On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities …
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 …
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 …
Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb …
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 …
Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ …
Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. We prove the following Cantor-Bernstein-type …
To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between …
In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models …