Nordhaus–Gaddum-type theorems for maximum average degree
Yair Caro, Zsolt Tuza · 2025
Read Nordhaus–Gaddum-type theorems for maximum average degree by Yair Caro, Zsolt Tuza (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-2505-04929.txt.
Introduction
Yair Caro and Zsolt Tuza prove new bounds in the style of a classic graph result, for a measure of how dense a graph's densest part can be. Their paper is from two thousand twenty-five.
The classic result bounds the sum and product of the color counts of two parts that split a full graph's edges. Caro and Tuza take up splits into any count of parts, and swap the color count for the max mean degree. They find a clean cap that the true value nears as both counts grow. They pin the exact value for splits in two, and for splits that leave a small count of edges out. They also give uses for the bounds in past work.
Catalog record
| CREATOR | Yair Caro, Zsolt Tuza |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nordhaus–Gaddum-type theorems for maximum average degree Yair Caro, Zsolt Tuza Abstract A k k -decomposition ( G 1 , … , G k ) (G_{1},\dots,G_{k}) of a graph G G is a partition of its edge set into k k spanning subgraphs G 1 , … , G k G_{1},\dots,G_{k} . The classical theorem of Nordhaus and Gaddum bounds χ ( G 1 ) + χ ( G 2 ) \chi(G_{1})+\chi(G_{2}) and χ ( G 1 ) χ ( G 2 ) \chi(G_{1})\chi(G_{2}) over all 2-decompositions of K n K_{n} . For a graph parameter 𝔭 {\mathfrak{p}} , let 𝔭 ( k , G ) = max { ∑ i = 1 k 𝔭 ( G i ) } {\mathfrak{p}}(k,G)=\max\{\sum_{i=1}^{k}{\mathfrak{p}}(Gi)\} , taken over all k k -decompositions of graph G G . In this paper we consider M ( k , K n ) = M ( k , n ) = max { ∑ i = 1 k Mad ( G i ) } M(k,K_{n})=M(k,n)=\max\{\sum_{i=1}^{k}\mathrm{Mad}(G_{i})\} , taken over all k k -decompositions of the complete graph K n K_{n} , where Mad ( G ) \mathrm{Mad}(G) denotes the maximum average degree of G G , Mad ( G ) = max { 2 e ( H ) / | H | : H ⊆ G } = max { d ( H ) : H ⊆ G } \mathrm{Mad}(G)=\max\{2e(H)/|H|:H\subseteq G\}=\max\{d(H):H\subseteq G\} . Among the many results obtained in this paper we mention the following selected ones. (1) M ( k , n ) < k n M(k,n)<\sqrt{k}\,n , and lim k → ∞ ( lim inf n → ∞ M ( k , n ) k n ) = 1 \lim_{k\to\infty}\bigl(\liminf_{n\to\infty}\frac{M(k,n)}{\sqrt{k}\,n}\bigr)=1 . (2) Exact determination of M ( 2 , n ) M(2,n) . (3) Exact determination of M ( k , n ) M(k,n) when k = ( n 2 ) − t k=\binom{n}{2}-t , 0 ≤ t ≤ ( n − 1 ) 2 / 3 0\leq t\leq(n-1)^{2}\!/3 . Applications of these bounds to other parameters considered before in the literature are given. 1 Introduction Nordhaus and Gaddum [ 18 ] proved that if G is a graph of order n then 2\sqrt{n}\leq\chi(G)+\chi(\overline{G})\leq n+1 and n\leq\chi(G)\cdot\chi(\overline{G})\leq(n+1)^{2}\!/4 . This theorem was the starting point of a reach theory of extremal results of the following form, called Nordhaus–Gaddum-type theorems. A k -decomposition of a graph G is a partition of its edge set with k spanning subgraphs G_{1},\dots,G_{k} . For a graph parameter {\mathfrak{p}} , this track of research investigates: (a) \max\,\{\sum_{i=1}^{k}{\mathfrak{p}}(G_{i})\} , (b) \min\,\{\sum_{i=1}^{k}{\mathfrak{p}}(G_{i})\} , (c) \max\,\{\prod_{i=1}^{k}{\mathfrak{p}}(G_{i})\} , (d) \min\,\{\prod_{i=1}^{k}{\mathfrak{p}}(G_{i})\} , where the maxima and minima are taken over all k-decompositions of G . Analogous functions have been studied in other combinatorial structures, too. Nordhaus and Gaddum considered the case k=2 for the parameter {\mathfrak{p}}(G)=\chi(G) , the chromatic number. Many other graphical parameters were studied in this context since then (more than 2000 articles in google scholar). We refer the reader to the survey [ 2 ] . Also, there is an evolving literature where Nordhaus-Gaddum type theorems are proved for k\geq 3 ; see, for example, [ 1 ] , [ 4 ] , [ 5 ] , [ 11 ] , [ 16 ] , [ 19 ] . In this paper we concentrate on a problem of type (a) , and consider the extremal function M(k,n):=\max\,\{\sum_{i=1}^{k}\mathrm{Mad}(G_{i})\} taken over all k -decompositions of the complete graph K_{n} , where \mathrm{Mad}(G)=\max\{2e(H)/|H|:H\subseteq G\}=\max\{d(H):H\subseteq G\} , called the maximum average degree of G . Somewhat surprisingly, we were unable to find any paper concerning Nordhaus–Gaddum-type results for the parameter \mathrm{Mad}(G) , despite that it is a parameter used frequently in determining the arboricity of graphs and also in many coloring problems. See, e.g., [ 6 ] , [ 17 ] . The value \mathrm{Mad}(G)+1 dominates or is closely related to many other parameters, including the clique number \omega(G) , the choice number or list chromatic number \mathrm{ch}(G) , and the Szekeres–Wilf number—also called coloring number—denoted \mathrm{col}(G) , which is just one greater than the degeneracy of G . Hence M(k,n) serves as an upper bound for the corresponding Nordhaus–Gaddum-type theorems for these parameters. We shall use this fact to comment on earlier results obtained in [ 11 ] . To deal with M(k,n) , we also introduce a List variant of Nordhaus–Gaddum as follows. A list \mathsf{L} of k graphs is a multiset, \mathsf{L}=\{G_{1},\dots,G_{k}\} , where repetitions are allowed. For a positive integer N define: M^{\mathsf{L}}(k,N)=\max\{\sum\mathrm{Mad}(G_{j})\} taken over all lists \mathsf{L} of k graphs such that \sum e(G_{j})=N . Clearly M(k,n)\leq M^{\mathsf{L}}(k,\binom{n}{2}) . Hence if there is a list of k graphs realizing M^{\mathsf{L}}(k,\binom{n}{2}) and this list can also be realized as a decomposition of K_{n} , then the the inequality M(k,n)\leq M^{\mathsf{L}}(k,\binom{n}{2}) turns to equality. This idea can be adopted for other Nordhaus–Gaddum-type results with distinct parameters. Organization of the paper In section 2 we present simple properties of \mathrm{Mad}(G) , which are used later along the paper. In section 3 we present, among other things: (i) A general upper bound: M(k,n)<\sqrt{k}\,n (Lemma 14 and Corollary 17 ). (ii) A complete determination of M^{\mathsf{L}}(k,N) (Theorem 20 in Section 5.1 ) and a sufficient condition for M(k,n)=M^{\mathsf{L}}(k,\binom{n}{2}) (Theorem 21 ), which are among the major results of this paper. In the appendix we supply a second, more algorithmic and direct proof of Theorem 21 . (iii) Armed with Theorems 20 and 21 we present various constructions based on Steiner systems, finite geometries, Wilson’s decomposition theorem and pairwise balanced K -designs where K=\{p,p+1\} , to obtain sharp or nearly sharp result on various values of M(k,n) . In Section 4.1 we determine M(2,n) exactly for all n (Theorem 18 ), and in Section 4.2 we supply lower-bound constructions for M(k,n) for 3\leq k\leq 7 (Proposition 19 ). In Section 5.2 we completely determine M(k,n) for k=\binom{n}{2}-t , 0\leq t\leq(n-1)^{2}\!/3 , and characterize the extremal decompositions. In Section 6.2 we further develop some lower-bound constructions via substitution and blow-up of complete graphs or Steiner systems, which allow us to finally prove (Theorem 34 ) that (1-o_{k}(1))\sqrt{k}\,n-c_{k}<M(k,n)<\sqrt{k}\,n for some constant c_{k} if k is fixed, which is another major result of this paper. As k grows, it means that the convergence \lim_{k\to\infty}\bigl(\liminf_{n\to\infty}\frac{M(k,n)}{\sqrt{k}\,n}\bigr)=1 is valid. Lastly in section 7 we consider applications of our results to several parameters dominated by or related to M(k,n) , which were already discussed in [ 11 ] , and also several further ones. Our main result here, Theorem 40 , is that if M(k,n)=M^{\mathsf{L}}(k,\binom{n}{2}) , then the analogously defined extremal function {\mathfrak{p}}(k,n) for many further graph parameters {\mathfrak{p}} is equal to M(k,n) or \left\lfloor M(k,n)\right\rfloor+k . This includes clique number, chromatic number, vertex/edge connectivity, and more. Section 8 contains open problems for future research. 1.1 Notation We apply the following standard notation for graphs G : |G|=|V(G)| is the number of vertices (the order of G ), e(G) is the number of edges, \delta(G) is the minimum degree of vertices, and d(G)=(\sum_{v\in V(G)}\deg(v))/|G|={2e(G)}/{|G|} is the average degree. Further common notation is