A note on the rainbow Turán number of brooms with length 2 handles
Anastasia Halfpap · 2025
Read A note on the rainbow Turán number of brooms with length 2 handles by Anastasia Halfpap (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-2512-15978.txt.
Introduction
Anastasia Halfpap studies the rainbow Turan number of broom graphs with length two handles in a 2025 paper. A broom is a short path with several pendant edges at one end. The rainbow Turan number asks for the most edges an n vertex graph can have while admitting a proper edge coloring with no rainbow copy of the target graph.
Johnston and Rombach began this study and claimed an asymptotic value for all brooms of this type. Halfpap corrects an error in that argument, finding two small cases where the claimed value is wrong. In all other cases the original value is recovered. The proof also characterizes the extremal constructions for certain residue classes of n modulo k.
Catalog record
| CREATOR | Anastasia Halfpap |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-15978
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note on the rainbow Turán number of brooms with length 2 handles Anastasia Halfpap Abstract For a fixed graph F F , the rainbow Turán number ex ∗ ( n , F ) \mathrm{ex^{*}}(n,F) is the largest number of edges possible in an n n -vertex graph which admits a rainbow- F F -free proper edge-coloring. We focus on the rainbow Turán numbers of trees obtained by appending some number of pendant edges to one end of a length 2 path; we call such a tree with k k total edges a k k -edge broom with length 2 2 handle, denoted by B k , 2 B_{k,2} . Study of ex ∗ ( n , B k , 2 ) \mathrm{ex^{*}}(n,B_{k,2}) was initiated by Johnston and Rombach, who claimed a proof asymptotically establishing the value of ex ∗ ( n , B k , 2 ) \mathrm{ex^{*}}(n,B_{k,2}) for all k k . We correct an error in this original argument, identifying two small cases in which the value claimed in the literature is incorrect; in all other cases, we recover the originally claimed value. Our argument also characterizes the extremal constructions for ex ∗ ( n , B k , 2 ) \mathrm{ex^{*}}(n,B_{k,2}) for certain congruence classes of n n modulo k k . 1 Introduction Given two graphs G and F , we say that G is F -free if G contains no subgraph isomorphic to F . The Turán number of F , denoted \mathrm{ex}(n,F) , is the maximum number of edges in an n -vertex F -free graph. Study of \mathrm{ex}(n,F) forms a cornerstone of extremal combinatorics, and has inspired a variety of generalizations and extensions in recent years. In particular, an edge-coloring of a graph G is a function c:E(G)\rightarrow\mathbb{N} . For e\in E(G) , we say that c(e) is the color of e . We say that an edge-coloring c of G is proper if no two incident edges of G receive the same color under c . We say that c is a rainbow edge-coloring (or that G is rainbow under c ) if all edges of G receive distinct colors under c (that is, if c is injective). Given graphs G and F and an edge-coloring c of G , we say that G is rainbow- F -free (under c ) if G does not contain any subgraph which is both isomorphic to F and rainbow under c . The rainbow Turán number of F , denoted \mathrm{ex^{*}}(n,F) , is the largest number of edges in an n -vertex graph G which admits a proper edge-coloring under which G is rainbow- F -free. Study of \mathrm{ex^{*}}(n,F) was initiated by Keevash, Mubayi, Sudakov, and Verstraëte [ 8 ] , who showed (among other things) that \mathrm{ex}(n,F)\leq\mathrm{ex^{*}}(n,F)\leq\mathrm{ex}(n,F)+o(n^{2}) for all graphs F . We have that \mathrm{ex}(n,F)=\Theta(n^{2}) for all non-bipartite F (and in fact the value of \mathrm{ex}(n,F) is asymptotically understood for non-bipartite F ; see [ 2 ] , [ 3 ] ). Thus, the study of \mathrm{ex^{*}}(n,F) has primarily focused on cases where F is bipartite. In this regime, it is natural to begin with trees and forests, and substantial work has been devoted to finding \mathrm{ex^{*}}(n,F) for various trees (see, for instance, [ 1 ] , [ 4 ] , [ 5 ] , [ 6 ] , [ 7 ] ). In this note, we denote by P_{\ell} the path on \ell edges – that is, the path of length \ell . A broom is a tree obtained from some path P_{\ell} by appending some number of pendant edges to one endpoint of P_{\ell} . We call the path P_{\ell} the handle of this broom and the pendant edges its bristles . Denote by B_{k,\ell} the broom with a length \ell handle and k total edges (so, B_{k,\ell} has k-\ell bristles). Brooms of various dimensions are depicted in Figure 1 . Figure 1 : The brooms B_{7,2} (left) and B_{5,3} (right). In general, determination of \mathrm{ex^{*}}(n,B_{k,\ell}) seems very difficult. The family of all brooms contains all paths, and we only understand \mathrm{ex^{*}}(n,P_{\ell}) precisely for \ell\leq 5 (see [ 7 ] and [ 5 ] ). However, for small values of \ell , finding \mathrm{ex^{*}}(n,B_{k,\ell}) seems much more tractable than other rainbow Turán problems for trees. Systematic study of \mathrm{ex^{*}}(n,B_{k,\ell}) was initiated by Johnston and Rombach, who claim the following result (Lemma 4.1 in [ 7 ] ). Theorem 1.1 (Johnston-Rombach [ 7 ] ) . \mathrm{ex^{*}}(n,B_{k,2})=\begin{cases}\frac{k}{2}n+O(1)&\text{ if }k\text{ is odd}\\ \frac{k^{2}}{2(k+1)}n+O(1)&\text{ if }k\text{ is even}\end{cases} Unfortunately, the statement of Theorem 1.1 is incorrect for two small values of k , and the original proof given by Johnston and Rombach contains an error in all cases where k is even. The purpose of this note is to amend the statement of Theorem 1.1 to capture these small exceptions and to provide a proof which both captures these exceptional cases and addresses the broader issue with the original argument. We state a corrected version of the theorem now. Theorem 1.2 . Let k\geq 2 . \mathrm{ex^{*}}(n,B_{k,2})=\begin{cases}\frac{k}{2}n+O(1)&\text{ if }k\text{ is odd}\\ \frac{k-1}{2}n+O(1)&\text{ if }k\in\{2,4\}\\ \frac{k^{2}}{2(k+1)}n+O(1)&\text{ if }k\text{ is even and }k\geq 6\end{cases} The remainder of this note is organized as follows. In Subsection 1.1 , we briefly summarize the notation used in our arguments. In Section 2 , we discuss the error in the original proof of Theorem 1.1 and we give a proof of Theorem 1.2 . 1.1 Notation We endeavor to use notation standard to the area. For reference, we collect a variety of ubiquitous definitions here. A graph G is defined by a pair of sets: a vertex set V(G) and an edge set E(G) of unordered pairs from V . All graphs in this note are finite and simple. Vertices u,v are adjacent in G if uv\in E(G) and vertex v is incident to edge e if v\in e . The degree of a vertex v\in V(G) , denoted d(v) , is the number of edges in E(G) which are incident to v . We denote the maximum degree in G by \Delta(G) . The neighborhood of v , denoted N(v) , is the set of vertices adjacent to v . In addition to the edge-coloring definitions given in the introduction, we use several standard terms to describe edge-colored graphs. Given a graph G , an edge-coloring c is a k -edge-coloring if the image of c has size k ; we say that G is k -edge-colored under c . Similarly, G is k -edge-colorable if there exists a proper coloring c of G using k colors. When it will not cause confusion, we typically omit the explicit reference to the coloring function c – so, say that G is a k -edge-colored graph. In an edge-colored graph G , a color class is a set of edges which all receive the same edge-color. We will use some standard graph operations to describe constructions. Given a graph G , the complement of G , denoted \overline{G} , is the graph with V(\overline{G})=V(G) and e\in E(\overline{G}) if and only if e\not\in E(G) . Given two graphs G and H on (disjoint) vertex sets V(G) and