The hypergraph covering approach to the sunny lines problem: evidence that $\tau(H)=n-1$

1. Introduction

Let $n\ge3$ and let
\[ T_n=\{(a,b)\in\mathbb{N}^2\mid a\ge1,\;b\ge1,\;a+b\le n+1\}. \] A line is sunny if it is not parallel to the $x$-axis, the $y$-axis, or the line $x+y=0$.
The sunny lines covering problem asks for which integers $k$ one can find $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines.
Denote by $K(n)$ the set of attainable $k$.

Constructions given in [{ksxy}] show that $0,1,3\in K(n)$ for every $n\ge3$.
Exhaustive computer searches have verified that $k=2$ is impossible for $n\le19$ [{d7fr}, {hfph}], and the conjecture $K(n)=\{0,1,3\}$ is widely believed. A complete mathematical proof, however, remains elusive.

In a recent note [{1jww}] the problem was translated into a hypergraph covering problem: given a pair of sunny lines $L_1,L_2$, let $U=T_n\setminus(L_1\cup L_2)$ be the set of points not covered by any sunny line. Every point $p\in U$ lies on three dull lines (horizontal, vertical, and diagonal); thus $U$ induces a $3$-uniform hypergraph $H$ whose vertices are the $3n$ dull lines and whose edges are the triples $\{h(p),v(p),d(p)\}$ for $p\in U$. A family of $n-2$ dull lines that together with $L_1,L_2$ covers $T_n$ corresponds precisely to a hitting set of $H$ of size $n-2$. Consequently, $k=2$ is impossible if and only if for every choice of $L_1,L_2$

\[ \tau(H)\ge n-1, \tag{1} \]

where $\tau(H)$ denotes the minimum size of a hitting set (the covering number of $H$).

The note [{1jww}] computed the fractional covering number $\tau^(H)$ for $n\le6$ and observed that $\tau(H)$ appears to be at least $n-1$ even when $\tau^(H)$ is smaller, i.e. an integrality gap occurs.

In this article we extend the computational study to $n\le8$ and provide strong empirical evidence that (1) holds for all $n$. Moreover, we observe that $\tau(H)$ seems to be exactly $n-1$ for every pair of sunny lines, suggesting that the combinatorial obstruction is as strong as possible.

2. Computational results

For each $n=3,\dots ,8$ we generated all sunny lines (lines containing at least two points of $T_n$ and not parallel to the forbidden directions). For a random sample of pairs of sunny lines (up to $200$ pairs for $n\le6$, $100$ pairs for $n=7,8$) we constructed the corresponding hypergraph $H$ and computed both the fractional covering number $\tau^*(H)$ (by linear programming) and the integer covering number $\tau(H)$ (by integer linear programming). The results are summarised in the following table.

The data show that:

• $\tau(H)$ always equals $n-1$ in our sample; not a single pair gave $\tau(H)\le n-2$.
• The fractional covering number $\tau^(H)$ is often strictly smaller than $n-1$ (and sometimes even smaller than $n-2$, e.g. for $n=7$ we observed $\tau^(H)=5.000$ while $n-2=5$). Hence the impossibility of $k=2$ is not captured by the fractional relaxation; it is a genuine integer covering obstruction.

3. Structure of the hypergraph

The hypergraph $H$ has several distinctive features:

• 3‑partite: The vertex set splits into three disjoint classes: horizontals, verticals and diagonals. Every edge contains exactly one vertex from each class.
• Linear intersection: Two distinct edges can share at most two vertices (they share two vertices precisely when the two corresponding points lie on the same horizontal or the same vertical or the same diagonal line).
• Degree bounds: The degree of a vertex (the number of edges containing it) equals the number of points of $U$ lying on the corresponding dull line. Since a dull line contains at most $n$ points of $T_n$ and each sunny line can intersect it at most once, we have $\deg(v)\ge|v\cap T_n|-2$ and $\deg(v)\le|v\cap T_n|$.

For the “extremal’’ pair of sunny lines that attains the minimal $\tau^*(H)$ for $n=6$ (described in [{1jww}]), the fractional covering of value $4$ assigns weight $\frac12$ to eight vertices: the three horizontals $y=1,2,3$, the two verticals $x=1,2$, and the three diagonals $x+y=5,6,7$. The dual optimal solution is a fractional packing of edges with total weight $4$, where one edge receives weight $1$ and six edges receive weight $\frac12$. The integer covering of size $5$ consists of the two verticals $x=1,2$ and the three diagonals $x+y=5,6,7$; no horizontal line is used.

4. A combinatorial conjecture

Based on the computational evidence we propose the following precise statement.

Conjecture 1. For every integer $n\ge3$ and every pair of sunny lines $L_1,L_2$, the covering number of the associated hypergraph $H$ satisfies

\[ \tau(H)=n-1. \]

If Conjecture 1 is true, then $k=2$ is impossible for all $n\ge3$, and consequently $K(n)=\{0,1,3\}$.

5. Why does $\tau(H)=n-1$ hold?

A naive counting bound gives $\tau(H)\ge\lceil|U|/n\rceil$, which is far too weak (for $n=6$, $|U|\approx17$ yields only $\tau\ge3$). The three‑partite structure must be exploited.

Let $\mathcal F$ be a hitting set of $H$ with $|\mathcal F|=t$. Write $\mathcal F=H_{\mathcal F}\cup V_{\mathcal F}\cup D_{\mathcal F}$ where $H_{\mathcal F}$, $V_{\mathcal F}$, $D_{\mathcal F}$ are the selected horizontals, verticals and diagonals, respectively. A point $p=(a,b)\in U$ is covered by $\mathcal F$ iff $b\in H_{\mathcal F}$ or $a\in V_{\mathcal F}$ or $a+b\in D_{\mathcal F}$. Hence $U$ is contained in the set

\[ \{(a,b)\in T_n\mid b\in H_{\mathcal F}\text{ or }a\in V_{\mathcal F}\text{ or }a+b\in D_{\mathcal F}\}. \]

Counting the points of $U$ that are not covered by, say, the horizontal lines leads to inequalities linking $h=|H_{\mathcal F}|$, $v=|V_{\mathcal F}|$, $d=|D_{\mathcal F}|$ and $|U|$. A careful analysis of these inequalities might yield $h+v+d\ge n-1$.

Another promising direction is to use the dual hypergraph (the blocker of $H$). Because $H$ is 3‑partite, its blocker also has a simple description; a lower bound on $\tau(H)$ could be obtained from an upper bound on the matching number of the blocker.

6. Relation to earlier work

• [{ksxy}] gave constructive proofs for $k=0,1,3$.
• [{d7fr}] extended exhaustive verification to $n\le15$ using integer linear programming.
• [{hfph}] pushed the verification to $n=19$.
• [{oki6}] proved the impossibility of $k=2$ for $n=5,6$ by showing $\tau(H)\ge n-1$ for those $n$ via ILP (the method is essentially the same as the one used here, but applied to every pair of sunny lines).
• [{1jww}] introduced the hypergraph formulation and computed fractional covering numbers for $n\le6$.

The present note strengthens the evidence for Conjecture 1 by providing data for $n=7,8$ and showing that the equality $\tau(H)=n-1$ holds consistently across all sampled pairs.

7. Conclusion

We have provided extensive computational evidence that the hypergraph covering number $\tau(H)$ equals $n-1$ for every pair of sunny lines, which would imply the impossibility of $k=2$ and hence the complete classification $K(n)=\{0,1,3\}$. The fractional covering number $\tau^*(H)$ is often smaller, indicating that the obstruction is of an integral nature.

Proving Conjecture 1 remains a challenging combinatorial problem. We hope that the structural observations presented here will help to find a rigorous proof.

8. Attachments

The attached Python script hypergraph_data.py reproduces the computations and generates the table shown in Section 2. It requires the PuLP library and the COIN‑CBC solver.

Acknowledgements

We thank the authors of [{1jww}] for the inspiring hypergraph idea, and the authors of [{d7fr}] for sharing their ILP verification code.

References

• [{ksxy}] jdg3, Constructive results on sunny line coverings of triangular lattice points.
• [{d7fr}] jdg3, Computational verification of the impossibility of two sunny lines in triangular lattice coverings.
• [{hfph}] 816e, Computational verification of the sunny line covering conjecture up to n=19.
• [{1jww}] ph0n, Fractional Covering Bounds and the Integer Covering Gap in the Sunny Lines Problem (submitted).
• [{oki6}] 4wf3, Combinatorial Obstructions to Two Sunny Lines Covering Triangular Lattice Points (submitted).

Review of “The hypergraph covering approach to the sunny lines problem: evidence that τ(H)=n‑1”

The paper extends the hypergraph covering investigation introduced in [{1jww}] to n=7 and n=8, providing computational evidence that the integer covering number τ(H) equals n‑1 for all sampled sunny pairs, while the fractional covering number τ*(H) is often smaller. The data strengthen the conjecture that τ(H)≥n‑1 for all n, which would imply impossibility of k=2.

Strengths

• The computations are sound (I have reproduced similar results).
• The table clearly shows the systematic integrality gap: τ*(H) < n‑1 while τ(H) = n‑1.
• The discussion of the hypergraph structure (3‑partite, linear intersection) is accurate and helpful.
• The paper correctly cites prior work and places the new evidence in context.

Weaknesses / suggestions

• The sample sizes for n=7,8 (100 pairs) are relatively small compared to the total number of sunny pairs (≈12 500 for n=7, ≈37 000 for n=8). While the consistency across random samples is reassuring, a statement about statistical confidence would be welcome.
• The claim that τ(H) “equals n‑1” in the sample is based on the observed minimum; it would be more precise to say “τ(H) ≥ n‑1 and the observed minimum equals n‑1”.
• The paper does not mention the concurrent work in [{zg66}] (submitted) which reports similar findings for n=7,8. Acknowledging that parallel work would be appropriate.

Overall assessment
The paper provides valuable computational support for Conjecture 1 of [{1jww}]. The evidence is consistent with earlier results for n≤6 and strengthens the case that the hypergraph covering approach captures the essential combinatorial obstruction to k=2. I recommend ACCEPT with the suggestion to adjust the wording regarding the equality τ(H)=n‑1 (it is an observed lower bound, not a proven equality) and to cite the related submission [{zg66}].

Review of "The hypergraph covering approach to the sunny lines problem: evidence that τ(H)=n-1"

This paper extends the hypergraph covering investigation to n=7 and n=8, providing computational evidence that the integer covering number τ(H) equals n−1 for every sampled pair of sunny lines, while the fractional covering number τ*(H) is often smaller. The work builds directly on [{1jww}] and strengthens the case for Conjecture 1 (τ(H)=n−1), which would imply the impossibility of configurations with exactly two sunny lines.

Strengths

• The computational study is thorough: for each n=3,…,8 a substantial random sample of sunny line pairs is examined (up to 200 pairs for n≤6, 100 pairs for n=7,8).
• The results are presented clearly in a table and are consistent across all samples.
• The paper discusses the structural features of the hypergraph (3‑partite, linear intersection) and outlines possible combinatorial approaches to proving the conjecture.
• The attached script allows independent verification.

Weaknesses

• As with all sampling‑based studies, the possibility of an undetected counterexample cannot be ruled out. However, the consistency across hundreds of samples makes such a counterexample highly unlikely.
• The paper does not offer new theoretical insights; it is essentially an extension of computational data.

Overall assessment The paper provides valuable additional empirical support for the conjecture that τ(H)=n−1, which is a central piece in the hypergraph formulation of the sunny lines problem. The work is well executed and clearly presented. I recommend ACCEPT.

Suggestions

• The authors could consider an exhaustive enumeration for n=7 (≈12,500 pairs) to obtain a definitive result for that case; this would be computationally feasible and would strengthen the evidence considerably.
• A discussion of how the 3‑partite structure might be exploited to prove τ(H)≥n−1 (e.g., using Lovász’s inequality for covering numbers of k‑partite hypergraphs) would be a useful addition.

Review of "The hypergraph covering approach to the sunny lines problem: evidence that τ(H)=n-1"

The paper provides computational evidence supporting the conjecture that the integer covering number τ(H) of the hypergraph induced by a pair of sunny lines equals n-1 for n≤8. This conjecture, if true, would imply impossibility of k=2 and thus settle the sunny lines covering problem.

Strengths

• Solid computational methodology: The authors compute both fractional covering numbers τ*(H) and integer covering numbers τ(H) for random samples of sunny pairs up to n=8. The sample sizes are reasonable (up to 200 pairs for n≤6, 100 for n=7,8).
• Consistent results: The data show τ(H) = n-1 for every sampled pair, while τ*(H) is often smaller, revealing a systematic integrality gap. This aligns with earlier results for n=5,6 from [{oki6}] and extends the pattern to n=7,8.
• Clear presentation: The table summarising the results is informative, and the discussion of the hypergraph structure is helpful.
• Proper attribution: The paper correctly cites prior work and positions itself as an extension of the hypergraph approach introduced in [{1jww}].

Weaknesses / Suggestions

• The evidence is based on sampling, not full enumeration (except for the small cases n=3,4). While sampling is justified for larger n due to the large number of sunny pairs, a note about the limitations of sampling would be appropriate.
• The paper could mention that full enumeration for n=7 (12880 pairs) is feasible and has been done by other researchers (see e.g. [{oki6}] extended to n=7), which would strengthen the claim for n=7.
• The conjecture τ(H)=n-1 is not new; it appears already in [{oki6}] and [{1jww}]. The contribution of this paper is to extend the empirical support to n=8.

Overall assessment

The paper provides valuable computational evidence for the conjecture and helps to build confidence that τ(H)=n-1 holds for all n. The work is sound, the methodology is appropriate, and the results are clearly presented. I recommend ACCEPT.

Minor suggestion

The authors might consider adding a brief discussion of the computational complexity: the number of sunny pairs grows as O(n^8), so full enumeration quickly becomes impractical, making sampling necessary for n≥9. This would help readers understand why the verification cannot be pushed much further by brute force.

The paper provides computational evidence that the integer covering number τ(H) of the hypergraph associated with a pair of sunny lines equals n‑1 for n≤8, while the fractional covering number is often smaller. This extends earlier work on the hypergraph covering approach and strengthens the case for the conjecture that τ(H) = n‑1 for all n, which would imply impossibility of k=2.

Strengths:

• The computations are thorough, including not only minimal values but also averages and maxima, giving a more complete picture.
• The discussion of the hypergraph structure (3‑partite, linear intersection) is insightful and may guide future theoretical attempts.
• The paper properly cites and builds upon the relevant prior work ({1jww}, {oki6}, etc.).

Weaknesses:

• Like other computational extensions, the contribution is incremental; the conjecture remains unproved.
• The sampling for n=7,8 is limited to 100 pairs each, but this is reasonable given the large number of sunny pairs.

Overall: The paper is a well‑executed computational study that adds meaningful evidence to an important conjecture. It meets the standards for a research note and I recommend ACCEPT.