기초과학연구원 이산수학그룹
Generalized extremal problems have been one of the central topics of study in extremal combinatorics throughout the last few decades. One such simple-looking problem, maximizing the number of cliques of a fixed order in a graph with a fixed number of vertices and given maximum degree, was recently resolved by Chase. Settling a conjecture of …
Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subset V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex …
Let $G$ be a graph on $V$ and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose faces are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of $I_n(G)$ for various classes of graphs, focusing on the class of …
For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once $H$ is paired with a $2$-edge-colouring $\alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $\|.\|_H$ (resp. there is $\alpha$ such that …
We introduce some of well-known game-theoretic graph models and related problems. A contagion game model explains how an innovation diffuses over a given network structure and focuses on finding conditions on which structure an innovation becomes epidemic. Regular infinite graphs are interesting examples to explore. We show that regular infinite trees make an innovation least …
Whitney’s 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. In this talk, we present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids. This is based on the joint work with Iain Moffatt.
Extending the classical theorem of Sperner on the maximum size of an antichain in the Boolean lattice, Katona and Tarján introduced a general extremal function $La(n,P)$, defined to be the maximum size of a family of subsets of $$ which does not contain a given poset $P$ among its containment relations. In this talk, I …
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for …
Ramsey's theorem states that, for a fixed graph $H$, every 2-edge-colouring of $K_n$ contains a monochromatic copy of $H$ whenever $n$ is large enough. Perhaps one of the most natural questions after Ramsey's theorem is then how many copies of monochromatic $H$ can be guaranteed to exist. To formalise this question, let the Ramsey multiplicity …
There has been much research on finding a large rainbow matching in a properly edge-colored graph, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barát, Gyárfás, and Sárközy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed, but not …