The Experts below are selected from a list of 231 Experts worldwide ranked by ideXlab platform
Nicholas J Cavenagh - One of the best experts on this subject based on the ideXlab platform.
-
Longest Partial Transversals in Plexes
Annals of Combinatorics, 2014Co-Authors: Nicholas J Cavenagh, Jaromy Kuhl, Ian M. WanlessAbstract:A k-protoplex of order n is a Partial Latin Square of order n such that each row and column contains precisely k entries and each symbol occurs precisely k times. If a k -protoplex is completable to a Latin Square, then it is a k-plex . A 1-protoplex is a transversal . Let $${\phi_k}$$ ϕ k denote the smallest order for which there exists a k -protoplex that contains no transversal, and let $${{{\phi_k}^{*}}}$$ ϕ k ∗ denote the smallest order for which there exists a k -plex that contains no transversal. We show that $${k \leqslant \phi_k = {{\phi_k}^{*}} \leqslant k+1}$$ k ⩽ ϕ k = ϕ k ∗ ⩽ k + 1 for all $${k \geqslant 6}$$ k ⩾ 6 . Given a k -protoplex P of order n , we define T ( P ) to be the size of the largest Partial transversal in P . We explore upper and lower bounds for T ( P ). Aharoni et al. have conjectured that $${T(P) \geqslant (k-1)n/k}$$ T ( P ) ⩾ ( k - 1 ) n / k . We find that $$T(P) > max \{ k(1-n^{-1/2}), k-n/(n-k), n-O (nk^{-1/2}log^{3/2} k)\}$$ T ( P ) > m a x { k ( 1 - n - 1 / 2 ) , k - n / ( n - k ) , n - O ( n k - 1 / 2 l o g 3 / 2 k ) } . In the special case of 3-protoplexes, we improve the lower bound for T ( P ) to 3 n /5.
-
on completing three cyclically generated transversals to a Latin Square
Finite Fields and Their Applications, 2009Co-Authors: Nicholas J Cavenagh, Carlo Hamalainen, Adrian M NelsonAbstract:Let P be a Partial Latin Square of prime order p>7 consisting of three cyclically generated transversals. Specifically, let P be a Partial Latin Square of the form:P={(i,c+i,s+i),(i,c^'+i,s^'+i),(i,c^''+i,s^''+i)|0=7, every Partial transversal of size 3 in the addition table for the integers modulo p can be completed to a full transversal.
-
When is a Partial Latin Square uniquely completable, but not its completable product?
Discrete Mathematics, 2008Co-Authors: Nicholas J Cavenagh, Diane Donovan, Abdollah Khodkar, John G. H. Van ReesAbstract:Let P and Q be uniquely completable Partial Latin Squares. It is an open problem to determine necessary and sufficient conditions so that the completable product [email protected]?Q is also uniquely completable. So far, only a few specific examples of P have been given such that the completable product of P with itself ([email protected]?P) does not have a unique completion. In this paper, we find a whole class of such Partial Latin Squares.
-
On completing three cyclic transversals to a Latin Square
arXiv: Combinatorics, 2007Co-Authors: Nicholas J Cavenagh, Carlo Hamalainen, Adrian M NelsonAbstract:Let $P$ be a Partial Latin Square of prime order $p>7$ consisting of three cyclically generated transversals. Specifically, let $P$ be a Partial Latin Square of the form: \[ P=\{(i,c+i,s+i),(i,c'+i,s'+i),(i,c''+i,s''+i)\mid 0 \leq i< p\} \] for some distinct $c,c',c''$ and some distinct $s,s',s''$. In this paper we show that any such $P$ completes to a Latin Square which is diagonally cyclic.
-
A superlinear lower bound for the size of a critical set in a Latin Square
Journal of Combinatorial Designs, 2007Co-Authors: Nicholas J CavenaghAbstract:A critical set is a Partial Latin Square that has a unique completion to a Latin Square, and is minimal with respect to this property. Let scs(n) denote the smallest possible size of a critical set in a Latin Square of order n. We show that for all n, . Thus scs(n) is superlinear with respect to n. We also show that scs(n) ≥ 2n−32 and if n ≥ 25, . © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 269–282, 2007
Kazuya Haraguchi - One of the best experts on this subject based on the ideXlab platform.
-
Iterated local search with Trellis-neighborhood for the Partial Latin Square extension problem
Journal of Heuristics, 2016Co-Authors: Kazuya HaraguchiAbstract:A Partial Latin Square ( PLS ) is a Partial assignment of n symbols to an $$n\times n$$ n × n grid such that, in each row and in each column, each symbol appears at most once. The PLS extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by ( p , q ) -swap , i.e., the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient $$(p,\infty )$$ ( p , ∞ ) -neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for $$p\in \{1,2,3\}$$ p ∈ { 1 , 2 , 3 } . The running time of the algorithm is $$O(n^{p+1})$$ O ( n p + 1 ) . We then propose a novel swap operation, Trellis-swap, which is a generalization of ( p , q )-swap with $$p\le 2$$ p ≤ 2 . The proposed Trellis-neighborhood search algorithm runs in $$O(n^{3.5})$$ O ( n 3.5 ) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with $$(p,\infty )$$ ( p , ∞ ) -neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver .
-
an efficient local search for Partial Latin Square extension problem
Integration of AI and OR Techniques in Constraint Programming, 2015Co-Authors: Kazuya HaraguchiAbstract:A Partial Latin Square (PLS) is a Partial assignment of \(n\) symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The Partial Latin Square extension problem is an NP-hard problem that asks for a largest extension of a given PLS. In this paper we propose an efficient local search for this problem. We focus on the local search such that the neighborhood is defined by \((p,q)\) -swap, i.e., removing exactly \(p\) symbols and then assigning symbols to at most \(q\) empty cells. For \(p\in \{1,2,3\}\), our neighborhood search algorithm finds an improved solution or concludes that no such solution exists in \(O(n^{p+1})\) time. We also propose a novel swap operation, Trellis-swap, which is a generalization of \((1,q)\)-swap and \((2,q)\)-swap. Our Trellis-neighborhood search algorithm takes \(O(n^{3.5})\) time to do the same thing. Using these neighborhood search algorithms, we design a prototype iterated local search algorithm and show its effectiveness in comparison with state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.
-
CPAIOR - An Efficient Local Search for Partial Latin Square Extension Problem
Integration of AI and OR Techniques in Constraint Programming, 2015Co-Authors: Kazuya HaraguchiAbstract:A Partial Latin Square (PLS) is a Partial assignment of \(n\) symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The Partial Latin Square extension problem is an NP-hard problem that asks for a largest extension of a given PLS. In this paper we propose an efficient local search for this problem. We focus on the local search such that the neighborhood is defined by \((p,q)\) -swap, i.e., removing exactly \(p\) symbols and then assigning symbols to at most \(q\) empty cells. For \(p\in \{1,2,3\}\), our neighborhood search algorithm finds an improved solution or concludes that no such solution exists in \(O(n^{p+1})\) time. We also propose a novel swap operation, Trellis-swap, which is a generalization of \((1,q)\)-swap and \((2,q)\)-swap. Our Trellis-neighborhood search algorithm takes \(O(n^{3.5})\) time to do the same thing. Using these neighborhood search algorithms, we design a prototype iterated local search algorithm and show its effectiveness in comparison with state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.
-
a constructive algorithm for Partial Latin Square extension problem that solves hardest instances effectively
WCO@FedCSIS, 2015Co-Authors: Kazuya HaraguchiAbstract:A Partial Latin Square (PLS) is a Partial assignment of \(n\) symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The Partial Latin Square extension (PLSE) problem asks to find such a PLS that is a maximum extension of a given PLS. Recently Haraguchi et al. proposed a heuristic algorithm for the PLSE problem. In this paper, we present its effectiveness especially for the “hardest” instances. We show by empirical studies that, when \(n\) is large to some extent, the instances such that symbols are given in 60–70 % of the \(n^2\) cells are the hardest. For such instances, the algorithm delivers a better solution quickly than IBM ILOG CPLEX, a state-of-the-art optimization solver, that is given a longer time limit. It also outperforms surrogate constraint based heuristics that are originally developed for the maximum independent set problem.
-
WCO@FedCSIS - A Constructive Algorithm for Partial Latin Square Extension Problem that Solves Hardest Instances Effectively
Recent Advances in Computational Optimization, 2014Co-Authors: Kazuya HaraguchiAbstract:A Partial Latin Square (PLS) is a Partial assignment of \(n\) symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The Partial Latin Square extension (PLSE) problem asks to find such a PLS that is a maximum extension of a given PLS. Recently Haraguchi et al. proposed a heuristic algorithm for the PLSE problem. In this paper, we present its effectiveness especially for the “hardest” instances. We show by empirical studies that, when \(n\) is large to some extent, the instances such that symbols are given in 60–70 % of the \(n^2\) cells are the hardest. For such instances, the algorithm delivers a better solution quickly than IBM ILOG CPLEX, a state-of-the-art optimization solver, that is given a longer time limit. It also outperforms surrogate constraint based heuristics that are originally developed for the maximum independent set problem.
Aleš Drápal - One of the best experts on this subject based on the ideXlab platform.
-
Homogeneous toroidal Latin bitrades
Ars Combinatoria, 2009Co-Authors: Terry S. Griggs, Aleš DrápalAbstract:Let T be a Partial Latin Square. Then T is a Latin trade if there exists a Partial Latin Square T1, called a trade mate of T, with the properties that (i) a cell is filled in T1 if and only if it is filled in T, (ii) no entry occurs in the same cell in T and T1, (iii) in any given row or column, T and T1 contain the same elements. The pair {T, T1} is called a Latin bitrade. A Latin trade T (and T1) is said to be (r, c, e)- homogeneous if each row contains precisely r entries, each column contains precisely c entries, and each entry occurs precisely e times. An (r, c, e)-homogeneous Latin bitrade can be embedded on the torus only for three parameter sets, namely (r, c, e) = (3, 3, 3), (4, 4, 2) or (6, 3, 2). In this talk I will present classifications for all three cases.
-
3-Homogeneous Latin trades
Discrete Mathematics, 2005Co-Authors: Nicholas J Cavenagh, Diane Donovan, Aleš DrápalAbstract:Let T be a Partial Latin Square and L be a Latin Square with [email protected]?L. We say that T is a Latin trade if there exists a Partial Latin Square T^' with T^'@[email protected] such that ([email protected]?T)@?T^' is a Latin Square. A k-homogeneous Latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous Latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous Latin trades of size 3m exist for each m>=3. This paper discusses existence results for Latin trades and provides a glueing construction which is subsequently used to construct all Latin trades of finite order greater than three.
-
4-homogeneous Latin trades
The Australasian Journal of Combinatorics, 2005Co-Authors: Nicholas J Cavenagh, Diane Donovan, Aleš DrápalAbstract:Let T be a Partial Latin Square and I be a Latin Square with T ⊆ L. We say that T is a Latin trade if there exists a Partial Latin Square T′ with T′ ∩ T = 0 such that (L\T) ∪ T′ is a Latin Square. A k-homogeneous Latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 4-homogeneous Latin trades from rectangular packings of the plane with circles.
-
3-Homogeneous Latin trades
Discrete Mathematics, 2005Co-Authors: Nicholas Cavenagh, Diane Donovan, Aleš DrápalAbstract:AbstractLet T be a Partial Latin Square and L be a Latin Square with T⊆L. We say that T is a Latin trade if there exists a Partial Latin Square T′ with T′∩T=∅ such that (L⧹T)∪T′ is a Latin Square. A k-homogeneous Latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous Latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous Latin trades of size 3m exist for each m⩾3. This paper discusses existence results for Latin trades and provides a glueing construction which is subsequently used to construct all Latin trades of finite order greater than three
Diane Donovan - One of the best experts on this subject based on the ideXlab platform.
-
When is a Partial Latin Square uniquely completable, but not its completable product?
Discrete Mathematics, 2008Co-Authors: Nicholas J Cavenagh, Diane Donovan, Abdollah Khodkar, John G. H. Van ReesAbstract:Let P and Q be uniquely completable Partial Latin Squares. It is an open problem to determine necessary and sufficient conditions so that the completable product [email protected]?Q is also uniquely completable. So far, only a few specific examples of P have been given such that the completable product of P with itself ([email protected]?P) does not have a unique completion. In this paper, we find a whole class of such Partial Latin Squares.
-
3-Homogeneous Latin trades
Discrete Mathematics, 2005Co-Authors: Nicholas J Cavenagh, Diane Donovan, Aleš DrápalAbstract:Let T be a Partial Latin Square and L be a Latin Square with [email protected]?L. We say that T is a Latin trade if there exists a Partial Latin Square T^' with T^'@[email protected] such that ([email protected]?T)@?T^' is a Latin Square. A k-homogeneous Latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous Latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous Latin trades of size 3m exist for each m>=3. This paper discusses existence results for Latin trades and provides a glueing construction which is subsequently used to construct all Latin trades of finite order greater than three.
-
4-homogeneous Latin trades
The Australasian Journal of Combinatorics, 2005Co-Authors: Nicholas J Cavenagh, Diane Donovan, Aleš DrápalAbstract:Let T be a Partial Latin Square and I be a Latin Square with T ⊆ L. We say that T is a Latin trade if there exists a Partial Latin Square T′ with T′ ∩ T = 0 such that (L\T) ∪ T′ is a Latin Square. A k-homogeneous Latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 4-homogeneous Latin trades from rectangular packings of the plane with circles.
-
3-Homogeneous Latin trades
Discrete Mathematics, 2005Co-Authors: Nicholas Cavenagh, Diane Donovan, Aleš DrápalAbstract:AbstractLet T be a Partial Latin Square and L be a Latin Square with T⊆L. We say that T is a Latin trade if there exists a Partial Latin Square T′ with T′∩T=∅ such that (L⧹T)∪T′ is a Latin Square. A k-homogeneous Latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous Latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous Latin trades of size 3m exist for each m⩾3. This paper discusses existence results for Latin trades and provides a glueing construction which is subsequently used to construct all Latin trades of finite order greater than three
-
A note on the completion of Partial Latin Squares
2004Co-Authors: Nicholas J Cavenagh, Diane Donovan, G. H. J. Van ReesAbstract:The problem of completing Partial Latin Squares to Latin Squares of the same order has been studied for many years. For instance, in 1960 Evans [9] conjectured that every Partial Latin Square of order n containing at most n− 1 filled cells is completable to a Latin Square of order n. This conjecture was shown to be true by Lindner [12] and Smetaniuk [13]. Recently, Bryant and Rodger [6] established necessary and sufficient conditions for completing an arbitary 2 by n Latin rectangle to an n by n symmetric Latin Square. Colbourn [8] demonstrated that the problem of determining whether an
Raúl M. Falcón - One of the best experts on this subject based on the ideXlab platform.
-
Using a CAS/DGS to Analyze Computationally the Configuration of Planar Bar Linkage Mechanisms Based on Partial Latin Squares
Mathematics in Computer Science, 2020Co-Authors: Raúl M. FalcónAbstract:Currently, the study of new isotopism invariants of Partial Latin Squares constitutes an open and active problem. This paper delves into this topic by analyzing computationally the configuration of planar bar linkage mechanisms for which the array formed by the lengths of their bars constitutes an empty-diagonal symmetric Partial Latin Square such that each one of its rows and columns has at least two non-empty cells. These assumptions enable one to define a series of algebraic and geometric constraints that can be readily implemented in any Computer Algebra or Dynamic Geometry System. In order to illustrate the different concepts and results introduced throughout the paper, it is explicitly determined and characterized the distribution of planar bar linkage mechanisms based on Partial Latin Squares of order up to five.
-
A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin Squares
Advances in Computational Mathematics, 2019Co-Authors: Raúl M. Falcón, V. Álvarez, Félix GudielAbstract:Latin Squares are used as scramblers on symmetric-key algorithms that generate pseudo-random sequences of the same length. The robustness and effectiveness of these algorithms are respectively based on the extremely large key space and the appropriate choice of the Latin Square under consideration. It is also known the importance that isomorphism classes of Latin Squares have to design an effective algorithm. In order to delve into this last aspect, we improve in this paper the efficiency of the known methods on computational algebraic geometry to enumerate and classify Partial Latin Squares. Particularly, we introduce the notion of affine algebraic set of a Partial Latin Square L = ( l _ i j ) of order n over a field K $\mathbb {K}$ as the set of zeros of the binomial ideal 〈 x i x j − x l ij : ( i , j ) is a non-empty cell in L 〉 ⊆ K [ x 1 , … , x n ] $\langle x_{i}x_{j}-x_{l_{ij}}\colon (i,j) \text { is a non-empty cell in} L \rangle \subseteq \mathbb {K}[x_{1},\ldots ,x_{n}]$ . Since isomorphic Partial Latin Squares give rise to isomorphic affine algebraic sets, every isomorphism invariant of the latter constitutes an isomorphism invariant of the former. In particular, we deal computationally with the problem of deciding whether two given Partial Latin Squares have either the same or isomorphic affine algebraic sets. To this end, we introduce a new pair of equivalence relations among Partial Latin Squares: being Partial transpose and being Partial isotopic.
-
Autotopism stabilized colouring games on rook’s graphs
Discrete Applied Mathematics, 2019Co-Authors: Raúl M. Falcón, Stephan Dominique AndresAbstract:Abstract This paper deals with the Θ -stabilized colouring game on the n × n rook’s graph, which constitutes a variant of the classical colouring game on finite graphs so that each configuration of the game is uniquely related to a Partial Latin Square of order n that respects a given autotopism Θ . The complexity of this variant is examined by means of its Θ -stabilized game chromatic number, whose currently known upper bound is improved to 2 n − 1 . Particularly, we introduce the concept of a passing board that enables us to describe a constructive method to compute this number. Based on this method, we explicitly determine the game chromatic number associated to those n × n rook’s graphs, for which n ≤ 4 .
-
A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin Squares
Advances in Computational Mathematics, 2018Co-Authors: Raúl M. Falcón, V. Álvarez, Félix GudielAbstract:Latin Squares are used as scramblers on symmetric-key algorithms that generate pseudo-random sequences of the same length. The robustness and effectiveness of these algorithms are respectively based on the extremely large key space and the appropriate choice of the Latin Square under consideration. It is also known the importance that isomorphism classes of Latin Squares have to design an effective algorithm. In order to delve into this last aspect, we improve in this paper the efficiency of the known methods on computational algebraic geometry to enumerate and classify Partial Latin Squares. Particularly, we introduce the notion of affine algebraic set of a Partial Latin Square L = (lij) of order n over a field \(\mathbb {K}\) as the set of zeros of the binomial ideal \(\langle x_{i}x_{j}-x_{l_{ij}}\colon (i,j) \text { is a non-empty cell in} L \rangle \subseteq \mathbb {K}[x_{1},\ldots ,x_{n}]\). Since isomorphic Partial Latin Squares give rise to isomorphic affine algebraic sets, every isomorphism invariant of the latter constitutes an isomorphism invariant of the former. In particular, we deal computationally with the problem of deciding whether two given Partial Latin Squares have either the same or isomorphic affine algebraic sets. To this end, we introduce a new pair of equivalence relations among Partial Latin Squares: being Partial transpose and being Partial isotopic.
-
Autoparatopism stabilized colouring games on rook's graphs
Electronic Notes in Discrete Mathematics, 2018Co-Authors: Stephan Dominique Andres, Helena Bergold, Raúl M. FalcónAbstract:Abstract We introduce the autoparatopism variant of the autotopism stabilized colouring game on the n × n rook's graph as a natural generalization of the latter so that each board configuration is uniquely related to a Partial Latin Square of order n that respects a given autoparatopism (θ; π). To this end, we distinguish between π ∈ { Id , ( 12 ) } and π ∈ { ( 13 ) , ( 23 ) , ( 123 ) , ( 132 ) } . The complexity of this variant is examined by means of the autoparatopism stabilized game chromatic number. Some illustrative examples and results are shown.