The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

Upper bounds on the depth of symmetric Boolean functions

A new method for implementing the counting function with Boolean circuits is proposed. It is based on modular arithmetic and allows us to derive new upper bounds for the depth of the majority function of n variables: 3.34log₂ n over the basis B ₂ of all binary Boolean functions and 4.87log₂ n over the standard basis B ₀ = {∧, ∨, ?}. As a consequence, the depth of the multiplication of n-digit binary numbers does not exceed 4.34log₂ n and 5.87log₂ n over the bases B ₂ and B ₀, respectively. The depth of implementation of an arbitrary symmetric Boolean function of n variables is shown to obey the bounds 3.34log₂ n and 4.88log₂ n over the same bases.     

The Erd?s-Ginzburg-Ziv theorem for dihedral groups

Let n≥23 be an integer and let D_2n be the dihedral group of order 2n. It is proved that, if g₁,g₂,…,g_3n is a sequence of 3n elements in D_2n, then there exist 2n distinct indices i₁,i₂,…,i_2n such that g_i1g_i2?g_i2n=1. This result is a sharpening of the famous Erd?s-Ginzburg-Ziv theorem for G=D_2n.     

Primitive digraphs with smallest large exponent

A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies α_n?γ(D)?w_n, where α_n=⌊w_n/2⌋+2 and w_n=(n-1)²+1. It is shown that the minimum number of arcs in a primitive digraph D on n?5 vertices with exponent equal to α_n is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent α_n and n+2 arcs. These constructions extend to digraphs with some exponents between α_n and w_n. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent α_n and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2.     

Intriguing Sets of Points of Q(2n, 2) \Q +(2n ? 1, 2)

Intriguing sets of vertices have been studied for several classes of strongly regular graphs. In the present paper, we study intriguing sets for the graphs Γ _n , n ≥ 2, which are defined as follows. Suppose Q(2n, 2), n?≥ 2, is a nonsingular parabolic quadric of PG(2n, 2) and Q ⁺(2n ? 1, 2) is a nonsingular hyperbolic quadric obtained by intersecting Q(2n, 2) with a suitable nontangent hyperplane. Then the collinearity relation of Q(2n, 2) defines a strongly regular graph Γ _n on the set Q(2n, 2) \ Q ⁺(2n ? 1, 2). We describe some classes of intriguing sets of Γ _n and classify all intriguing sets of Γ₂ and Γ₃.     

Minimal free resolutions of monomial curves in P3k

Minimal free resolutions for prime ideals with generic zero (tn3,tn3?n10tn11,tn3?n20tn2, tn31), n1<n2<n3 positive integers, (n1,n2,n3)=1, are determined.     

A new class of multiset Wilf equivalent pairs

We say the pair of patterns (σ,τ) is multiset Wilf equivalent if, for any multiset M, the number of permutations of M that avoid σ is equal to the number of permutations of M that avoid τ. In this paper, we find a large new class of multiset Wilf equivalent pairs, namely, the pair (σ_n-2(n-1)n, σ_n-2n(n-1)), for n?3 and σ_n-2 a permutation of {1^x₁,2^x₂,…,(n-2)^x_n-2}. It is the most general multiset Wilf equivalence result to date.     

Arithmetic properties of bipartitions with even parts distinct

In this work, we consider various arithmetic properties of the function ped _?2(n) that denotes the number of bipartitions of n with even parts distinct. We prove two infinite families of congruences for p _?2(n) modulo 3. We also give characterizations of ped _?2(n) modulo 2 and 4. Furthermore, for a fixed positive integer k, we show that ped _?2(n) is divisible by 2 ^k for almost all n.     

The Ramsey numbers of paths versus wheels

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let P_n denote a path of order n and W_m a wheel of order m+1. In this paper, we show that R(P_n,W_m)=2n-1 for m even and n?m-1?3 and R(P_n,W_m)=3n-2 for m odd and n?m-1?2.     

Hamiltonian decompositions of complete graphs

It is well known that K_{2n + 1} can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K_{2n + 1} is given and a procedure for obtaining all Hamiltonian decompositions of of K_{2n + 1} is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of K_r (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K_{2n + 1} so that each of the classes forms part of a Hamilton cycle.     

On elliptic curves y=x−nx with rank zero

In this paper we determine all elliptic curves E_n:y²=x³−n²x with the smallest 2-Selmer groups S_n=Sel₂(E_n(Q))={1} and S_n′=Sel₂(E_n′(Q))={±1,±n}(E_n′:y²=x³+4n²x) based on the 2-descent method. The values of n for such curves E_n are described in terms of graph-theory language. It is well known that the rank of the group E_n(Q) for such curves E_n is zero, the order of its Tate-Shafarevich group is odd, and such integers n are non-congruent numbers.     

On a partition identity

Two proofs are given, one combinatorial, the other by character theory, for the identity, ∏_λa₁! a₂! … a_n! = ∏_λ1^a₁2^a₂ … n^a_n, where λ ranges over all partitions λ = (1^a₁2^a₂ … n^a_n) of n. The two demonstrations yield a simple proof of the known formula, det²T(n) = [∏_λ1^a₁2^a₂ … n^a_n]², where T(n) is the matrix formed by the character table of S_n. Finally a sufficient condition is given so that the permanent of T(n) is zero.     

Relative probabilities of majority winners under partial information

Suppose the only observable characteristic of each of n random variables that is uniformly distributed on the six rankings of objects in a three-element set is its first-ranked object. Let ?(n₁,n₂,n₃) be the probability that one of the three objects has majorities over the other two within the rankings when n_j of the n rankings have the jth object in first place. It is assumed that n is odd, so that ?(n₁,n₂,n₃)=1 only if n_j≥(n+1)/2 for some j.It is shown that $\text{?(a+1,b,c)<?(a,b+1,c) if a <b,a ≤ c ≤ b+1}$ and max {b,c}≤(n?1)/2. It follows from this that ? is minimized for fixed n if and only if n_j?n_k≤1 for all j,k? {1,2,3}. However, ? does not necessarily increase when two of its arguments get farther apart. For example, ?(b,b,3)>?(b?1,b+1,3) for b≥28, and ?(b,b,2b?1)>?(b?1,b+1,2b?1) for b≥12.     

On Ramsey numbers of fans

It is shown that r(F₂,F_n)=4n+1 for n≥2, and r(F_s,F_n)≤4n+2s for n≥s≥2.     

On the topology of two partition posets with forbidden block sizes

We study two subposets of the partition lattice obtained by restricting block sizes. The first consists of set partitions of {1,…,n} with block size at most k, for k≤n−2. We show that the order complex has the homotopy type of a wedge of spheres, in the cases 2k+2≥n and n=3k+2. For 2k+2>n, the posets in fact have the same S_n−1-homotopy type as the order complex of Π_n−1, and the S_n-homology representation is the “tree representation” of Robinson and Whitehouse. We present similar results for the subposet of Π_n in which a unique block size k≥3 is forbidden. For 2k≥n, the order complex has the homotopy type of a wedge of (n−4)-spheres. The homology representation of S_n can be simply described in terms of the Whitehouse lifting of the homology representation of Π_n−1.     

Maximal dimensional partially ordered sets III: a characterization of Hiraguchi's inequality for interval dimension

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ?_n such that if |X| ?2n+1, the dim X < n unless X contains one of the posets from ?_n. Although |?₃|=24, for each n ≥ 4, ?_n contains only the crown S⁰_n — the poset consisting of all 1 element and n ? 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S⁰_n.     

Ramanujan-type congruences for broken 2-diamond partitions modulo 3

The notion of broken k-diamond partitions was introduced by Andrews and Paule.Let△k(n)denote the number of broken k-diamond partitions of n.Andrews and Paule also posed three conjectures on the congruences of△2(n)modulo 2,5 and 25.Hirschhorn and Sellers proved the conjectures for modulo 2,and Chan proved the two cases of modulo 5.For the case of modulo 3,Radu and Sellers obtained an infinite family of congruences for△2(n).In this paper,we obtain two infinite families of congruences for△2(n)modulo 3 based on a formula of Radu and Sellers,a 3-dissection formula of the generating function of triangular number due to Berndt,and the properties of the U-operator,the V-operator,the Hecke operator and the Hecke eigenform.For example,we find that△2(243n+142)≡△2(243n+223)≡0(mod 3).The infinite family of Radu and Sellers and the two infinite families derived in this paper have two congruences in common,namely,△2(27n+16)≡△2(27n+25)≡0(mod 3).     

On the determination of a tridiagonal matrix from its spectrum and a submatrix

Given a set of 2n real numbers λ₁<λ₂<?<λ_2n, the authors describe the set {S} of n × n tridiagonal matrices with the property that each S can be completed to a 2n×2n tridiagonal matrix L with spec(L)={λ₁, λ₂,…,λ_2n}.     

Bases for some reciprocity algebras II

We construct bases for the stable branching algebras for the symmetric pairs (GL_n,O_n), (O_n+m,O_n×O_m) and (Sp_2n,GL_n).     

On indecomposable subcones

Let K₁,K₂ be cones. We say that K₁ is a subcone of K₂ if ExtK₁?ExtK₂. Furthermore, if K₁≠K₂, K₁ is called a proper subcone; if dimK₁=dimK₂, K₁ is called a non-degenerate subcone. We first prove that every n-dimensional indecomposable cone, n?3, contains a non-degenerate indecomposable subcone which has no more than 2n-2 extremals. Then we construct for each n?3 an n-dimensional indecomposable cone with exactly 2n-2 extremals such that each of its proper non-degenerate subcones is decomposable.