Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α(G)?n-t, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.     

On avoiding odd partial Latin squares and r-multi Latin squares

We show that for any positive integer k?4, if R is a (2k-1)×(2k-1) partial Latin square, then R is avoidable given that R contains an empty row, thus extending a theorem of Chetwynd and Rhodes. We also present the idea of avoidability in the setting of partial r-multi Latin squares, and give some partial fillings which are avoidable. In particular, we show that if R contains at most nr/2 symbols and if there is an n×n Latin square L such that δn of the symbols in L cover the filled cells in R where 0<δ<1, then R is avoidable provided r is large enough.     

Existence of r-self-orthogonal Latin squares

Two Latin squares of order v are r-orthogonal if their superposition produces exactly r distinct ordered pairs. If the second square is the transpose of the first one, we say that the first square is r-self-orthogonal, denoted by r-SOLS(v). It has been proved that for any integer v?28, there exists an r-SOLS(v) if and only if v?r?v² and r∉{v+1,v²-1}. In this paper, we give an almost complete solution for the existence of r-self-orthogonal Latin squares.     

Bounding the size of square-free subgraphs of the hypercube

We investigate the maximum size of a subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erd?s to be asymptotically 1/2. Following a computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284… to 0.62256… in the limit.     

Super-simple, pan-orientable and pan-decomposable GDDs with block size 4

In this paper we study (4,2μ)-GDDs of type gⁿ possessing both the pan-decomposable property introduced by Granville, Moisiadis, Rees, On complementary decompositions of the complete graph, Graphs and Combinatorics 5 (1989) 57-61 and the pan-orientable property introduced by Grüttmüller, Hartmann, Pan-orientable block designs, Australas. J. Combin. 40 (2008) 57-68. We show that the necessary condition for a (4,2μ)-GDD satisfying both of these properties, namely (1) n≥4, μg(n−1)≡0 (mod 3), and (2) g−1,n are not both even if μ is odd are sufficient. When λ=2, our designs are super-simple.We also determine the spectrum of (4,2)-GDDs which are super-simple and possess some of the decomposable/orientable conditions, but are not pan-decomposable or pan-orientable. In particular, we show that the necessary conditions for a super-simple directable (4,2)-GDD of type gⁿ are sufficient.     

Sloane's box stacking problem

Recently, Sloane suggested the following problem: We are given n boxes, labeled 1,2,…,n. For i=1,…,n, box i weighs (m-1)i grams (where m?2 is a fixed integer) and box i can support a total weight of i grams. What is the number of different ways to build a single stack of boxes in which no box will be squashed by the weight of the boxes above it? Prior to this generalized problem, Sloane and Sellers solved the case m=2. More recently, Andrews and Sellers solved the case m?3. In this note we give new and simple proofs of the results of Sloane and Sellers and of Andrews and Sellers, using a known connection with m-ary partitions.     

On time-relaxed broadcasting networks

Given a communication network (modelled as a graph), a message is transmitted to at one vertex transmits to all other vertices in such a way that each message transmission takes one time unit and each vertex participates in at most one transmission to its neighbor per time step. We call this process broadcasting. For t≥0, let B_t(n) be the number of edges in the sparsest possible graph on n vertices in which broadcasting can be accomplished in ⌈log₂n⌉+t steps regardless of the originator. Shastri [A. Shastri, Time-relaxed broadcasting in communication networks, Discrete Applied mathematics 83 (1998) 263-278] conjectured that B₁(22)=24 and B₂(n)=n+1 for 25≤n≤29. In this paper, we show that B₁(22)=24, B₂(n)=n for 25≤n≤28 and 37≤n≤44, B₂(n)≤n+1 for 45≤n≤49, B₂(n)≤n+4 for 50≤n≤56, and B₃(n)=n for 55≤n≤64.     

Faulhaber’s theorem on power sums

We observe that the classical Faulhaber’s theorem on sums of odd powers also holds for an arbitrary arithmetic progression, namely, the odd power sums of any arithmetic progression a+b,a+2b,…,a+nb is a polynomial in na+n(n+1)b/2. While this assertion can be deduced from the original Fauhalber’s theorem, we give an alternative formula in terms of the Bernoulli polynomials. Moreover, by utilizing the central factorial numbers as in the approach of Knuth, we derive formulas for r-fold sums of powers without resorting to the notion of r-reflective functions. We also provide formulas for the r-fold alternating sums of powers in terms of Euler polynomials.     

On the signed edge domination number of graphs

Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where K_m,n is the complete bipartite graph with part sizes m and n.     

Binary relations and reduced hypergroups

Different partial hypergroupoids are associated with binary relations defined on a set H. In this paper we find sufficient and necessary conditions for these hypergroupoids in order to be reduced hypergroups. Given two binary relations ρ and σ on H we investigate when the hypergroups associated with the relations ρ∩σ, ρ∪σ and ρσ are reduced. We also determine when the cartesian product of two hypergroupoids associated with a binary relation is a reduced hypergroup.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Partition and composition matrices

This paper introduces two matrix analogues for set partitions. A composition matrix on a finite set X is an upper triangular matrix whose entries partition X, and for which there are no rows or columns containing only empty sets. A partition matrix is a composition matrix in which an order is placed on where entries may appear relative to one-another.We show that partition matrices are in one-to-one correspondence with inversion tables. Non-decreasing inversion tables are shown to correspond to partition matrices with a row ordering relation. Partition matrices which are s-diagonal are classified in terms of inversion tables. Bidiagonal partition matrices are enumerated using the transfer-matrix method and are equinumerous with permutations which are sortable by two pop-stacks in parallel.We show that composition matrices on X are in one-to-one correspondence with (2+2)-free posets on X. Also, composition matrices whose rows satisfy a column-ordering relation are shown to be in one-to-one correspondence with parking functions. Finally, we show that pairs of ascent sequences and permutations are in one-to-one correspondence with (2+2)-free posets whose elements are the cycles of a permutation, and use this relation to give an expression for the number of (2+2)-free posets on {1,…,n}.     

Vertex-transitive self-complementary uniform hypergraphs of prime order

For an integer n and a prime p, let . In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that for every prime p, where ?=max{k₍₂₎,(k−1)₍₂₎}, and consequently we prove that the necessary conditions on the order of vertex-transitive self-complementary uniform hypergraphs of rank k=2^? or k=2^?+1 due to Potoňick and Šajna are sufficient. In addition, we use Burnside’s characterization of transitive groups of prime degree to characterize the structure of vertex-transitive self-complementary k-hypergraphs which have prime order p in the case where k=2^? or k=2^?+1 and , and we present an algorithm to generate all of these structures. We obtain a bound on the number of distinct vertex-transitive self-complementary graphs of prime order , up to isomorphism.     

Graph designs for the eight-edge five-vertex graphs

The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order n exists exactly when and n≠16, with the possible exception of n=48. For the unique graph with vertex sequence (2,3,3,4,4), a graph design of order n exists exactly when , with the possible exceptions of n∈{32,48}.     

Degree conditions for group connectivity

Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K_2,3,C₄ and C₅ by repeatedly contracting proper A-connected subgraphs, where C_k is a cycle of length k. We also show that the bound n≥13 is the best possible.     

Turán’s theorem inverted

In this note we complete an investigation started by Erd?s in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turán’s theorem in extremal graph theory.Let be the complete r-partite graph with parts of sizes s₁≥2,s₂,…,s_r with an edge added to the first part. Letting t_r(n) be the number of edges of the r-partite Turán graph of order n, we prove that:For all r≥2 and all sufficiently small c>0, every graph of sufficiently large order n with t_r(n)+1 edges contains a .We also give a corresponding stability theorem and two supporting results of wider scope.     

A group-based search for solutions of the n-queens problem

The n-queens problem is a well-known problem in mathematics, yet a full search for n-queens solutions has been tackled until now using only simple algorithms (with the exception of the Rivin-Zabih algorithm). In this article, we discuss optimizations that mainly rely on group actions on the set of n-queens solutions. Most of our arguments deal with the case of toroidal queens; at the end, the application to the regular n-queens problem is discussed, and also the Rivin-Zabih algorithm.     

Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

Path bundles on n-cubes

A path bundle is a set of 2^a paths in an n-cube, denoted Q_n, such that every path has the same length, the paths partition the vertices of Q_n, the endpoints of the paths induce two subcubes of Q_n, and the endpoints of each path are complements. This paper shows that a path bundle exists if and only if n>0 is odd and 0?a?n-⌈log₂(n+1)⌉.     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.