Asymptotic enumeration of two-dimensional posets

In this paper we show that the number of pairwise nonisomorphic two-dimensional posets with n elements is asymptotically equivalent to 1/2n!. This estimate is based on a characterization, in terms of structural decomposition, of two-dimensional posets having a unique representation as the intersection of two linear extensions.     

f-Class two graphs whose f-cores have maximum degree two

An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v∈V(G) at most f(v) times.The f-core of G is the subgraph of G induced by the vertices v of degree d(v)=f(v) maxv∈V(G){ d(v)/f(v) }.In this paper,we find some necessary conditions for a simple graph,whose f-core has maximum degree two,to be of class 2 for f-colorings.     

All graphs with maximum degree three whose complements have 4-cycle decompositions

Let G be the set that contains precisely the graphs on n vertices with maximum degree 3 for which there exists a 4-cycle system of their complement in K_n. In this paper G is completely characterized.     

Linear extensions of finite posets and a conjecture of G. Kreweras on permutations

We prove a conjecture of G. Kreweras on the number of solutions of the equation xy=z for permutations of a given signature.     

The union of two random permutations does not have a directed Hamilton cycle

We prove that the union of two random permutations does not usually contain a directed Hamilton cycle. This answers a question posed by Frieze [Random Struct 11 (2000), 000–000]. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 95–98, 2001     

The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree

We study the maximum possible multiplicity of an eigenvalue of a matrix whose graph is a tree, expressing that maximum multiplicity in terms of certain parameters associated with the tree.     

The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree

We study the maximum possible multiplicity of an eigenvalue of a matrix whose graph is a tree, expressing that maximum multiplicity in terms of certain parameters associated with the tree.     

The existence ofd-polytopes whose facets have prescribed areas

Three positive numbersa(1),a(2),a(3) are the lengths of the sides of some triangle if, and only if,a(i₁)+a(i₂)<a(i₃) for each permutationi ₁, i₂, i₃ of 1,2,3. Here we extend this result to the areas of facets ofd-polytopes.     

Groups whose non-subnormal subgroups have a transitive normality relation

This article investigates the structure of groups in which every subgroup either is subnormal or has a transitive normality relation, with special attention to the case in which subnormal subgroups have bounded defect.     

Groups whose non-normal subgroups have a transitive normality relation

A group is calledmetahamiltonian if all its non-normal subgroups are abelian. The structure of metahamiltonian groups has been investigated by Romalis and Sesekin. In this paper groups are studied in which every non-normal subgroup has a transitive normality relation.     

Derivative polynomials and enumeration of permutations by number of interior and left peaks

Derivative polynomials in two variables are defined by repeated differentiation of the tangent and secant functions. We establish the connections between the coefficients of these derivative polynomials and the number of interior and left peaks over the symmetric group. Properties of the generating functions for the number of interior and left peaks over the symmetric group, including recurrence relations, generating functions and real-rootedness, are studied.     

The delay of circuits whose inputs have specified arrival times

Let C be a circuit representing a straight-line program on n inputs x₁,x₂,…,x_n. If for 1?i?n an arrival timet_i∈N₀ for x_i is given, we define the delay of x_i in C as the sum of t_i and the maximum number of gates on a directed path in C starting in x_i. The delay of C is defined as the maximum delay of one of its inputs.The notion of delay is a natural generalization of the notion of depth. It is of practical interest because it corresponds exactly to the static timing analysis used throughout the industry for the analysis of the timing behaviour of a chip. We prove a lower bound on the delay and construct circuits of close-to-optimal delay for several classes of functions. We describe circuits solving the prefix problem on n inputs that are of essentially optimal delay and of size O(nlog(logn)). Finally, we relate delay to formula size.     

Boundedness of bilinear multipliers whose symbols have a narrow support

This work is devoted to studying the boundedness on Lebesgue spaces of bilinear multipliers on ? whose symbol is narrowly supported around a curve (in the frequency plane). We are looking for the optimal decay rate (depending on the width of this support) for exponents satisfying a sub-Hölder scaling. As expected, the geometry of the curve plays an important role, which is described. This has applications to the bilinear Bochner-Riesz problem (in particular, boundedness of multipliers whose symbol is the characteristic function of a set), as well as to the bilinear restriction-extension problem.     

Spanning trees whose reducible stems have a few branch vertices

Czechoslovak Mathematical Journal - Let T be a tree. Then a vertex of T with degree one is a leaf of T and a vertex of degree at least three is a branch vertex of T. The set of leaves of T is...     

Unbiased Estimation for a Multivariate Exponential whose Components have a Common Shift

It is shown that for independent and identically distributed random vectors, for which the components are independent and exponentially distributed with a common shift, we can construct unbiased estimators of their density, derived from the Uniform Minimum Variance Unbiased Estimator (UMVUE) of their distribution function. As direct applications of the UMVUEs of the density functions we present a Chi-square goodness of fit test of the model, and give two tables of the UMVUEs of some commonly used functions of the unknown parameters of the multivariate exponential model considered in this paper.     

On the maximum number of permutations with given maximal or minimal distance

Let us denote by R(k, ? λ)[R(k, ? λ)] the maximal number $\text{M}$ such that there exist $\text{M}$ different permutations of the set {1,…, k} such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ? λ) ? kR(k ? 1, ? λ ? 1), R(k, ? λ) ? R(k, ? λ ? 1) ? k!, R(k, ? λ) ? kR(k ? 1, ? λ ? 1). We show: R(k, ? k ? 2) = 2, R(k, ? 1) = (k ? 1)!, R(p^m, ? 2) = (p^m ? 2)!, R(p^m + 1, ? 3) = (p^m ? 2)!, $\text{R(k, ? k ? 3) =}\text{k!}\text{2}$, R(k, ? 0) = k, R(p^m, ? 1) = p^m(p^m ? 1), R(p^m + 1, ? 2) = (p^m + 1)p^m(p^m ? 1). The exact value of R(k, ? λ) is determined whenever k ? k₀(k ? λ); we conjecture that R(k, ? λ) = (k ? λ)! for k ? k₀(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ? λ) ? R(k, ? λ)| is attained for $\text{λ = (}\text{k}\text{2}\text{) + O(}\text{k}\text{log}\text{k}\text{)}$.     

On linear codes whose weights and length have a common divisor

In this paper we prove that a set of points (in a projective space over a finite field of q elements), which is incident with 0 mod r points of every hyperplane, has at least (r−1)q+(p−1)r points, where 1<r<q=ph, p prime. An immediate corollary of this theorem is that a linear code whose weights and length have a common divisor r<q and whose dual minimum distance is at least 3, has length at least (r−1)q+(p−1)r. The theorem, which is sharp in some cases, is a strong generalisation of an earlier result on the non-existence of maximal arcs in projective planes; the proof involves polynomials over finite fields, and is a streamlined and more transparent version of the earlier one.