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 .     

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.     

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).     

Edge intersection graphs of linear 3-uniform hypergraphs

Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16.     

On the Wiener integral with respect to a sub-fractional Brownian motion on an interval

The domain of the Wiener integral with respect to a sub-fractional Brownian motion , , k≠0, is characterized. The set is a Hilbert space which contains the class of elementary functions as a dense subset. If , any element of is a function and if , the domain is a space of distributions.     

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.     

On cyclic semi-regular subgroups of certain 2-transitive permutation groups

We determine the cyclic semi-regular subgroups of the 2-transitive permutation groups and with n a suitable power of a prime number p.     

Lifting Bailey pairs to WP-Bailey pairs

A pair of sequences such that and

     

Finite-sample inference with monotone incomplete multivariate normal data, II

We continue our recent work on inference with two-step, monotone incomplete data from a multivariate normal population with mean and covariance matrix . Under the assumption that is block-diagonal when partitioned according to the two-step pattern, we derive the distributions of the diagonal blocks of and of the estimated regression matrix, . We represent in terms of independent matrices; derive its exact distribution, thereby generalizing the Wishart distribution to the setting of monotone incomplete data; and obtain saddlepoint approximations for the distributions of and its partial Iwasawa coordinates. We prove the unbiasedness of a modified likelihood ratio criterion for testing , where is a given matrix, and obtain the null and non-null distributions of the test statistic. In testing , where and are given, we prove that the likelihood ratio criterion is unbiased and obtain its null and non-null distributions. For the sphericity test, , we obtain the null distribution of the likelihood ratio criterion. In testing we show that a modified locally most powerful invariant statistic has the same distribution as a Bartlett-Pillai-Nanda trace statistic in multivariate analysis of variance.     

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.     

Large monochromatic components in colorings of complete 3-uniform hypergraphs

Let f(n,r) be the largest integer m with the following property: if the edges of the complete 3-uniform hypergraph are colored with r colors then there is a monochromatic component with at least m vertices. Here we show that and . Both results are sharp under suitable divisibility conditions (namely if n is divisible by 7, or by 6 respectively).     

Quadratic prediction problems in multivariate linear models

Linear and quadratic prediction problems in finite populations have become of great interest to many authors recently. In the present paper, we mainly aim to extend the problem of quadratic prediction from a general linear model, of form , to a multivariate linear model, denoted by with . Firstly, the optimal invariant quadratic unbiased (OIQU) predictor and the optimal invariant quadratic (potentially) biased (OIQB) predictor of for any particular symmetric nonnegative definite matrix satisfying are derived. Secondly, we consider predicting and . The corresponding restricted OIQU predictor and restricted OIQB predictor for them are given. In addition, we also offer four concluding remarks. One concerns the generalization of predicting and , and the others are concerned with three possible extensions from multivariate linear models to growth curve models, to restricted multivariate linear models, and to matrix elliptical linear models.     

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).     

On the relation between cluster and classical tilting

Let be a triangulated category with a cluster tilting subcategory U. The quotient category is abelian; suppose that it has finite global dimension.We show that projection from to sends cluster tilting subcategories of to support tilting subcategories of , and that, in turn, support tilting subcategories of can be lifted uniquely to weak cluster tilting subcategories of .     

Higher Kurtz randomness

A real x is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.     

Kirillov-Reshetikhin crystals for nonexceptional types

We provide combinatorial models for all Kirillov-Reshetikhin crystals of nonexceptional type, which were recently shown to exist. For types , , we rely on a previous construction using the Dynkin diagram automorphism which interchanges nodes 0 and 1. For type we use a Dynkin diagram folding and for types , a similarity construction. We also show that for types and the analog of the Dynkin diagram automorphism exists on the level of crystals.     

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 Δ, .     

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 .     

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.     

Tail behavior of random sums of negatively associated increments

Let be a sequence of negatively associated random variables with a common distribution function and finite expectation and let τ be a nonnegative integer-valued random variable independent of . In this paper we give unified form for the asymptotic behavior of the random sums in the case of . The results extend the earlier results of Aleškevi?iené et al. (2008) [2].