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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201203T163000
DTEND;TZID=Asia/Seoul:20201203T173000
DTSTAMP:20260422T232000
CREATED:20201013T135812Z
LAST-MODIFIED:20240705T194003Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201209T163000
DTEND;TZID=Asia/Seoul:20201209T173000
DTSTAMP:20260422T232000
CREATED:20201013T135938Z
LAST-MODIFIED:20240705T193042Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201217T100000
DTEND;TZID=Asia/Seoul:20201217T110000
DTSTAMP:20260422T232000
CREATED:20201028T010135Z
LAST-MODIFIED:20240707T082135Z
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: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201230T100000
DTEND;TZID=Asia/Seoul:20201230T110000
DTSTAMP:20260422T232000
CREATED:20201220T231608Z
LAST-MODIFIED:20240707T082035Z
UID:3389-1609322400-1609326000@dimag.ibs.re.kr
SUMMARY:Paul Seymour\, The Erdős-Hajnal conjecture is true for excluding a five-cycle
DESCRIPTION:In an n-vertex graph\, there must be a clique or stable set of size at least $C\log n$\, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph\, the largest clique or stable set is bigger. \nErdős and Hajnal conjectured in 1977 that for every graph H\, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G|^c$ (“H-free” means not containing H as an induced subgraph\, and |G| means the number of vertices of G). This is still open\, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five. \nIt is true in that case. We will give a sketch of the proof\, which is via applying a lemma about bipartite graphs\, a variant of a theorem of I. Tomon. \nThis lemma has several other applications to the Erdős-Hajnal conjecture. For instance\, it implies that for every cycle C and forest T\, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G|^c$. (Until now this was open when C has length five and T is a 5-vertex path.) \nJoint work with Maria Chudnovsky\, Alex Scott and Sophie Spirkl.
URL:https://dimag.ibs.re.kr/event/2020-12-30/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR