Generalized mix functions and orthogonal equitable rectangles

Ristenpart and Rogaway defined “mix” functions, which are used to mix inputs from two sets of equal size, and produce outputs from the same two sets, in an optimal way. These functions have a cryptographic application in the context of extending the domain of a block cipher. It was observed that mix functions could be constructed from orthogonal latin squares. In this article, we give a simple, scalable construction for mix functions. We also consider a generalization of mix functions, in which the two sets need not be of equal size. These generalized mix functions turn out to be equivalent to an interesting type of combinatorial design which has not previously been studied. We term these “orthogonal equitable rectangles” and we construct them for all possible parameter situations, with a small number of exceptions and possible exceptions. Research supported by NSERC discovery grant 203114-06.     

Mutually orthogonal equitable Latin rectangles

Let ab=n². We define an equitable Latin rectangle as an a×b matrix on a set of n symbols where each symbol appears either or times in each row of the matrix and either or times in each column of the matrix. Two equitable Latin rectangles are orthogonal in the usual way. Denote a set of ka×b mutually orthogonal equitable Latin rectangles as a k– MOELR (a,b;n). When a≠9,18,36, or 100, then we show that the maximum number of k– MOELR (a,b;n)≥3 for all possible values of (a,b).     

Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

Multimagic rectangles based on large sets of orthogonal arrays

Large sets of orthogonal arrays (LOAs) have been used to construct resilient functions and zigzag functions by Stinson. In this paper, an application of LOAs in constructing multimagic rectangles is given. Further, some recursive constructions for multimagic rectangles are presented, and some infinite families of bimagic rectangles are obtained.     

Existence of centre-complementary magic rectangles

A magic rectangle of size $(m_1,m_2)$ is an $m_1\times m_2$ array consisting of $m_1{m}_2$ consecutive integers in which the sum of each row is a constant and the sum of each column is another (different if $m_1\ne m_2$). It is centre-complementary if the sum of any pair of centrally symmetric positions is constant. As a natural generalization of symmetric magic squares, centre-complementary magic rectangles are instrumental in the construction of 3-dimensional rectangles. In this paper, we focus our attention on the existence of centre-complementary magic rectangles and prove that the necessary conditions for the existence of centre-complementary magic rectangles are also sufficient.     

On the orthogonal Latin squares polytope

Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity.     

Embedding a latin square in a pair of orthogonal latin squares

In this paper, it is shown that a latin square of order n with n ≥ 3 and n ≠ 6 can be embedded in a latin square of order n² which has an orthogonal mate. A similar result for idempotent latin squares is also presented. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 270–276, 2006     

Existence of magic 3‐dimensional rectangles

Since the complete solution for the existence of magic 2‐dimensional rectangles in 1881, much attention has been paid on the existence of magic l‐dimensional rectangles for . The existence problem for magic l‐dimensional rectangles with even sizes has been solved completely for all integers . However, very little is known for the existence of magic l‐dimensional rectangles () with odd sizes except for some families and a few sporadic examples. In this paper, we focus our attention on the existence of magic 3‐dimensional rectangles and prove that the necessary conditions for the existence of magic 3‐dimensional rectangles are also sufficient. Our construction method is mainly based on a new concept, symmetric zero‐sum subset partition, which plays a crucial role in the recursive constructions of magic 3‐rectangles similar to that of PBD in the PBD‐closure construction in combinatorial design theory.     

A regional Kronecker product and multiple-pair latin squares

We introduce a variant of the Kronecker product, called the regional Kronecker product, that can be used to build new, larger multiple-pair latin squares from existing multiple-pair latin squares. We present applications to the existence and orthogonality of multiple-pair latin squares.     

一些图的Mycielski图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到了路、圈、星和扇的Mycielski图的均匀邻强边色数.     

若干图的倍图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数．本文得到了星、扇和轮的倍图的均匀邻强边色数．     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

On the maximum number of different ordered pairs of symbols in sets of latin squares

In this paper, we study the problem of constructing sets of s latin squares of order m such that the average number of different ordered pairs obtained by superimposing two of the s squares in the set is as large as possible. We solve this problem (for all s) when m is a prime power by using projective planes. We also present upper and lower bounds for all positive integers m. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 1–15, 2005.     

An LP-based proof for the non-existence of a pair of orthogonal Latin squares of order 6

This paper presents an alternative proof for the non-existence of orthogonal Latin squares of order 6. Our method is algebraic, rather than enumerative, and applies linear programming in order to obtain appropriate dual vectors. The proof is achievable only after extending previously known results for symmetry elimination.     

On a Class of Traceability Codes

Traceability codes are designed to be used in schemes that protect copyrighted digital data against piracy. The main aim of this paper is to give an answer to a Staddon–Stinson–Wei's problem of the existence of traceability codes with q< w ² and b>q. We provide a large class of these codes constructed by using a new general construction method for q-ary codes.