On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

Reconstruction from vertex-switching

Let X be a graph with vertices x₁ ,…, x_n. Let X_i be the graph obtained by removing all edges {x_i, x_j} of X and inserting all nonedges {x_i, x_k}. If n ? 0 (mod 4), then X can be uniquely reconstructed from the unlabeled graphs X₁.…, X_n. If n = 4 the result is false, while for n = 4m≥8 the result remains open. The proof uses linear algebra and does not explicitly describe the reconstructed graph X.     

Jointly ergodic measure-preserving transformations

The notion of ergodicity of a measure-preserving transformation is generalized to finite sets of transformations. The main result is that ifT ₁,T ₂, …,T _s are invertible commuting measure-preserving transformations of a probability space (X, ?, μ) then 1 $$\frac{1}{{N - M}}\sum\limits_{n = M}^{N - 1} {T{}_1^n } f_1 .T_2^n f_2 .....T_s^n f_s \xrightarrow[{N - M \to \propto }]{{I^2 (X)}}(\int_X {f1d\mu )} (\int_X {f2d\mu )...(\int_X {fsd\mu )} } $$ for anyf ₁,f ₂, …,f _s∈L ^x (X, ?, μ) iffT ₁×T ₂×…×T _s and all the transformationsT _iT_j ¹,i≠j, are ergodic. The multiple recurrence theorem for a weakly mixing transformation follows as a special case.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

A note on the kernels of higher derivations

Let k ? k′ be a field extension. We give relations between the kernels of higher derivations on k[X] and k′[X], where k[X]:= k[x ₁,…, x _n ] denotes the polynomial ring in n variables over the field k. More precisely, let D = {D _n } _n=0 ^∞ a higher k-derivation on k[X] and D′ = {D′ _n } _n=0 ^∞ a higher k′-derivation on k′[X] such that D′ _m (x _i ) = D _m (x _i ) for all m ? 0 and i = 1, 2,…, n. Then (1) k[X] ^D = k if and only if k′[X] ^D′ = k′; (2) k[X] ^D is a finitely generated k-algebra if and only if k′[X] ^D′ is a finitely generated k′-algebra. Furthermore, we also show that the kernel k[X] ^D of a higher derivation D of k[X] can be generated by a set of closed polynomials.     

A Fisher type inequality

In this paper we study subsets of a finite set that intersect each other in at most one element. Each subset intersects most of the other subsets in exactly one element. The following theorem is one of our main conclusions. Let S₁,… S_m be m subsets of an n-set S with |S₁| ? 2 (l = 1, …,m) and |S_i ∩ S_j| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each S_i has non-empty intersection with at least m ? c of the remaining subsets. Then there is a least positive integer M(c) depending only on c such that either m ? n or m ? M(c).     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

A fundamental inequality for the sum of sets of m-tuples

For n a positive integer and A₁, A₂, …, A_k sets of nonnegative integers, sufficient conditions are found which imply that the sum of the cardinalities of the sets $\text{{1, 2, …, n} ? A}{}_{\mathrm{i}}\text{(i = 1, 2, …, k)}$ does not exceed the cardinality of the intersection of {1, 2, …, n} and the number theoretic sum of the k sets. Some of the results are generalized to sets of m-tuples of nonnegative integers.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Sets of Double and Triple Weights of Trees

Let T be a weighted tree with n leaves numbered by the set {1, . . . , n}. Let D _{i, j} (T) be the distance between the leaves i and j. Let D_i,j,k(T) = \frac12(D_i,j(T)+D_j,k(T)+D_i,k(T)){{D_{i,j,k}(T) = \frac{1}{2}(D_{i,j}(T)+D_{j,k}(T)+D_{i,k}(T))}} . We will call such numbers “triple weights” of the tree. In this paper, we give a characterization, different from the previous ones, for sets indexed by 2-subsets of a n-set to be double weights of a tree. By using the same ideas, we find also necessary and sufficient conditions for a set of real numbers indexed by 3-subsets of an n-set to be the set of the triple weights of a tree with n leaves. Besides we propose a slight modification of Saitou-Nei’s Neighbour-Joining algorithm to reconstruct trees from the data D _{i, j} .     

On multi-coloured lines in a linear space

We prove that if X₁, X₂,…, X_k are pairwise disjoint sets of points in a linear space, each of cardinality n, whose union ∪_{j = 1}^kX_j, is not collinear, then there are at least (k ? 1) n lines in the space, which intersect at least two of th e X_j's. Equality occurs if and only if k = n + 1 and X₁,…, X_{n + 1} are obtained by taking n + 1 concurrent lines in a projective plane of order n, and omitting, from each of them, their common point. When n = 1, this reduces to a theorem of de Bruijn and Erdos (Indag. Math.10 (1984), 421–423).     

Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.     

Maps preserving the spectrum of generalized Jordan product of operators

Let A₁,A₂ be standard operator algebras on complex Banach spaces X₁,X₂, respectively. For k?2, let (i₁,…,i_m) be a sequence with terms chosen from {1,…,k}, and define the generalized Jordan product

     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

A unique exchange property for bases

We define the concept of unique exchange on a sequence (X₁,…, X_m) of bases of a matroid M as an exchange of x ? X_i for y ? X_j such that y is the unique element of X_j which may be exchanged for x so that (X_i ? {x}) ∪ {y} and (X_j ? {y}) ∪ {x} are both bases. Two sequences X and Y are compatible if they are on the same multiset. Let UE(1) [UE(2)] denote the class of matroids such that every pair of compatible basis sequences X and Y are related by a sequence of unique exchanges [unique exchanges and permutations in the order of the bases]. We similarly define UE(3) by allowing unique subset exchanges. Then UE(1),UE(2), and UE(3) are hereditary classes (closed under minors) and are self-dual (closed under orthogonality). UE(1) equals the class of series-parallel networks, and UE(2) and UE(3) are contained in the class of binary matroids. We conjecture that UE(2) contains the class of unimodular matroids, and prove a related partial result for graphic matroids. We also study related classes of matroids satisfying transitive exchange, in order to gain information about excluded minors of UE(2) and UE(3). A number of unsolved problems are mentioned.     

Maximizing the probability of correctly ordering random variables using linear predictors

Let (T₁, x₁), (T₂, x₂), …, (T_n, x_n) be a sample from a multivariate normal distribution where T_i are (unobservable) random variables and x_i are random vectors in R^k. If the sample is either independent and identically distributed or satisfies a multivariate components of variance model, then the probability of correctly ordering {T_i} is maximized by ranking according to the order of the best linear predictors {E(T_i|x_i)}. Furthermore, it orderings are chosen according to linear functions {b′x_i} then the conditional probability of correct order given (T_i = t₁; i = 1, …, n) is maximized when b′x_i is the best linear predictor. Examples are given to show that linear predictors may not be optimal and that using a linear combination other that the best linear predictor may give a greater probability of correctly ordering {T_i} if {(T_i, x_i)} are independent but not identically distributed, or if the distributions are not normal.     

Conditional ordering of order statistics

For any positive integers m and n, let X₁,X₂,…,X_m∨n be independent random variables with possibly nonidentical distributions. Let X_1:n≤X_2:n≤?≤X_n:n be order statistics of random variables X₁,X₂,…,X_n, and let X_1:m≤X_2:m≤?≤X_m:m be order statistics of random variables X₁,X₂,…,X_m. It is shown that (X_j:n,X_j+1:n,…,X_n:n) given X_i:m>y for j−i≥max{n−m,0}, and (X_1:n,X_2:n,…,X_j:n) given X_i:m≤y for j−i≤min{n−m,0} are all increasing in y with respect to the usual multivariate stochastic order. We thus extend the main results in Dubhashi and Häggström (2008) [1] and Hu and Chen (2008) [2].