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:20211207T163000
DTEND;TZID=Asia/Seoul:20211207T173000
DTSTAMP:20260506T174512
CREATED:20211207T073000Z
LAST-MODIFIED:20240707T080616Z
UID:4804-1638894600-1638898200@dimag.ibs.re.kr
SUMMARY:Eun-Kyung Cho (조은경)\, Independent domination of graphs with bounded maximum degree
DESCRIPTION:The independent domination number of a graph $G$\, denoted $i(G)$\, is the minimum size of an independent dominating set of $G$. In this talk\, we prove a series of results regarding independent domination of graphs with bounded maximum degree. \nLet $G$ be a graph with maximum degree at most $k$ where $k \ge 1$. We prove that if $k = 4$\, then $i(G) \le \frac{5}{9}|V(G)|$\, which is tight. Generalizing this result and a result by Akbari et al.\, we suggest a conjecture on the upper bound of $i(G)$ for $k \ge 1$\, which is tight if true. \nLet $G’$ be a connected $k$-regular graph that is not $K_{k\, k}$ where $k\geq 3$. We prove that $i(G’)\le \frac{k-1}{2k-1}|V(G’)|$\, which is tight for $k \in \{3\, 4\}$\, generalizing a result by Lam\, Shiu\, and Sun. This result also answers a question by Goddard et al. in the affirmative. \nIn addition\, we show that $\frac{i(G’)}{\gamma(G’)} \le \frac{k^3-3k^2+2}{2k^2-6k+2}$\, strengthening upon a result of Knor\, Škrekovski\, and Tepeh\, where $\gamma(G’)$ is the domination number of $G’$. \nMoreover\, if we restrict $G’$ to be a cubic graph without $4$-cycles\, then we prove that $i(G’) \le \frac{4}{11}|V(G’)|$\, which improves a result by Abrishami and Henning. \nThis talk is based on joint work with Ilkyoo Choi\, Hyemin Kwon\, and Boram Park.
URL:https://dimag.ibs.re.kr/event/2021-12-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211130T163000
DTEND;TZID=Asia/Seoul:20211130T173000
DTSTAMP:20260506T174512
CREATED:20211130T073000Z
LAST-MODIFIED:20240707T080630Z
UID:4852-1638289800-1638293400@dimag.ibs.re.kr
SUMMARY:Seonghyuk Im (임성혁)\, Large clique subdivisions in graphs without small dense subgraphs
DESCRIPTION:What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = \Theta(\sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d\,d}$. However\, this example contains a much smaller subgraph with the almost same average degree\, for example\, one copy of $K_{d\,d}$. \nIn 2017\, Liu and Montgomery proposed the study on the parameter $c_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact\, they conjectured that for small enough $\varepsilon>0$\, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d\, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6\,(\log \log c_{\varepsilon}(G))^6\}$-term. \nAs a corollary\, for every graph $F$\, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term. \nThis is joint work with Jaehoon Kim\, Youngjin Kim\, and Hong Liu.
URL:https://dimag.ibs.re.kr/event/2021-11-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211123T163000
DTEND;TZID=Asia/Seoul:20211123T173000
DTSTAMP:20260506T174512
CREATED:20211123T073000Z
LAST-MODIFIED:20240707T080759Z
UID:4798-1637685000-1637688600@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Ramsey numbers of Boolean lattices
DESCRIPTION:The poset Ramsey number $R(Q_{m}\,Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2}\,Q_{n})\le2n+2$. Recently\, Lu and Thompson\nimproved the upper bound to $\frac{5}{3}n+2$. In this paper\, we solve this problem asymptotically by showing that $R(Q_{2}\,Q_{n})=n+O(n/\log n)$.\nJoint work with Dániel Grósz and Abhishek Methuku.
URL:https://dimag.ibs.re.kr/event/2021-11-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211109T163000
DTEND;TZID=Asia/Seoul:20211109T173000
DTSTAMP:20260506T174512
CREATED:20211109T073000Z
LAST-MODIFIED:20240705T181024Z
UID:4588-1636475400-1636479000@dimag.ibs.re.kr
SUMMARY:Jaehoon Kim (김재훈)\, 2-complexes with unique embeddings in 3-space
DESCRIPTION:A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere\, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.
URL:https://dimag.ibs.re.kr/event/2021-11-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211102T163000
DTEND;TZID=Asia/Seoul:20211102T173000
DTSTAMP:20260506T174512
CREATED:20211109T073000Z
LAST-MODIFIED:20240707T080853Z
UID:4780-1635870600-1635874200@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Maximal 3-wise intersecting families
DESCRIPTION:A family $\mathcal F$ of subsets of {1\,2\,…\,n} is called maximal k-wise intersecting if every collection of at most k members from $\mathcal F$ has a common element\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. In 1974\, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family\, for k≥3. We resolve this problem for k=3 and n even and sufficiently large. \nThis is joint work with Kevin Hendrey\, Casey Tompkins\, and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-11-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211026T163000
DTEND;TZID=Asia/Seoul:20211026T173000
DTSTAMP:20260506T174512
CREATED:20211026T073000Z
LAST-MODIFIED:20240707T080901Z
UID:4709-1635265800-1635269400@dimag.ibs.re.kr
SUMMARY:Donggyu Kim (김동규)\, 𝝘-graphic delta-matroids and their applications
DESCRIPTION:Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$\, which generalizes a graphic delta-matroid. \nFor an abelian group $\Gamma$\, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid\, which we call a $\Gamma$-graphic delta-matroid\, and provide a polynomial-time algorithm to solve the separation problem\, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$\, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$\, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$. \nThis is joint work with Duksang Lee and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-10-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211012T163000
DTEND;TZID=Asia/Seoul:20211012T173000
DTSTAMP:20260506T174512
CREATED:20211012T073000Z
LAST-MODIFIED:20240707T080915Z
UID:4374-1634056200-1634059800@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, Majority dynamics on sparse random graphs
DESCRIPTION:Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini\, Chan\, O’Donnell\, Tamuz and Tan conjectured that\, in the Erdős-Rényi random graph $G(n\,p)$\, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$. \nThis conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis\, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin\, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n\,p)$\, where $\lambda’ n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda’>0$. \nJoint work with Debsoumya Chakraborti\, Jeong Han Kim and Tuan Tran.
URL:https://dimag.ibs.re.kr/event/2021-10-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211005T163000
DTEND;TZID=Asia/Seoul:20211005T173000
DTSTAMP:20260506T174512
CREATED:20211005T073000Z
LAST-MODIFIED:20240707T080940Z
UID:4503-1633451400-1633455000@dimag.ibs.re.kr
SUMMARY:Eunjin Oh (오은진)\, Feedback Vertex Set on Geometric Intersection Graphs
DESCRIPTION:I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k\, if it exists\, which runs in time $2^{O(\sqrt{k})}(n + m)$\, where $n$ and $m$ denote the numbers of vertices and edges\, respectively. This improves the $2^{O(\sqrt{k}\log k)}(n + m)$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017].
URL:https://dimag.ibs.re.kr/event/2021-10-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210928T163000
DTEND;TZID=Asia/Seoul:20210928T173000
DTSTAMP:20260506T174512
CREATED:20210928T073000Z
LAST-MODIFIED:20240707T080955Z
UID:4452-1632846600-1632850200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, Extremal functions for sparse minors
DESCRIPTION:The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor\, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005)\, Norin\, Reed\, Thomason and Wood (2020)\, and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$\, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results\, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example\, we prove that for every planar graph $H$\, \[c(H) = (1+o(1))\max (v(H)/2\, v(H)-\alpha(H))\,\] extending recent results of Haslegrave\, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.
URL:https://dimag.ibs.re.kr/event/2021-09-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210907T163000
DTEND;TZID=Asia/Seoul:20210907T173000
DTSTAMP:20260506T174512
CREATED:20210907T073000Z
LAST-MODIFIED:20240705T182054Z
UID:4495-1631032200-1631035800@dimag.ibs.re.kr
SUMMARY:Dabeen Lee (이다빈)\, Mixing sets\, submodularity\, and chance-constrained optimization
DESCRIPTION:A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk\, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular\, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then\, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull. This is based on joint work with Fatma Fatma Kılınç-Karzan and Simge Küçükyavuz.
URL:https://dimag.ibs.re.kr/event/2021-09-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210831T163000
DTEND;TZID=Asia/Seoul:20210831T173000
DTSTAMP:20260506T174512
CREATED:20210831T073000Z
LAST-MODIFIED:20240707T081024Z
UID:4341-1630427400-1630431000@dimag.ibs.re.kr
SUMMARY:Cheolwon Heo (허철원)\, Representations of even-cycle matroids
DESCRIPTION:A signed graph is a pair $(G\,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. A cycle $C$ of $G$ is a subset of edges of $G$ such that every vertex of the subgraph of $G$ induced by $C$ has an even degree. We say that $C$ is even in $(G\,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise\, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G\,\Sigma)$ such that circuits of $M$ precisely corresponds to inclusion-wise minimal non-empty even cycles of $(G\,\Sigma)$. For even-cycle matroids\, two fundamental questions arise:\n(1) what is the relationship between two signed graphs representing the same even-cycle matroids?\n(2) how many signed graphs can an even-cycle matroid have?\nFor (a)\, we characterize two signed graphs $(G_1\,\Sigma_1)$ and $(G_2\,\Sigma_2)$ where $G_1$ and $G_2$ are $4$-connected that represent the same even-cycle matroids.\nFor (b)\, we introduce pinch-graphic matroids\, which can generate exponentially many representations even when the matroid is $3$-connected. An even-cycle matroid is a pinch-graphic matroid if there exists a signed graph with a pair of vertices such that every odd cycle intersects with at least one of them. We prove that there exists a constant $c$ such that if a matroid is even-cycle matroid that is not pinch-graphic\, then the number of representations is bounded by $c$. This is joint work with Bertrand Guenin and Irene Pivotto.
URL:https://dimag.ibs.re.kr/event/2021-08-31/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210824T163000
DTEND;TZID=Asia/Seoul:20210824T173000
DTSTAMP:20260506T174512
CREATED:20210810T073000Z
LAST-MODIFIED:20240707T081032Z
UID:4212-1629822600-1629826200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, A Constant-factor Approximation for Weighted Bond Cover
DESCRIPTION:The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks\, given a weighted graph $G$\, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal F$-Vertex Deletion. Only three cases of minor-closed $\mathcal F$ are known to admit constant-factor approximations\, namely Vertex Cover\, Feedback Vertex Set and Diamond Hitting Set. \nWe study the problem for the class $\mathcal F$ of $\theta_c$-minor-free graphs\, under the equivalent setting of the Weighted c-Bond Cover\, and present a constant-factor approximation algorithm using the primal-dual method. For this\, we leverage a structure theorem implicit in [Joret et al.\, SIDMA’14] which states the following: any graph $G$ containing a $\theta_c$-minor-model either contains a large two-terminal protrusion\, or contains a constant-size $\theta_c$-minor-model\, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case\, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case\, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal F$-Vertex Deletion\, our result may be useful as a template for algorithms for other minor-closed families. \nThis is joint work with Euiwoong Lee and Dimitrios M. Thilikos.
URL:https://dimag.ibs.re.kr/event/2021-08-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210817T163000
DTEND;TZID=Asia/Seoul:20210817T173000
DTSTAMP:20260506T174512
CREATED:20210817T073000Z
LAST-MODIFIED:20240707T081153Z
UID:4242-1629217800-1629221400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Two results on graphs with holes of restricted lengths
DESCRIPTION:We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006\, Chudnovksy\, Seymour\, Robertson\, and Thomas famously proved that a graph is perfect if and only if it does not contain an odd hole or a complement of an odd hole. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc provided a structural description of the class of even-hole-free graphs. I will describe the structure of all graphs that contain only holes of length $\ell$ for every $\ell \geq 7$ (joint work with Jake Horsfield\, Myriam Preissmann\, Paul Seymour\, Ni Luh Dewi Sintiari\, Cléophée Robin\, Nicolas Trotignon\, and Kristina Vuškovíc. \nAnalysis of how holes interact with graph structure has yielded detection algorithms for holes of various lengths and parities. In 1991\, Bienstock showed it is NP-Hard to test whether a graph G has an even (or odd) hole containing a specified vertex $v \in V(G)$. In 2002\, Conforti\, Cornuéjols\, Kapoor\, and Vuškovíc gave a polynomial-time algorithm to recognize even-hole-free graphs using their structure theorem. In 2003\, Chudnovsky\, Kawarabayashi\, and Seymour provided a simpler and slightly faster algorithm to test whether a graph contains an even hole. In 2019\, Chudnovsky\, Scott\, Seymour\, and Spirkl provided a polynomial-time algorithm to test whether a graph contains an odd hole. Later that year\, Chudnovsky\, Scott\, and Seymour strengthened this result by providing a polynomial-time algorithm to test whether a graph contains an odd hole of length at least $\ell$ for any fixed integer $\ell \geq 5$. I will present a polynomial-time algorithm (joint work with Paul Seymour) to test whether a graph contains an even hole of length at least $\ell$ for any fixed integer $\ell \geq 4$.
URL:https://dimag.ibs.re.kr/event/2021-08-17/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210810T163000
DTEND;TZID=Asia/Seoul:20210810T173000
DTSTAMP:20260506T174512
CREATED:20210817T073000Z
LAST-MODIFIED:20240705T183002Z
UID:4408-1628613000-1628616600@dimag.ibs.re.kr
SUMMARY:Duksang Lee (이덕상)\, Intertwining connectivities for vertex-minors and pivot-minors
DESCRIPTION:We show that for pairs (Q\,R) and (S\,T) of disjoint subsets of vertices of a graph G\, if G is sufficiently large\, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids. Joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-08-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210727T150000
DTEND;TZID=Asia/Seoul:20210727T160000
DTSTAMP:20260506T174512
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210720T163000
DTEND;TZID=Asia/Seoul:20210720T173000
DTSTAMP:20260506T174512
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:20210713T163000
DTEND;TZID=Asia/Seoul:20210713T173000
DTSTAMP:20260506T174512
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:20210706T163000
DTEND;TZID=Asia/Seoul:20210706T173000
DTSTAMP:20260506T174512
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:20210629T163000
DTEND;TZID=Asia/Seoul:20210629T173000
DTSTAMP:20260506T174512
CREATED:20210614T232723Z
LAST-MODIFIED:20240707T081306Z
UID:4251-1624984200-1624987800@dimag.ibs.re.kr
SUMMARY:Jeong Ok Choi (최정옥)\, Invertibility of circulant matrices of arbitrary size
DESCRIPTION:In this talk\, we present sufficient conditions to guarantee the invertibility of rational circulant matrices with any given size. These sufficient conditions consist of linear combinations in terms of the entries in the first row with integer coefficients. Using these conditions we show the invertibility of some family of circulant matrices with particular forms of integers generated by a primitive element in $\mathbb{Z}_p$. Also\, the invertibility of circulant 0\, 1-matrices can be argued combinatorially by applying sufficient conditions. This is joint work with Youngmi Hur.
URL:https://dimag.ibs.re.kr/event/2021-06-29/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210622T163000
DTEND;TZID=Asia/Seoul:20210622T173000
DTSTAMP:20260506T174512
CREATED:20210430T062352Z
LAST-MODIFIED:20240705T184213Z
UID:4028-1624379400-1624383000@dimag.ibs.re.kr
SUMMARY:Hongseok Yang (양홍석)\, DAG-symmetries and Symmetry-Preserving Neural Networks
DESCRIPTION:The preservation of symmetry is one of the key tools for designing data-efficient neural networks. A representative example is convolutional neural networks (CNNs); they preserve translation symmetries\, and this symmetry preservation is often attributed to their success in real-world applications. In the machine-learning community\, there is a growing body of work that explores a new type of symmetries\, both discrete and continuous\, and studies neural networks that preserve those symmetries. \nIn this talk\, I will explain what I call DAG-symmetries and our preliminary results on the shape of neural networks that preserve these symmetries. DAG-symmetries are finite variants of DAG-exchangeability developed by Jung\, Lee\, Staton\, and Yang (2020) in the context of probabilistic symmetries. Using these symmetries\, we can express that when a neural network works on\, for instance\, sets of bipartite graphs whose edges are labelled with reals\, the network depends on neither the order of elements in the set nor the identities of vertices of the graphs. I will explain how a group of specific DAG-symmetries is constructed by applying a form of wreath product over a given finite DAG. Then\, I will explain what linear layers of neural networks preserving these symmetries should look like. \nThis is joint work with Dongwoo Oh.
URL:https://dimag.ibs.re.kr/event/2021-06-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210608T150000
DTEND;TZID=Asia/Seoul:20210608T160000
DTSTAMP:20260506T174512
CREATED:20210514T092018Z
LAST-MODIFIED:20240707T081316Z
UID:4080-1623164400-1623168000@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Classes of intersection digraphs with good algorithmic properties
DESCRIPTION:An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v\, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs\, not many algorithmic applications on intersection digraphs have been developed. \nMotivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width\, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular\, we show that as a natural extension of $H$-graphs\, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$\, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020] \nFor applications\, we introduce a novel framework of directed versions of locally checkable problems\, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width\, when a branch decomposition is given. Locally checkable problems include Kernel\, Dominating Set\, and Directed $H$-Homomorphism. \nThis seminar is a part of the\n“Round the World Relay in Combinatorics”\non June 8\, 2021.\nhttp://people.maths.ox.ac.uk/scott/relay.htm \n\n2:00 UTC\, 11:00 KST Melbourne (Australia) Monash University\nDavid Wood (Monash University)\, Universality in Minor-Closed Graph Classes\n3:00 UTC\, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences\nBaogang Xu (Nanjing Normal University\, China)\, On coloring of graphs of girth 2l+1 without longer odd holes\n4:00 UTC\, 13:00 KST Auckland (New Zealand) The University of Auckland\nJeroen Schillewaert (University of Auckland)\, Constructing highly regular expanders from hyperbolic Coxeter groups\n5:00 UTC\, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia\nGordon Royle (University of Western Australia (UWA))\, Real chromatic roots of planar graphs\n6:00 UTC\, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group\nO-joung Kwon (Incheon National University and IBS Discrete Mathematics Group)\, Classes of intersection digraphs with good algorithmic properties\n7:00 UTC\, 16:00 KST Krakow (Poland) Jagiellonian University\nBartosz Walczak (Jagiellonian)\, Coloring polygon visibility graphs and their generalizations\n8:00 UTC\, 17:00 KST Glasgow (UK) University of Glasgow\nHeng Guo (University of Edinburgh)\, A Markov chain approach towards the sampling Lovász local lemma\n9:00 UTC\, 18:00 KST London (UK) London School of Economics\nAnnika Heckel (LMU)\, How does the chromatic number of a random graph vary?\n10:00 UTC\, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology\nNoga Alon (Princeton and Tel Aviv)\n11:00 UTC\, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University\nLászló Lovász (Eotvos University\, Budapest)\n12:00 UTC\, 21:00 KST Bordeaux (France) LaBRI\nCarla Groenland (Utrecht University)\, Universal Graphs and Labelling Schemes\n13:00 UTC\, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University\nDeepak Bal (Montclair State University)\n14:00 UTC\, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics\nDhruv Mubayi (University of Illinois at Chicago)\, The feasible region of hypergraphs\n15:00 UTC\, 00:00 KST Brno (Czech) Masaryk University\nJames Davies (University of Waterloo)\, Colouring circle graphs and their generalisations\n16:00 UTC\, 01:00 KST Oxford (UK) University of Oxford\nJacob Fox (Stanford University)\, Removal lemmas\n17:00 UTC\, 02:00 KST Columbus (USA) Ohio State University\nAllan Sly (Princeton University)\n18:00 UTC\, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada\nMarcelo Campos (IMPA)\, The singularity probability of a random symmetric matrix is exponentially small\n19:00 UTC\, 04:00 KST Atlanta (USA) Georgia Institute of Technology\nJim Geelen (University of Waterloo)\, Homomorphisms and colouring for graphs and binary matroids\n20:00 UTC\, 05:00 KST Santiago (Chile) Universidad de Chile\nDavid Conlon (Caltech)\n21:00 UTC\, 06:00 KST Burnaby (Canada) Simon Fraser University\nFan Chung (UCSD)\, Trees and forests in Green’s functions of a graph\n22:00 UTC\, 07:00 KST Victoria (Canada) University of Victoria\nAndrew Suk (UCSD)\, Turán-type problems for point-line incidences\n23:00 UTC\, 08:00 KST Fairbanks (USA) University of Alaska\nRon Gould (Emory)\, Chorded cycles\n\n 
URL:https://dimag.ibs.re.kr/event/2021-06-08/
LOCATION:Zoom ID: 875 9395 3555 (relay) [CLOSED]
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210601T163000
DTEND;TZID=Asia/Seoul:20210601T173000
DTSTAMP:20260506T174512
CREATED:20210517T132410Z
LAST-MODIFIED:20240707T081332Z
UID:4091-1622565000-1622568600@dimag.ibs.re.kr
SUMMARY:Doowon Koh (고두원)\, Mattila-Sjölin type functions: A finite field model
DESCRIPTION:Let $\mathbb{F}_q$ be a finite field of order $q$ which is a prime power. In the finite field setting\, we say that a function $\phi\colon \mathbb{F}_q^d\times \mathbb{F}_q^d\to \mathbb{F}_q$ is a Mattila-Sjölin type function in $\mathbb{F}_q^d$ if for any $E\subset \mathbb{F}_q^d$ with $|E|\gg q^{\frac{d}{2}}$\, we have $\phi(E\, E)=\mathbb{F}_q$. The main purpose of this talk is to present the existence of such a function. More precisely\, we will construct a concrete function $\phi: \mathbb{F}_q^4\times \mathbb{F}_q^4\to \mathbb{F}_q$ with $q\equiv 3 \mod{4}$ such that if $E\subset \mathbb F_q^4$ with $|E|>q^2\,$ then $\phi(E\,E)=\mathbb F_q$. This is a joint work with Daewoong Cheong\, Thang Pham\, and Chun-Yen Shen.
URL:https://dimag.ibs.re.kr/event/2021-06-01/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210525T163000
DTEND;TZID=Asia/Seoul:20210525T173000
DTSTAMP:20260506T174512
CREATED:20210520T102659Z
LAST-MODIFIED:20240707T081345Z
UID:4112-1621960200-1621963800@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Limit shape of lattice Zonotopes
DESCRIPTION:A convex lattice polytope is the convex hull of a set of integral points. Vershik conjectured the existence of a limit shape for random convex lattice polygons\, and three proofs of this conjecture were given in the 1990s by Bárány\, by Vershik\, and by Sinai. To state this old result more precisely\, there is a convex curve $L \subset [0\,1]^2$ such that the following holds. Let $P$ be a convex lattice polygon chosen uniformly at random from the set of convex lattice polygons with vertices in $[0\,N]^2$. Then\, for $N$ sufficiently large\, $(1/N)P$ will be arbitrarily close (in Hausdorff distance) to $L$ with high probability. It is an open question whether there exists a limit shape for three dimensional polyhedra. \nI will discuss this problem and some relatives\, as well as joint work with Bárány and Bureaux on the existence of a limit shape for lattice zonotopes in all dimensions.
URL:https://dimag.ibs.re.kr/event/2021-05-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210518T163000
DTEND;TZID=Asia/Seoul:20210518T173000
DTSTAMP:20260506T174512
CREATED:20210420T015329Z
LAST-MODIFIED:20240705T185044Z
UID:3967-1621355400-1621359000@dimag.ibs.re.kr
SUMMARY:Pascal Gollin\, Enlarging vertex-flames in countable digraphs
DESCRIPTION:A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large\, where the latter means that it preserves the local connectivity to each vertex from the root. A structural generalisation of vertex-flames and largeness to infinite digraphs was given by Joó and the analogue of Lovász’ result for countable digraphs was shown. \nIn this talk\, I present a strengthening of this result stating that in every countable rooted digraph each vertex-flame can be extended to a large vertex-flame. \nJoint work with Joshua Erde and Attila Joó.
URL:https://dimag.ibs.re.kr/event/2021-05-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210511T163000
DTEND;TZID=Asia/Seoul:20210511T173000
DTSTAMP:20260506T174512
CREATED:20210420T015716Z
LAST-MODIFIED:20240705T185043Z
UID:3969-1620750600-1620754200@dimag.ibs.re.kr
SUMMARY:Mark Siggers\, The list switch homomorphism problem for signed graphs
DESCRIPTION:A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other by the iteration of the local action of switching all signs on edges incident to a given vertex\, we say that there is a switch homomorphism from a signed graph $G$ to a signed graph $H$ if there is a sign preserving homomorphism from $G’$ to $H$ for some graph $G’$ that is switch equivalent to $G$.  By reductions to CSP this problem\, and its list version\, are known to be either polynomial time solvable or NP-complete\, depending on $H$.  Recently those signed graphs $H$ for which the switch homomorphism problem is in $P$ were characterised.  Such a characterisation is yet unknown for the list version of the problem. \nWe talk about recent work towards such a characterisation and about how these problems fit in with bigger questions that still remain around the recent CSP dichotomy theorem.
URL:https://dimag.ibs.re.kr/event/2021-05-11/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210427T163000
DTEND;TZID=Asia/Seoul:20210427T173000
DTSTAMP:20260506T174512
CREATED:20210419T130854Z
LAST-MODIFIED:20240705T185048Z
UID:3961-1619541000-1619544600@dimag.ibs.re.kr
SUMMARY:Jungho Ahn (안정호)\, Well-partitioned chordal graphs with the obstruction set and applications
DESCRIPTION:We introduce a new subclass of chordal graphs that generalizes split graphs\, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure\, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First\, the cliques in the partition can be arranged in a tree structure\, and second\, each clique is of arbitrary size. We mainly provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs and give a polynomial-time algorithm that given any graph\, either finds an obstruction or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices are in FPT\, parameterized by k\, on well-partitioned chordal graphs\, while on chordal graphs\, these problems are only known to be in XP. From the other end\, we introduce some problems that are polynomial-time solvable on split graphs but become NP-complete on well-partitioned chordal graphs. \nThis is joint work with Lars Jaffke\, O-joung Kwon\, and Paloma T. Lima.
URL:https://dimag.ibs.re.kr/event/2021-04-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210420T163000
DTEND;TZID=Asia/Seoul:20210420T173000
DTSTAMP:20260506T174512
CREATED:20210416T123209Z
LAST-MODIFIED:20240705T185049Z
UID:3946-1618936200-1618939800@dimag.ibs.re.kr
SUMMARY:Sang-il Oum (엄상일)\, What is an isotropic system?
DESCRIPTION:Bouchet introduced isotropic systems in 1983 unifying some combinatorial features of binary matroids and 4-regular graphs. The concept of isotropic system is a useful tool to study vertex-minors of graphs and yet it is not well  known. I will give an introduction to isotropic systems.
URL:https://dimag.ibs.re.kr/event/2021-04-20/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210413T163000
DTEND;TZID=Asia/Seoul:20210413T173000
DTSTAMP:20260506T174512
CREATED:20210329T063026Z
LAST-MODIFIED:20240705T190013Z
UID:3866-1618331400-1618335000@dimag.ibs.re.kr
SUMMARY:William Overman\, Some Ordered Ramsey Numbers of Graphs on Four Vertices
DESCRIPTION:Ordered Ramsey numbers were introduced in 2014 by Conlon\, Fox\, Lee\, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We show the first nontrivial results for ordered Ramsey numbers of specific small graphs. In particular we prove upper bounds for orderings of graphs on four vertices\, and determine some numbers exactly using  SAT solvers for lower bounds. These results are in the spirit of exact calculations for classical Ramsey numbers and use only elementary combinatorial arguments. \nThis is joint work with Jeremy Alm\, Kayla Coffey\, and Carolyn Langhoff.
URL:https://dimag.ibs.re.kr/event/2021-04-13/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210406T163000
DTEND;TZID=Asia/Seoul:20210406T173000
DTSTAMP:20260506T174512
CREATED:20210308T061306Z
LAST-MODIFIED:20240705T190041Z
UID:3731-1617726600-1617730200@dimag.ibs.re.kr
SUMMARY:Rutger Campbell\, Matroid orientability and representability
DESCRIPTION:In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
URL:https://dimag.ibs.re.kr/event/2021-04-06/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210330T163000
DTEND;TZID=Asia/Seoul:20210330T173000
DTSTAMP:20260506T174512
CREATED:20210225T090612Z
LAST-MODIFIED:20240707T081638Z
UID:3676-1617121800-1617125400@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, 3-uniform hypergraphs avoiding a cycle of length four
DESCRIPTION:We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya. Joint work with Ergemlidze\, Győri\, Methuku\, Salia.
URL:https://dimag.ibs.re.kr/event/2021-03-30/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR