{"id":"d6c7f115-7fc2-4630-8d07-1b84b98cff7a","arxiv_id":"2504.19167","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Split comparability graphs are exactly the split graphs whose clique can be labeled so that each independent-set vertex sees a prefix, a suffix, or a two-ended interval, and every such graph has permutation-representation number at most three.","lead":"This paper proves that every split comparability graph, a graph split into a fully connected part and an independent part, can be represented by a word built from three permutations. It also gives a labeling rule that identifies exactly when three permutations are necessary, providing an alternative proof of a known bound on the dimension of split orders.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof that Rp(G) <= 3 defers all A1 cases to an unpublished companion preprint; until that transfer is verified, the main theorem rests on an uncheckable dependency.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing concern. I examined the internal argument of Theorem 5 and the non-A1 cases of Lemmas 3-5; they are coherent, and the B4 characterization in Theorem 6 is sound once the upper bound Rp(G) <= 3 is available, since it follows from published forbidden-subgraph characterizations [1,3]. The single fragile point is the transfer of the A1 cases from the unpublished companion preprint [2]. I have no independent reason to believe the transfer is false, but the paper does not provide enough information to verify it: Remark 3 asserts equality of the relevant constructions, and the proofs simply defer to [2] without reproducing the needed steps. There is also a minor algorithmic ambiguity about coincident m_a or n_a values that the deferred proof would need to settle. For these reasons the conditional status is appropriate, and no change to the reader's verdict is needed. A direct re-derivation of the A1 cases, or a brute-force verification of Algorithm 1 on all small split comparability graphs, would resolve the concern.","tokens_in":8795,"tokens_out":12360,"duration_ms":123255,"concrete_test":"Extract from arXiv:2502.00872 the proofs of the A-case lemmas and re-verify them for A1 under the transitive orientation of Theorem 5, specifically testing the tie case where two A1 vertices satisfy m_a = m_b and Algorithm 1's insertion order is unspecified: compute z restricted to {a,b} for both possible processing orders and confirm the projection is not alternating in either order. Then repeat this re-derivation for the A1 cases of Lemmas 3 and 5. If any of these cases produces an alternating projection, or uses a fact from [2] that depends on its semi-transitive rather than transitive orientation, the transfer in Remark 3 fails and the proof of Rp(G) <= 3 is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4's correctness argument for Algorithm 1 is not self-contained. Lemmas 3, 4, and 5 each cover the case where the independent vertex lies in A1 only by invoking Remark 3 and 'Case 1' of the corresponding lemma in the same authors' companion preprint [2] (arXiv:2502.00872). Since A1 is one of the three classes in the partition I = A1 union A2 union A3 from Theorem 5, every edge and non-edge incident with an A1 vertex is justified by this deferred argument: alternation for adjacent C-A1 pairs (Lemma 3), non-alternation for A1-A1 pairs (Lemma 4), and non-alternation for non-adjacent C-A1 pairs (Lemma 5). Remark 3 asserts that the set A of [2] is identical to A1 and that the insertion lines for A in [2, Algorithm 1] are the same as those for A1 here, but [2] is unpublished and is not reproduced. If the orientation or the definition of A in [2] differs from the transitive orientation and labeling used here in any relevant way, the proof of Rp(G) <= 3 is unsupported for a whole class of vertices; the theorem could still be true through a different construction. The converse part of Theorem 6 and the B4 characterization are not the weak point: they follow from published results [1,3] once the upper bound is established. A further internal wrinkle is that Algorithm 1 leaves the iteration order of 'for a in I' unspecified, which matters when two A1 vertices share the same m_a or n_a; the deferred proof from [2] must cover these tie cases, but the present text does not address them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies split comparability graphs, i.e., split graphs that admit a transitive orientation. Its main results are (1) a characterization of split comparability graphs in terms of a labeling of the clique vertices (Theorem 5), and (2) an algorithmic proof that every split comparability graph has permutation-representation number at most three (Theorem 6), with equality three exactly when the graph contains B4 as an induced subgraph. The algorithm constructs a word that is a concatenation of three permutations, each a permutation on the vertex set, and the proof of correctness is organized into Lemmas 3-5 establishing alternation and non-alternation properties. The paper also derives, via a known equivalence between permutation-representation number and poset dimension, an alternative proof that split orders have dimension at most three (Corollary 1).","tokens_in":9190,"tokens_out":7207,"duration_ms":69475,"significance":"If the proof can be made fully self-contained, the paper gives a clean labeling characterization of split comparability graphs and a constructive upper bound of three on their permutation-representation number, together with an exact characterization of when the bound is attained. The constructive algorithm is concrete and the converse direction of Theorem 6 rests on established published results. The main caveat is that the correctness proof for a whole class of independent vertices, A1, is deferred to an unpublished companion preprint by the same authors; until that transfer is verified, the central upper-bound claim is not checkable from the manuscript alone.","major_comments":[{"comment":"The proof that vertices in A1 have the required alternation behavior is not contained in this paper. For adjacent C-A1 pairs, non-adjacent C-A1 pairs, and A1-A1 pairs, the proof simply invokes Remark 3 and 'Case 1' of the corresponding lemma in the same authors' unpublished preprint [2]. Because A1 is one of the three classes in the partition I = A1 ∪ A2 ∪ A3, every edge and non-edge incident with an A1 vertex is justified only by this external reference. This is load-bearing for Theorem 6: without a verified proof of these cases, the claim Rp(G) ≤ 3 is unsupported for graphs with nonempty A1. The authors should either include the missing arguments in the present manuscript or provide a verifiable source (e.g., a published version of [2] or a machine-checked proof) for the claimed alternation behavior of A1 vertices in this exact construction.","section":"Section 4, Lemma 3 Case 1, Lemma 4 Case 1, Lemma 5 Case 1, and Remark 3"},{"comment":"The loop 'for a ∈ I do' does not specify the order in which the vertices of I are processed. This matters because the algorithm replaces occurrences of labels in q1 and q2, and if two vertices share the same m_a, n_a, r_a, or l_a, the resulting word depends on the iteration order. No tie-breaking rule is given, and no order-independence claim is proved. The companion proof from [2] must cover such tie cases, but the present text does not state how they are resolved, so Algorithm 1 as written is not fully deterministic and the correctness of Lemmas 3-5 cannot be checked without additional information.","section":"Algorithm 1, line 3"},{"comment":"In the proof of transitivity, when both a and c belong to C, the paper rules out the resulting directed cycle by saying 'in view of Theorem 4, D is indeed a semi-transitive orientation and thus, D is acyclic.' As stated, Theorem 4 is an existence characterization of semi-transitive orientability via a labeling, not a statement about the particular orientation D defined in the proof. If acyclicity of D is needed for the argument, it should be verified directly for the three types A1, A2, A3, or the authors should cite a specific result that applies exactly to the constructed orientation D rather than to the existence of some semi-transitive orientation.","section":"Section 3, proof of Theorem 5"}],"minor_comments":[{"comment":"In the sentence 'In [10], It was proved that...', the word 'It' should not be capitalized.","section":"Section 1, paragraph 1"},{"comment":"The notation [a, b] is defined only after Theorem 4 is stated, but Theorem 4 already uses brackets such as [1, m]; the definition should be given before the first use.","section":"Section 1, paragraph after Theorem 4"},{"comment":"The sentence 'If B4 is an induced subgraph of G, then clearly Rp(G) = 3' could be expanded to make the monotonicity argument explicit: Rp is monotone under induced subgraphs, and since Rp(B4) = 3 and Rp(G) ≤ 3, equality follows.","section":"Theorem 6, proof"},{"comment":"The abbreviation prn is used before it is formally defined; the definition 'permutation-representation number (in short, prn)' appears only in a later parenthetical, so it would be clearer to introduce the abbreviation at first mention.","section":"General notation"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a serious self-citation issue: the correctness of the central upper-bound theorem depends on an unpublished companion preprint by the same authors, and the dependency is not merely cosmetic. I would not recommend rejection if the authors can complete the proof by including the A1 cases or by making [2] available in a verifiable form. The Algorithm 1 tie-order issue should also be fixed, as it affects reproducibility of the construction. The rest of the paper appears sound and the converse of Theorem 6 is well supported by existing results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a decent, honest subfield paper. The genuinely new content is the labeling characterization in Theorem 5 and the equality certificate in Theorem 6 saying Rp(G)=3 exactly when B4 appears as an induced subgraph. The headline bound Rp(G)<=3 is not new: via the prn/dimension equivalence from [13], it is the known result that split orders have dimension at most three. What the paper adds is a direct word construction and a concrete equality statement, so the contribution is modest but real.\n\nThe paper does some things well. Theorem 5 is self-contained, and I checked the converse direction: the orientation D is built by explicit cases, and the claims that no A3/A2/A1 vertex can appear as left or right endpoint of a nontransitive triple are internally consistent. Lemma 2 is a neat use of transitivity. The proof of the B4 half of Theorem 6 is short and follows from known split permutation graph results once the upper bound is in place. Algorithm 1 is concrete enough to implement.\n\nThe soft spots are real. First and largest: the A1 cases of Lemmas 3, 4, and 5 are not proved in this paper. Remark 3 asserts that the set A in the companion preprint [2] is identical to A1 and the insertion rules are the same, but [2] is unpublished and the reviewer cannot check that identity. Since every edge and non-edge involving an A1 vertex is justified by that transfer, the correctness proof of the word construction is not self-contained. That is a genuine refereeing problem, not a style complaint. Second, Algorithm 1 does not specify the iteration order for 'for a in I'. If two A1 vertices have the same m_a or n_a, the order changes placements, and this paper does not discuss those tie cases; the deferred argument from [2] would have to cover them. Third, [2] and [13] are both self-citations to preprints. That does not make them wrong, but it does mean an editor should ask for those dependencies to be made available or fully incorporated.\n\nOverall, I agree with the conditional verdict. The theorem probably holds—it matches the known dimension result—and the new characterization is useful for people working on word-representable graphs and prn. I would send this to peer review with a request that the A1 argument be made checkable. If I needed the B4 characterization, I would cite it.","headline":"Useful labeling characterization and B4 equality result, but the main upper bound's proof defers all A1 cases to an unpublished companion preprint; worth reviewing with that condition attached.","tokens_in":9669,"tokens_out":3586,"would_cite":true,"duration_ms":38093,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C75","06A07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Three permutations represent every split comparability graph","keywords":["split graphs","comparability graphs","word-representable graphs","permutation-representation number","transitive orientation","split orders","poset dimension"],"falsifier":"Run Algorithm 1 on a split comparability graph whose clique labels make some independent vertex adjacent to both the first few and last few clique vertices, and inspect the restricted word for that vertex together with each clique vertex: a single adjacent pair that fails to alternate, or a non-adjacent pair that alternates, would refute the companion step on which Lemmas 3--5 rely.","tokens_in":8616,"feed_emoji":"🔀","tokens_out":8808,"duration_ms":80494,"temperature":0.7,"pith_summary":"This paper establishes a vertex-labelling characterization of split comparability graphs and uses it to show that every such graph is encoded by a word that is the concatenation of three permutations, with each vertex appearing once in each permutation. In the labelling, the clique vertices are ordered 1 to k, and every independent vertex has one of three neighbourhood shapes: a prefix of the clique, a suffix of the clique, or two separated end-blocks. From this labelling, an explicit algorithm builds the three-permutation word, so the permutation-representation number of every split comparability graph is at most 3. The number is exactly 3 precisely when the graph contains the small forbidden induced subgraph B4. Since the permutation-representation number of a comparability graph equals the dimension of its induced poset, the paper re-derives the known order-theory fact that every split order has dimension at most 3, with the bound tight.","feed_headline":"Three permutations represent every split comparability graph","feed_subtitle":"A vertex-labelling rule builds the word; four permutations appear exactly when the forbidden graph B4 is present.","key_machinery":"The load-bearing object is the labelling of the clique $C$ by $1, \\ldots, k$, which divides the independent set into three classes: $A_1$ with neighbourhood $[1,m] \\cup [n,k]$, $A_2$ with neighbourhood $[1,r]$, and $A_3$ with neighbourhood $[l,k]$. Algorithm 1 uses this labelling to insert each independent vertex into three initially identical permutations $12\\cdots k$, choosing insertion positions so that alternation in the final word $q_1q_2q_3$ matches adjacency exactly. The four inequalities of Theorem 5 enforce the order of those insertions, and the resulting word is 3-uniform, so it is a permutation representation.","core_discovery":"Theorem 5 states that a split graph $G = (I \\cup C, E)$ is transitively orientable if and only if its clique vertices can be labelled $1, \\ldots, k$ so that independent vertices have neighbourhoods of one of three forms, $[1,m] \\cup [n,k]$, $[1,r]$, or $[l,k]$, and the cross-inequalities (ii)--(v) hold. Using that labelling, Algorithm 1 constructs three permutations $q_1, q_2, q_3$ on $V$ and returns the word $q_1q_2q_3$, which is 3-uniform and is proved to represent $G$. Theorem 6 then asserts that $R_p(G) \\le 3$, with equality if and only if $G$ contains $B_4$ as an induced subgraph. Corollary 1 restates this as: every split order has dimension at most 3, and the bound is tight.","pith_inferences":["If the companion construction is supplied self-contained, the same labelling likely yields a linear-time construction of the three-permutation word, because each vertex is inserted at a fixed position determined by its neighbourhood endpoints.","The $B_4$ dichotomy gives a finite forbidden-subgraph test for whether a split comparability graph is a permutation graph: checking for induced $B_4$ would decide $R_p = 3$ versus $R_p \\le 2$.","Because $R_p$ equals poset dimension for comparability graphs, the three-permutation bound might transfer to other hereditary graph classes whose transitive orientations can be normalized so that every vertex's neighbourhood is a union of at most two intervals on a fixed ordering."],"forward_implications":["For every split comparability graph, $R_p(G) \\le 3$; the constructed word is 3-uniform and permutationally represents the graph.","A split comparability graph with no induced $B_4$ is a permutation graph, so $R_p(G) \\le 2$; the bound 3 is forced exactly by $B_4$.","The dimension of every induced poset of a split comparability graph is at most 3, and the bound is tight, giving an alternative proof of the split-order dimension theorem.","The labelling of Theorem 5 turns transitivity into four inequalities on neighbourhoods, so the three-permutation word can be read off directly from the clique labelling rather than from an arbitrary transitive orientation."],"supporting_citations":[{"why":"Supplies the forbidden-subgraph characterization of split permutation graphs, used to show that $R_p = 3$ forces $B_4$.","marker":"[1]"},{"why":"Carries the proof that the insertion of $A_1$ vertices makes adjacent pairs alternate and non-adjacent pairs non-alternate; the paper's Lemmas 3--5 defer to it.","marker":"[2]"},{"why":"Gives the characterization of split comparability graphs as those avoiding $B_1, B_2, B_3$, used to identify $B_4$ as the only comparability graph in the family.","marker":"[4]"},{"why":"Provides the split-order concept and the theorem that split orders have dimension at most three, which Corollary 1 re-proves.","marker":"[5]"},{"why":"Supplies the semi-transitive orientation structure and the labelling theorem for split graphs on which Lemma 1 and Theorem 5 build.","marker":"[8]"},{"why":"Contributes the semi-transitive orientability characterization of split graphs cited as part of Theorem 4's origin.","marker":"[11]"},{"why":"Establishes that permutationally representable graphs are exactly comparability graphs, the foundational equivalence for the permutation-representation number.","marker":"[12]"},{"why":"Relates the permutation-representation number of a comparability graph to the dimension of its induced poset, giving Corollary 1.","marker":"[13]"}],"fun_headline_variants":["Three permutations: the max for split comparability graphs","All split comparability graphs use at most three permutations","Split comparability graphs decoded by three permutations","Three permutations enough for any split comparability graph","Dimension of split orders ≤3 via three permutations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction's correctness for independent vertices whose neighbourhood consists of two separated blocks of the clique is not proved in this paper; it rests entirely on an unpublished companion paper, so if that companion step fails, the bound $R_p(G) \\le 3$ is unproved for those vertices.","fun_headline_variants_meta":{"raw":{"variants":["Three permutations: the max for split comparability graphs","All split comparability graphs use at most three permutations","Split comparability graphs decoded by three permutations","Three permutations enough for any split comparability graph","Dimension of split orders ≤3 via three permutations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000493,"raw_usage":{"total_tokens":2355,"prompt_tokens":814,"completion_tokens":1541,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":1469}},"tokens_in":430,"tokens_out":1541,"duration_ms":11292,"temperature":1.0,"reasoning_tokens":1469,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:59:53.407016+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a split comparability graph whose clique labels make some independent vertex adjacent to both the first few and last few clique vertices, and inspect the restricted word for that vertex together with each clique vertex: a single adjacent pair that fails to alternate, or a non-adjacent pair that alternates, would refute the companion step on which Lemmas 3--5 rely.","supporting_citations":[{"cited_title":"Bonomo-Braberman, G","cited_arxiv_id":null,"evidence_quote":"Supplies the forbidden-subgraph characterization of split permutation graphs, used to show that $R_p = 3$ forces $B_4$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the characterization of split comparability graphs as those avoiding $B_1, B_2, B_3$, used to identify $B_4$ as the only comparability graph in the family."},{"cited_title":"Kitaev, Y","cited_arxiv_id":null,"evidence_quote":"Supplies the semi-transitive orientation structure and the labelling theorem for split graphs on which Lemma 1 and Theorem 5 build."}],"review_version":1}