Tuesday, February 4, 2025

<< >>  
2025. 1
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
2025. 2
Sun Mon Tue Wed Thu Fri Sat
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
2025. 3
Sun Mon Tue Wed Thu Fri Sat
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
2025-02-11 / 16:30 ~ 17:30
IBS-KAIST 세미나 - 이산수학: A coarse Erdős-Pósa theorem for constrained cycles 인쇄
by Jungho Ahn(KIAS)
An induced packing of cycles in a graph is a set of vertex-disjoint cycles such that the graph has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem shows that for every positive integer $k$, every graph contains $k$ vertex-disjoint cycles or a set of $O(k\log k)$ vertices which intersects every cycle of $G$. We generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least $\ell$ for any integer $\ell$. We show that there exists a function $f(k,\ell)=O(\ell k\log k)$ such that for all positive integers $k$ and $\ell$ with $\ell\geq3$, every graph $G$ contains an induced packing of $k$ cycles of length at least $\ell$ or a set $X$ of at most $f(k,\ell)$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. Furthermore, we extend the result to long cycles containing prescribed vertices. For a graph $G$ and a set $S\subseteq V(G)$, an $S$-cycle in $G$ is a cycle containing a vertex in $S$. We show that for all positive integers $k$ and $\ell$ with $\ell\geq3$, every graph $G$, and every set $S\subseteq V(G)$, $G$ contains an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set $X$ of at most $\ell k^{O(1)}$ vertices such that the closed neighbourhood of $X$ intersects every cycle of $G$. Our proofs are constructive and yield polynomial-time algorithms, for fixed $\ell$, finding either the induced packing of the constrained cycles or the set $X$. This is based on joint works with Pascal Gollin, Tony Huynh, and O-joung Kwon.
2025-02-04 / 16:30 ~ 17:30
IBS-KAIST 세미나 - 이산수학: Longest elements in a semigroup of functions and Slater indices 인쇄
by Jang Soo Kim(Sungkyunkwan University)
The group \( S_n \) of permutations on \([n]=\{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 \( S_n \) has length \( n(n-1)/2 \). Let \( F_n \) be the semigroup of functions \( f:[n]\to[n] \), which are generated by the simple transpositions \( s_i \) and the function \( t:[n]\to[n] \) given by \( t(1) =t(2) = 1 \) and \( t(i) = i \) for \( i\ge3 \). The length \( \ell(f) \) of a function \( f\in F_n \) is defined to be the minimum number of these generators whose product is \( f \). In this talk, we study the length of longest elements in \( F_n \). We also find a connection with the Slater index of a tournament of the complete graph \( K_n \). This is joint work with Yasuhide Numata.
Events for the 취소된 행사 포함 모두인쇄
export to Google calendar  .ics download