On the intricacy of combinatorial construction problems

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Orthogonal arrays, Latin squares, Room squares (05B15) Designs and configurations (05Bxx) Eulerian and Hamiltonian graphs (05C45)

Review text

\textit{D. E. Daykin} and \textit{R. Häggkvist} [Advanced problems and solutions, Am. Math. Mon. 88(6), 446 (1981)] asked the following problem. Given any partial latin square of order n what is the minimum \(\kappa\) (the intricacy) so that if the occupied cells are spread amongst \(\kappa\) arrays each array can be completed to a latin square of order n. Clearly \(\kappa \geq 2\) and they conjectured that \(\kappa =2\). This paper (which arose from the work of ten authors attending a combinatorial meeting at the Open University) generalizes the notion of intricacy to other combinatorial structures. We shall state two of the results. Theorem. Take any set S of pairwise edge disjoint Hamilton cycles from \(K_{2m+1}\). Write S as \(S=S_ 1\cup...\cup S_{\kappa}\) where each \(S_ i\) can be completed to a Hamilton decomposition of \(K_{2m+1}\). Then \(2\leq\kappa \leq 6.\) Theorem. Let \(q\neq 3\) be an odd prime power. Let A be an arc in PG(2,q). Write \(A=A_ 1\cup...\cup A_{\kappa}\) where each \(A_ i\) can be completed to an oval. Then \(\lceil (q+1)/12\rceil\leq /\kappa\leq \min (\lceil q/5\rceil,\quad\lceil 1/5(q- \sqrt{q}/4+7/4\rceil).\)

Recommendations

Cites work

Cited in

(7)

This page was built for publication: On the intricacy of combinatorial construction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799678)