🔢 mathematics

On Graphical Partitions with Restricted Parts

This paper investigates the probability that a uniformly random integer partition of an even number $n$ with parts restricted to a prescribed set is graphical, establishing an upper bound based on the Durfee square and proving that this probability decays to zero as $n$ increases.

Original authors: Gilead Levy

Published 2026-04-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gilead Levy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a city planner trying to design a new neighborhood. You have a list of residents (the parts of a number), and you need to decide how many roads each resident needs to connect to their neighbors.

In the world of mathematics, this is called a Graphical Partition.

The Number ( $n$ ): The total number of "connections" or "roads" needed.
The Parts: The specific number of roads each house needs (e.g., House A needs 3 roads, House B needs 5).
The Graphical Condition: Can you actually draw a map where these houses connect without any roads crossing over each other or looping back on themselves in a weird way? If yes, it's a "graphical" partition. If no, it's an impossible map.

For a long time, mathematicians studied this with no rules. You could have a house with 1 road, another with 1,000 roads, or anything in between. They found that as the city gets huge, the chance of a random list of road counts actually working out is surprisingly low, but they knew roughly how low.

The New Twist: Restricted Parts
This paper asks a new question: What if we put strict rules on the houses?
Imagine a zoning law that says: "You can only build houses that need 2, 4, 6, or 8 roads," or maybe "Only houses with perfect square numbers of roads (1, 4, 9, 16) are allowed."

The author, Gilead Levy, investigates: If we force the city to follow these strict rules, how likely is it that a random list of house sizes will actually form a valid map?

The Main Findings (The "Aha!" Moments)

1. The "Durfee Square" is the Magic Key

To solve this, the author uses a shape called a Durfee Square.

Analogy: Imagine your list of house sizes is a staircase. The Durfee Square is the largest perfect square you can fit inside that staircase.
The Discovery: The author proves that the probability of the map working depends almost entirely on the size of this square.
The Result: As the square gets bigger, the chance of the map working drops extremely fast. It's like trying to fit a giant square peg into a round hole; the bigger the peg, the less likely it is to fit without breaking the rules. The paper gives a precise formula showing this probability vanishes like a ghost as the city grows.

2. The "Perfect Square" City

The paper looks at a specific, tricky case: What if every house must have a number of roads that is a perfect square (1, 4, 9, 16...)?

Old Belief: Mathematicians guessed that if you restrict the city to only square numbers, the chance of a valid map existing would eventually hit zero.
New Proof: This paper proves it. Not only does it hit zero, but the author calculates exactly how fast it disappears. It's not just "unlikely"; it's mathematically impossible for a random large city with these rules to work.

3. The Tools Used (The "Swiss Army Knife")

How did the author solve this? They used a mix of three powerful tools:

The Nash-Williams Condition: Think of this as a "Traffic Cop." It's a rule that checks if the roads are balanced enough to form a map. If the traffic is too heavy in one area, the map fails.
The Saddle-Point Method: Imagine you are hiking a mountain range to find the lowest valley (the most likely scenario). This method helps you find that "sweet spot" in the math where the numbers balance out.
Edgeworth Expansions: This is like a "fine-tuning" tool. If you know the average shape of a mountain, this tool helps you see the tiny bumps and dips that make the real shape different from the perfect average.

The Big Picture Takeaway

In simple terms:
If you let people build houses with any number of roads, you have a decent (though small) chance of making a valid map. But if you force them to follow strict rules (like "only even numbers" or "only square numbers"), the odds of making a valid map crash to zero incredibly fast as the city gets bigger.

The author didn't just say "it's impossible"; they gave us a speedometer for how fast the probability dies. They showed that the size of the "Durfee Square" (the core of the city's structure) is the single most important factor in determining whether the city can exist at all.

Why does this matter?
It connects two different worlds: Number Theory (how numbers break down) and Graph Theory (how things connect). It tells us that when we impose strict patterns on numbers, the ability of those numbers to form real-world connections (like social networks, computer circuits, or road maps) becomes vanishingly rare.

1. Problem Statement

The paper investigates graphical partitions (integer partitions that correspond to the degree sequences of simple graphs) under restricted parts. While the asymptotic behavior of unrestricted graphical partitions is well-studied (notably by Barnes and Savage), the behavior of graphical partitions where the parts are constrained to a specific prescribed set $\{ \mu(i) : i \in \mathbb{N} \}$ remains largely unknown.

The core objective is to determine the probability $p_g(n)$ that a uniformly random partition of an even integer $n$ , subject to these restrictions, is graphical. Specifically, the author aims to:

Establish an upper bound on this probability based on the partition's Durfee square side length ( $D$ ).
Determine the asymptotic decay rate of $p_g(n)$ as $n \to \infty$ .
Prove that the limit inferior of this probability is zero ( $\liminf p_g(n) = 0$ ).

2. Methodology

The author employs a synthesis of combinatorial number theory, graph theory, and advanced probabilistic analysis. The methodology proceeds through the following stages:

A. Mathematical Framework and Definitions

Restricted Partitions ( $P_\mu$ ): The set of partitions where the $i$ -th smallest part is at least $\mu(i)$ . The function $\mu$ is defined as continuous, differentiable, strictly increasing, and mapping integers to integers ( $\mu \in \mathcal{M}$ ).
Nash-Williams Condition: The paper utilizes the Nash-Williams theorem (reformulated by Barnes and Savage) as the necessary and sufficient condition for a partition to be graphical. A partition with Durfee square side $D$ $D$ is graphical if and only if its successive ranks $R_k = Y_k - X_k$ $R_{k} = Y_{k} - X_{k}$ satisfy $\sum_{k=1}^d R_k \leq -d$ $\sum_{k = 1}^{d} R_{k} \leq - d$ for all $1 \leq d \leq D$ $1 \leq d \leq D$ .
- $Y_k$ : The $k$ -th largest part.
- $X_k$ : The number of parts $\geq k$ .

B. Probabilistic Modeling (Fristedt's Model)

To analyze random partitions, the author adopts Fristedt's probabilistic model, where the number of parts of size $k$ ( $Z_k$ ) are independent geometric random variables with parameter $q = e^{-\alpha}$ .

The parameter $\alpha$ is determined by the constraint that the expected sum of parts equals $n$ .
The author analyzes the asymptotic behavior of the largest part ( $Y_1$ ) and the number of parts ( $X_1$ ) as $n \to \infty$ .

C. Asymptotic Analysis and Limit Distributions

Gumbel Distribution: Using saddle-point methods and Edgeworth expansions, the paper proves that the normalized variables $\eta(Y_k)$ and $\eta(\mu(X_k))$ converge to a Gumbel distribution (extreme value distribution).
Successive Ranks: The paper derives the joint distribution of successive ranks $R_k$ . It establishes that the centered ranks $A_k = R_k - E[R_k]$ behave like independent random variables with specific moments (cumulants) that depend on the restriction function $\mu$ .

D. Saddle-Point and Edgeworth Expansions

The core analytical tool is the saddle-point method to estimate the generating functions of restricted partitions.

Edgeworth Expansion: The author applies Edgeworth expansions to approximate the Cumulative Distribution Function (CDF) of the normalized sum of the successive ranks. This allows for a precise estimation of the probability that the Nash-Williams inequalities are satisfied.
Error Bounds: The expansion provides error terms of order $O((\log d)^{-3/2})$ , which are crucial for establishing the final upper bounds.

3. Key Contributions and Results

Theorem 4.1: Upper Bound via Durfee Square

The paper establishes a universal upper bound for the probability that a restricted partition is graphical, expressed solely in terms of the Durfee square side length $D$ .

Result: For sufficiently large $D$ , the probability is bounded by:
$\exp\left( -\frac{3}{2} D \ln \ln D + \frac{3}{2} D \right)$
Significance: This bound is invariant of the specific restrictions $\mu$ placed on the parts; it depends only on the geometry of the partition (the Durfee square).

Theorem 4.2: Decay Rate and Limit Inferior

The paper proves that the probability of a random restricted partition being graphical decays to zero as $n \to \infty$ .

Result:
$\liminf_{\substack{n \to \infty \\ n \text{ even}}} e^{\frac{3}{2} \sqrt{n} \ln \ln n} p_g(n; \mu) = 0$
(Note: The exact exponent involves $v_n = \mu(n)$ , the $n$ -th smallest allowable part, but the form highlights the decay rate).
Implication: $\liminf_{n \to \infty} p_g(n) = 0$ . This confirms that "almost all" restricted partitions are not graphical for large $n$ .

Specific Applications

The paper applies these general theorems to specific cases:

Unrestricted Partitions ( $\mu(x) = x$ ): The result recovers known bounds (e.g., $\limsup p_g(n) \leq 1/4$ ) and provides a new explicit decay rate for the limit inferior.
Perfect Squares ( $\mu(x) = x^2$ ): The paper resolves a conjecture regarding partitions with parts restricted to perfect squares. It proves:
$\liminf_{\substack{n \to \infty \\ n \text{ even}}} e^{\frac{3}{2} n^{1/4} \ln \ln n} p_{sq}(n) = 0$
This provides the first rigorous proof and explicit decay bound for this specific restriction.

4. Significance

Bridging Fields: The work successfully connects Number Theory (partition asymptotics) and Graph Theory (degree sequences) using probabilistic methods.
Generalization: It moves beyond the classical case of unrestricted partitions to a broad class of restrictions defined by continuous functions $\mu$ , offering a unified framework.
Resolution of Conjectures: It provides the first rigorous proof that the probability of graphical partitions vanishes for specific restricted sets (like perfect squares), where previously only conjectures existed.
Methodological Innovation: The application of Edgeworth expansions to the Nash-Williams condition for successive ranks in the context of restricted partitions is a novel technical approach that yields precise decay rates rather than just qualitative limits.

In summary, Gilead Levy demonstrates that imposing restrictions on partition parts significantly reduces the likelihood of the partition being graphical, and provides a rigorous mathematical framework to quantify this decay based on the Durfee square and the nature of the restrictions.