기초과학연구원 이산수학그룹
Let $F_{k,d}(n)$ be the maximal size of a set ${A}\subseteq $ such that the equation \ has no solution with $a_1,a_2,\ldots,a_k\in A$ and integer $x$. Erdős, Sárközy and T. Sós …
Extremely sparse random binary matrices tend to be singular, due to the likely presence of "local combinatorial dependencies" such as all-zero columns or pairs of identical columns. We discuss this …
We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k, which is updated by edge …
Given a prime power $q \equiv 1 \pmod 4$, the Paley graph of order $q$ is the graph defined over $\mathbb{F}_q$ (the finite field with $q$ elements), such that two …
We present a new cryptomorphic definition of orthogonal matroids with coefficients using Grassmann-Plücker functions. The equivalence is motivated by Cayley's identities expressing principal and almost-principal minors of a skew-symmetric matrix …
Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer, Frieze, and Kannan in 1989, convex-body sampling has been a central problem at the intersection of …
In , Fabianski et. al. developed a simple, yet surprisingly powerful algorithmic framework to develop efficient parameterized graph algorithms. Notably they derive a simple parameterized algorithm for the dominating set …