Maximum uniformly resolvable designs with block sizes 2 and 4

A central question in design theory dating from Kirkman in 1850 has been the existence of resolvable block designs. In this paper we will concentrate on the case when the block size k=4. The necessary condition for a resolvable design to exist when k=4 is that v≡4mod12; this was proven sufficient in 1972 by Hanani, Ray-Chaudhuri and Wilson [H. Hanani, D.K. Ray-Chaudhuri, R.M. Wilson, On resolvable designs, Discrete Math. 3 (1972) 343-357]. A resolvable pairwise balanced design with each parallel class consisting of blocks which are all of the same size is called a uniformly resolvable design, a URD. The necessary condition for the existence of a URD with block sizes 2 and 4 is that v≡0mod4. Obviously in a URD with blocks of size 2 and 4 one wishes to have the maximum number of resolution classes of blocks of size 4; these designs are called maximum uniformly resolvable designs or MURDs. So the question of the existence of a MURD on v points has been solved for by the result of Hanani, Ray-Chaudhuri and Wilson cited above. In the case this problem has essentially been solved with a handful of exceptions (see [G. Ge, A.C.H. Ling, Asymptotic results on the existence of 4-RGDDs and uniform 5-GDDs, J. Combin. Des. 13 (2005) 222-237]). In this paper we consider the case when and prove that a exists for all u≥2 with the possible exception of u∈{2,7,9,10,11,13,14,17,19,22,31,34,38,43,46,47,82}.     

Uniformly resolvable designs with index one, block sizes three and five and up to five parallel classes with blocks of size five

Each parallel class of a uniformly resolvable design (URD) contains blocks of only one block size k (denoted k-pc). The number of k-pcs is denoted r_k. The necessary conditions for URDs with v points, index one, blocks of size 3 and 5, and r₃,r₅>0, are . If r_k>1, then v≥k², and r₃=(v−1−4⋅r₅)/2. For r₅=1 these URDs are known as group divisible designs. We prove that these necessary conditions are sufficient for r₅=3 except possibly v=105, and for r₅=2,4,5 with possible exceptions (v=105,165,285,345) New labeled frames and labeled URDs, which give new URDs as ingredient designs for recursive constructions, are the key in the proofs.     

Transitive resolvable idempotent quasigroups and large sets of resolvable Mendelsohn triple systems

We first define a transitive resolvable idempotent quasigroup (TRIQ), and show that a TRIQ of order v exists if and only if 3∣v and . Then we use TRIQ to present a tripling construction for large sets of resolvable Mendelsohn triple systems s, which improves an earlier version of tripling construction by Kang. As an application we obtain an for any integer n≥1, which provides an infinite family of even orders.     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

Constructions of optimal quaternary constant weight codes via group divisible designs

Generalized Steiner systems were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g+1 with minimum Hamming distance 2k−3, in which each codeword has length v and weight k. As to the existence of a , a lot of work has been done for k=3, while not so much is known for k=4. The notion k-^∗GDD was first introduced by Chen et al. and used to construct . The necessary condition for the existence of a is v≥14. In this paper, it is proved that there exists a for any prime power and v≥19. By using this result, the known results on the existence of optimal quaternary constant weight codes are then extended.     

How to play the Majority game with a liar

The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q^∗ denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q^∗ in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).     

Super-simple group divisible designs with block size 4 and index 5

In this paper, we investigate the existence of a super-simple (4, 5)-GDD of type g^u and show that such a design exists if and only if u≥4, g(u−2)≥10, and .     

Resolvable group divisible designs with block size four and general index

In this paper, we investigate the existence of resolvable group divisible designs (RGDDs) with block size four, group-type hⁿ and general index λ. The necessary conditions for the existence of such a design are n≥4, and . These necessary conditions are shown to be sufficient for all λ≥2, with the definite exceptions of (λ,h,n)∈{(3,2,6)}∪{(2j+1,2,4):j≥1}. The known existence result for λ=1 is also improved.     

Super-simple balanced incomplete block designs with block size 4 and index 5

In statistical planning of experiments, super-simple designs are the ones providing samples with maximum intersection as small as possible. Super-simple designs are also useful in other constructions, such as superimposed codes and perfect hash families etc. The existence of super-simple (v,4,λ)-BIBDs have been determined for λ=2,3,4 and 6. When λ=5, the necessary conditions of such a design are that and v≥13. In this paper, we show that there exists a super-simple (v,4,5)-BIBD for each and v≥13.     

Pair covering designs with block size 5

In this article we look at pair covering designs with a block size of 5 and . The number of blocks in a minimum covering design is known as the covering number C(v,5,2). For v?24, these values are known, and all but v=8 exceed the Schönheim bound, L(v,5,2)=⌈v/5⌈(v-1)/4⌉⌉. However, for all v?28 with , it seems probable that C(v,5,2)=L(v,5,2). We establish this for all but 17 possible exceptional values lying in the range 40?v?280.     

Posets of annular non-crossing partitions of types B and D

We study the set of annular non-crossing permutations of type B, and we introduce a corresponding set of annular non-crossing partitions of type B, where p and q are two positive integers. We prove that the natural bijection between and is a poset isomorphism, where the partial order on is induced from the hyperoctahedral group B_p+q, while is partially ordered by reverse refinement. In the case when q=1, we prove that is a lattice with respect to reverse refinement order.We point out that an analogous development can be pursued in type D, where one gets a canonical isomorphism between and . For q=1, the poset coincides with a poset “NC^(D)(p+1)” constructed in a paper by Athanasiadis and Reiner [C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group D_n, SIAM Journal of Discrete Mathematics 18 (2004) 397-417], and is a lattice by the results of that paper.     

On wreathed lexicographic products of graphs

This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G.     

Steiner almost self-complementary graphs and halving near-Steiner triple systems

We show that for every admissible order v≡0 or there exists a near-Steiner triple system of order v that can be halved. As a corollary we obtain that a Steiner almost self-complementary graph with n vertices exists if and only if n≡0 or .     

Directed 3-cycle decompositions of complete directed graphs with quadratic leaves

Let G be a vertex-disjoint union of directed cycles in the complete directed graph D_t, let |E(G)| be the number of directed edges of G and suppose or if t=5, and if t=6. It is proved in this paper that for each positive integer t, there exist -decompositions for D_t−G if and only if .     

A note on an embedding problem in transitive tournaments

Let TT_n be a transitive tournament on n vertices. It is known Görlich, Pil?niak, Wo?niak, (2006) [3] that for any acyclic oriented graph of order n and size not greater than , two graphs isomorphic to are arc-disjoint subgraphs of TT_n. In this paper, we consider the problem of embedding of acyclic oriented graphs into their complements in transitive tournaments. We show that any acyclic oriented graph of size at most is embeddable into all its complements in TT_n. Moreover, this bound is generally the best possible.     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Game colouring of the square of graphs

This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, .     

Smallest defining sets of directed triple systems

A directed triple system of order v, , is a pair (V,B) where V is a set of v elements and B is a collection of ordered triples of distinct elements of V with the property that every ordered pair of distinct elements of V occurs in exactly one triple as a subsequence. A set of triples in a D is a defining set for D if it occurs in no other on the same set of points. A defining set for D is a smallest defining set for D if D has no defining set of smaller cardinality. In this paper we are interested in the quantity

     

Sequences of integers with missing quotients

Let S be any set of natural numbers, and A be a given set of rational numbers. We say that S is an A-quotient-free set if x,y∈S implies y/x∉A. Let and , where the supremum is taken over all A-quotient-free sets S, and are the upper and lower asymptotic densities of S respectively. Let ρ(A)=sup_Sδ(S), where the supremum is taken over all A-quotient-free sets S such that δ(S) exists. In this paper we study the properties of , and ρ(A).     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .