A Two-Graph Refinement of Paulsen's Lollipop Bounds

Paras Chopra; Siddhartha Mahajan

arxiv: 2606.06064 · v1 · pith:QF4YNPFYnew · submitted 2026-06-04 · 🧮 math.CO · math.MG

A Two-Graph Refinement of Paulsen's Lollipop Bounds

Siddhartha Mahajan , Paras Chopra This is my paper

Pith reviewed 2026-06-28 00:41 UTC · model grok-4.3

classification 🧮 math.CO math.MG

keywords lollipop divisionsplane regionscrossing inequalitiesK4-free graphsK5-free graphscombinatorial geometryobstruction graphsPaulsen bounds

0 comments

The pith

A two-graph refinement using K4-free D and K5-free E closes the remaining gaps in a_L(n) for n up to 17 and n=19.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes exact values for a_L(n), the maximum number of regions into which n lollipops divide the plane, by recasting Paulsen's second obstruction as a crossing inequality on two graphs. It models non-close stem pairs as a K4-free graph D and non-intriguing circle pairs as a K5-free graph E, then bounds total crossings C by 4 times the number of pairs plus the sizes of D, E, and their intersection. Retaining the overlap term and enumerating near-extremal configurations determines the sequence 1,2,10,25,45,71,104,142,186,237,294,356,425,500,580,667,761,859 for n from 0 to 17, sets a_L(19) at 1076, and narrows the gaps at n=18 and 20 to single values. A sympathetic reader cares because these are the last open cases left by prior obstruction methods in this combinatorial geometry problem.

Core claim

The central claim is that the inequality C ≤ 4inom{n}{2} + |D| + |E| + |D∩E| together with exhaustive analysis of near-extremal D and E configurations determines a_L(n) exactly for n ≤ 17 and n=19, giving the values 1,2,10,25,45,71,104,142,186,237,294,356,425,500,580,667,761,859 for n=0 to 17 and 1076 for n=19, while leaving one-region gaps at n=18 and 20.

What carries the argument

The two-graph refinement consisting of a K4-free graph D on non-close stem pairs and a K5-free graph E on non-intriguing circle pairs, which tightens the bound on total pairwise crossings C.

If this is right

a_L(n) equals the listed sequence for every n from 0 through 17.
a_L(19) equals 1076.
964 ≤ a_L(18) ≤ 965 and 1193 ≤ a_L(20) ≤ 1194.
Keeping the intersection term |D ∩ E| improves on Paulsen's original bound that replaced it by |D| alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same two-graph approach might be applied to other plane-division problems that involve multiple distinct types of geometric obstructions.
If the enumeration of near-extremal graphs can be automated or extended, exact values for a_L(n) at larger n could become reachable.
Analogous refinements that retain overlap terms between two constraint graphs may close gaps in related combinatorial bounds on curve arrangements.

Load-bearing premise

The geometric constraints imply D is K4-free and E is K5-free, the crossing inequality holds, and the enumeration of near-extremal D and E configurations is exhaustive for each n.

What would settle it

An explicit arrangement of 17 lollipops that produces 860 or more regions would falsify the claimed exact value a_L(17)=859.

read the original abstract

Let $a_L(n)$ be the maximum number of regions into which $n$ lollipops divide the plane. Paulsen introduced a second obstruction for this problem, based on pairs of circles meeting at obtuse angle, in addition to the stem-direction obstruction of Cutler-Karlsson-Sloane. We recast Paulsen's argument as a weighted problem for two graphs: a $K_4$-free graph $D$ of non-close stem pairs and a $K_5$-free graph $E$ of non-intriguing circle pairs. For the total number $C$ of pairwise crossings, $$ C\le 4\binom n2+|D|+|E|+|D\cap E|. $$ Paulsen bounds the final term by $|D|$. We keep the overlap term and analyze near-extremal configurations of $D$ and $E$. This closes all of Paulsen's remaining gaps up to $n=17$, and also closes $n=19$: $$ \begin{array}{c} a_L(0),a_L(1),\ldots,a_L(17)\\ =1,2,10,25,45,71,104,142,186,237,294,356,425,500,580,667,761,859, \end{array} $$ and $$ a_L(19)=1076. $$ The same method gives the one-region gaps $$ 964\le a_L(18)\le965,\qquad 1193\le a_L(20)\le1194. $$

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Keeps the |D∩E| term in the crossing bound and uses near-extremal enumeration to pin exact a_L(n) values up to 17 and at 19, but the load-bearing claim is that no higher-weight configuration was missed.

read the letter

The useful move is recasting the two obstructions as a K4-free graph D and a K5-free graph E on the same vertex set, then retaining the intersection term in the inequality C ≤ 4inom{n}{2} + |D| + |E| + |D∩E| instead of replacing it by |D|. That single change lets the upper bound meet the known lower bound for every n from 0 to 17 and also for n=19, giving the explicit sequence listed in the abstract plus a_L(19)=1076.

The geometric incidence rules that produce the forbidden-subgraph conditions and the crossing inequality itself are the standard ones from the lollipop literature, so that part is not the novelty. The novelty is the decision to keep the overlap and then exhaust the near-extremal pairs for each small n.

The obvious soft spot is exactly the exhaustiveness of that enumeration. For n=19 the vertex count is already large enough that any missed pair with a larger weighted sum would break the claimed equality. The abstract states that the analysis closes the gaps, but without the actual list or the verification method it is impossible to judge whether the enumeration is complete. The fact that they leave one-region gaps at 18 and 20 shows they are not claiming a general method, only these finite cases.

This is narrow combinatorial geometry work. Readers already tracking Paulsen’s bounds or similar circle-stem arrangements will want the new numbers; outsiders will not. It is worth sending to a referee who can check the configuration search, because the claimed values are concrete and the refinement is a clear technical improvement over the earlier bound.

Referee Report

1 major / 0 minor

Summary. The manuscript refines Paulsen's approach to the lollipop division problem by recasting the stem-direction and obtuse-angle obstructions as a K4-free graph D and a K5-free graph E. It establishes the crossing bound C ≤ 4inom{n}{2} + |D| + |E| + |D∩E| and determines exact values of a_L(n) for n=0..17 and n=19 (with one-region gaps for n=18,20) by maximizing the weighted sum over near-extremal admissible pairs (D,E).

Significance. If the enumeration of near-extremal configurations is exhaustive, the work supplies the first exact determinations for multiple open cases left by Paulsen, strengthens the geometric incidence arguments with an explicit two-graph model, and demonstrates that retaining the overlap term |D∩E| yields tighter bounds than Paulsen's |D|-only estimate.

major comments (1)

The exact claims a_L(n) for n≤17 and a_L(19)=1076 rest on the assertion that every admissible pair (D,E) with |D|+|E|+|D∩E| near the maximum has been enumerated; any omitted configuration yielding a strictly larger sum would falsify the equality with the known lower bound. The manuscript must supply a self-contained argument or verifiable computational certificate establishing this exhaustiveness for each n.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the two-graph model and its ability to close gaps left by Paulsen. The single major comment correctly identifies that the exact determinations rest on computational exhaustiveness; we address this directly below and will revise the manuscript to strengthen the presentation.

read point-by-point responses

Referee: The exact claims a_L(n) for n≤17 and a_L(19)=1076 rest on the assertion that every admissible pair (D,E) with |D|+|E|+|D∩E| near the maximum has been enumerated; any omitted configuration yielding a strictly larger sum would falsify the equality with the known lower bound. The manuscript must supply a self-contained argument or verifiable computational certificate establishing this exhaustiveness for each n.

Authors: We agree that a self-contained justification of exhaustiveness is required. In the revision we will insert a dedicated subsection (Section 4.3) that (i) specifies the backtracking algorithm used to generate all K4-free D and K5-free E on n labeled vertices subject to the geometric constraints of the lollipop model, (ii) describes the pruning rules that eliminate pairs whose weighted sum cannot exceed the known lower bound, and (iii) reports the total number of admissible pairs examined for each n together with the machine and runtime. Pseudocode will be included, and the source code will be deposited in a public repository with a DOI. This supplies both a self-contained argument and a verifiable certificate. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation from geometric constraints and finite graph enumeration is self-contained

full rationale

The paper derives the crossing inequality C ≤ 4inom{n}{2} + |D| + |E| + |D∩E| directly from stated geometric obstructions on stem directions and circle angles, which force D to be K4-free and E to be K5-free. It then maximizes the weighted sum over such graphs on n vertices and matches the resulting upper bound on a_L(n) to known lower bounds. This process uses external references to Paulsen and Cutler-Karlsson-Sloane for the initial obstructions but contains no self-citation that is load-bearing, no parameter fitted to the target sequence, and no reduction of the claimed equalities to a definition or ansatz by construction. The finite enumeration for n≤19 is a standard exhaustive search whose completeness is independent of the final numerical values; it does not create a self-referential loop. The result is therefore not forced by any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

No free parameters or invented entities appear. The work rests on domain assumptions that the two geometric obstructions translate exactly into the stated forbidden-subgraph graphs and that the crossing inequality holds with the listed terms.

axioms (3)

domain assumption Geometric stem-direction constraints imply that the graph D of non-close stem pairs is K4-free.
Abstract states this as the recasting of the first obstruction.
domain assumption Geometric circle-angle constraints imply that the graph E of non-intriguing circle pairs is K5-free.
Abstract states this as the recasting of the second obstruction.
domain assumption The total pairwise crossings satisfy C ≤ 4inom{n}{2} + |D| + |E| + |D∩E|.
Abstract presents this as the weighted two-graph formulation of Paulsen's argument.

pith-pipeline@v0.9.1-grok · 5812 in / 1555 out tokens · 59521 ms · 2026-06-28T00:41:43.982950+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 1 linked inside Pith

[1]

David O. H. Cutler, Jonas Karlsson, and Neil J. A. Sloane,Cutting a Pancake with an Exotic Knife, arXiv:2511.15864v3 [math.CO], 19 Apr. 2026. https://arxiv.org/abs/2511.15864

Pith/arXiv arXiv 2026
[2]

https://math.mp42.de/lollipop/

Matthias Paulsen,The Lollipop Problem, 2026. https://math.mp42.de/lollipop/

2026
[3]

Maximum number of regions that can be formed in the plane by drawingn lollipop (or qoppa) shapes of any size and orientation

OEIS Foundation Inc.,The On-Line Encyclopedia of Integer Sequences, entry A389624, “Maximum number of regions that can be formed in the plane by drawingn lollipop (or qoppa) shapes of any size and orientation.” https://oeis.org/A389624
[4]

Turan, On an extremal problem in graph theory,Matematikai es Fizikai Lapok48(1941), 436–452

P. Turan, On an extremal problem in graph theory,Matematikai es Fizikai Lapok48(1941), 436–452. 9 A Paulsen’s forced intriguing pair We recall Paulsen’s proof that among five circles, some pair is intriguing. Suppose, toward a contradiction, that five circles with centersxi∈R2 and radiiri > 0are pairwise non-intriguing. Thus every pair intersects at an ob...

1941

[1] [1]

David O. H. Cutler, Jonas Karlsson, and Neil J. A. Sloane,Cutting a Pancake with an Exotic Knife, arXiv:2511.15864v3 [math.CO], 19 Apr. 2026. https://arxiv.org/abs/2511.15864

Pith/arXiv arXiv 2026

[2] [2]

https://math.mp42.de/lollipop/

Matthias Paulsen,The Lollipop Problem, 2026. https://math.mp42.de/lollipop/

2026

[3] [3]

Maximum number of regions that can be formed in the plane by drawingn lollipop (or qoppa) shapes of any size and orientation

OEIS Foundation Inc.,The On-Line Encyclopedia of Integer Sequences, entry A389624, “Maximum number of regions that can be formed in the plane by drawingn lollipop (or qoppa) shapes of any size and orientation.” https://oeis.org/A389624

[4] [4]

Turan, On an extremal problem in graph theory,Matematikai es Fizikai Lapok48(1941), 436–452

P. Turan, On an extremal problem in graph theory,Matematikai es Fizikai Lapok48(1941), 436–452. 9 A Paulsen’s forced intriguing pair We recall Paulsen’s proof that among five circles, some pair is intriguing. Suppose, toward a contradiction, that five circles with centersxi∈R2 and radiiri > 0are pairwise non-intriguing. Thus every pair intersects at an ob...

1941