기초과학연구원 이산수학그룹
Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few …
The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) - p|U|(|U|-1)/2$, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is a $d$-regular graph on $n$ vertices and $d = O(n^{1/9})$, then the positive discrepancy of $G$ …
Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally, a delta-matroid is a pair $D=(V,\mathcal F)$ where $\mathcal F$ is a collection of subsets of V known as "feasible sets." (They can be thought of as …
We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B, we have that Λ(A) maps homomorphically to B if and only if A maps homomorphically to Γ(B). If this is the case Λ is called the left adjoint to Γ and Γ …
A family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies of graphs in $\mathcal F$ within $G$ such that any vertex of $G$ is contained in at most 2, respectively at most 4, of these …