A proof of Hessian Sobolev inequality

In this paper, taking the Hessian Sobolev inequality (0<p≤k) (X.-J. Wang, 1994 [2]) as the starting point, we give a proof of the Hessian Sobolev inequality when k<p≤k^∗, where k^∗ is the critical Sobolev embedding index of k-Hessian type. We also prove that k^∗ is optimal by one-dimensional Hardy’s inequality.     

Currents carried by the subgradient graphs of semi-convex functions and applications to Hessian measures

In this paper we study integer multiplicity rectifiable currents carried by the subgradient (subdifferential) graphs of semi-convex functions on an n-dimensional convex domain, and show a weak continuity theorem with respect to pointwise convergence for such currents. As an application, the structure theorem of the Lagrangian currents for semi-convex functions is given and the k-Hessian measures are calculated by a different method in terms of currents.     

k-intolerant capacities and Choquet integrals

We define an aggregation function to be (at most) k-intolerant if it is bounded from above by its kth lowest input value. Applying this definition to the discrete Choquet integral and its underlying capacity, we introduce the concept of k-intolerant capacities which, when varying k from 1 to n, cover all the possible capacities on n objects. Just as the concepts of k-additive capacities and p-symmetric capacities have been previously introduced essentially to overcome the problem of computational complexity of capacities, k-intolerant capacities are proposed here for the same purpose but also for dealing with intolerant or tolerant behaviors of aggregation. We also introduce axiomatically indices to appraise the extent to which a given capacity is k-intolerant and we apply them on a particular recruiting problem.     

Moser-Trudinger type inequalities for the Hessian equation

The k-Hessian equation for k?2 is a class of fully nonlinear partial differential equation of divergence form. A Sobolev type inequality for the k-Hessian equation was proved by the second author in 1994. In this paper, we prove the Moser-Trudinger type inequality for the k-Hessian equation.     

Automatic differentiation: Reduced gradient and reduced Hessian matrix

This paper is concerned with automatic differentiation methods for computing the reduced gradient M ^t G and the reduced Hessian matrix M ^t HM. Hereby G is the gradient and H is the Hessian matrix of a real function F of n variables, and M is a matrix with n rows and k columns where kn. The reduced quantities are of particular interest in constrained optimization with objective function F. Two automatic differentiation methods are described, a standard method that produces G and H as intermediate results, and an economical method that takes a shortcut directly to the reduced quantites. The two methods are compared on the basis of the reqired computing time and storage. It is shown that the costs for the economical method are less than (k ²+3k+2)/(n ²+3n+2) times the expenses for the standard method.     

The graphs G(n, k) of the Johnson Schemes are unique for n ≥ 20

Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.     

Highly connected monochromatic subgraphs

We conjecture that for n>4(k-1) every 2-coloring of the edges of the complete graph K_n contains a k-connected monochromatic subgraph with at least n-2(k-1) vertices. This conjecture, if true, is best possible. Here we prove it for k=2, and show how to reduce it to the case n<7k-6. We prove the following result as well: for n>16k every 2-colored K_n contains a k-connected monochromatic subgraph with at least n-12k vertices.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

Further gossip problems

n people have distinct bits of information. They can communicate via k-party conference calls. How many such calls are needed to inform everyone of everyone else's information? Let f(n,k) be this minimum number. Then we give a simple proof that f(n,k)= [(n?k)(k?1)]+[nk] for 1?n?k², f(n,k)=2[(n?k)(k?1)] for n>k².In the 2-party case we consider the case in which certain of the calls may permit information flow in only one direction. We show that any 2n-4 call scheme that conveys everone's information to all must contain a 4-cycle, each of whose calls is “two way”, along with some other results. The method follows that of Bumby who first proved the 4-cycle conjecture.     

Homology representations arising from the half cube

We construct a CW decomposition Cn of the n-dimensional half cube in a manner compatible with its structure as a polytope. For each 3?k?n, the complex Cn has a subcomplex Cn,k, which coincides with the clique complex of the half cube graph if k=4. The homology of Cn,k is concentrated in degree k−1 and furthermore, the (k−1)st Betti number of Cn,k is equal to the (k−2)nd Betti number of the complement of the k-equal real hyperplane arrangement. These Betti numbers, which also appear in theoretical computer science, numerical analysis and engineering, are the coefficients of a certain Pascal-like triangle (Sloane's sequence A119258). The Coxeter groups of type Dn act naturally on the complexes Cn,k, and thus on the associated homology groups.     

Perfect matchings in large uniform hypergraphs with large minimum collective degree

We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.     

Positivity of Riesz functionals and solutions of quadratic and quartic moment problems

We employ positivity of Riesz functionals to establish representing measures (or approximate representing measures) for truncated multivariate moment sequences. For a truncated moment sequence y, we show that y lies in the closure of truncated moment sequences admitting representing measures supported in a prescribed closed set K⊆Rn if and only if the associated Riesz functional Ly is K-positive. For a determining set K, we prove that if Ly is strictly K-positive, then y admits a representing measure supported in K. As a consequence, we are able to solve the truncated K-moment problem of degree k in the cases: (i) (n,k)=(2,4) and K=R²; (ii) n?1, k=2, and K is defined by one quadratic equality or inequality. In particular, these results solve the truncated moment problem in the remaining open cases of Hilbert's theorem on sums of squares.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Extremal edge problems for graphs with given hyperoctahedral automorphism group

For k > 1, let H_k denote the hyperoctahedral group S_k[S₂] of order 2^kk!. An (H_k, n)- graph is a graph on n vertices with automorphism group abstractly isomorphic to H_k. For each k an (H_k, n)-graph exists precisely when n ? 2k; for each n ? 2k the minimum and maximum number of edges possible for such graphs are determined. The analogous results for connected (H_k, n)-graphs are also obtained.     

Reliability and covariance estimation of weighted k-out-of-n multi-state systems

In the literature of reliability engineering, reliability of the weighted k-out-of-n system can be calculated using component reliability based on the structure function. The calculation usually assumes that the true component reliability is completely known. However, this is not the case in practical applications. Instead, component reliability has to be estimated using empirical sample data. Uncertainty arises during this estimation process and propagates to the system level. This paper studies the propagation mechanism of estimation uncertainty through the universal generating function method. Equations of the complete solution including the unbiased system reliability estimator and the corresponding unbiased covariance estimator are derived. This is a unified approach. It can be applied to weighted k-out-of-n systems with multi-state components, to weighted k-out-of-n systems with binary components, and to simple series and parallel systems. It may also serve as building blocks to derive estimators of system reliability and uncertainty measures for more complicated systems.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

On some friends of the sociable numbers

Let s(n) denote the sum of the proper divisors of n. Set s ₀(n) = n, and for k > 0, put s _k (n) := s(s _k-1(n)) if s _k-1(n) > 0. Thus, perfect numbers are those n with s(n)?=?n and amicable numbers are those n with s(n) ?? n but s ₂(n)?=?n. We prove that for each fixed k ?? 1, the set of n which divide s _k (n) has density zero, and similarly for the set of n for which s _k (n) divides n. These results generalize the theorem of Erd?s that for each fixed k, the set of n for which s _k (n)?=?n has density zero.     

On the number of combinations without unit separation

Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if $\text{n ? 2(k ? 1), f(n,k)=}\text{∑}\text{i=0}\text{κ}\text{(}\text{n?k+I?2i}\text{k?2i}\text{)}$ (where $\text{κ = [}\text{k}\text{2}\text{]}$). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then $\text{(n,k)=(}\text{n?k}\text{k}\text{)+(}\text{n?k?1}\text{k?1}\text{)}$.     

On shortest crucial words avoiding abelian powers

Let k≥2 be an integer. An abeliankth power is a word of the form X₁X₂?X_k where X_i is a permutation of X₁ for 2≤i≤k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelian kth power for any letter x occurring in W.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4n−7 for n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−13 for n≥5. They have also conjectured that for any k≥4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ?_k(n), is k²n−(k²+k+1). This is currently the best known upper bound for ?_k(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1) for n≥5 and k≥4. In this note, we improve this lower bound by proving that for n≥2k−1, ?_k(n)≥k²n−(2k³−3k²+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).