기초과학연구원 이산수학그룹
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 …
The peaceable queens problem asks to determine the maximum number $a(n)$ such that there is a placement of $a(n)$ white queens and $a(n)$ black queens on an $n \times n$ chessboard so that no queen can capture any queen of the opposite color. We consider the peaceable queens problem and its variant on the toroidal …
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 …
The group \( S_n \) of permutations on \(=\{1,2,\dots,n\} \) is generated by simple transpositions \( s_i = (i,i+1) \). The length \( \ell(\pi) \) of a permutation \( \pi \) is defined to be the minimum number of generators whose product is \( \pi \). It is well-known that the longest element in \( …