BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210322T163000
DTEND;TZID=Asia/Seoul:20210322T173000
DTSTAMP:20260507T032544
CREATED:20210307T042041Z
LAST-MODIFIED:20240705T190041Z
UID:3721-1616430600-1616434200@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, Nested cycles with no geometric crossing
DESCRIPTION:In 1975\, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$\, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders. \nThis is joint work with Irene Gil Fernández\, Jaehoon Kim and Younjin Kim.
URL:https://dimag.ibs.re.kr/event/2021-03-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210316T163000
DTEND;TZID=Asia/Seoul:20210316T173000
DTSTAMP:20260507T032544
CREATED:20210304T000046Z
LAST-MODIFIED:20240705T190041Z
UID:3717-1615912200-1615915800@dimag.ibs.re.kr
SUMMARY:Se-Young Yun (윤세영)\, Regret in Online Recommendation Systems
DESCRIPTION:We propose a theoretical analysis of recommendation systems in an online setting\, where items are sequentially recommended to users over time. In each round\, a user\, randomly picked from a population of m users\, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly\, an item cannot be recommended twice to the same user. The probabilities that a user likes each item are unknown. The performance of the recommendation algorithm is captured through its regret\, considering as a reference an Oracle algorithm aware of these probabilities. We investigate various structural assumptions on these probabilities: we derive for each structure regret lower bounds\, and devise algorithms achieving these limits. Interestingly\, our analysis reveals the relative weights of the different components of regret: the component due to the constraint of not presenting the same item twice to the same user\, that due to learning the chances users like items\, and finally that arising when learning the underlying structure. \nThis is joint work with Kaito Ariu\, Narae Ryu\, and Alexandre Proutière.
URL:https://dimag.ibs.re.kr/event/2021-03-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210309T163000
DTEND;TZID=Asia/Seoul:20210309T173000
DTSTAMP:20260507T032544
CREATED:20210225T090525Z
LAST-MODIFIED:20240707T081706Z
UID:3674-1615307400-1615311000@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Some classical problems in graph saturation
DESCRIPTION:Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$\, but the addition of any edge creates a copy of $F$. The function $\operatorname{sat}(n\,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph. \nIn the first half of the talk\, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964)\, which determined the value of $\operatorname{sat}(n\,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices\, confirming a conjecture of Kritschgau\, Methuku\, Tait\, and Timmons. We further establish a corresponding stability result. \nIn the second half\, we will focus on a central conjecture in graph saturation made by Tuza (1986)\, which states that for every graph $F$\, the limit $\lim_{n \rightarrow \infty} \frac{\operatorname{sat}(n\,F)}{n}$ exists. We make progress in the negative direction of this conjecture. \nThis talk will be based on a joint work with Po-Shen Loh.
URL:https://dimag.ibs.re.kr/event/2021-03-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210302T163000
DTEND;TZID=Asia/Seoul:20210302T173000
DTSTAMP:20260507T032544
CREATED:20210217T044249Z
LAST-MODIFIED:20240707T081721Z
UID:3639-1614702600-1614706200@dimag.ibs.re.kr
SUMMARY:Kevin Hendrey\, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
DESCRIPTION:Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles.  However\, in 1999\, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups\, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. \nA multitude of natural properties of cycles can be encoded in this setting\, for example cycles of length at least $\ell$\, cycles of length $p$ modulo $q$\, cycles intersecting a prescribed set of vertices at least $t$ times\, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties. \nThis is joint work with J. Pascal Gollin\, Ken-ichi Kawarabayashi\, O-joung Kwon\, and Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2021-03-02/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210223T163000
DTEND;TZID=Asia/Seoul:20210223T173000
DTSTAMP:20260507T032544
CREATED:20210217T043908Z
LAST-MODIFIED:20240707T081835Z
UID:3637-1614097800-1614101400@dimag.ibs.re.kr
SUMMARY:Minki Kim (김민기)\, Rainbow paths and rainbow matchings
DESCRIPTION:We prove that if $n \geq 3$\, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves on a previous result\, in which $3n-3$ is replaced by $3n-2$. We also prove a “cooperative” generalization: for $t > 0$ and $n \geq 3$\, any $3n-4+t$ sets of edges\, the union of every $t$ of which contains a matching of size $n$\, have rainbow matching of size $n$. This is joint work with Ron Aharoni\, Joseph Briggs\, and Jinha Kim.
URL:https://dimag.ibs.re.kr/event/2021-02-23/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210216T163000
DTEND;TZID=Asia/Seoul:20210216T173000
DTSTAMP:20260507T032544
CREATED:20210205T012237Z
LAST-MODIFIED:20240705T191023Z
UID:3594-1613493000-1613496600@dimag.ibs.re.kr
SUMMARY:Martin Ziegler\, Quantitative Coding and Complexity Theory of Continuous Data
DESCRIPTION:Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices\, characters as integers\, integers as bit strings\, and vice versa. For such discrete data\, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time\, say). \nBut concerning continuous data\, already real numbers naturally suggest various encodings with very different computational properties. \nWe recall the existing qualitative theory of computably ‘sensible’ encodings of topological spaces; and we newly develop the quantitative theory of complexity-theoretically ‘sensible’ encodings of metric spaces. \nJoint work with Donghyun Lim.
URL:https://dimag.ibs.re.kr/event/2021-02-16/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210209T163000
DTEND;TZID=Asia/Seoul:20210209T173000
DTSTAMP:20260507T032544
CREATED:20210203T050722Z
LAST-MODIFIED:20240705T191023Z
UID:3581-1612888200-1612891800@dimag.ibs.re.kr
SUMMARY:Doowon Koh (고두원)\, On the cone restriction conjecture in four dimensions and applications in incidence geometry
DESCRIPTION:Main purpose of this talk is to introduce a connection between restriction estimates for cones and point-sphere incidence theorems in the finite field setting. First\, we review the finite field restriction problem for cones and address new results on the conical restriction problems. In particular\, we establish the restriction conjecture for the cone in four dimensions. Second\, we study how to apply the conical restriction results to the point-sphere incidence bounds. As a consequence\, we obtain sharp point-sphere incidence bounds when sphere sets are not too big.
URL:https://dimag.ibs.re.kr/event/2021-02-09/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210126T043000
DTEND;TZID=Asia/Seoul:20210126T173000
DTSTAMP:20260507T032544
CREATED:20210125T042312Z
LAST-MODIFIED:20240707T081932Z
UID:3545-1611635400-1611682200@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Minimum saturated families of sets
DESCRIPTION:A family $\mathcal F$ of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets\, and moreover\, no set can be added to $\mathcal F$ while preserving this property. More than 40 years ago\, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least $(1 – 2^{-(s-1)})2^n$. It is a simple exercise to show that every s-saturated family has size at least $2^{n-1}$\, but\, as was mentioned by Frankl and Tokushige\, even obtaining a slightly better bound of $(1/2 + \varepsilon)2^n$\, for some fixed $\varepsilon > 0$\, seems difficult. We prove such a result\, showing that every s-saturated family of subsets of [n] has size at least $(1 – 1/s)2^n$. In this talk\,  I will present two short proofs. This is joint work with M. Bucic\, S. Letzter and B. Sudakov.
URL:https://dimag.ibs.re.kr/event/2021-01-26/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210119T163000
DTEND;TZID=Asia/Seoul:20210119T173000
DTSTAMP:20260507T032544
CREATED:20210114T070412Z
LAST-MODIFIED:20240705T191136Z
UID:3498-1611073800-1611077400@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Perfect matchings and derangements on graphs
DESCRIPTION:We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph\, and in terms of derangements and permutations on graphs. We give several related results and open questions. This is joint work with Matija Bucic\, Pat Devlin\, Mo Hendon\, and Dru Horne.
URL:https://dimag.ibs.re.kr/event/2021-01-19/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210112T163000
DTEND;TZID=Asia/Seoul:20210112T173000
DTSTAMP:20260507T032544
CREATED:20201231T074146Z
LAST-MODIFIED:20240705T191150Z
UID:3431-1610469000-1610472600@dimag.ibs.re.kr
SUMMARY:Andreas Holmsen\, Discrete geometry in convexity spaces
DESCRIPTION:The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years\, we have seen some progress on several open problems in the area\, and in this talk\, I will focus on the recent results relating to Tverberg’s theorem and the Alon-Kleitman (p\,q) theorem.
URL:https://dimag.ibs.re.kr/event/2021-01-12/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210105T163000
DTEND;TZID=Asia/Seoul:20210105T173000
DTSTAMP:20260507T032544
CREATED:20201126T024545Z
LAST-MODIFIED:20240707T082022Z
UID:3313-1609864200-1609867800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Directed tangles and applications
DESCRIPTION:The canonical tree-decomposition theorem\, proved by Robertson and Seymour in their seminal graph minors series\, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper\, we prove the analogous result for digraphs\, the directed tangle tree-decomposition theorem. More precisely\, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore\, for any integer $k$\, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$\, for any integer $k$. \nBy relaxing the bound slightly\, we can make the previous result algorithmic: for fixed $k$\, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$. \nWe provide two direct applications of this tangle tree-decomposition theorem. First\, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property\, that is\, there is a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that for every digraph $G$ and every integer $k$\, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles\, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles\, shown by Reed [Mangoes and blueberries. Combinatorica 1999]. \nSecond\, for every fixed $k$ we show that there is a polynomial-time algorithm which\, on input $G$\, and source and sink vertices $(s_1\, t_1)\, \dots\, (s_k\, t_k)$\, either finds a family of paths $P_1\, \dots\, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths\, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”)\, and given known hardness results\, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths. \nThis is joint work with Archontia C. Giannopoulou\, Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and Qiqin Xie.
URL:https://dimag.ibs.re.kr/event/2021-01-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201222T163000
DTEND;TZID=Asia/Seoul:20201222T173000
DTSTAMP:20260507T032544
CREATED:20201208T060000Z
LAST-MODIFIED:20240705T192115Z
UID:3349-1608654600-1608658200@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, On a conjecture by Kalai and Meshulam - the Betti number of the independence complex of ternary graphs
DESCRIPTION:Given a graph G=(V\,E)\, the independence complex of G is the abstract simplicial complex I(G) on V whose faces are the independent sets of G. A graph is ternary if it does not contain an induced cycle of length divisible by three. Kalai and Meshulam conjectured that if G is ternary then the sum of the Betti numbers of I(G) is either 0 or 1. In this talk\, I will introduce a result by Zhang and Wu\, which proves the Kalai-Meshulam conjecture.
URL:https://dimag.ibs.re.kr/event/2020-12-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201208T163000
DTEND;TZID=Asia/Seoul:20201208T173000
DTSTAMP:20260507T032544
CREATED:20201120T042705Z
LAST-MODIFIED:20240705T193010Z
UID:3287-1607445000-1607448600@dimag.ibs.re.kr
SUMMARY:Hong Liu (刘鸿)\, A solution to Erdős and Hajnal's odd cycle problem
DESCRIPTION:I will go over the history on the study of the set of cycle lengths of graphs with large average degree or chromatic number\, and discuss recent work with Richard Montgomery on this topic. In particular\, we will see the divergence of harmonic sum of odd cycle lengths in graphs with large chromatic number and the appearance of cycle lengths in very sparse sequences (such as powers of 2). The methods developed in this work allows also us to embed equally divided clique subdivisions\, which was conjectured by Thomassen.
URL:https://dimag.ibs.re.kr/event/2020-12-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201202T170000
DTEND;TZID=Asia/Seoul:20201202T180000
DTSTAMP:20260507T032544
CREATED:20201126T022405Z
LAST-MODIFIED:20240705T192124Z
UID:3309-1606928400-1606932000@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On common graphs
DESCRIPTION:A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is minimised by the random colouring. Burr and Rosta\, extending a famous conjecture by Erdős\, conjectured that every graph is common. The conjectures by Erdős and by Burr and Rosta were disproved by Thomason and by Sidorenko\, respectively\, in the late 1980s. \nDespite its importance\, the full classification of common graphs is still a wide open problem and has not seen much progress since the early 1990s. In this lecture\, I will present some old and new techniques to prove whether a graph is common or not.
URL:https://dimag.ibs.re.kr/event/2020-12-02/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201201T163000
DTEND;TZID=Asia/Seoul:20201201T173000
DTSTAMP:20260507T032544
CREATED:20201115T235924Z
LAST-MODIFIED:20240705T193016Z
UID:3273-1606840200-1606843800@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Rainbow matchings in edge-colored simple graphs
DESCRIPTION:There has been much research on finding a large rainbow matching in a properly edge-colored graph\, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barát\, Gyárfás\, and Sárközy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed\, but not loops) with $2q$ colors where each color appears at least $q$ times\, there is always a rainbow matching of size $q$. We prove that $2q + o(q)$ colors are enough if the graph is simple\, confirming the conjecture asymptotically for simple graphs. We also make progress in the lower bound on the required number of colors for simple graphs\, which disproves a conjecture of Aharoni and Berger. We use a randomized algorithm to obtain a large rainbow matching\, and the analysis of the algorithm is based on differential equations method. We will also briefly comment on the limitations of using our probabilistic approach for the problem. This talk will be based on a joint work with Po-Shen Loh.
URL:https://dimag.ibs.re.kr/event/2020-12-01/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201130T170000
DTEND;TZID=Asia/Seoul:20201130T180000
DTSTAMP:20260507T032544
CREATED:20201126T022202Z
LAST-MODIFIED:20240707T082346Z
UID:3307-1606755600-1606759200@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On Ramsey multiplicity
DESCRIPTION:Ramsey’s theorem states that\, for a fixed graph $H$\, every 2-edge-colouring of $K_n$ contains a monochromatic copy of $H$ whenever $n$ is large enough. Perhaps one of the most natural questions after Ramsey’s theorem is then how many copies of monochromatic $H$ can be guaranteed to exist. To formalise this question\, let the Ramsey multiplicity $M(H;n)$ be the minimum number of labelled copies of monochromatic $H$ over all 2-edge-colouring of $K_n$. We define the Ramsey multiplicity constant $C(H)$ is defined by $C(H):=\lim_{n\rightarrow\infty}\frac{M(H\,n)}{n(n-1)\cdots(n-v+1)}$. I will discuss various bounds for C(H) that are known so far.
URL:https://dimag.ibs.re.kr/event/2020-11-30/
LOCATION:Zoom ID:8628398170 (123450)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201124T163000
DTEND;TZID=Asia/Seoul:20201124T173000
DTSTAMP:20260507T032544
CREATED:20201111T070608Z
LAST-MODIFIED:20240705T193020Z
UID:3264-1606235400-1606239000@dimag.ibs.re.kr
SUMMARY:Duksang Lee (이덕상)\, Characterizing matroids whose bases form graphic delta-matroids
DESCRIPTION:We introduce delta-graphic matroids\, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most 48 elements. This is joint work with Sang-il Oum.
URL:https://dimag.ibs.re.kr/event/2020-11-24/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201110T163000
DTEND;TZID=Asia/Seoul:20201110T173000
DTSTAMP:20260507T032544
CREATED:20201028T010325Z
LAST-MODIFIED:20240705T193037Z
UID:3212-1605025800-1605029400@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, Extremal forbidden poset problems in Boolean and linear lattices
DESCRIPTION:Extending the classical theorem of Sperner on the maximum size of an antichain in the Boolean lattice\, Katona and Tarján introduced a general extremal function $La(n\,P)$\, defined to be the maximum size of a family of subsets of $[n]$ which does not contain a given poset $P$ among its containment relations.  In this talk\, I will discuss what is known about the behavior of $La(n\,P)$ and its natural extension to the lattice of subspaces of a vector space over a finite field.  In particular\, I will highlight some recent joint work with Jimeng Xiao.  Many open problems will also be discussed.
URL:https://dimag.ibs.re.kr/event/2020-11-10/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201103T163000
DTEND;TZID=Asia/Seoul:20201103T173000
DTSTAMP:20260507T032544
CREATED:20201022T132652Z
LAST-MODIFIED:20240705T193042Z
UID:3188-1604421000-1604424600@dimag.ibs.re.kr
SUMMARY:Jaeseong Oh (오재성)\, A 2-isomorphism theorem for delta-matroids
DESCRIPTION:Whitney’s 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. In this talk\, we present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids. This is based on the joint work with Iain Moffatt.
URL:https://dimag.ibs.re.kr/event/2020-11-03/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201027T163000
DTEND;TZID=Asia/Seoul:20201027T173000
DTSTAMP:20260507T032544
CREATED:20201009T013533Z
LAST-MODIFIED:20240707T082504Z
UID:3107-1603816200-1603819800@dimag.ibs.re.kr
SUMMARY:Jeong Ok Choi (최정옥)\, Various game-theoretic models on graphs
DESCRIPTION:We introduce some of well-known game-theoretic graph models and related problems. \nA contagion game model explains how an innovation diffuses over a given network structure and focuses on finding conditions on which structure an innovation becomes epidemic. Regular infinite graphs are interesting examples to explore. We show that regular infinite trees make an innovation least advantageous to be epidemic considering the whole class of infinite regular graphs. \nA network creation game model\, on the other hand\, tries to explain the dynamics on forming a network structure when each vertex plays independently and selfishly. An important question is how costly a formation can be made without any central coordination\, and the concept of Price of Anarchy (PoA) is introduced. In the model originally suggested by Fabrikant et al.\, PoA measures how bad the forming cost can be at Nash equilibria compared to absolute minimum\, and they conjectured that this inefficiency can happen only when some tree structures are formed (Tree Conjecture). We will introduce recent progress on this tree conjecture\, remaining open problems\, and possible variations. \nThis talk includes part of joint work with Unjong Yu.
URL:https://dimag.ibs.re.kr/event/2020-10-27/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201021T163000
DTEND;TZID=Asia/Seoul:20201021T173000
DTSTAMP:20260507T032544
CREATED:20200930T112510Z
LAST-MODIFIED:20240707T082519Z
UID:3085-1603297800-1603301400@dimag.ibs.re.kr
SUMMARY:Joonkyung Lee (이준경)\, On graph norms for complex-valued functions
DESCRIPTION:For any given graph $H$\, one may define a natural corresponding functional $\|.\|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions\, once $H$ is paired with a $2$-edge-colouring $\alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $\|.\|_H$ (resp. there is $\alpha$ such that $\|.\|_{H\,\alpha}$) is a norm on the vector space of real-valued (resp. complex-valued) functions. This generalises Gowers norms\, a widely used tool in extremal combinatorics to quantify quasirandomness. \nWe unify these two seemingly different notions of graph norms in real- and complex-valued settings\, by proving that $H$ is complex-norming if and only if it is real-norming. Our proof does not explicitly construct a suitable $2$-edge-colouring $\alpha$ but obtain its existence and uniqueness\, which may be of independent interest. \nAs an application\, we give various example graphs that are not norming. In particular\, we show that hypercubes are not norming\, which answers the only question appeared in Hatami’s pioneering work in the area that remained untouched. This is joint work with Alexander Sidorenko.
URL:https://dimag.ibs.re.kr/event/2020-10-21/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200929T163000
DTEND;TZID=Asia/Seoul:20200929T173000
DTSTAMP:20260507T032544
CREATED:20200921T045326Z
LAST-MODIFIED:20240705T194112Z
UID:3014-1601397000-1601400600@dimag.ibs.re.kr
SUMMARY:Minki Kim (김민기)\, Complexes of graphs with bounded independence number
DESCRIPTION:Let $G$ be a graph on $V$ and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose faces are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of $I_n(G)$ for various classes of graphs\, focusing on the class of graphs with bounded maximum degree. This is joint work with Alan Lew.
URL:https://dimag.ibs.re.kr/event/2020-09-29/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200922T163000
DTEND;TZID=Asia/Seoul:20200922T173000
DTSTAMP:20260507T032544
CREATED:20200914T065243Z
LAST-MODIFIED:20240707T082727Z
UID:2960-1600792200-1600795800@dimag.ibs.re.kr
SUMMARY:Jinha Kim (김진하)\, Collapsibility of Non-Cover Complexes of Graphs
DESCRIPTION:Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subset V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$\, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex on $V$ whose faces are non-covers of $G$. Then the non-cover complex of $G$ is the combinatorial Alexander dual of the independence complex of $G$. In this talk\, I will show the $(|V(G)|-i\gamma(G)-1)$-collapsibility of the non-cover complex of a graph $G$ where $i\gamma(G)$ denotes the independence domination number of $G$ using the minimal exclusion sequence method. This is joint work with Ilkyoo Choi and Boram Park.
URL:https://dimag.ibs.re.kr/event/2020-09-22/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200915T163000
DTEND;TZID=Asia/Seoul:20200915T173000
DTSTAMP:20260507T032544
CREATED:20200901T083403Z
LAST-MODIFIED:20240705T194142Z
UID:2919-1600187400-1600191000@dimag.ibs.re.kr
SUMMARY:Debsoumya Chakraborti\, Maximum number of cliques in a graph with bounded maximum degree
DESCRIPTION:Generalized extremal problems have been one of the central topics of study in extremal combinatorics throughout the last few decades. One such simple-looking problem\, maximizing the number of cliques of a fixed order in a graph with a fixed number of vertices and given maximum degree\, was recently resolved by Chase. Settling a conjecture of Kirsch and Radcliffe\, we resolve the edge variant of this problem\, where the number of edges is fixed instead of the number of vertices. This talk will be based on joint work with Da Qi Chen.
URL:https://dimag.ibs.re.kr/event/2020-09-15/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200908T163000
DTEND;TZID=Asia/Seoul:20200908T173000
DTSTAMP:20260507T032544
CREATED:20200820T123810Z
LAST-MODIFIED:20240705T194152Z
UID:2831-1599582600-1599586200@dimag.ibs.re.kr
SUMMARY:Rutger Campbell\, Disasters in abstracting combinatorial properties of linear dependence
DESCRIPTION:Let E be a finite set and I be a collection of subsets of E. When is there a set of real vectors indexed by E such that I correspond to its linearly independent subsets? In 1935\, Whitney introduced matroids using some necessary conditions for this. However\, complete characterizations with various techniques are intractable. This remains the case even if it is already known that there is a set of complex vectors indexed by E whose collection of linearly independent subsets corresponds to I.
URL:https://dimag.ibs.re.kr/event/2020-09-08/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200901T103000
DTEND;TZID=Asia/Seoul:20200901T113000
DTSTAMP:20260507T032544
CREATED:20200825T130632Z
LAST-MODIFIED:20240707T082809Z
UID:2855-1598956200-1598959800@dimag.ibs.re.kr
SUMMARY:Junguk Lee (이정욱)\, A quick introduction to stability and NIP: Part III. NIP
DESCRIPTION:I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally\, we aim to give several characterizations of stability and NIP of a given formula in terms of counting types and definability types.
URL:https://dimag.ibs.re.kr/event/2020-09-01/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200831T161500
DTEND;TZID=Asia/Seoul:20200831T171500
DTSTAMP:20260507T032544
CREATED:20200825T130503Z
LAST-MODIFIED:20240707T082818Z
UID:2851-1598890500-1598894100@dimag.ibs.re.kr
SUMMARY:Junguk Lee (이정욱)\, A quick introduction to stability and NIP: Part II. Stability
DESCRIPTION:I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally\, we aim to give several characterizations of stability and NIP of a given formula in terms of counting types and definability types.
URL:https://dimag.ibs.re.kr/event/2020-08-31-part2/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200831T150000
DTEND;TZID=Asia/Seoul:20200831T160000
DTSTAMP:20260507T032544
CREATED:20200825T130214Z
LAST-MODIFIED:20240707T082829Z
UID:2848-1598886000-1598889600@dimag.ibs.re.kr
SUMMARY:Junguk Lee (이정욱)\, A quick introduction to stability and NIP: Part I. Basic first order logic
DESCRIPTION:I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. We review basic properties of stability and NIP. Finally\, we aim to give several characterizations of stability and NIP of a given formula in terms of counting types and definability types.
URL:https://dimag.ibs.re.kr/event/2020-08-31/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200825T163000
DTEND;TZID=Asia/Seoul:20200825T173000
DTSTAMP:20260507T032544
CREATED:20200816T234618Z
LAST-MODIFIED:20240707T082841Z
UID:2794-1598373000-1598376600@dimag.ibs.re.kr
SUMMARY:Ben Lund\, Point-plane incidence bounds
DESCRIPTION:In the early 1980s\, Beck proved that\, if P is a set of n points in the real plane\, and no more than g points of P lie on any single line\, then there are $\Omega(n(n-g))$ lines that each contain at least 2 points of P. In 2016\, I found a generalization of this theorem\, giving a similar lower bound on the number of planes spanned by a set of points in real space. I will discuss this result\, along with a number of applications and related open problems.
URL:https://dimag.ibs.re.kr/event/2020-08-25/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200818T163000
DTEND;TZID=Asia/Seoul:20200818T173000
DTSTAMP:20260507T032544
CREATED:20200804T124550Z
LAST-MODIFIED:20240707T082915Z
UID:2750-1597768200-1597771800@dimag.ibs.re.kr
SUMMARY:Tuan Tran\, Anti-concentration phenomena
DESCRIPTION:Let $X$ be a real random variable; a typical anti-concentration inequality asserts that (under certain assumptions) if an interval $I$ has small length\, then $\mathbb{P}(X\in I)$ is small\, regardless the location of $I$. Inequalities of this type have found powerful applications in many branches of mathematics. In this talk we will discuss several recent applications of anti-concentration inequalities in extremal combinatorics\, as well as random matrix theory. The talk is partially based on joint work with Matthew Kwan and Benny Sudakov.
URL:https://dimag.ibs.re.kr/event/2020-08-18/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR