BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv5.2.1.1//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
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20210614
DTEND;VALUE=DATE:20210619
DTSTAMP:20201201T084013
CREATED:20190607T162650Z
LAST-MODIFIED:20200914T072532Z
UID:947-1623628800-1624060799@dimag.ibs.re.kr
SUMMARY:Seymour is Seventy
DESCRIPTION:A conference honouring the seventieth birthday of Paul Seymour \n\nTo be held in ENS de Lyon\, France\, June 15 – 19\, 2020. \nDue to the COVID-19\, we have postponed the conference to June 14-18\, 2021 tentatively. The final decision will be made at the beginning of 2021. \nConference Website: https://dimag.ibs.re.kr/seymour70/ \nSponsors: \n\nIBS Discrete Mathematics Group.\nLIP\, ENS de Lyon\, France.\nDepartment of Mathematics\, Princeton University.
URL:https://dimag.ibs.re.kr/event/seymour-is-seventy/
LOCATION:ENS de Lyon\, Lyon\, France
CATEGORIES:Workshops and Conferences
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210113T100000
DTEND;TZID=Asia/Seoul:20210113T110000
DTSTAMP:20201201T084013
CREATED:20201126T045239Z
LAST-MODIFIED:20201126T045316Z
UID:3318-1610532000-1610535600@dimag.ibs.re.kr
SUMMARY:Rose McCarty\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/2021-01-13/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210106T163000
DTEND;TZID=Asia/Seoul:20210106T173000
DTSTAMP:20201201T084013
CREATED:20201106T054235Z
LAST-MODIFIED:20201106T054235Z
UID:3241-1609950600-1609954200@dimag.ibs.re.kr
SUMMARY:Ron Aharoni\, TBA
DESCRIPTION:
URL:https://dimag.ibs.re.kr/event/ron-aharoni-tba/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210105T163000
DTEND;TZID=Asia/Seoul:20210105T173000
DTSTAMP:20201201T084013
CREATED:20201126T024545Z
LAST-MODIFIED:20201126T024545Z
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:20201217T100000
DTEND;TZID=Asia/Seoul:20201217T110000
DTSTAMP:20201201T084013
CREATED:20201028T010135Z
LAST-MODIFIED:20201111T053800Z
UID:3210-1608199200-1608202800@dimag.ibs.re.kr
SUMMARY:Jaiung Jun (전재웅)\, On the Hopf algebra of multi-complexes
DESCRIPTION:In combinatorics\, Hopf algebras appear naturally when studying various classes of combinatorial objects\, such as graphs\, matroids\, posets or symmetric functions. Given such a class of combinatorial objects\, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of a Hopf algebra to return to combinatorial identities of combinatorial objects of interest. \nIn this talk\, I introduce a general class of combinatorial objects\, which we call multi-complexes\, which simultaneously generalizes graphs\, hypergraphs and simplicial and delta complexes. I also introduce a combinatorial Hopf algebra obtained from multi-complexes. Then\, I describe the structure of the Hopf algebra of multi-complexes by finding an explicit basis of the space of primitives\, which is of combinatorial relevance. If time permits\, I will illustrate some potential applications. \nThis is joint work with Miodrag Iovanov.
URL:https://dimag.ibs.re.kr/event/2020-12-17/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201209T163000
DTEND;TZID=Asia/Seoul:20201209T173000
DTSTAMP:20201201T084013
CREATED:20201013T135938Z
LAST-MODIFIED:20201109T082320Z
UID:3125-1607531400-1607535000@dimag.ibs.re.kr
SUMMARY:Karl Heuer\, Even Circuits in Oriented Matroids
DESCRIPTION:In this talk I will state a generalisation of the even directed cycle problem\, which asks whether a given digraph contains a directed cycle of even length\, to orientations of regular matroids. Motivated by this problem\, I will define non-even oriented matroids generalising non-even digraphs\, which played a central role in resolving the computational complexity of the even dicycle problem. Then I will present and discuss our two results regarding these notions: \nFirst we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. \nSecond and with the main focus for this talk\, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors\, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. The second result makes use of a new concept of minors for oriented matroids\, which generalises butterfly minors for digraphs to oriented matroids. \nThe part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory. \nThis talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht. \n[1] K. Heuer\, R. Steiner and S. Wiederrecht\, Even Circuits in Oriented Matroids\, arxiv:2010.08988
URL:https://dimag.ibs.re.kr/event/2020-12-09/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201208T163000
DTEND;TZID=Asia/Seoul:20201208T173000
DTSTAMP:20201201T084013
CREATED:20201120T042705Z
LAST-MODIFIED:20201120T042705Z
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:20201203T163000
DTEND;TZID=Asia/Seoul:20201203T173000
DTSTAMP:20201201T084013
CREATED:20201013T135812Z
LAST-MODIFIED:20201109T082239Z
UID:3122-1607013000-1607016600@dimag.ibs.re.kr
SUMMARY:Deniz Sarikaya\, What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs
DESCRIPTION:The study of Hamiltonian graphs\, i.e. finite graphs having a cycle that contains all vertices of the graph\, is a central theme of finite graph theory. For infinite graphs such a definition cannot work\, since cycles are finite. We shall debate possible concepts of Hamiltonicity for infinite graphs and eventually follow the topological approach by Diestel and Kühn [2\,3]\, which allows to generalize several results about being a Hamiltonian graph to locally finite graphs\, i.e. graphs where each vertex has finite degree. An infinite cycle of a locally finite connected graph G is defined as a homeomorphic image of the unit circle $S^1$ in the Freudenthal compactification |G| of G. Now we call G Hamiltonian if there is an infinite cycle in |G| containing all vertices of G. For an introduction see [1]. \nWe examine how to force Hamiltonicity via forbidden induced subgraphs and present recent extensions of results for Hamiltonicity in finite claw-free graphs to locally finite ones. The first two results are about claw- and net-free graphs\, claw- and bull-free graphs\, the last also about further graph classes being structurally richer\, where we focus on paws as relevant subgraphs\, but relax the condition of forbidding them as induced subgraphs. \nThe goal of the talk is twofold: (1) We introduce the history of the topological viewpoint and argue that there are some merits to it (2) sketch the proofs for the results mentioned above in some details. \nThis is based on joint work [4\,5] with Karl Heuer. \nBibliography\n[1] R. Diestel (2017) Infinite Graphs. In: Graph Theory. Graduate Texts in Mathematics\, vol 173. Springer\, Berlin\, Heidelberg. https://doi.org/10.1007/978-3-662-53622-3_8 \n[2] R. Diestel and D. Kühn\, On infinite cycles I\, Combinatorica 24 (2004)\, pp. 69-89. \n[3] R. Diestel and D. Kühn\, On infinite cycles II\, Combinatorica 24 (2004)\, pp. 91-116. \n[4] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls\, arXiv:2006.09160 \n[5] K. Heuer and D. Sarikaya\, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws\, arXiv:2006.09166
URL:https://dimag.ibs.re.kr/event/2020-12-03/
LOCATION:Zoom ID: 934 3222 0374 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201202T170000
DTEND;TZID=Asia/Seoul:20201202T180000
DTSTAMP:20201201T084013
CREATED:20201126T022405Z
LAST-MODIFIED:20201126T024854Z
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:20201201T084013
CREATED:20201115T235924Z
LAST-MODIFIED:20201115T235924Z
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
END:VCALENDAR