Erd?s-Ko-Rado for three sets

Fix integers k?3 and n?3k/2. Let F be a family of k-sets of an n-element set so that whenever A,B,C∈F satisfy |A∪B∪C|?2k, we have A∩B∩C≠∅. We prove that with equality only when ?_F∈FF≠∅. This settles a conjecture of Frankl and Füredi [2], who proved the result for n?k²+3k.     

Products of reflections in the general linear group over a division ring

Let F be a division ring and A?GL_n(F). We determine the smallest integer k such that A admits a factorization A=R₁R₂?R_k?1B, where R₁,…,R_k?1 are reflections and B is such that rank(B?I_n)=1. We find that, apart from two very special exceptional cases, k=rank(A?I_n). In the exceptional cases k is one larger than this rank. The first exceptional case is the matrices A of the form I_m⊕αI_n?m where n?m?2, α≠?1, and α belongs to the center of F. The second exceptional case is the matrices A satisfying (A?I_n)²=0, rank(A?I_n)?2 in the case when char F≠2 only. This result is used to determine, in the case when F is commutative, the length of a matrix A?GL_n(F) with detA=±1 with respect to the set of all reflections in GL_n(F).     

On the exactness of certain inequalities in approximation theory

We prove the following: for every sequence {F_v}, F_v ? 0, F_v > 0 there exists a functionf such that

1. E_n(f)?F_n (n=0, 1, 2, ...) and
2. A_kn^?k? _v=1 ⁿ v^k?1 F_v?1?Ω_k (f, n^?1) (n=1, 2, ...).

     

Rigidity theorems for hypersurfaces with constant mean curvature

Let M ⁿ be a compact oriented hypersurface of a unit sphere \(\mathbb{S}^{n + 1} \) (1) with constant mean curvature H. Given an integer k between 2 and n ? 1, we introduce a tensor ? related to H and to the second fundamental form A of M, and show that if |?|² ≤ B _H,k and tr(? ³) ≤ C _n,k |?|³, where B _H,k and C _n,k are numbers depending only on H, n and k, then either |?|² ≡ 0 or |?|² ≡ B _H,k . We characterize all M ⁿ with |?|² ≡ B _H,k . We also prove that if \(\left| A \right|^2 \leqslant 2\sqrt {k(n - k)}\) and tr(? ³) ≤ C _n,k |?|³ then |A|² is constant and characterize all M ⁿ with |A|² in the interval \(\left[ {0,2\sqrt {k\left( {n - k} \right)} } \right] \) . We also study the behavior of |?|², with the condition additional tr(? ³) ≤ C _n,k |?|³, for complete hypersurfaces with constant mean curvature immersed in space forms and show that if sup _M |?|² = B _H,k and this supremum is attained in M ⁿ then M ⁿ is an isoparametric hypersurface with two distinct principal curvatures of multiplicities k y n ? k. Finally, we use rotation hypersurfaces to show that the condition on the trace of ? ³ is necessary in our results; more precisely, for each integer k with 2 ≤ k ≤ n ? 1 and \(H \geqslant 1/\sqrt {2n - 1} \) there is a complete hypersurface M ⁿ in \(\mathbb{S}^{n + 1} \) (1) with constant mean curvature H such that sup _M |?|² = B _H,k , and this supremum is attained in M ⁿ , and which is not a product of spheres.     

Some limit results for longest common subsequences

The length l_n of a longest common subsequence before time n sequences (B₁₁, B₁₂, …) (B₂₁, B₂₂, …) is the cardinality of the largest increasing set of pairs of integers {(j_1α, j_2α)}

$\text{l?}\text{j}{}_{11}\text{<}\text{j}{}_{12}\text{<·<}\text{j}{}_{11}{}_{\mathrm{n}}\text{?}\text{n}\text{l?}\text{j}{}_{21}\text{<}\text{j}{}_{22}\text{<·<}\text{j}{}_{21}{}_{\mathrm{n}}\text{?}\text{n}$

such that ?1?α?l_n, (B_1j1α=B_2j2α). If B₁ and B₂ are independent random sequences with co-ordinates i.i.d. uniform on {1, 2, …, k}, it follows from Kingman's subadditive ergodic theorem that the ratio l_n/n converges to a constant c_k a.s. A method of deriving lower bounds for the constants c_k is given, the bounds obtained improving known lower bounds, for k>2. The rate of decrease of c_k with k is shown to be no faster than 1/√k, contrasting with P{B_1i?B_2i}=1/k. Finally, an alternative method of deriving lower bounds is given and used to improve the lower bound for c₂.     

Laurent expansion of an inverse of a function matrix

This paper suggests a general procedure based on the Taylor expansion of a function matrixF(z) for calculating the Laurent expansion ofF ^?1(z) around an isolated pole. It is shown that in order to compute thejth Laurent coefficient matrixB _j ofF ^?1(z), one needs in any case the Taylor coefficientsA ₀, A₁,..., A_2n+j ofF(z), wheren is the order of the pole. Theorem 1 helps to determine the order of the pole, while Theorem 2 shows also how the Laurent coefficients can be computed in the general case.     

The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

On a conjecture of Erdős and Simonovits: Even cycles

Let F be a family of graphs. A graph is F-free if it contains no copy of a graph in F as a subgraph. A cornerstone of extremal graph theory is the study of the Turán number ex(n,F), the maximum number of edges in an F-free graph on n vertices. Define the Zarankiewicz number z(n,F) to be the maximum number of edges in an F-free bipartite graph on n vertices. Let C _k denote a cycle of length k, and let C _k denote the set of cycles C _?, where 3≤?≤k and ? and k have the same parity. Erd?s and Simonovits conjectured that for any family F consisting of bipartite graphs there exists an odd integer k such that ex(n,F ∪ C _k ) ～ z(n,F) — here we write f(n) ～ g(n) for functions f,g: ? → ? if lim _n→∞ f(n)/g(n)=1. They proved this when F ={C ₄} by showing that ex(n,{C ₄;C ₅})～z(n,C ₄). In this paper, we extend this result by showing that if ?∈{2,3,5} and k>2? is odd, then ex(n,C _2? ∪{C _k }) ～ z(n,C _2? ). Furthermore, if k>2?+2 is odd, then for infinitely many n we show that the extremal C _2? ∪{C _k }-free graphs are bipartite incidence graphs of generalized polygons. We observe that this exact result does not hold for any odd k<2?, and furthermore the asymptotic result does not hold when (?,k) is (3, 3), (5, 3) or (5, 5). Our proofs make use of pseudorandomness properties of nearly extremal graphs that are of independent interest.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

Singular integral operators and norm ideals satisfying a quantitative variant of Kuroda's condition

A norm ideal C is said to satisfy condition (QK) if there exist constants 0<t<1 and 0<B<∞, such that ∥X^[k]∥_C?Bk^t∥X∥_C for every finite-rank operator X and every k∈N, where X^[k] denotes the direct sum of k copies of X. Let μ be a regular Borel measure whose support is contained in a unit cube Q in Rⁿ and let K_j be the singular integral operator on L²(Rⁿ,μ) with the kernel function (x_j-y_j)/|x-y|², 1?j?n. Let {Q_w:w∈W} be the usual dyadic decomposition of Q, i.e., {Q_w:|w|=?} is the dyadic partition of Q by cubes of the size 2^-?×?×2^-?. We show that if C satisfies (QK) and if ∥∑_w∈W2^|w|μ(Q_w)ξ_w⊗ξ_w∥_C^′<∞, where C^′ is the dual of C⁽⁰⁾ and {ξ_w:w∈W} is any orthonormal set, then K₁,…,K_n∈C^′. This is a very general obstruction result for the problem of simultaneous diagonalization of commuting tuples of self-adjoint operators modulo C.     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

The Pettis integral for multi-valued functions via single-valued ones

We study the Pettis integral for multi-functions defined on a complete probability space (Ω,Σ,μ) with values into the family cwk(X) of all convex weakly compact non-empty subsets of a separable Banach space X. From the notion of Pettis integrability for such an F studied in the literature one readily infers that if we embed cwk(X) into ?_∞(BX^∗) by means of the mapping defined by j(C)(x^∗)=sup(x^∗(C)), then j○F is integrable with respect to a norming subset of B?_∞^∗(BX^∗). A natural question arises: When is j○F Pettis integrable? In this paper we answer this question by proving that the Pettis integrability of any cwk(X)-valued function F is equivalent to the Pettis integrability of j○F if and only if X has the Schur property that is shown to be equivalent to the fact that cwk(X) is separable when endowed with the Hausdorff distance. We complete the paper with some sufficient conditions (involving stability in Talagrand's sense) that ensure the Pettis integrability of j○F for a given Pettis integrable cwk(X)-valued function F.     

Characterization of similarities between two n-frames of projectors

An n-frame on a Banach space $\text{X}$ is E=(E₁,?, E_n) where the E_j's are bounded linear operators on $\text{X}$ such that E_j≠0,

$\text{∑}\text{j=1}\text{n}\text{E}{}_{\mathrm{j}}$

, and E_jE_k=δ_jkE_k (j, k=1,?, n). It is known that if two n-frames E and F are sufficiently close to each other, then they are similar, that is, F_j=TE_jT^-1 with T a bounded linear operator. Among the operators which realize the similarity of the two frames, there is the balanced transformation U(F, E)=(Σⁿ_j=1F_jE_j)(Σⁿ_j=1E_jF_jE_j)^{$\text{-1}\text{2}$}. One of our main results is a local characterization of the balanced transformation. Another operator which implements the similarity between E and F is the direct rotation R(F, E). It comes up in connection with the study of the set of all n-frames as a Banach manifold with an affine connection. Finally, it is shown that for quite a large set of pairs of 2-frames, the direct rotation has a global characterization.     

The diagnonal multivariate natural exponential families and their classification

A natural exponential family (NEF)F in ? ⁿ ,n>1, is said to be diagonal if there existn functions,a ₁,...,a _n , on some intervals of ?, such that the covariance matrixV _F (m) ofF has diagonal (a ₁(m ₁),...,a _n (m _n )), for allm=(m ₁,...,m _n ) in the mean domain ofF. The familyF is also said to be irreducible if it is not the product of two independent NEFs in ? ^k and ? ^n-k , for somek=1,...,n?1. This paper shows that there are only six types of irreducible diagonal NEFs in ? ⁿ , that we call normal, Poisson, multinomial, negative multinomial, gamma, and hybrid. These types, with the exception of the latter two, correspond to distributions well established in the literature. This study is motivated by the following question: IfF is an NEF in ? ⁿ , under what conditions is its projectionp(F) in ? ^k , underp(x ₁,...,x _n )∶=(x ₁,...,x _k ),k=1,...,n?1, still an NEF in ? ^k ? The answer turns out to be rather predictable. It is the case if, and only if, the principalk×k submatrix ofV _F (m ₁,...,m _n ) does not depend on (m _k+1,...,m _n ).     

Fluctuations of the empirical quantiles of independent Brownian motions

We consider iid Brownian motions, B_j(t), where B_j(0) has a rapidly decreasing, smooth density function f. The empirical quantiles, or pointwise order statistics, are denoted by B_j:n(t), and we consider a sequence Q_n(t)=B_j(n):n(t), where j(n)/n→α∈(0,1). This sequence converges in probability to q(t), the α-quantile of the law of B_j(t). We first show convergence in law in C[0,∞) of F_n=n^1/2(Q_n−q). We then investigate properties of the limit process F, including its local covariance structure, and Hölder-continuity and variations of its sample paths. In particular, we find that F has the same local properties as fBm with Hurst parameter H=1/4.     

An extension of Birkhoff’s theorem with an application to determinants

Let M_n(F) denote the algebra of n×n matrices over the field F of complex, or real, numbers. Given a self-adjoint involution J∈M_n(C), that is, J=J^*,J²=I, let us consider Cⁿ endowed with the indefinite inner product [,] induced by J and defined by [x,y]?〈Jx,y〉,x,y∈Cⁿ. Assuming that (r,n-r), 0?r?n, is the inertia of J, without loss of generality we may assume J=diag(j₁,?,j_n)=I_r⊕-I_n-r. For T=(|t_ik|²)∈M_n(R), the matrices of the form T=(|t_ik|²j_ij_k), with all line sums equal to 1, are called J-doubly stochastic matrices. In the particular case r∈{0,n}, these matrices reduce to doubly stochastic matrices, that is, non-negative real matrices with all line sums equal to 1. A generalization of Birkhoff’s theorem on doubly stochastic matrices is obtained for J-doubly stochastic matrices and an application to determinants is presented.     

Conditions under which the order of two non-negative Hermitian matrices is preserved when taking integral powers

Let A and B be two n×n non-negative matrices. We write A ? B iff

$\text{u}{}^1\text{(A ? B)u ? 0}$

for all column vectors u in Cⁿ. Here u¹ is the conjugate transpose of u. In this paper are stated equivalent conditions under which A^k ? B^k for all natural numbers k. The result is then generalized to Hermitian operators in a Hilbert space.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.