Inside-out polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.     

On Integer Solutions to Linear Equations

A magic square is an n × n matrix with non-negative integer entries, such that the sum of the entries in each row and column is the same. We study the enumeration and P-recursivity of these in the case in which the sum along each row and column is fixed, with the size n of the matrix as the variable. A method is developed that nicely proves some known results about the case when the row and column sum is 2, and we prove new results for the case when the sum is 3. Received December 23, 2005     

The Moore–Penrose inverse of block magic rectangles

As is known, a semi-magic square is an n?×?n matrix having the sum of entries in each row and each column equal to a constant. This note generalizes this notion and introduce a special class of block matrices called block magic rectangles. It is proved that the Moore–Penrose inverse of a block magic rectangle is also a block magic rectangle.     

Existence of weakly pandiagonal orthogonal Latin squares

A weakly pandiagonal Latin square of order n over the number set {0, 1, . . . , n-1} is a Latin square having the property that the sum of the n numbers in each of 2n diagonals is the same. In this paper, we shall prove that a pair of orthogonal weakly pandiagonal Latin squares of order n exists if and only if n ≡ 0, 1, 3 (mod 4) and n≠3.     

Continued fractions associated with the Newton-Padé table

Summary We discuss first the block structure of the Newton-Padé table (or, rational interpolation table) corresponding to the double sequence of rational interpolants for the data{(z _k, h(z_k)} _k =0. (The (m, n)-entry of this table is the rational function of type (m,n) solving the linearized rational interpolation problem on the firstm+n+1 data.) We then construct continued fractions that are associated with either a diagonal or two adjacent diagonals of this Newton-Padé table in such a way that the convergents of the continued fractions are equal to the distinct entries on this diagonal or this pair of diagonals, respectively. The resulting continued fractions are generalizations of Thiele fractions and of Magnus'sP-fractions. A discussion of an some new results on related algorithms of Werner and Graves-Morris and Hopkins are also given.Dedicated to the memory of Helmut Werner (1931–1985)     

Magic square spectra

To study the eigenvalues of low order singular and non-singular magic squares we begin with some aspects of general square matrices. Additional properties follow for general semimagic squares (same row and column sums), with further properties for general magic squares (semimagic with same diagonal sums). Parameterizations of general magic squares for low orders are examined, including factorization of the linesum eigenvalue from the characteristic polynomial.For nth order natural magic squares with matrix elements 1,…,n² we find examples of some remarkably singular cases. All cases of the regular (or associative, or symmetric) type (antipodal pair sum of 1+n²) with n-1 zero eigenvalues have been found in the only complete sets of these squares (in fourth and fifth order). Both the Jordan form and singular value decomposition (SVD) have been useful in this study which examines examples up to 8th order.In fourth order these give examples illustrating a theorem by Mattingly that even order regular magic squares have a zero eigenvalue with odd algebraic multiplicity, m. We find 8 cases with m=3 which have a non-diagonal Jordan form. The regular group of 48 squares is completed by 40 squares with m=1, which are diagonable. A surprise finding is that the eigenvalues of 16 fourth order pandiagonal magic squares alternate between m=1, diagonable, and m=3, non-diagonable, on rotation by π/2. Two 8th order natural magic squares, one regular and the other pandiagonal, are also examined, found to have m=5, and to be diagonable.Mattingly also proved that odd order regular magic squares have a zero eigenvalue with even multiplicity, m=0,2,4,... Analyzing results for natural fifth order magic squares from exact backtracking calculations we find 652 with m=2, and four with m=4. There are also 20, 604 singular seventh order natural ultramagic (simultaneously regular and pandiagonal) squares with m=2, demonstrating that the co-existence of regularity and pandiagonality permits singularity. The singular odd order examples studied are all non-diagonable.     

Striking patterns in natural magic squares’ associated electrostatic potentials: Matrices of the 4th and 5th order

A magic square is a square matrix whereby the sum of any row, column, or any one of the two principal diagonals is equal. A surrogate of this abstract mathematical construct, introduced in 2012 by Fahimi and Jaleh, is the “electrostatic potential (ESP)” that results from treating the matrix elements of the magic square as electric charges. The overarching idea is to characterize patterns associated with these matrices that can possibly be used, in the future, in reverse to generate these squares. This study focuses on squares of order 4 and 5 with 880 and 275,305,224 distinct (irreducible/unique) realizations, respectively. It is shown that characteristic patterns emerge from plots of the ESPs of the matrices representing the studied squares. The electrostatic potentials for natural magic squares exhibit a striking pattern of maxima and minima in all distinct 880 of the 4th order and all distinct 275,305,224 of the 5th order matrices. The minimum values of ESP of Dudeney groups are discussed. Equipotential points and certain constants are found among the ESP sums along horizontal and vertical lines on the square lattice. These findings may help to open a new perspective regarding magic squares unsolved problems. While mathematics often leads discovery in physics, the latter (physics) is used here to detect otherwise invisible patterns in a mathematical object such as magic squares.     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

Convex nonagons with five intervertex distances

The vertices of a convex planar nonagon determine exactly five distances if and only if they are nine vertices of a regular 10-gon or a regular 11-gon. This result has important ties to related concerns, including the maximum number of points in the plane that determine exactly five distances and, for each n7, the samllest t for which there exists a convex n-gon whose vertices determine t distances and are not all on one circle.     

Constructing orthogonal pandiagonal Latin squares and panmagic squares from modular n‐queens solutions

In this article, we show how to construct pairs of orthogonal pandiagonal Latin squares and panmagic squares from certain types of modular n‐queens solutions. We prove that when these modular n‐queens solutions are symmetric, the panmagic squares thus constructed will be associative, where for an n × n associative magic square A = (a_ij), for all i and j it holds that a_ij + an?i?1,n?j?1 = c for a fixed c. We further show how to construct orthogonal Latin squares whose modular difference diagonals are Latin from any modular n‐queens solution. As well, we analyze constructing orthogonal pandiagonal Latin squares from particular classes of non‐linear modular n‐queens solutions. These pandiagonal Latin squares are not row cyclic, giving a partial solution to a problem of Hedayat. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 221–234, 2007     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,f _n ) is called the profile of ℱ wheref _i denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

A simple method for constructing doubly diagonalized Latin squares

A Latin square of order n we call doubly diagonalized if both its diagonals consist of n distinct symbols. In this paper a new method to construct such squares for any order is given.     

Point sets with distinct distances

For positive integersd andn letf _d (n) denote the maximum cardinality of a subset of then ^d -gird {1,2,...,n} ^d with distinct mutual euclidean distances. Improving earlier results of Erds and Guy, it will be shown thatf ₂ (n)c·n ^2/3 and, ford3, thatf _d (n)c _d ·n ^2/3 ·(lnn)^1/3, wherec, c _d >0 are constants. Also improvements of lower bounds of Erds and Alon on the size of Sidon-sets in {1²,22²,...,n ²} are given.Furthermore, it will be proven that any set ofn points in the plane contains a subset with distinct mutual distances of sizec ₁·n ^1/4, and for point sets in genral position, i.e. no three points on a line, of sizec ₂·n ^1/3 with constantsc ₁,c ₂>0. To do so, it will be shown that forn points in ² with distinct distancesd ₁,d ₂,...,d _t , whered _i has multiplicitym _i , one has _i=1 ^t m _i ² c·n _3.25 for a positive constantc. If then points are in general position, then we prove _i=1 ^t m _i ² c·n ₃ for a positive constantc and this bound is tight.Moreover, we give an efficient sequential algorithm for finding a subset of a given set with the desired properties, for example with distinct distances, of size as guaranteed by the probabilistic method under a more general setting.     

Clustering Methods in Microarrays

Summary DCT Given a finite set of points in an Euclidean space the \emph{spanning tree} is a tree of minimal length having the given points as vertices. The length of the tree is the sum of the distances of all connected point pairs of the tree. The clustering tree with a given length of a given finite set of points is the spanning tree of an appropriately chosen other set of points approximating the given set of points with minimal sum of square distances among all spanning trees with the given length. DCM A matrix of real numbers is said to be column monotone orderable if there exists an ordering of columns of the matrix such that all rows of the matrix become monotone after ordering. The {\emph{monotone sum of squares of a matrix}} is the minimum of sum of squares of differences of the elements of the matrix and a column monotone orderable matrix where the minimum is taken on the set of all column monotone orderable matrices. Decomposition clusters of monotone orderings of a matrix is a clustering ofthe rows of the matrix into given number of clusters such that thesum of monotone sum of squares of the matrices formed by the rowsof the same cluster is minimal.DCP A matrix of real numbers is said to be column partitionable if there exists a partition of the columns such that the elements belonging to the same subset of the partition are equal in each row. Given a partition of the columns of a matrix the partition sum of squares of the matrix is the minimum of the sum of square of differences of the elements of the matrix and a column partitionable matrix where the minimum is taken on the set of all column partitionable matrices. Decomposition of the rows of a matrix into clusters of partitions is the minimization of the corresponding partition sum of squares given the number of clusters and the sizes of the subsets of the partitions.     

Pooling, lattice square, and union jack designs

Simplified pooling designs employ rows, columns, and principal diagonals from square and rectangular plates. The requirement that every two samples be tested together in exactly one pool leads to a novel combinatorial configuration: The union jack design. Existence of union jack designs is settled affirmatively whenever the ordern is a prime andn3 (mod 4).     

Near optimal bounds for the Erdős distinct distances problem in high dimensions

We show that the number of distinct distances in a set of n points in ℝ ^d is Ω(n ^{2/d − 2 / d(d + 2)}), d ≥ 3. Erdős’ conjecture is Ω(n ^2/d ).     

Multidimensional Permanents and an Upper Bound on the Number of Transversals in Latin Squares

The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. A nonnegative matrix whose every 1‐dimensional plane sums to 1 is called polystochastic. A latin square of order n is an array of n symbols in which each symbol occurs exactly once in each row and each column. A transversal of such a square is a set of n entries such that no two entries share the same row, column, or symbol. Let T(n) be the maximum number of transversals over all latin squares of order n. Here, we prove that over the set of multidimensional polystochastic matrices of order n the permanent has a local extremum at the uniform matrix for whose every entry is equal to . Also, we obtain an asymptotic value of the maximal permanent for a certain set of nonnegative multidimensional matrices. In particular, we get that the maximal permanent of polystochastic matrices is asymptotically equal to the permanent of the uniform matrix, whence as a corollary we have an upper bound on the number of transversals in latin squares      

Separation of a finite set in ℝ d by spanned hyperplanes

A question of the following kind will concern us here: what is the minimal numbern, ensuring that any spanning set ofn points in 3-space spans a plane, every open side of which contains at least, say, 1000 points of the set. The answer isn=4001 (see Theorem 2.1 below).This is a part of a Ph.D. thesis, with the same title, supervised by Professor Micha A. Perles in the Hebrew University of Jerusalem