Distribution of independent sets in perfect r r -ary trees

Daniel Iľkovič, Jun Yan · 2026

Read Distribution of independent sets in perfect r r -ary trees by Daniel Iľkovič, Jun Yan (2026) 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-2601-16953.txt.

Introduction

Daniel Iľkovič and Jun Yan count lone point sets in a class of trees. A lone set holds points with no edge twixt them. Trees here branch in an r-way form with no flaws. A star set is all lone sets of a size through one point. Their 2026 preprint works out how those sets spread.

Counts by size and hub point fill the work. Such counts tie to hard sums in graph math. They also feed codes that place guards or hubs on nets. Pure counts on clean trees give base truth. Rough real nets can then be set next to that base.

Catalog record

CREATORDaniel Iľkovič, Jun Yan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16953

Browse the full library · About the Tower of Babel

Full text

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

Distribution of independent sets in perfect r r -ary trees Daniel Iľkovič, Jun Yan Abstract Given a graph G G , the family of all independent sets of size k k containing a fixed vertex v v is called a star with centre v v , and is denoted by ℐ G k ​ ( v ) \mathcal{I}_{G}^{k}(v) . Motivated by a generalisation of the Erdős-Ko-Rado Theorem to the setting of independent sets in graphs, Hurlbert and Kamat conjectured that for every tree T T and every k k , the maximum of | ℐ T k ​ ( v ) | |\mathcal{I}_{T}^{k}(v)| can always be attained by a leaf of T T . While this conjecture turns out to be false in general, it is known to hold for specific families of trees like spiders and caterpillars. In this paper, we prove that this conjecture holds for a new family of trees, the perfect r r -ary trees, by constructing injections from stars centred at arbitrary vertices to stars centred at leaves. We also show that the analogous property holds for every forest 𝒯 \mathcal{T} that is the disjoint union of perfect trees with possibly varying sizes and arities, and determine the leaf that maximises | ℐ 𝒯 k ​ ( v ) | |\mathcal{I}_{\mathcal{T}}^{k}(v)| . 1 Introduction A family \mathcal{F} of sets is called intersecting if any A,B\in\mathcal{F} satisfies A\cap B\not=\varnothing . The well-known Erdős-Ko-Rado Theorem [ 4 ] , published in 1961, states that if n\geq 2k and \mathcal{F} is an intersecting family of subsets of [n] of size k , then |\mathcal{F}|\leq\binom{n-1}{k-1} . Moreover, if n>2k , then equality holds if and only if \mathcal{F}=\{A:i\in A,|A|=k\} for some i\in[n] . Since then, there have been many generalisations and variants of the Erdős-Ko-Rado Theorem in the literature. In this paper, we focus on a generalisation to the following setting of independent sets in graphs proposed by Holroyd, Spencer, and Talbot [ 7 , 8 ] in 2005. Definition 1.1 . Let G=(V(G),E(G)) be a graph, let v\in V(G) , and let k be an integer. • A subset I\subseteq V(G) is an independent set in G if uw\notin E(G) for all u,w\in I . • The family of all independent sets of size k in G is denoted by \mathcal{I}_{G}^{k} . • The family \{A\in\mathcal{I}_{G}^{k}:v\in A\} of all independent sets of size k in G containing v is denoted by \mathcal{I}_{G}^{k}(v) . Each family of the form \mathcal{I}_{G}^{k}(v) is called a star , and v is called its star centre . Note that every star \mathcal{I}^{k}_{G}(v) is an intersecting family in \mathcal{I}^{k}_{G} by definition. Definition 1.2 . Let G be a graph and let k be an integer. • G is k -EKR if no intersecting family of sets in \mathcal{I}_{G}^{k} is larger than the largest star in \mathcal{I}_{G}^{k} . • G is strictly k -EKR if every intersecting family of sets in \mathcal{I}_{G}^{k} of maximum size is a star. Observe that using this language, the Erdős-Ko-Rado Theorem can be restated as saying the empty graph on n vertices is k -EKR if n\geq 2k , and strictly k -EKR if n>2k . Several families of graphs have been shown to be k -EKR for suitable values of k . These include powers of cycles [ 12 ] , powers of paths [ 7 ] , and certain graphs with an isolated vertex [ 2 , 7 , 9 ] . A major outstanding conjecture due to Holroyd and Talbot [ 8 ] states that if \mu(G) is the minimum size of a maximal independent set in G , then G is k -EKR if k\leq\mu(G)/2 , and strictly so if k<\mu(G)/2 . Many positive results in this direction proceed by induction and use a shifting/compression proof technique involving the deletion of edges and vertices. The presence of an isolated vertex x in G is very useful as it is not affected by the deletion process, and due to the easy observation that for every k , the maximum of |\mathcal{I}_{G}^{k}(v)| can always be attained by x . For a graph G without an isolated vertex, finding the centre of a star of maximum size is no longer trivial, and it seems difficult in general to prove that G is k -EKR without knowing which star has maximum size. Motivated by this, Hurlbert and Kamat [ 9 ] proposed to study the intermediate problem of determining which vertex v\in V(G) maximises |\mathcal{I}^{k}_{G}(v)| . In particular, they considered the case when G is a tree, and conjectured that there is always a maximum-sized star centred at a leaf. Conjecture 1.3 ( [ 9 ] ) . For any k\geq 1 and any tree T , there exists a leaf \ell of T such that |\mathcal{I}_{T}^{k}(v)|\leq|\mathcal{I}_{T}^{k}(\ell)| for every v\in V(T) . Hurlbert and Kamat proved this conjecture for k\leq 4 [ 9 ] . However, independent work of Baber [ 1 ] and Borg [ 3 ] produced counterexamples disproving Conjecture 1.3 for every k\geq 5 . Feghali, Johnson, and Thomas [ 6 ] produced further counterexamples showing that maximum-sized stars can be centred on a vertex with arbitrarily large degree and arbitrarily far away from any leaves in T , which disprove Conjecture 1.3 in a very strong sense. Even though Conjecture 1.3 is now disproved, it remains interesting to determine which trees satisfy the condition in Conjecture 1.3 . We use the following terminology introduced by Estrugo and Pastine in [ 5 ] . Definition 1.4 . Let T be a tree and let k\geq 1 be an integer. • T is k -HK if there exists a leaf \ell of T such that |\mathcal{I}_{T}^{k}(v)|\leq|\mathcal{I}_{T}^{k}(\ell)| for each v\in V(T) . • T is HK if it is k -HK for every k\geq 1 . Two families of trees known to be HK are spiders [ 10 ] and caterpillars [ 5 ] . We refer interested readers to a detailed survey [ 11 ] by Hurlbert of other results on graphs with EKR-type and/or HK-type properties. The main result of this paper, Theorem 1.5 , shows that the perfect r -ary trees are HK. For every integer r\geq 2 , a perfect r -ary tree with h levels is the unique rooted plane tree T that has exactly r^{h-1} leaves, all at distance h-1 away from the root, and whose non-leaf vertices all have exactly r children. The arity of a perfect r -ary tree is r . A perfect tree is a perfect r -ary tree for some r\geq 2 . The r=2 case of Theorem 1.5 answers a question of Hurlbert [ 11 ] . Theorem 1.5 . Let T be a perfect r -ary tree. For any integer k\geq 1 , any vertex v\in V(T) , and any leaf \ell\in V(T) , we have |\mathcal{I}_{T}^{k}(v)|\leq|\mathcal{I}_{T}^{k}(\ell)| . Using similar ideas, we also show that if \mathcal{T} is a disjoint union of perfect trees, then the maximum star size can similarly be attained by a star centred at a leaf. Moreover, we determine which leaf achieves the maximum. Theorem 1.6 . Let \mathcal{T} be a forest with components T_{1},T_{2},\ldots,T_{n} , such that T_{i} is a perfect

Read the complete text