BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let F be an antichain of finite subsets of N. How quickly can the quantities ∣F∩2[n]∣ grow as n→∞? We show that for any sequence (fn)n≥n0 of positive integers satisfying ∑n=n0∞fn/2n≤1/4, fn0=1 and fn≤fn+1≤2fn, there exists an infinite antichain F of finite subsets of N such that ∣F∩2[n]∣≥fn for all n≥n0. It follows that for any ε>0 there exists an antichain F⊆2N such that liminfn→∞∣F∩2[n]∣⋅(nlog1+εn2n)−1>0. This resolves a problem of Sudakov, Tomon and Wagner in a strong form, and is essentially tight.
Two boxes in Rd are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in Rd. We show that proper minor-closed classes have bounded comparable box dimensions and explore further properties of this notion.
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class G to be the minimum non-negative integer c such that, for some function f, for every graph G∈G there is a graph H with tw(H)≤c such that G is isomorphic to a subgraph of H⊠Kf(tw(G)). We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of Ks,t-minor-free graphs has underlying treewidth s (for t≥max{s,3}); and the class of Kt-minor-free graphs has underlying treewidth t−2. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no H subgraph has bounded underlying treewidth if and only if every component of H is a subdivided star, and that the class of graphs with no induced H subgraph has bounded underlying treewidth if and only if every component of H is a star.
The deck of a graph G is the multiset of cards {G−v:v∈V(G)}. Myrvold (1992) showed that the degree sequence of a graph on n≥7 vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree d can reconstructed from any deck missing O(n/d3) cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.