Completions of -dense partial Latin squares

DOI10.1002/JCD.21355zbMATH Open1276.05015arXiv1205.1558OpenAlexW2965457536MaRDI QIDQ2864800FDOQ2864800

Authors: Padraic Bartlett 

Publication date: 26 November 2013

Published in: Journal of Combinatorial Designs (Search for Journal in Brave)

Abstract: A classical question in combinatorics is the following: given a partial latin square P, when can we complete P to a latin square L? In this paper, we will investigate the class of leqepsilon-dense partial latin squares: partial latin squares in which each symbol, row, and column contains leqepsilon n-many nonblank cells. A conjecture of Nash-Williams on triangulations of graphs led Daykin and H"aggkvist to conjecture that all leq(1/4)-dense partial latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random latin squares, and use this technique to study leqepsilon-dense partial latin squares that contain leqdn^2 cells. In particular, we establish that all leq(1/5300)-dense n by n partial latin squares are completable, as well as all leq(1/13)-dense n by n partial latin squares that contain leq(8.8*10^(-5)*n^2)-many filled cells. This improves prior results of Gustavsson, which required epsilon = d leq 10^(-7), as well as Chetwynd and Haggkvist, which required epsilon = d leq 10^(-5) and n even, leq 10^7.

Full work available at URL: https://arxiv.org/abs/1205.1558

Recommendations

• Restricted completion of sparse partial Latin squares
• scientific article; zbMATH DE number 3887704
• Completing partial Latin squares with blocks of non-empty cells
• A note on completing Latin squares
• scientific article; zbMATH DE number 2170449

zbMATH Keywords

Latin squarespartial Latin squaresepsilon-dense partial Latin squaresGustavssonimproper Latin squaresHäggkvist

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15)

Cites Work

• An existence theorem for latin squares
• Generating uniformly distributed random latin squares
• A Combinatorial Theorem with an Application to Latin Rectangles
• A generalization of transversals for Latin squares

Cited In (13)

• Loops with exponent three in all isotopes
• Title not available (Why is that?)
• The complexity of completing partial Latin squares
• Bounds on the number of small Latin subsquares
• Substructures in Latin squares
• Restricted extension of sparse partial edge colorings of hypercubes
• Restricted extension of sparse partial edge colorings of complete graphs
• Title not available (Why is that?)
• Completing a solution of the embedding problem for incomplete idempotent Latin squares when numerical conditions suffice
• The linear system for Sudoku and a fractional completion threshold
• Clique decompositions of multipartite graphs and completion of Latin squares
• Latin cubes of even order with forbidden entries
• Restricted completion of sparse partial Latin squares

This page was built for publication: Completions of \(\epsilon \)-dense partial Latin squares

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