BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210706T163000
DTEND;TZID=Asia/Seoul:20210706T173000
DTSTAMP:20260416T022517
CREATED:20210518T100610Z
LAST-MODIFIED:20240707T081252Z
UID:4101-1625589000-1625592600@dimag.ibs.re.kr
SUMMARY:Suil O (오수일)\, Eigenvalues and [a\, b]-factors in regular graphs
DESCRIPTION:For positive integers\, $r \ge 3\, h \ge 1\,$ and $k \ge 1$\, Bollobás\, Saito\, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor in 1985. Lu gave an upper bound for the third-largest eigenvalue in a connected $r$-regular graph to have a $k$-factor in 2010. Gu found an upper bound for certain eigenvalues in an $h$-edge-connected $r$-regular graph to have a $k$-factor in 2014. For positive integers $a \le b$\, an even (or odd) $[a\, b]$-factor of a graph $G$ is a spanning subgraph $H$ such that for each vertex $v \in V (G)$\, $d_H(v)$ is even (or odd) and $a \le d_H(v) \le b$. In this talk\, we provide best upper bounds (in terms of $a\, b$\, and $r$) for certain eigenvalues (in terms of $a\, b\, r$\, and $h$) in an $h$-edge-connected $r$-regular graph $G$ to guarantee the existence of an even $[a\, b]$-factor or an odd $[a\, b]$-factor. This result extends the one of Bollobás\, Saito\, and Wormald\, the one of Lu\, and the one of Gu.
URL:https://dimag.ibs.re.kr/event/2021-07-06/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210713T163000
DTEND;TZID=Asia/Seoul:20210713T173000
DTSTAMP:20260416T022517
CREATED:20210519T133727Z
LAST-MODIFIED:20240707T081244Z
UID:4110-1626193800-1626197400@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, $K_{r+1}$-saturated graphs with small spectral radius
DESCRIPTION:For a graph $H$\, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$\, $G+e$ contains $H$. In this note\, we prove a sharp lower bound for the number of paths and walks on length 2 in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to \infty$.
URL:https://dimag.ibs.re.kr/event/2021-07-13/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210720T163000
DTEND;TZID=Asia/Seoul:20210720T173000
DTSTAMP:20260416T022517
CREATED:20210601T234138Z
LAST-MODIFIED:20240707T081226Z
UID:4190-1626798600-1626802200@dimag.ibs.re.kr
SUMMARY:Semin Yoo (유세민)\, Combinatorics of Euclidean spaces over finite fields
DESCRIPTION:$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$\, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients\, denoted by $\binom{n}{k}_{q}$\, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$\, this reverts to the binomial coefficients which measure the number of $k$-sets in $\left [ n \right ]$. \nIn this talk\, we add one more structure in $\mathbb{F}_{q}^{n}$\, which is the Euclidean quadratic form: $\text{dot}_{n}:=x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}$. It turns out that the number of quadratic subspaces of Euclidean type in $(\mathbb{F}_{q}^{n}\,\text{dot}_{n})$ can be described as the form of the analogue of binomial coefficients. The main goal of this talk is to define the dot-analogues of the binomial coefficients and to study related combinatorics. No prior knowledge about the theory of quadratic form is required.
URL:https://dimag.ibs.re.kr/event/2021-07-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210727T150000
DTEND;TZID=Asia/Seoul:20210727T160000
DTSTAMP:20260416T022517
CREATED:20210623T055635Z
LAST-MODIFIED:20240707T081214Z
UID:4288-1627398000-1627401600@dimag.ibs.re.kr
SUMMARY:Euiwoong Lee (이의웅)\, The Karger-Stein algorithm is optimal for k-cut
DESCRIPTION:In the k-cut problem\, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with the running time of $O(n^{2k-2})$. Using tree packings\, Thorup gave a deterministic algorithm that has the same running time. \nIn this work\, we show that for any fixed $k\ge 2$\, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least $\Omega(n^{-k})$. This also gives an extremal bound of $O(n^k)$ on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are essentially tight. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta)OPT/k$\, using the Sunflower lemma. \nJoint work with Anupam Gupta\, David G. Harris\, and Jason Li.
URL:https://dimag.ibs.re.kr/event/2021-07-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR