On the Conjecture of the Representation Number of Bipartite Graphs

Khyodeno Mozhui; K. V. Krishna

REVIEW 3 major objections 4 minor 10 references

On the Conjecture of the Representation Number of Bipartite Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that every bipartite graph is (1+ceil(m/2))-representable, that the bound improves to ceil(m/2) when the smaller partite set has odd size, and that the standing representation-number conjecture therefore holds for all…

desk verdict The general 1+ceil(m/2) bound is a real new result, but Theorem 3's ordering rule for B-vertices is inconsistent, so the odd-m improvement and the conjecture check for odd partite sets don't hold as written. read the letter →

arxiv 2506.01057 v1 pith:Q6FODKTP submitted 2025-06-01 math.CO cs.DM

Khyodeno Mozhui , K. V. Krishna This is my paper

classification math.COcs.DM MSC 05C6205C75

keywords word-representablegraphsrepresentationnumberbipartiteuniformwordneighborhoodinclusiongraphcrownrepresentation-numberconjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A graph is word-representable when a word over its vertices can encode adjacency by alternation: two letters alternate in the word exactly when the corresponding vertices share an edge. The paper tries to bound the representation number—the least number of times each vertex must be repeated in such a word—for every bipartite graph. It constructs, explicitly, a word that represents any bipartite graph with smaller partite set of size $m$ using at most $1+\lceil m/2\rceil$ repeats per vertex, and shows that when $m$ is odd this can be reduced to $\lceil m/2\rceil$. These bounds are enough to prove the standing conjecture that the representation number is at most $\lceil (m+n)/4\rceil$ for all bipartite graphs with partite sizes $m\le n$, leaving only the case where the two partite sets have equal even size; several subclasses of that remaining case are settled through neighborhood inclusion posets.

What carries the argument

The load-bearing object is the explicit uniform word $w = w_{(1,2)}D_{(1:4)}w_{(3,4)}D_{(3:6)}\cdots w_{(m-1,m)}D_{(m-1:2)}w_0$. For each pair $(a_{2s-1},a_{2s})$ of the smaller partite set, the pair-word $w_{(2s-1,2s)}$ places vertices of $B$ in blocks according to whether they are non-neighbors, private neighbors, or common neighbors of the two $A$-vertices, so that inside one pair-word every $A$-$B$ edge alternates. The $D_{(p:q)}$ words move $A$-vertices from pair to pair, letting each $A$-vertex meet the $B$-vertices it needs across the whole word, and $w_0$ forces any two $B$-vertices to fail alternation by reversing the $B$-order of the first pair-word. The odd-$m$ improvement changes the internal ordering of the $B$-blocks so that this $B$-versus-$B$ failure is already forced by the pair-words, allowing $w_0$ to be dropped. For the equal-even cases, the machinery is the neighborhood-inclusion poset $P_A$, ordered by $N(a)\subseteq N(b)$; a chain of length three, or two disjoint comparable pairs, lets one pair-word hold three $A$-vertices and reduces the word to $k$ repeats per vertex when $m=2k$.

What would settle it

Enumerate all reduced connected bipartite graphs with $|A|=5$ and $|B|=5$ (or slightly larger odd $m$), build the word of Section 3 with the prescribed ordering of $B$, and test whether the word with $w_0$ deleted still makes every non-adjacent pair fail to alternate; a single non-adjacent pair that alternates in the shortened word would refute Theorem 3 and with it the odd-$m$ improvement.

Watch

Extended reading notes

Core claim

Every reduced connected bipartite graph $G=(A\cup B,E)$ with $|A|=m\le n$ is $\left(1+\lceil m/2\rceil\right)$-representable. The construction partitions $A$ into pairs, builds a pair-word $w_{(i,j)}$ for each pair whose separate blocks carry the non-neighbors, the private neighbors of each member, and the common neighbors in $B$, then inserts the interleaving words $D_{(p:q)}$ and a final word $w_0$ that reverses the $B$-order of the first pair-word. For odd $m\ge 5$, the construction orders the vertices of $B$ inside every block according to their order in $w_{(1,2)}$ and then deletes the final $w_0$, yielding a $\lceil m/2\rceil$-uniform representant. For the remaining equal-even case, the paper proves representability with $m/2$ repeats per vertex when the neighborhood-inclusion poset on the smaller part contains a chain of three vertices, or two disjoint chains of two vertices, by folding three $A$-vertices into one pair-word. The consequence is that the conjectured bound $\lceil (m+n)/4\rceil$ holds for every bipartite graph except those with partite sets of equal even size, and for several of those as well.

Load-bearing premise

The odd-$m$ improvement depends on the unproved assertion that the final block $w_0$ can be deleted: the ordering rules for the $B$-vertices inside the pair-blocks are assumed to be globally consistent, and $w_0$ is assumed to play no role in keeping non-adjacent pairs non-alternating for $m>4$; if either fails, the sharpened bound collapses.

Editorial extensions

If this is right

Every bipartite graph has an explicit uniform word-representant whose length per vertex is controlled by the smaller partite set, not by the total number of vertices.
The representation-number conjecture holds for all bipartite graphs with $n\ge m+3$, for all with even $m$ and $n=m+1$ or $m+2$, and for all with odd $m\ge 5$.
When the smaller part has odd size, the bound $\lceil m/2\rceil$ equals the conjectured value $\lceil (m+n)/4\rceil$ for $n\in\{m,m+1,m+2\}$, so the conjecture is verified in those ranges.
For bipartite graphs with equal even partite sets whose smaller part has a neighborhood-inclusion chain of length at least three, or two disjoint comparable pairs, the conjectured bound is also verified.
The odd-$m$ bound yields a partial verification of the companion conjecture that crown graphs are extremal among bipartite graphs on an odd number of vertices in the smaller part.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct extension: if the deletion of $w_0$ in the odd-$m$ argument can be justified in full generality, the open case collapses to equal even partite sets, and the crown-graph extremality conjecture would follow for all equal-size cases once the even case is handled.
A testable strengthening suggested by the paper's approach: try all chain covers of the smaller partite set and check whether the associated explicit word has the alternation property; success for every chain cover would close the remaining class.
Because the construction is explicit rather than existential, it yields a polynomial-time procedure that outputs a uniform representant for any bipartite graph, even though computing the exact representation number is NP-hard in general.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper has two distinct parts. Section 2 proves R(G) ≤ 1+ceil(m/2) for every bipartite graph with smaller part size m, via an explicit word construction. That is a genuine new general bound, and the worked example in the appendix helps. The neighborhood inclusion graph approach in Section 4 is also fresh, and it gives subclasses of the equal-even case where the conjecture holds. Those parts are worth reading and likely correct.

The problem is Theorem 3. The proof claims to improve the bound to ceil(m/2) for odd m by constructing a word from the Section 2 word minus the final block w0. The construction depends on an ordering rule for vertices of B that share a block of w(1,2): their relative order is governed by their positions in other pair-words, while for i>1 the order in w(i,i+1) is governed by w(1,2). This is circular, and no consistency proof is given. It is not just missing justification; the rule is actually inconsistent. Take m=5, add isolated a6, and set N(b1)={a4,a5}, N(b2)={a3}, N(b3)={a5}, N(b4)={a1,a3}, N(b5)={a2}, N(b6)={a1,a4}. Following steps 1–3, b1, b2, b3 all land in B*_1 of w(1,2). The pair-words then force b1 before b2, b2 before b3, and b3 before b1 in that same block, a 3-cycle. So the word w(1,2) cannot be constructed, and Theorem 3 collapses for such graphs.

The sentence claiming that w0 'does not have any role in the proof of non-adjacency for m>4' is also too quick, but that is secondary. The ordering issue alone is load-bearing: Corollary 2 and the paper's main claim that the Glen et al. conjecture holds for all bipartite graphs except equal-even partite sets rest on Theorem 3. Without it, the conjecture remains open for odd m with n=m, m+1, m+2, exactly the cases the paper claims to close.

This is a solid general-bound paper with a broken stronger claim. The right outcome is peer review, not desk rejection. A referee should ask the authors to repair the ordering rule in Theorem 3 (perhaps by a different placement strategy) or remove the unsupported odd-m results. If the Theorem 3 gap cannot be fixed, the paper should be published only for Section 2 and Section 4, with the conjecture left open.

Referee Report

3 major / 4 minor

Summary. The paper studies upper bounds on the representation number R(G) of bipartite graphs. It constructs a (1+ceil(m/2))-uniform word-representant for every connected reduced bipartite graph with smaller partite set size m (Theorem 1), and then attempts to improve this to ceil(m/2)-uniformity when m is odd (Theorem 3). From these bounds it derives that the Glen et al. conjecture R(G) <= ceil((m+n)/4) holds for all bipartite graphs except those with equal even partite sets, and it gives additional partial results for equal-even cases via neighborhood inclusion posets (Theorems 4 and 5).

Significance. If the main bounds were correct, the paper would settle the Glen et al. conjecture for a large family of bipartite graphs and would substantially advance the representation-number theory of this class. The construction in Theorem 1 is self-contained, uses only independent external lemmas (reduced graph equivalence and the crown-graph bound), and is illustrated with a worked example; those parts are a genuine contribution. However, the construction in Theorem 3 is not well-defined (see Major Comment 1), and the announced resolution of the odd-m case is therefore not established. The equal-even partial results in Sections 4 are plausible but rest on proofs that are only described as similar to Theorem 1.

major comments (3)

[Section 3, proof of Theorem 3 (ordering rules for vertices of B)] The two bullet points defining the order inside each block of the pair-words are circular and inconsistent. The first bullet orders a block of w(1,2) by the relative order of the vertices in 'some' w(t,t+1) with t != 1, while the second bullet orders every block of w(t,t+1) for t > 1 by the order in w(1,2); the proof never shows that different w(t,t+1) impose compatible orders on the block of w(1,2). The incompatibility is concrete. Let m=5, A={a1,...,a5}, add an isolated a6, and take B={b1,...,b7} with N(b2)={a3}, N(b3)={a5}, N(b1)={a4,a5}, N(b4)={a1,a3}, N(b5)={a2}, N(b6)={a1,a4}, N(b7)={a2,a4}; this graph is reduced and connected. Following steps 1-3, b2 is placed in B*_1 of w(1,2) and in B'_{*6} of w(5,6), while b3 is placed in B*_1 of w(1,2) and in B'_{*4} of w(3,4). In w(3,4), b2 lies in B_3 and b3 in B'_{*4}, so b2 precedes b3; in w(5,6), b3 lies in B_5 and b2 in B'_{*6}, so b3 precedes b2. The first ordering rule therefore demands both b3 < b2 and b2 < b3 inside the same block B*_1 of w(1,2), so the construction does not produce a well-defined word for a graph satisfying the theorem's hypotheses. Consequently, the Claim in the proof of Theorem 3 is unsupported.
[Section 3, first paragraph after the definition of w1] The assertion that 'if any two vertices are adjacent in G ∪ {a_{m+1}} then they alternate in w and hence they also alternate in w1' is not justified as stated. Removing a suffix from an alternating word can destroy alternation in general; the proof must show that the explicit alternating subword constructed in Theorem 1 remains a subword of w1 after the occurrences of a and b in w0 are deleted. In particular, the final a^{(k)}b^{(k)} pair used in the adjacency part of Theorem 1 is supplied by w0, and the manuscript does not prove that the prefix w1 still contains a(1)b(1)...a^{(k)}b^{(k)} with k = ceil(m/2). This gap is repairable, but it is load-bearing for the reduction from the (1+ceil(m/2))-uniform word to the ceil(m/2)-uniform word.
[Section 3, Claim in the proof of Theorem 3] The Claim states that for any two non-adjacent vertices a,b in B there exist two pair-words with opposite orders ab and ba. The proof of this Claim relies on the block-ordering rules that are shown in Major Comment 1 to be inconsistent. Moreover, the proof leaves a case unresolved: if two B-vertices are never placed in different blocks of any pair-word, the ordering rule falls back to an arbitrary default, and no argument is given that the opposite-order pair of words still exists. Thus the non-alternation of non-adjacent B-vertices in w1 is not established.

minor comments (4)

[Section 2, Remark 3 and proof of Theorem 1, Case 1] The indexing for a in {a1,a2} at i = m/2 appears to be incorrect: for m=6, the third occurrence of a1 lies in D(3:6), not in D(5:2) as the displayed formula 'D(m-1:2), if i=m/2' would give. Please check and correct the displayed cases in Remark 3 and in the adjacency proof.
[Section 3, ordering rules] The phrase 'if b' occur before b in different blocks of some word w(t,t+1)' is ambiguous when there are several words w(t,t+1) in which the two vertices occur in different blocks; the rule should specify whether it applies to all such words, and in that case a consistency proof is needed.
[Sections 4, Theorems 4 and 5] The proofs of Theorems 4 and 5 say that the argument is 'similar' to the proof of Theorem 1, but the case analyses are lengthy and the constructions are modified in nontrivial ways; please include the full details or state a precise reduction lemma so that the reader can verify that no hidden assumptions on the neighborhood inclusion chains are used.
[Section 3, proof of Theorem 3] The sentence 'w0 does not have any role in the proof of non-adjacency for m>4 in Theorem 1' should be justified explicitly, since the validity of dropping w0 depends on exactly which non-adjacency witnesses in Theorem 1 use w0. In particular, the B-B case does use w0, and this case is handled separately only after the Claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bipartite representation-number bounds are derived from explicit self-contained word constructions, with only peripheral self-citations.

full rationale

The paper's central derivation is self-contained rather than circular. In Section 2, for a bipartite graph G=(A∪B,E) with |A|=m, the authors explicitly construct a (1+ceil(m/2))-uniform word w from the neighborhoods of paired vertices and from defined D(p:q) permutations, then prove in Theorem 1 that adjacency is equivalent to alternation by tracking occurrences of each vertex. Corollary 1 is a direct consequence of this construction, and Theorem 2 is arithmetic comparison with the Glen et al. bound. Theorem 3 modifies the block orderings inside the pair-words, constructs a new word w1 by dropping the final suffix w0, and argues via a claim about pairs of B-vertices; this is an internal proof step, not an input-output circularity. Even if the ordering rule or the w0-dropping argument is flawed, that would be a correctness gap, not a circular reduction. Section 4 builds alternative k-uniform words for equal-even cases using neighborhood-inclusion posets and again proves representability by direct occurrence arguments. The paper does not fit any parameter to a target quantity and then rename it a prediction; the uniform words are constructed, not fitted. The cited external results, such as the reduced-graph equivalence, the existence of k-uniform representants, and the crown graph bound from Glen et al., are independent of the paper's main claims. The self-citations (Refs. [2] and [10]) concern split graphs and melon graphs and are not load-bearing for the bipartite results proved here. No equation in the paper defines a derived quantity in terms of the conjecture itself, and no uniqueness or ansatz is imported from the authors' prior work to force an otherwise underdetermined choice. Accordingly, the paper warrants a circularity score of 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted; the construction is deterministic. The proof relies on standard cited lemmas about reduced graphs, component-wise representation numbers, uniform words, and the crown graph bound, all external to this paper. A temporary isolated vertex a_{m+1} is added when m is odd and removed at the end; it is a proof device, not a new entity with independent evidence.

assumptions (4)

domain assumption The representation number of a disconnected graph equals the maximum of the representation numbers of its connected components.
Invoked in Section 1 to justify restricting attention to connected graphs.
domain assumption The representation number of a bipartite graph equals the representation number of its reduced graph, obtained by keeping only vertices with distinct neighborhoods.
Invoked in Section 1 to assume all vertices have distinct neighborhoods.
domain assumption The crown graph H_{m,m} is ceil(m/2)-representable.
Used in Theorem 3 for the case P2 = empty, citing Glen et al. Theorem 7.
domain assumption Every word-representable graph has a k-uniform word-representant for some k.
Background definition used throughout, citing Kitaev and Pyatkin.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Conjecture of the Representation Number of Bipartite Graphs." pith.science (2026). https://pith.science/paper/Q6FODKTP

@misc{pith2026250601057,
  author       = {Pith},
  title        = {Pith review of: On the Conjecture of the Representation Number of Bipartite Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q6FODKTP}},
  note         = {Machine review of arXiv:2506.01057}
}

abstract

While the problem of determining the representation number of an arbitrary word-representable graph is NP-hard, this problem is open even for bipartite graphs. The representation numbers are known for certain bipartite graphs including all the graphs with at most nine vertices. For bipartite graphs with partite sets of sizes $m$ and $n$, Glen et al. conjectured that the representation number is at most $\lceil \frac{m+n}{4}\rceil$, where $m+n \ge 9$. In this paper, we show that every bipartite graph is $\left( 1+ \lceil \frac{m}{2} \rceil \right)$-representable, where $m$ is the size of its smallest partite set. Furthermore, if $m$ is odd then we prove that the bipartite graphs are $\lceil \frac{m}{2} \rceil $-representable. Accordingly, we establish that the conjecture by Glen et al. holds good for all bipartite graphs leaving the bipartite graphs whose partite sets are of equal and even size. In case of the bipartite graphs with partite sets of equal and even size, we prove the conjecture for certain subclasses using the neighborhood inclusion graph approach.

Figures

Figures reproduced from arXiv: 2506.01057 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 8 canonical work pages

[1]

Akg¨ un, I

O. Akg¨ un, I. Gent, S. Kitaev, and H. Zantema. Solving computational problems in the theory of word-representable graphs.J. Integer Seq., 22(2):Art. 19.2.5, 18, 2019

work page 2019
[2]

Representation Number of Word-Representable Split Graphs

T. Dwary, K. Mozhui, and K. V. Krishna. Representation number of word-representable split graphs. arXiv:2502.00872, 2025

work page Pith review arXiv 2025
[3]

M. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph.Discrete Appl. Math., 244:89–93, 2018. 18

work page 2018
[4]

M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Alternation graphs. InGraph-theoretic concepts in computer science, volume 6986 ofLecture Notes in Comput. Sci., pages 191–202. Springer, Heidelberg, 2011

work page 2011
[5]

Hefty, P

Z. Hefty, P. Horn, C. Muir, and A. Owens. Word-representable graphs: orientations, posets, and bounds. Electron. J. Combin., 31(4):Paper No. 4.2, 26, 2024

work page 2024
[6]

S. Kitaev. On graphs with representation number 3.J. Autom. Lang. Comb., 18(2):97–112, 2013

2013
[7]

Kitaev and V

S. Kitaev and V. Lozin.Words and graphs. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Cham, 2015

work page 2015
[8]

Kitaev and A

S. Kitaev and A. Pyatkin. On representable graphs.J. Autom. Lang. Comb., 13(1):45–54, 2008

2008

Show all 10 references

[9]

Kitaev and S

S. Kitaev and S. Seif. Word problem of the Perkins semigroup via directed acyclic graphs.Order, 25(3):177–194, 2008

2008
[10]

Mozhui and K

K. Mozhui and K. V. Krishna. Word-representation of melon graphs.Communicated, 2024. A Demonstration of Construction given in Section 2 B A b1 b2 b3 b4 b5 b6 a1 a2 a3 a4 a5 Fig. 1.A bipartite graph LetG= (A∪B, E) be the bipartite graph given in Fig. 1. Consider the smaller par...

2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Akg¨ un, I

O. Akg¨ un, I. Gent, S. Kitaev, and H. Zantema. Solving computational problems in the theory of word-representable graphs.J. Integer Seq., 22(2):Art. 19.2.5, 18, 2019

work page 2019

[2] [2]

Representation Number of Word-Representable Split Graphs

T. Dwary, K. Mozhui, and K. V. Krishna. Representation number of word-representable split graphs. arXiv:2502.00872, 2025

work page Pith review arXiv 2025

[3] [3]

M. Glen, S. Kitaev, and A. Pyatkin. On the representation number of a crown graph.Discrete Appl. Math., 244:89–93, 2018. 18

work page 2018

[4] [4]

M. M. Halld´ orsson, S. Kitaev, and A. Pyatkin. Alternation graphs. InGraph-theoretic concepts in computer science, volume 6986 ofLecture Notes in Comput. Sci., pages 191–202. Springer, Heidelberg, 2011

work page 2011

[5] [5]

Hefty, P

Z. Hefty, P. Horn, C. Muir, and A. Owens. Word-representable graphs: orientations, posets, and bounds. Electron. J. Combin., 31(4):Paper No. 4.2, 26, 2024

work page 2024

[6] [6]

S. Kitaev. On graphs with representation number 3.J. Autom. Lang. Comb., 18(2):97–112, 2013

2013

[7] [7]

Kitaev and V

S. Kitaev and V. Lozin.Words and graphs. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Cham, 2015

work page 2015

[8] [8]

Kitaev and A

S. Kitaev and A. Pyatkin. On representable graphs.J. Autom. Lang. Comb., 13(1):45–54, 2008

2008