The polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

Generalized equivalence of pairs of matrices

Pairs (A₁B₁) and (A₂B₂) of matrices over a principal ideal domain R are called the generalized equivalent pairs if A₂=UA₁V₁B₂=UB₁V₂ for some invertible matrices UV₁V₂ over R. A special form is established to which a pair of matrices can be reduced by means of generalized equivalent transformations. Besides necessary and sufficient conditions are found, under which a pair of matrices is generalized equivalent to a pair of diagonal matrices. Applications are made to study the divisibility of matrices and multiplicative property of the Smith normal form.     

Smoothness of the gradient of weak solutions of degenerate linear equations

Let Q(x) be a nonnegative definite, symmetric matrix such that (Q(x))(1/2) is Lipschitz continuous. Given a real-valued function b(x) and a weak solution u(x) of div(Q▽u) = b, we find sufficient conditions in order that Q(1/2)▽u has some first order smoothness. Specifically, if Ω is a bounded open set in R~n, we study when the components of Q(1/2)▽u belong to the first order Sobolev space W_Q~(1,2)(Ω)defined by Sawyer and Wheeden. Alternately, we study when each of n first order Lipschitz vector field derivatives X_iu has some first order smoothness if u is a weak solution in Ω of ∑_(i=1)~n X′_iX_(iu) + b = 0.We do not assume that {X_i} is a Hormander collection of vector fields in Ω. The results signal ones for more general equations.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.     

Bandwidth of the composition of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define w_G(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of w_G(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph.     

Bondage number of strong product of two paths

The bondage number b(G) of a graph G is the cardinality of a minimum set of edges whose removal from G results in a graph with a domination number greater than that of G. In this paper, we obtain the exact value of the bondage number of the strong product of two paths. That is, for any two positive integers m≥2 and n≥2, b(P_m?P_n) = 7 - r(m) - r(n) if (r(m), r(n)) = (1, 1) or (3, 3), 6 - r(m) - r(n) otherwise, where r(t) is a function of positive integer t, defined as r(t) = 1 if t ≡ 1 (mod 3), r(t) = 2 if t ≡ 2 (mod 3), and r(t) = 3 if t ≡ 0 (mod 3).     

Grothendieck rings of a class of Hopf algebras of Kac-Paljutkin type

We construct the Grothendieck rings of a class of 2n²dimensional semisimple Hopf Algebras H_2n²,which can be viewed as a generalization of the 8 dimensional Kac-Paljutkin Hopf algebra H8.All irreducible H_2n²-modules are classified.Furthermore,we describe the Grothendieck rings r(H_2n²)by generators and relations explicitly.