A family of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from has a common element, and moreover, no set can be added to while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a …
The independence number of a tree decomposition of a graph is the smallest integer such that each bag of induces a subgraph with independence number at most . If a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can …
A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of …
Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya's Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk …
The poset Ramsey number is the smallest integer such that any blue-red coloring of the elements of the Boolean lattice has a blue induced copy of or a red induced copy of . Axenovich and Walzer showed that . Recently, Lu and Thompson improved the upper bound to . In …
Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing …
What is the largest number where every graph with average degree at least contains a subdivision of ? Mader asked this question in 1967 and was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of . However, this …
