기초과학연구원 이산수학그룹
I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally, we aim to give several characterizations of stability and NIP of a given formula in terms of …
I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally, we aim to give several characterizations of stability and NIP of a given formula in terms of …
Let E be a finite set and I be a collection of subsets of E. When is there a set of real vectors indexed by E such that I correspond to its linearly independent subsets? In 1935, Whitney introduced matroids using some necessary conditions for this. However, complete characterizations with various techniques are intractable. This remains the case even if it is already known …
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 …