REVIEW 1 major objections 3 minor 14 references
Property O and Erd\H{o}s--Szekeres properties in linear hypergraphs
T0 review · 1 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read The paper proves that an oriented linear k-uniform hypergraph with Property O needs between roughly (k!)²/k⁴ and roughly (k!)²·k⁶·ln²k edges, and similarly determines the minimum vertex count up to a polynomial factor.
desk verdict Nice first bounds for linear Property O and ES properties; the poly(k) results likely hold, but the upper-bound proof of Theorem 1.5 has a real constant gap that needs fixing before the stated (1+o(1)) constants are taken seriously. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Three tools carry the proofs. (1) The local lemma: for each edge, the event that a random permutation is consistent with it has probability 1/k!, and linearity keeps the dependency graph of these events sparse; the lemma forces the existence of a vertex of degree at least (k−1)!/ek, since otherwise a random ordering would hit no edge. (2) The finite affine space over a field: the upper bound takes the vertex set F_p^d, takes its lines as edges (shrunk to k vertices), orients each independently, and counts edges as (p^d choose 2)/(p choose 2); affine density is what produces the polynomial factors in k. (3) The monotone-subsequence theorem: for the Erdős–Szekeres variants, any two orderings a
What would settle it
Take k large, choose p as the largest prime below 2k, set p^d to the smallest power of p at least 2k³ ln k · k!, and compute (p^d)! · (1 − 1/k!)^{(p^d choose 2)/(p choose 2)}. If the result is at least 1, the union-bound argument behind the upper bound of Theorem 1.5 fails at that parameter, and the stated (1+o(1)) constant would need revision.
Extended reading notes
Core claim
The central claim is that linearity makes Property O much more expensive: the minimum number of edges in a linear oriented k-graph with Property O is (k!)² up to a polynomial factor, whereas the best known bounds for ordinary oriented k-graphs are roughly k!. The lower bound is proved by a local-lemma argument: if every vertex had degree below about (k−1)!/ek, then a random ordering of the vertices would avoid all edges with positive probability, contradicting Property O. Hence every valid construction has a high-degree vertex, and counting incidences across such vertices yields the (k!)² lower bound. The matching upper bound uses the lines of a finite affine space as edges, shrinking each l
Load-bearing premise
The upper bound rests on the unstated estimate that a random orientation of the lines of a finite affine space covers every vertex ordering with high enough probability at the chosen vertex count; in particular, the inequality n ln n < n²/(p² k!) must hold for the affine-space vertex count n = p^d, and since p can be nearly 2k, whether the constant 2 in the stated choice of p^d is enough is not immediate. If this estimate fails, the (1+o(1)) constants in Theorem 1.5 must be e
Editorial extensions
If this is right
- The edge count f'(k) for linear Property O is now known to within a k^{O(1)} factor, and is of order (k!)², roughly the square of the ordinary f(k).
- The vertex count n'(k) is also determined up to a polynomial factor and grows like k!, in contrast to the polynomial n(k) for non-linear hypergraphs.
- Every linear k-graph with Property O must contain a vertex incident to at least (k−1)!/ek edges, a structural consequence of the lower-bound proof.
- If a counterexample to the vertex-ordered Erdős–Hajnal conjecture exists, the linear Property O hypergraphs constructed here convert it into a counterexample to the original unordered conjecture.
- The paper leaves an exp(O(k)) gap for the linear Erdős–Szekeres variants and raises the question whether the strong Erdős–Szekeres edge count can be smaller than the full binomial bound.
Reading between the lines
- Because the upper bound uses an explicit affine geometry, finding an explicit orientation is a finite search problem; a derandomized version could yield deterministic constructions useful for the Erdős–Hajnal transfer.
- The forced high-degree vertex suggests extremal linear constructions must be built around dense stars; deciding how such stars must be oriented relative to one another may be the route to closing the remaining polynomial gap.
- The same local-lemma template may apply to other 'consistent with every ordering' properties, predicting that linearity multiplies the non-linear edge count by an extra k! factor; testing this on the weak and strong Erdős–Szekeres variants would be a natural follow-up.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies oriented linear k-uniform hypergraphs. For linear Property O, it defines f'(k) and n'(k) as the minimum number of edges and vertices, respectively, and proves Theorem 1.5: lower bounds (k!)²/(2e²k⁴) ≤ f'(k) and (k−1)(k−1)!/ek ≤ n'(k), with upper bounds (1+o(1))·4k⁶ln²k·(k!)² and (1+o(1))·4k⁴ln k·k!. The lower bounds are proved via the Lovász Local Lemma by pruning high-degree vertices; the upper bounds use a random orientation of lines in an affine space over F_p. The paper also introduces weak and strong Erdős–Szekeres properties, proves bounds in the linear setting (Theorem 1.9) via an incremental random construction, and gives an improved upper bound for the weak Erdős–Szekeres property in general k-graphs (Theorem 1.8).
Significance. If the results are correct, the paper determines f'(k) and n'(k) up to polynomial factors and exhibits a quadratic blow-up relative to the non-linear Property O function f(k) ≈ k!. The lower-bound argument is clean and the Erdős–Szekeres part (Theorems 1.8 and 1.9) appears carefully argued. The main caveat is the upper-bound proof of Theorem 1.5: it relies on an unshown 'careful estimation' whose stated threshold is not sufficient for primes p near 2k. This is a load-bearing gap for the explicit constants, though the central poly(k) claim may survive after a repair. The introduction's application to the ordered Erdős–Hajnal conjecture is a nice motivational observation.
major comments (1)
- [Section 2, upper bound of Theorem 1.5] The proof contains the sentence 'A careful estimation shows that choosing p^d ≥ (1+o(1))·2k³ln k·k! makes the right-hand side strictly less than 1', but the estimation is not shown. Moreover, the stated threshold appears to be too small. Let N = p^d and m = binom(N,2)/binom(p,2). The failure probability is at most N!(1−1/k!)^m, so its log is approximately N ln N − m/k!. For p = 2k and N = (2+o(1))k³ln k·k!, Stirling gives m/k! ≈ k⁴ln²k·k! while ln N! ≈ 2k⁴ln²k·k!, so the log of the failure probability is positive. Thus the inequality P(fail) < 1 is not established for primes near 2k. The later bounds |V| ≤ p·(1+o(1))·2k³ln k·k! and |E| ≤ binom(N,2)/binom(p,2) also depend on this estimate. A valid proof would need a different choice of p (e.g., p=(1+o(1))k via the prime number theorem) or a larger threshold constant; as written, the explicit constants in Theorem 1.5 are not justified.
minor comments (3)
- [Section 2, lower bound of Theorem 1.5] In the counting argument after defining S′, the text says 'Since H is linear, each edge contains at most one pair of vertices in S′'. This is not literally true: an edge can contain several vertices of S′. The intended and sufficient fact is that each pair of vertices of S′ lies in at most one edge; then the total overcount is at most the number of pairs inside edges, which is at most binom(|S′|,2). The bound is correct, but the wording should be fixed.
- [Tables 1 and 2] The table headers are garbled: 'Results for f ′. (k) and f.(k)' appears to have a typo; the formatting should be cleaned up.
- [Introduction, paragraph after Definition 1.7] The reference 'see how the proof of Theorem 1.2 in [10] uses linear hypergraphs with the weak Erdős–Szekeres property (Lemma 6.3 in the same paper)' is confusing: it cites a theorem number that does not match the reference's content. Please clarify or correct the cross-reference.
Circularity Check
No significant circularity: lower bounds use LLL/counting and upper bounds use random constructions; target functions f'(k), n'(k) are not inputs to any assumption or fit.
full rationale
The derivation chain for Theorem 1.5 is self-contained. The lower bound starts from an arbitrary linear oriented k-graph with Property O and derives |E| >= (k!)²/(2e²k⁴) and |V| >= (k−1)·(k−1)!/ek via the Lovász Local Lemma and a degree-counting argument; none of the asserted bounds is assumed. The upper bound constructs a random orientation of lines in F_p^d and uses a union bound over vertex orderings with edge probability 1/k!; the claimed threshold p^d >= (1+o(1))·2k³ ln k·k! is an estimate in the proof, not a fitted parameter or a restatement of the conclusion. Theorem 1.9 is proved by an incremental random construction and Claim 3.2, again with no parameter fitted to the target value; Theorem 1.8 is a direct counting/Erdős–Szekeres argument. Cited external results (LLL, Erdős–Szekeres theorem, Bertrand's postulate for the prime p) are standard and do not assume Property O. The only self-citations are contextual ([9] contains a coauthor's earlier work on the non-linear case; [10] is mentioned only as an example of an application), and neither is load-bearing for the new theorems. The skeptical concern about the 'careful estimation' in the upper bound of Theorem 1.5 is a possible numerical gap in the proof as written, not a circularity: if the estimate fails, the result would still be a valid bound with adjusted constants, and the target quantities are not built into any assumption. Therefore no circular step is identified.
Assumptions & free parameters
assumptions (4)
- standard math Lovász Local Lemma
- standard math Erdős–Szekeres theorem
- standard math Existence of a prime between k and 2k (Bertrand's postulate)
- standard math Stirling-type asymptotic estimates and union bound
Cite this review
Pith. "Pith review of Property O and Erd\H{o}s--Szekeres properties in linear hypergraphs." pith.science (2026). https://pith.science/paper/G3436RYT
@misc{pith2026250908692,
author = {Pith},
title = {Pith review of: Property O and Erd\Hos--Szekeres properties in linear hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/G3436RYT}},
note = {Machine review of arXiv:2509.08692}
}
abstract
An oriented $k$-uniform hypergraph, or oriented $k$-graph, is said to satisfy Property O if, for every linear ordering of its vertex set, there is some edge oriented consistently with this order. The minimum number $f(k)$ of edges in a $k$-graph with Property O was first studied by Duffus, Kay, and R\"{o}dl, and later improved by Kronenberg, Kusch, Lamaison, Micek, and Tran. In particular, they established the bounds $k! + 1 \le f(k) \le \left(\lfloor\tfrac{k}{2}\rfloor+1 \right) k! - \lfloor\tfrac{k}{2}\rfloor(k-1)!$ for every $k \ge 2$. In this note, we extend the study of Property O to the linear setting. We determine the minimum number $f'(k)$ of edges in a linear $k$-graph up to a $\operatorname{poly}(k)$ multiplicative factor, showing that $\frac{(k!)^2}{2e^2k^4} \le f'(k) \le (1+o(1)) \cdot 4 k^6 \ln^2 k \cdot (k!)^2$. Our approach also yields bounds on the minimum number $n'(k)$ of vertices in an oriented linear $k$-graph with Property O. Additionally, we explore the minimum number of edges and vertices required in a linear $k$-graph satisfying the newly introduced Erd\H{o}s--Szekeres properties.
Reference graph
Works this paper leans on
-
[1]
Alon and J
N. Alon and J. H. Spencer. The probabilistic method. Wiley Series in Discrete Mathematics and Optimiza- tion. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016
2016
-
[2]
J. Beck. On 3-chromatic hypergraphs. Discrete Math., 24(2):127–137, 1978
1978
-
[3]
Bernstein
F. Bernstein. Zur theorie der trigonometrischen reihe. Journal f¨ ur die reine und angewandte Mathematik, 132:270–278, 1907
1907
-
[4]
D. D. Cherkashin and J. Kozik. A note on random greedy coloring of uniform hypergraphs. Random Structures Algorithms, 47(3):407–413, 2015
2015
-
[5]
Duffus, B
D. Duffus, B. Kay, and V. R¨ odl. The minimum number of edges in uniform hypergraphs with property O. Combin. Probab. Comput. , 27(4):531–538, 2018
2018
-
[6]
P. Erd˝ os. On a combinatorial problem. Nordisk Mat. Tidskr. , 11:5–10, 40, 1963
1963
-
[7]
P. Erd˝ os. On a combinatorial problem. II. Acta Math. Acad. Sci. Hungar. , 15:445–447, 1964
1964
-
[8]
Erd˝ os and G
P. Erd˝ os and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463–470, 1935
1935
Show all 14 references
-
[9]
Kronenberg, C
G. Kronenberg, C. Kusch, A. Lamaison, P. Micek, and T. Tran. A note on the minimum number of edges in hypergraphs with property O. European J. Combin., 81:172–177, 2019
2019
- [10]
-
[11]
Radhakrishnan and A
J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures Algorithms, 16(1):4–32, 2000
2000
-
[12]
J. B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241–245, 1985
1985
-
[13]
J. H. Spencer. Asymptotic lower bounds for Ramsey functions. Discrete Math., 20(1):69–76, 1977
1977
-
[14]
J. H. Spencer. Coloring n-sets red and blue. J. Combin. Theory Ser. A , 30(1):112–113, 1981. 10
1981
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.