ﻻ يوجد ملخص باللغة العربية
Shrub-depth and rank-depth are dense analogues of the tree-depth of a graph. It is well known that a graph has large tree-depth if and only if it has a long path as a subgraph. We prove an analogous statement for shrub-depth and rank-depth, which was conjectured by Hlinv{e}ny, Kwon, Obdrv{z}alek, and Ordyniak [Tree-depth and vertex-minors, European J.~Combin. 2016]. Namely, we prove that a graph has large rank-depth if and only if it has a vertex-minor isomorphic to a long path. This implies that for every integer $t$, the class of graphs with no vertex-minor isomorphic to the path on $t$ vertices has bounded shrub-depth.
DeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a natural analogue of tree-depth of graphs. They conjectured that a matroid of sufficiently large branch-depth contains the uniform matroid $U_{n,2n}$ or the cycle matroid of
We characterize classes of graphs closed under taking vertex-minors and having no $P_n$ and no disjoint union of $n$ copies of the $1$-subdivision of $K_{1,n}$ for some $n$. Our characterization is described in terms of a tree of radius $2$ whose lea
We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of local classical optimization algorithms and show that a single step version of these algorithms can achieve the same performanc
We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3log d. The previous best rank bound known was 2^{O(k^2)}(log d)^{k-2} by Dvir and Shpilka (STOC 2005). This almost resolves the rank question f
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width.