{"id":"1332e8f3-a315-40a7-b122-70fed93c70cf","arxiv_id":"2506.19123","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For permutations sampled from the Brownian separable permuton, LIS(σ_n)/n^{α(p)} converges almost surely to a positive finite random variable, and α(p) is the explicit solution of a Gamma-function equation.","lead":"This paper finds the exact growth exponent for the longest increasing subsequence in random permutations built from Brownian separable permutons, and the matching exponent for largest cliques in Brownian cographons. The exponent is a closed-form function of a parameter p, with a random scaling limit instead of just polynomial bounds.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"A.s. convergence rests on Lemma 9.2, whose proof is absent from the provided text: Section 9.3 breaks off before Lemmas 9.3–9.6, leaving the key remainder estimate unverified.","rationale":"Most of the paper's chain is coherent: the supermultiplicativity argument, the rough regularity estimates, the local convergence via black-golden coupling, the good regularity estimates, and the extraction of the exponent via test sequences all appear internally consistent. The recursion for q in Lemma 2.4 is correct; apparent missing factors are accounted for by the probability 1/2 that the BGW root is a leaf. Lemma 3.8 is a standard Dirichlet-multinomial decomposition and seems sound. The single point where the central almost-sure claim is not fully checkable from the provided text is the proof of Lemma 9.2, which is essential because the conclusion n^{-alpha} LIS(T_n) -> X almost surely depends on summability of the remainder sequence. The reader's MODERATE confidence is justified, but the missing proof prevents full verification; acceptance should be conditional on confirming that the omitted section delivers exactly the stated almost-sure polynomial tail.","tokens_in":77024,"tokens_out":36517,"duration_ms":353917,"concrete_test":"Retrieve the complete Section 9.3 from the arXiv source and verify that Lemmas 9.3, 9.4, 9.5 and 9.6 prove Lemma 9.2 as stated. In particular, check that the transfer from E[|#Lmax_intersect(T_k)/k - alpha|] = O(k^{-epsilon}) in Theorem 9.1 to the unconditioned remainders R_n yields sum_{n>=n0} |R_n| <= n0^{-epsilon} almost surely, not merely convergence in probability or along a subsequence. If the proof requires additional assumptions or gives a weaker tail bound, the almost-sure convergence in Theorem 2.3 does not follow.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"To upgrade the exponent result to the almost-sure scaling limit, Section 9 writes n^{-alpha} LIS(T_n) as a backward martingale plus remainder terms R_n (Eq. 9.3) and needs sum_{n>=n0} |R_n| <= n0^{-epsilon} almost surely (Lemma 9.2). This is the step that turns Theorem 9.1, a quantitative law of large numbers for #Lmax_intersect(T_k) under the conditioning LIS(T_k)=k, into control of the unconditioned Remy tree T_n. The text states Lemma 9.2 and says it follows from Lemmas 9.3, 9.4, 9.5 and 9.6, but the provided manuscript stops mid-sentence in Section 9.3 before any of those lemmas or their proofs appear. Without that argument, the almost-sure convergence of n^{-alpha} LIS(T_n), and hence the scaling limit in Theorem 1.1, is not actually demonstrated in the available text. The reader's identified Lemma 3.8 is standard and I found no defect there; the insecure point is this omitted remainder transfer.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the longest increasing subsequence (LIS) of permutations sampled from the Brownian separable permuton μ_p, and the largest clique of graphs sampled from the Brownian cographon W_p. The main result, Theorem 1.1, asserts that for every p∈(0,1), with the natural Rémy coupling, LIS(σ_n)/n^{α(p)} converges almost surely to a non-deterministic, almost surely positive and finite random variable X(p) that is a deterministic measurable function of μ_p, where α(p) is the unique solution in (1/2,1) of the Gamma-function equation (1.3). The proof proceeds by translating the problem into a statement about the largest positive subtree of a p-signed uniform binary tree: existence of the exponent is proved by supermultiplicativity (Section 4), rough regularity of the sequences q and Q is established in Section 5, a local convergence and a law of large numbers for the intersection of maximal positive subtrees are proved in Sections 6–7, the exact exponent is extracted in Section 8, and the almost-sure scaling limit is claimed to follow in Section 9 via a backward-martingale decomposition with remainder control. The paper also announces a scaling limit for the leftmost maximal positive subtree (Theorem 2.6) and states analogous clique/independent-set results for the Brownian cographon.","tokens_in":77154,"tokens_out":4152,"duration_ms":47226,"significance":"If the claimed results hold, this is a substantial contribution. Prior to this work, even the existence of the exponent α(p) for LIS of Brownian separable permutons was open; the paper not only proves existence but identifies α(p) exactly through a simple Gamma-function equation and upgrades the earlier polynomial-factor bounds of BDSG24 to an almost-sure scaling limit with an explicit random variable. The same exponent governs the largest clique of the Brownian cographon, unifying the permuton and graphon settings. The proof strategy is impressive and self-contained: the exponent is first produced by a supermultiplicativity argument, the constant λ from the law of large numbers for #L^max_∩(T_k) is later identified with α a posteriori, and the final identification of α uses regularly varying sequences and a comparison with test sequences. The paper also connects the exponent to the spectral zeta function and gives a by-product scaling limit of the leftmost maximal positive subtree. The main caveat is completeness: the final almost-sure convergence step is not actually present in the submitted text, so the central claim cannot currently be verified.","major_comments":[{"comment":"The proof of Lemma 9.2 is absent. The text states Lemma 9.2 and says it follows from Lemmas 9.3–9.6, but the manuscript breaks off in Section 9.3 immediately after Eq. (9.12), before any of those lemmas or their proofs appear. Lemma 9.2 is load-bearing: it is the estimate Σ_{n≥n0}|R_n| ≤ n0^{-ε} that turns the quantitative law of large numbers for the conditioned model T_k (Theorem 9.1) into control of the remainder R_n in the backward-martingale decomposition (9.3) for the unconditioned Rémy tree T_n. Without this argument, the almost-sure convergence of n^{-α}LIS(T_n) in Theorem 2.3, and hence the main scaling limit in Theorem 1.1, is not demonstrated in the available text.","section":"Section 9.3, Lemma 9.2 and Eq. (9.3)"},{"comment":"Sections 9.4 and 9.5 are announced in the table of contents but their content is not present in the submitted manuscript. Section 9.4 is needed to conclude the martingale argument and establish Theorem 2.3, while Section 9.5 is the only place where the statement that X is a deterministic measurable function of the Brownian separable permuton is justified; that measurability is part of the statement of Theorem 1.1. Section 9.6, which contains the proof of Theorem 2.6, is also missing. The final theorems are therefore not verifiable from the version under review, and this is not a presentation issue but a gap in the proof of the central claim.","section":"Sections 9.4 and 9.5"}],"minor_comments":[{"comment":"The definition of good scales in Definition 6.10 depends on a constant C coming from Lemma 6.9, but the relation between this C and the constants in Lemma 6.12 is not made explicit; adding a sentence stating that the C is fixed and universal throughout Section 6 would improve readability.","section":"Section 6.3.3, Definition 6.10"},{"comment":"In the display after Eq. (9.7), the radical expression is typeset awkwardly with 'radicaltp/radicalvertex' artifacts; the intended expression is the square root of δ2(k)-2αδ1(k). This is a typesetting issue but should be corrected.","section":"Section 9.2, proof of Theorem 9.1"},{"comment":"The caption says 'Left: The graph of the functions α*(p), α(p) and β*(p)' but the figure contains two panels and the right panel shows α(p)-α*(p); the caption's first 'Left' appears to describe both panels. Clarify the panel labels.","section":"Page 5, Figure 3"}],"recommendation":"major_revision","confidential_remarks":"The copy of the manuscript provided to me ends mid-sentence in Section 9.3, before Lemmas 9.3–9.6 and before Sections 9.4–9.6. The reader's accept recommendation appears to have assumed that the missing proofs exist. I would advise the editor to verify whether a complete version exists and, if so, to send that version for review before any acceptance decision. The omission is not merely cosmetic: the almost-sure convergence and the measurability of the limit are exactly the parts of the main theorem that are missing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper solves a genuinely open problem: for the Brownian separable permuton μ_p, it gives the exact exponent α(p) for the length of the longest increasing subsequence, and it states an almost-sure scaling limit with a non-degenerate limit X(p). The previous state of the art was polynomial upper and lower bounds with different exponents; even existence of the exponent was open. This is a real breakthrough, and the companion result for cliques in the Brownian cographon follows from the same tree construction.\n\nWhat is actually new: the proof establishes existence of the exponent via supermultiplicativity, proves regular variation of the tail and point probabilities q and Q, and then extracts the Gamma-function equation by comparing the recursion with test sequences. The argument is long but unusually transparent about its structure. The auxiliary lemmas are stated explicitly, the diagram in Section 2 is helpful, and the final formula is determined analytically, not fitted. Overlaps with prior work by the same authors are used only as external bounds, not as the target conclusion; I saw no citation red flags.\n\nThe soft spot, at least in the text we have, is at the very end. The almost-sure convergence in Theorem 2.3 depends on Lemma 9.2, which controls the sum of the remainder terms |R_n|. The lemma is stated, and the text says it follows from Lemmas 9.3–9.6, but the provided manuscript stops mid-sentence in Section 9.3 before any of those lemmas or proofs appear. That is a real gap in what we can verify. Everything through Section 8 establishes the exponent and convergence in probability, but the a.s. scaling limit claim is not demonstrated in the available text. This might be an artifact of a truncated arXiv file, but a referee needs the complete manuscript to check the remainder argument.\n\nThe paper is for probabilists working on random permutations, permutons, and branching structures; the coupling in Section 6 is of independent interest.\n\nMy verdict: send it to peer review. The result is important, the proof up to Section 8 looks sound, and the missing part is localized rather than a refutation. The referee should ask for the full manuscript, then focus on Lemma 9.2 and its four sub-lemmas.\n\nBest,","headline":"Exact exponent for LIS in Brownian separable permutons, with a plausible a.s. scaling limit; the provided text is missing the proof of Lemma 9.2 that underpins the almost-sure step.","tokens_in":77804,"tokens_out":3269,"would_cite":true,"duration_ms":34178,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","05A05","60F15","60J80"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every p in (0,1), the longest increasing subsequence of a permutation sampled from the Brownian separable permuton has an almost-sure scaling law with exponent fixed by a Gamma-function equation, and the rescaled limit is a…","keywords":["longest increasing subsequence","Brownian separable permuton","Brownian cographon","scaling limit","pattern-avoiding permutations","separable permutations","largest positive subtree","regular variation"],"falsifier":"Run the recursion (2.8) at $p=1/2$ with $q(1)=(1+\\sqrt{p})^{-1}$, compute $q(k)$ for $k$ up to $10^6$, and estimate the local exponent $-\\log q(k)/\\log k$; if it does not approach $\\gamma=1+1/(2\\alpha(1/2))\\approx 1.6134$, the exponent identification in Theorem 2.2 fails. In parallel, simulate the coupled trees up to size $10^7$ and check that $n^{-\\alpha(1/2)}\\operatorname{LIS}(T_n)$ remains bounded away from $0$ and $\\infty$ and that repeated independent simulations of the limit do not all produce the same constant.","tokens_in":76756,"feed_emoji":"📈","tokens_out":14381,"duration_ms":134902,"temperature":0.7,"pith_summary":"The paper answers a long-open question: how long is the longest increasing subsequence of a typical permutation drawn from the Brownian separable permuton, the universal limit of pattern-avoiding permutations? It proves that the length $\\operatorname{LIS}(\\sigma_n)$ has an exact almost-sure power law $n^{\\alpha(p)}$, with the exponent $\\alpha(p)$ determined explicitly by a Gamma-function equation, and that the rescaled length converges to a non-deterministic random variable $X(p)$ that is a function of the limiting permuton itself. The same result applies to the largest clique of the Brownian cographon, since both problems reduce to the same optimization problem on a random signed tree. Previous results only sandwiched $\\operatorname{LIS}(\\sigma_n)$ between $n^{\\alpha_*(p)-\\varepsilon}$ and $n^{\\beta_*(p)+\\varepsilon}$ with different upper and lower exponents, so even the existence of a single exponent was open. A key feature is that the fluctuations survive: the limit $X(p)$ is not a constant.","feed_headline":"Found: exact LIS exponent for Brownian separable permutons","feed_subtitle":"For every p the limit is a genuine random variable, so fluctuations survive at scale n^α.","key_machinery":"The central object is the pair of sequences $q(k)=\\mathbb{P}(\\operatorname{LIS}(T)=k)$ and $Q(k)=\\mathbb{P}(\\operatorname{LIS}(T)\\ge k)$, where $T$ is the $p$-signed critical binary branching tree; these sequences satisfy an exact recursive relation obtained by splitting $T$ at the root according to the root sign and the LIS values of the two subtrees. The recursion determines $q$, but is too sensitive to initial conditions to read the exponent off directly. The argument therefore studies the conditioned tree $T_k$ with $\\operatorname{LIS}(T)=k$, and a decreasing Markov chain that records, along the spine from the root to a uniformly chosen leaf of the leftmost maximal positive subtree, the size of the distinguished subtree and the sizes of the sibling subtrees. A black-and-golden coupling built from the transition probabilities shows that chains started at large $k$ and $k'$ merge quickly; from this local convergence one obtains $$\\frac{\\#L_{\\max}^{\\cap}(T_k)}{k} \\xrightarrow[k\\to\\infty]{\\mathbb{P}} \\$\\lambda$\\in(0,1),$$ where $L_{\\max}^{\\cap}$ is the set of leaves belonging to all maximal positive subtrees. Re-running the tail estimate with $\\lambda$ in place of the crude bound identifies $\\lambda=\\alpha$, upgrades the tail asymptotics to regular variation $$q(k)=$k^{{-1-1/(2\\alpha)}}$\\varphi(k),\\qquad Q(k)=$k^{{-1/(2\\alpha)}}$\\Phi(k)$$ with slowly varying $\\varphi,\\Phi$, and then a comparison with power-law test sequences in the recursion forces the Gamma equation. The final scaling limit is obtained by writing the rescaled process as a backward martingale plus a remainder that is controlled by the quantitative law of large numbers for $\\#L_{\\max}^{\\cap}$.","core_discovery":"For fixed $p\\in(0,1)$, sample $\\sigma_n$ from the Brownian separable permuton $\\mu_p$ under the natural coupling coming from the growth algorithm on the $p$-signed uniform binary tree $T_n$. The paper's central claim is that, with $\\operatorname{LIS}(T_n)$ denoting the maximal number of leaves of a subtree all of whose internal nodes carry the $\\oplus$ sign, $\\operatorname{LIS}(\\sigma_n)=\\operatorname{LIS}(T_n)$ and $$\\frac{\\operatorname{LIS}(T_n)}{$n^{{\\alpha(p)}}$} \\xrightarrow[n\\to\\infty]{\\mathrm{a.s.}} X(p),$$ where $\\alpha(p)$ is the unique solution in $(1/2,1)$ of the Gamma equation $$\\frac{1}{$4^{{1/(2\\alpha)}}$\\sqrt{\\pi}}\\,\\frac{\\Gamma(1/2-1/(2\\$\\alpha$))}{\\Gamma(1-1/(2\\$\\alpha$))}=\\frac{p}{p-1},$$ and $X(p)$ is almost surely positive and finite, is not deterministic, and is a deterministic measurable function of $\\mu_p$. Because the same tree construction generates the Brownian cographon $W_p$, the identical result holds for the largest clique of a graph sampled from $W_p$, while the largest independent set is governed by $\\alpha(1-p)$. This is an exact almost-sure scaling limit: neither a logarithmic correction nor a range of possible exponents is left open.","pith_inferences":["If the main theorem is correct, the same exponent should govern uniform separable permutations and uniform cographs, with a constant factor of order $0.901$ as the paper conjectures; this would make the Brownian model the exact-exponent representative of the whole universality class.","The proof mechanism suggests a testable general principle: on random recursive trees where a natural exploration along a marked leaf converges locally, the size of the largest almost-monochromatic subtree has an exponent read off from the tail of the subtree-size distribution via a regular-variation index, rather than from the mean-field shape.","The paper's conjectures connecting $\\alpha(p)$ to the Hausdorff dimension of the largest increasing subset of the permuton support and to a directed version of critical Liouville quantum gravity become quantitative predictions that can be checked independently once those objects are constructed.","One could test the robustness of the exponent by perturbing the tree signs to introduce short-range correlations; the method should break exactly where the symmetric region-size independence fails, predicting a different exponent."],"forward_implications":["For every $p\\in(0,1)$, $\\operatorname{LIS}(\\sigma_n)$ grows as $n^{\\alpha(p)}$ almost surely, with no multiplicative logarithmic corrections.","The exponent $\\alpha(p)$ increases continuously from $1/2$ to $1$ as $p$ goes from $0$ to $1$, with $\\alpha(1/2)\\approx 0.815226$ in the separable-permutation case; larger $p$ means more $\\oplus$ nodes and hence longer increasing subsequences.","The same exponent and the same limiting variable govern the largest clique of the Brownian cographon, while the largest independent set is governed by $(\\alpha(1-p),X(1-p))$.","The limiting variable $X(p)$ is a deterministic measurable function of the Brownian separable permuton, so the whole sequence of longest increasing subsequence lengths is coupled to a single continuum object.","The leftmost maximal positive subtree of the conditioned tree $T_k$, rescaled by $\\varphi(k)/k^{\\gamma-1}$, converges in the Gromov-Hausdorff sense to a self-similar fragmentation tree."],"supporting_citations":[{"why":"Supplies the prior polynomial upper and lower bounds that put the exponent in $(1/2,1)$ and states the conjecture this paper solves.","marker":"[BDSG24, Theorem 1.1]"},{"why":"Gives the construction of $\\sigma_n$ from a $p$-signed tree and the consistency property identifying $\\operatorname{LIS}(\\sigma_n)$ with the largest positive subtree.","marker":"[BBF+20]"},{"why":"Provides the superbranching-process theorem adapted into the supermultiplicativity equation used to prove existence of the exponent.","marker":"[DG88, Theorem 1]"},{"why":"Supplies the standard tree-decomposition facts behind Lemma 3.8, the exact symmetric law of the region sizes around selected leaves.","marker":"[Pit06, Exercises 2.2.2 and 7.4.13]"},{"why":"Introduces the growth and removal coupling algorithm on which all almost-sure, stopping-time and backward-martingale arguments are built.","marker":"[Rém85]"},{"why":"Gives the regular-variation characterization used to convert ratio limits into slowly varying representations of $q$ and $Q$.","marker":"[BGT89, Theorem 1.4.1]"},{"why":"Defines the Brownian cographon and its tree construction, which extends the main theorem to largest cliques and independent sets.","marker":"[BBF+22a]"}],"fun_headline_variants":["LIS exponent pinned down for Brownian separable permutons","Random limit for LIS of Brownian separable permutons at n^alpha","For every p, LIS of Brownian separable permutons has a.s. limit","Brownian separable permutons: LIS scaling exponent solved exactly","No log corrections: LIS of Brownian separable permutons has exact exponent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole derivation rests on one exact combinatorial decomposition: after picking $m$ uniform leaves of the random tree, the sizes of the leftover regions around those leaves have a symmetric joint law with all parameters $1/2$ and are independent of the reduced tree; if that were not exact, the exponent could not be pinned to the Gamma equation.","fun_headline_variants_meta":{"raw":{"variants":["LIS exponent pinned down for Brownian separable permutons","Random limit for LIS of Brownian separable permutons at n^alpha","For every p, LIS of Brownian separable permutons has a.s. limit","Brownian separable permutons: LIS scaling exponent solved exactly","No log corrections: LIS of Brownian separable permutons has exact exponent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00088,"raw_usage":{"total_tokens":3903,"prompt_tokens":1144,"completion_tokens":2759,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":760,"completion_tokens_details":{"reasoning_tokens":2658}},"tokens_in":760,"tokens_out":2759,"duration_ms":17165,"temperature":1.0,"reasoning_tokens":2658,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:36:36.559510+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the recursion (2.8) at $p=1/2$ with $q(1)=(1+\\sqrt{p})^{-1}$, compute $q(k)$ for $k$ up to $10^6$, and estimate the local exponent $-\\log q(k)/\\log k$; if it does not approach $\\gamma=1+1/(2\\alpha(1/2))\\approx 1.6134$, the exponent identification in Theorem 2.2 fails. In parallel, simulate the coupled trees up to size $10^7$ and check that $n^{-\\alpha(1/2)}\\operatorname{LIS}(T_n)$ remains bounded away from $0$ and $\\infty$ and that repeated independent simulations of the limit do not all produce the same constant.","supporting_citations":[],"review_version":2}