When a forest, narrowed to an atom of subset algebra, turns out to be a tree

V. A. Buslov · 2025

Read When a forest, narrowed to an atom of subset algebra, turns out to be a tree by V. A. Buslov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19068.txt.

Introduction

Vasily Buslov proves a structural fact about cheapest spanning forests in a directed graph. Take a minimum-weight forest with k trees and one with k-1 trees, and narrow both to a single atom of the subset algebra built from the vertex sets of such forests. The claim is that the narrowed k-component forest is still a tree, one connected piece rather than a scatter. Buslov shows the property fails in general for forests with fewer components, which marks the k and k-1 pairing as the special case.

Catalog record

CREATORV. A. Buslov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-19068

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

When a forest, narrowed to an atom of subset algebra, turns out to be a tree V. A. Buslov Abstract It is proved that the restriction of a k k and ( k − 1 ) (k-1) -component directed spanning forest of minimal weight to an atom of the subset algebra generated by the sets of vertices of trees of k k -component minimal spanning forests is a tree. For spanning minimal forests consisting of fewer components, this property, generally speaking, does not exist. UDC 519.17 When a forest, narrowed to an atom of subset algebra, turns out to be a tree V. A. Buslov This article is based on the work of [ 1 ] and is a continuation of the work of [ 2 ] . Definitions and designations correspond to those adopted in them. We present all the results used in the form of a list of properties, highlighting separately only the fundamental lemma on replacing arcs [ 1 , Lemma 1] . 1 Notations and definitions We denote the set of vertices of a digraph G by {\cal V}G , and the set of its arcs by {\cal A}G . The starting object is a weighted digraph V , the set of vertices of which is denoted separately for convenience — {\cal N} , |{\cal N}|=N ; arcs (i,j)\in{\cal A}V are assigned real weights v_{ij} . We study the spanning subgraphs (subgraphs with a set of vertices {\cal N} ) of the digraph V , which are entering forests. An entering forest (hereinafter simply, forest) is a digraph in which no more than one arc outgoes from each vertex and there are no contours in it. The connected components of a forest are trees. The only vertex of the tree from which the arc does not go is the root. We denote the set of roots of the forest F by {\cal K}_{F} . By T^{F}_{i} we mean the inclusion-maximal subtree of the forest F rooted at vertex i . If i\in{\cal K}_{F} , then T^{F}_{i} is a connected component of F . Since only digraphs appear in the work (except for a specially stated point), we use the term graph for them, where this does not lead to misunderstandings. For a subgraph G of V and a set {\cal S}\subseteq{\cal N} we define weights \Upsilon^{G}_{\cal S}=\sum_{\begin{smallmatrix}i\in{\cal S}\\ (i,j)\in{\cal A}G\end{smallmatrix}}v_{ij}\ ,\ \ \Upsilon^{G}=\Upsilon^{G}_{\cal N}=\sum_{(i,j)\in{\cal A}G}v_{ij}\ . {\cal F}^{k} — a set of spanning forests consisting of k trees. The minimum weight of k -component forests is denoted by \phi^{k}=\min_{F\in{\cal F}^{k}}\Upsilon^{F}. If {\cal F}^{k}=\emptyset , we put \phi^{k}=\infty , in particular, \phi^{0}=\infty . F\in\tilde{\cal F}^{k} means that F\in{\cal F}^{k} and \Upsilon^{F}=\phi^{k} . We will agree to call such forests minimal. G|_{\cal S} is a subgraph of G induced by the set {\cal S} , that is, {\cal V}G|_{\cal S}={\cal S} and {\cal A}G|_{\cal S} consists of all arcs of G , both ends of which belong to the set {\cal S} . G|_{\cal S} is also called the restriction of G to the set {\cal S} . {\cal F}^{k}|_{\cal S} is a set of subgraphs of k -component forests induced by the set {\cal S} . \tilde{\cal F}^{k}|_{\cal S} is a set of subgraphs of k -component forests of minimal weight induced by the set {\cal S} . G^{F}_{\uparrow{\cal S}} is a graph obtained from G by replacing arcs outgoing from the vertices of {\cal S} with arcs outgoing from the same vertices in F . If there is an arc whose outcome belongs to the set {\cal S} , but its entry does not, then we say that the arc outgoes from the set {\cal S} . Similarly, if there is an arc whose entry belongs to {\cal S} and whose outcome does not belong, then we say that the arc enters {\cal S} . The outgoing neighborhood {\cal N}^{out}_{\cal S}(G) of the set {\cal S} is the set of arc entries outgoing in G from the set {\cal S} ; The incoming neighborhood {\cal N}^{in}_{\cal S}(G) is defined similarly. For any subset {\cal D}\subset{\cal N} , its complement \overline{\cal D}={\cal N}\setminus{\cal D} . A family \mathfrak{B} of nonempty sets {\cal B}_{i} is called a partition of {\cal N} if {\cal B}_{i}\cap{\cal B}_{j}=\emptyset for i\neq j , and {\cal N}=\underset{i}{\cup}{\cal S}_{i} . Let \mathfrak{B} be some family of subsets of {\cal N} . The family \mathfrak{A} , consisting of all possible complements and intersections of these subsets, is called an algebra generated by the family \mathfrak{B} . A non-empty set {\cal A} of algebra \mathfrak{A} is called an atom if for any element {\cal B} of algebra \mathfrak{A} either {\cal A}\cap{\cal B}=\emptyset , or {\cal A}\cap{\cal B}={\cal A} . 2 Some properties of the arc replacement operation The main tool of all the constructions carried out is the operation of replacing arcs outgoing from the vertices of a certain set {\cal D} between two forests F and G . Independently of each other, each of two graphs F_{\uparrow\cal D}^{G} and G_{\uparrow\cal D}^{F} obtained by this procedure may turn out to be a forest or not. The fundamental statement is the following Lemma 1 . [ 1 , Lemma 1] Let F and G be forests, {\cal V}F={\cal V}G={\cal N} , {\cal D}\subset{\cal N} . Then graph F_{\uparrow\cal D}^{G} is a forest if in F the set {\cal N}^{in}_{\cal D}(F) is unreachable from {\cal N}^{out}_{\cal D}(G) . Remark 1 . Note that if {\cal N}^{in}_{\cal D}(F)\cap{\cal N}^{out}_{\cal D}(G)\neq\emptyset , then these sets are reachable from each other in any forest, since by definition each vertex is considered reachable from itself. In this case, graph F_{\uparrow\cal D}^{G} may or may not be a forest. The simplest special cases of unreachability of {\cal N}^{in}_{\cal D}(F) from {\cal N}^{out}_{\cal D}(G) are situations when in F arcs do not enter {\cal D} , or in G arcs do not originate from {\cal D} . Then F_{\uparrow\cal D}^{G} turns out to be a forest. [ 1 , Corollaries 1 and 2 from Lemma 1] . The situation most in demand for proofs is when both graphs F_{\uparrow\cal D}^{G} and G_{\uparrow\cal D}^{F} turn out to be forests. Property 1 . [ 1 , Corollaries 3-7 from Lemma 1] Let F and G be forests, {\cal V}F={\cal V}G={\cal N} , and let T^{F} and T^{G} — some connected components (trees) of forests F and G , respectively, {\cal D}\subset{\cal N} . Then graphs F_{\uparrow\cal D}^{G} and G_{\uparrow\cal D}^{F} are forests if any of the following points are true: (a) {\cal D}={\cal V}T^{F} ; (b) {\cal D}={\cal V}T^{F}\cap{\cal V}T^{G} ; (c) {\cal D}={\cal V}T^{F}\setminus{\cal V}T^{G} ; (d) {\cal D}\subset{\cal V}T^{F}\cap{\cal V}T^{G} , {\cal N}^{in}_{\cal D}(F)=\emptyset and {\cal N}^{out}_{\cal D}(F)\subset{\cal V}T^{F}\setminus{\cal V}T^{G} ; (e) {\cal D}\subset{\cal V}T^{F}\setminus{\cal V}T^{G} , {\cal N}^{in}_{\cal D}(F)=\emptyset and {\cal N}^{out}_{\cal D}(F)\subset{\cal V}T^{G} . When constructing minimal forests, the following is useful: Property 2 . [ 2 , Proposition 1] Let F\in\tilde{\cal F}^{n} , G\in\tilde{\cal F}^{m} and let m\leq n for definiteness. Let also the set {\cal D} be such that graphs P=F^{G}_{\uparrow\cal D} and Q=G^{F}_{\uparrow\cal D} are forests, then 1) if {\cal D} contains the same number of roots of forests F and G , then P\in\tilde{\cal F}^{n} and Q\in\tilde{\cal F}^{m}

Read the complete text