Events Search and Views Navigation

Event Views Navigation

Today

Combinatorial and Discrete Optimization (2019 KSIAM Annual Meeting)

Venezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔) 

Special Session @ 2019 KSIAM Annual MeetingA special session on "Combinatorial and Discrete Optimization" at the 2019 KSIAM Annual Meeting is organized by Dabeen Lee. URL: https://www.ksiam.org/conference/84840fb6-87b0-4566-acc1-4802bde58fbd/welcomeDateNov 8, 2019 – Nov 9, 2019 Address: 61-13 Odongdo-ro, Sujeong-dong, Yeosu-si, Jeollanam-do (전남 여수시 오동도로 61-13)VenueVenezia Hotel & Resort Yeosu, Yeosu, Korea (여수 베네치아 호텔)  Address: 61-13 Odongdo-ro, Sujeong-dong, …

Continue Reading

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

Room B232 IBS (기초과학연구원)

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is …

Continue Reading

Ruth Luo, Induced Turán problems for hypergraphs

Room B232 IBS (기초과학연구원)

Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$, $f(xy) \cap V(F) = \{x,y\}$. In this talk, we show asymptotics for the maximum number of …

Continue Reading

Frédéric Meunier, Topological bounds for graph representations over any field

Room B232 IBS (기초과학연구원)

Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for …

Continue Reading

Jakub Gajarský, First-order interpretations of bounded expansion classes

Room B232 IBS (기초과학연구원)

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of …

Continue Reading

Hong Liu, A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs

Room 1401, Bldg. E6-1, KAIST

Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of …

Continue Reading

Attila Joó, Base partition for finitary-cofinitary matroid families

Room B232 IBS (기초과학연구원)

Let ${\mathcal{M} = (M_i \colon i\in K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$. We prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i \colon i\in K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint …

Continue Reading

Jaiung Jun (전재웅), The Hall algebra of the category of matroids

Room 1401, Bldg. E6-1, KAIST

To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting, Dyckerhoff and Kapranov introduced the notion of proto-exact categories, as a non-additive generalization of an exact category, which …

Continue Reading

Sanjeeb Dash, Boolean decision rules via column generation

Room B232 IBS (기초과학연구원)

In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) …

Continue Reading

Ben Lund, Furstenberg sets over finite fields

Room B232 IBS (기초과학연구원)

An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir's proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area. …

Continue Reading
DIMAG on YouTube

We use YouTube Live to broadcast seminar talks live if the speaker agrees.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.