Let be a family of graphs, and let and be nonnegative integers. The -Covering problem asks whether for a graph and an integer , there exists a set of at most vertices in such that has no induced subgraph isomorphic to a graph in , where …
Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete, which is likely to exclude FPT algorithms. However, we prove that computing a tree-partition of approximate …
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya asked for which (0, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the …
For fixed integers , and , let denote the maximum number of edges in an -vertex -uniform hypergraph in which the union of arbitrary distinct edges contains at least vertices. In 1973, Brown, Erdős and Sós initiated the study of the function and they proved that . …
A linear -graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices. A linear -graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge. A simple greedy algorithm shows that every -vertex Steiner triple system contains all …
Official website (with the abstract) https://www.ibs.re.kr/ecopro/online-workshop-developments-in-combinatorics/ Invited Speakers Nov. 28 Monday Jie Han, Beijing Institute of Technology 15:30 Seoul, 14:30 Beijing, 06:30 UK, 07:30 EU Joonkyung Lee (이준경), Hanyang University 16:10 Seoul, 15:10 Beijing, 07:10 UK, 08:10 EU Lior Gishboliner, ETH Zürich 16:50 Seoul, 15:50 Beijing, 07:50 UK, 08:50 EU Alex Scott, University of Oxford …
Finding the smallest integer such that in every configuration of points in in general position, there exist points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that holds, which was nearly settled by …