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:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20190211
DTEND;VALUE=DATE:20190213
DTSTAMP:20260425T012320
CREATED:20190118T003152Z
LAST-MODIFIED:20240707T090601Z
UID:396-1549843200-1550015999@dimag.ibs.re.kr
SUMMARY:2019-1 IBS Workshop on Graph Theory
DESCRIPTION:Invited Speakers\n\nJeong Han Kim (김정한)\, KIAS\, Seoul\nMartin Balko\, Charles University\, Prague\nDániel Gerbner\, Alfréd Rényi Institute of Mathematics\, Budapest\nCory T. Palmer\, University of Montana\, Missoula\nBoram Park (박보람)\, Ajou University\nDong Yeap Kang (강동엽)\, KAIST\n\nSchedule\nFeb. 11\, 2019\, Monday\n1:30pm-2:20pm Jeong Han Kim: Entropy and sorting\n2:20pm-3:10pm Cory T. Palmer: Generalized Turán problems – Berge hypergraphs\nCoffee Break\n4:00pm-4:50pm Martin Balko: Ramsey numbers of edge-ordered graphs\n4:50pm-5:40pm Dong Yeap Kang: On the rational Turán exponents conjecture\nBanquet \nFeb. 12\, 2019\, Tuesday\n9:30am-10:20am Boram Park: Sum-free set problem on integers\nCoffee Break\n11:00am-11:50am Dániel Gerbner: Generalized Turán problems – counting subgraphs\nLunch \nWe plan to provide meals to all participants and provide a room at a near-by hotel for invited speakers and selected participants. Please register in the following form below by January 28\, Monday; please register early if you want to receive the support for the accommodation. \nAbstracts\nJeong Han Kim (김정한)\, Entropy and Sorting \nWe reconsider the old problem of sorting under partial information\, and give polynomial time algorithms for the following tasks: (1) Given a partial order P\, find (adaptively) a sequence of comparisons (questions of the form\, “is x < y?”) which sorts ( i.e.\, finds an unknown linear extension of) P using O(log(e(P))) comparisons in worst case (where e(P) is the number of linear extensions of P). (2) Compute (on line) answers to any comparison algorithm for sorting a partial order P which force the algorithm to use Ω(log(e(P))) comparisons. (3) Given a partial order P of size n\, estimate e(P) to within a factor exponential in n. (We give upper and lower bounds which differ by the factor $n^n /n!$.) Our approach\, based on entropy of the comparability graph of P and convex minimization via the ellipsoid method\, is completely different from earlier attempts to deal with these questions. \nJoint work with J. Kahn. \nCory T. Palmer\, Generalized Turán problems – Berge hypergraphs\nLet $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f : E(F) \rightarrow E(H )$ such that $e \subseteq f(e)$ for every $e \in E(F)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted $\operatorname{ex}_r(n\,\textrm{Berge-}F)$. Observe that when $r=2$\, then a Berge-$F$ is simply the graph $F$ and thus again we! are investigating the Tur\’an function $\operatorname{ex}(n\,F)$. \nIn this talk we will survey results on the function $\operatorname{ex}_r(n\,\textrm{Berge-}F)$ for various graphs $F$. We will also describe several interesting open problems. \nMartin Balko\, Ramsey numbers of edge-ordered graphs\nAn edge-ordered graph is a graph with linearly ordered set of edges. We introduce and study Ramsey numbers of edge-ordered graphs\, called edge-ordered Ramsey numbers. We prove some basic properties of these numbers for general edge! -ordered graphs and we provide some stronger estimates for special classes of edge-ordered graphs. We also pose some new open problems and compare edge-ordered Ramsey numbers with the standard Ramsey numbers of graphs and with ordered Ramsey numbers\, which are Ramsey numbers for graphs with linearly ordered vertex sets. \nJoint work with Mate Vizer. \nDong Yeap Kang (강동엽)\, On the rational Turán exponents conjecture\nThe extremal number ${\rm ex}(n\,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1\,2]$ is realisable if there exists a graph $F$ with ${\rm ex}(n \, F) = \Theta(n^r)$. Several decades ago\, Erdős and Simonovits conjectured that every rational number in $[1\,2]$ is realisable. Despite decades of effort\, the only known realisable numbers are $1\,\frac{7}{5}\,2$\, and the numbers of the form $1+\frac{1}{m}$\, $2-\frac{1}{m}$\, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular\, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2. \nWe discuss some recent progress on the conjecture of Erdős and Simonovits. First\, we show that $2 – \frac{a}{b}$ is realisable for any integers $a\,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones\, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. \nSecondly\, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own\, we show that\, somewhat surprisingly\, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable. \nThis is joint work with Jaehoon Kim and Hong Liu. \nBoram Park (박보람)\, Sum-free set problem on integers\nFor an abelian  group $G$\, a set $A \subset G$ is sum-free if there are no $x\, y\, z \in A$ such that $x + y = z$. Sum-free sets was initiated by Schur (1916) by an attempt to prove the famous Fermat’s Last Theorem. Since then\, there have been intensive and fruitful research in the field of additive combinatorics. One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers\, which has attracted a significant attention in the literature over the years. \nIn this talk\, some recent results on sum-free sets of integers are discussed. Then we present a result on $k$-sum $\bf{n}$-free set\, where $\bf{n}$ is an $n$-dimensional integer vector. The work is based on joint work with Ilkyoo Choi and Ringi Kim. \nDániel Gerbner\, Generalized Turán problems – counting subgraphs\nGiven two graphs $H$ and $F$\, our goal is to determine the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices. The systematic research of these problems was initiated (after several sporadic results) by Alon and Shikhelman. I describe several results of mine in this area\, with different sets of co-authors. \nJoint work with Ervin Győri\, Abhishek Methuku\, Cory Palmer and Mate Vizer.
URL:https://dimag.ibs.re.kr/event/2019-1-graph-theory/
LOCATION:Room B234\, IBS (기초과학연구원)
CATEGORIES:Workshops and Conferences
END:VEVENT
END:VCALENDAR