Kevin Hendrey, Product Structure of Graph Classes with Bounded Treewidth
Room B232 IBS (기초과학연구원)The strong product
10 events found.
Seminars and Colloquiums
Jinyoung Park (박진영), Thresholds 1/2
Room B332 IBS (기초과학연구원)Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. …
Jinyoung Park (박진영), Thresholds 2/2
Room B332 IBS (기초과학연구원)Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. …
Noam Lifshitz, Product free sets in the alternating group
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product free subset of
Seunghun Lee (이승훈), Inscribable order types
Room B332 IBS (기초과학연구원)We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable, and that the number of such order …
Lars Jaffke, Taming graphs with no large creatures and skinny ladders
Zoom ID: 869 4632 6610 (ibsdimag)We confirm a conjecture of Gartland and Lokshtanov : if for a hereditary graph class
Eun Jung Kim (김은정), Directed flow-augmentation
Room B332 IBS (기초과학연구원)We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers
Akash Kumar, Random walks and Forbidden Minors
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk, I will present how random walks helped make progress on algorithmic problems on planar graphs. In particular, I show how random walk based (i.e., spectral) approaches led to progress …
Noleen Köhler, Testing first-order definable properties on bounded degree graphs
Room B332 IBS (기초과학연구원)Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study …
Raul Lopes, Temporal Menger and related problems
Room B332 IBS (기초과학연구원)A temporal graph is a graph whose edges are available only at specific times. In this scenario, the only valid walks are the ones traversing adjacent edges respecting their availability, i.e. sequence of adjacent edges whose appearing times are non-decreasing. Given a graph G and vertices s and t of G, Menger’s Theorem states that …