기초과학연구원 이산수학그룹
We will give an overview of the recent attempts of building a structure theory for graphs centered around First-Order transductions: a notion of containment inspired by finite model theory. Particularly, we will speak about the notions of monadic dependence and monadic stability, their combinatorial characterizations, and the developments on the algorithmic front.
The IBS-DIMAG Workshop on Topology and Combinatorics will be held on November 11, 2024 at Room B332, Institute for Basic Science (IBS), Daejeon, South Korea. Invited Speakers (tentative) Karim Adiprasito (Jussieu Institute of Mathematics) Minho Cho조민호 (IBS Extremal Combinatorics and Probability Group) Niloufar Fuladi (INRIA Center of Université de Lorraine) Minki Kim김민기 (GIST) Dohyeon Lee이도현 (KAIST & …
Ehrhart theory is the study of lattice polytopes, specifically aimed at understanding how many lattice points are inside dilates of a given lattice polytope, and the study has a wide range of connections ranging from coloring graphs to mirror symmetry and representation theory. Recently, we introduced new algebraic tools to understand this theory, and resolve …
In 2005, Bollobás, Janson and Riordan introduced and extensively studied a general model of inhomogeneous random graphs parametrised by graphons. In particular, they studied the emergence of a giant component in these inhomogeneous random graphs by relating them to a broad collection of inhomogeneous Galton-Watson branching processes. Fractional isomorphism of finite graphs is an important …
An $r$-graph is an $r$-regular graph in which every odd set of vertices is connected to its complement by at least $r$ edges. A central question regarding $r$-graphs is determining the maximum number of pairwise disjoint perfect matchings they can contain. This talk explores how edge connectivity influences this parameter. For ${0 \leq \lambda \leq …
For a positive real number $p$, the $p$-norm $\|G\|_p$ of a graph $G$ is the sum of the $p$-th powers of all vertex degrees. We study the maximum $p$-norm $\mathrm{ex}_{p}(n,F)$ of $F$-free graphs on $n$ vertices, focusing on the case where $F$ is a bipartite graph. It is natural to conjecture that for every bipartite …
An edge-weighted graph $G$, possibly with loops, is said to be antiferromagnetic if it has nonnegative weights and at most one positive eigenvalue, counting multiplicities. The number of graph homomorphisms from a graph $H$ to an antiferromagnetic graph $G$ generalises various important parameters in graph theory, including the number of independent sets and proper vertex …
In 1966, Kleitman established that if \( |A \triangle B| \leq d \) for any \( A, B \in \mathcal{F} \), then \( |\mathcal{F}| \leq \sum_{i=0}^{k} \binom{n}{i} \) for \( d = 2k \), and \( |\mathcal{F}| \leq 2 \sum_{i=0}^{k} \binom{n-1}{i} \) for \( d = 2k+1 \). These upper bounds are attained by the …
A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman's celebrated theorem first provided a structural characterization of sets with small doubling over the integers, and subsequently Ruzsa in 1999 proved an analog for abelian groups with …
A replacement action is a function $\mathcal L$ that maps each graph to a collection of subgraphs of smaller size. Given a graph class $\mathcal H$, we consider a general family of graph modification problems, called "$\mathcal L$-Replacement to $\mathcal H$", where the input is a graph $G$ and the question is whether it is …