Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.     

The maximum size of a partial 3-spread in a finite vector space over <Emphasis Type="Italic">GF</Emphasis>(2)

Let n ≥ 3 be an integer, let V _n (2) denote the vector space of dimension n over GF(2), and let c be the least residue of n modulo 3. We prove that the maximum number of 3-dimensional subspaces in V _n (2) with pairwise intersection {0} is \frac2ⁿ-2^c7-c{\frac{2^n-2^c}{7}-c} for n ≥ 8 and c = 2. (The cases c = 0 and c = 1 have already been settled.) We then use our results to construct new optimal orthogonal arrays and (s, k, λ)-nets.     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

Menger (N?beling) Manifolds versus Hilbert Cube (Space) Manifolds – A Categorical Comparison

 We show that the n-homotopy category of connected (n+1)-dimensional Menger manifolds is isomorphic to the homotopy category of connected Hilbert cube manifolds whose k-dimensional homotopy groups are trivial for each .     

On the number of affine equivalence classes of spherical tube hypersurfaces

We consider Levi non-degenerate tube hypersurfaces in \mathbbCⁿ⁺¹{\mathbb{C}^{n+1}} that are (k, n − k)-spherical, i.e. locally CR-equivalent to the hyperquadric with Levi form of signature (k, n − k), with n ≤ 2k. We show that the number of affine equivalence classes of such hypersurfaces is infinite (in fact, uncountable) in the following cases: (i) k = n − 2, n ≥ 7; (ii) k = n − 3, n ≥ 7; (iii) k ≤ n − 4. For all other values of k and n, except for k = 3, n = 6, the number of affine classes was known to be finite. The exceptional case k = 3, n = 6 has been recently resolved by Fels and Kaup who gave an example of a family of (3, 3)-spherical tube hypersurfaces that contains uncountably many pairwise affinely non-equivalent elements. In this paper we deal with the Fels–Kaup example by different methods. We give a direct proof of the sphericity of the hypersurfaces in the Fels–Kaup family, and use the j-invariant to show that this family indeed contains an uncountable subfamily of pairwise affinely non-equivalent hypersurfaces.     

On the Existence of Absolutely Simple Abelian Varieties of a Given Dimension over an Arbitrary Field

We prove that for every field k and every positive integer n there exists an absolutely simple n-dimensional abelian variety over k. We also prove an asymptotic result for finite fields: For every finite field k and positive integer n, we let S(k, n) denote the fraction of the isogeny classes of n-dimensional abelian varieties over k that consist of absolutely simple ordinary abelian varieties. Then for every n we have S(F_q, n)→1 as q→∞ over the prime powers.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

Upper bound theorems for homology manifolds

In this paper we prove the Upper Bound Conjecture (UBC) for some classes of (simplicial) homology manifolds: we show that the UBC holds for all odd-dimensional homology manifolds and for all 2k-dimensional homology manifolds Δ such that β _k (Δ)⩽Σ{β _i (Δ):i ≠k-2,k,k+2 and 1 ⩽i⩽2k-1}, where β _i (Δ) are reduced Betti numbers of Δ. (This condition is satisfied by 2k-dimensional homology manifolds with Euler characteristic χ≤2 whenk is even or χ≥2 whenk is odd, and for those having vanishing middle homology.) We prove an analog of the UBC for all other even-dimensional homology manifolds. Kuhnel conjectured that for every 2k-dimensional combinatorial manifold withn vertices, . We prove this conjecture for all 2k-dimensional homology manifolds withn vertices, wheren≥4k+3 orn≤3k+3. We also obtain upper bounds on the (weighted) sum of the Betti numbers of odd-dimensional homology manifolds.     

Non-radial clustered spike solutions for semilinear elliptic problems on s<Superscript>N</Superscript>

We consider the superlinear elliptic equation on Sⁿ

Menger (Nöbeling) Manifolds versus Hilbert Cube (Space) Manifolds – A Categorical Comparison

 We show that the n-homotopy category of connected (n+1)-dimensional Menger manifolds is isomorphic to the homotopy category of connected Hilbert cube manifolds whose k-dimensional homotopy groups are trivial for each . (Received 30 August 1999; in revised form 7 December 1999)     

Equivariant Schubert calculus

We describe T-equivariant Schubert calculus on G(k,n), T being an n-dimensional torus, through derivations on the exterior algebra of a free A-module of rank n, where A is the T-equivariant cohomology of a point. In particular, T-equivariant Pieri’s formulas will be determined, answering a question raised by Lakshmibai, Raghavan and Sankaran (Equivariant Giambelli and determinantal restriction formulas for the Grassmannian, Pure Appl. Math. Quart. 2 (2006), 699–717).     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Sum Complexes—a New Family of Hypertrees

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k−1)-dimensional skeleton and \binomn-1k\binom{n-1}{k} facets such that H _k (X;ℚ)=0. Here we introduce the following family of simplicial complexes. Let n,k be integers with k+1 and n relatively prime, and let A be a (k+1)-element subset of the cyclic group ℤ _n . The sum complex X _A is the pure k-dimensional complex on the vertex set ℤ _n whose facets are σ⊂ℤ _n such that |σ|=k+1 and ∑ _x∈σ x∈A. It is shown that if n is prime, then the complex X _A is a k-hypertree for every choice of A. On the other hand, for n prime, X _A is k-collapsible iff A is an arithmetic progression in ℤ _n .     

Uniform boundedness of <Emphasis Type="Italic">p</Emphasis>-primary torsion of abelian schemes

Let k be a field finitely generated over ℚ and p a prime. The torsion conjecture (resp. p-primary torsion conjecture) for abelian varieties over k predicts that the k-rational torsion (resp. the p-primary k-rational torsion) of a d-dimensional abelian variety A over k should be bounded only in terms of k and d. These conjectures are only known for d=1. The p-primary case was proved by Y. Manin, in 1969; the general case was completed by L. Merel, in 1996, after a series of contributions by B. Mazur, S. Kamienny and others. Due to the fact that moduli of elliptic curves are 1-dimensional, the d=1 case of the torsion conjecture (resp. p-primary torsion conjecture) is closely related to the following. For any k-curve S and elliptic scheme E→S, the k-rational torsion (resp. the p-primary k-rational torsion) is uniformly bounded in the fibres E _s , s∈S(k). In this paper, we extend this result in the p-primary case to arbitrary abelian schemes over curves.     

Reconstruction of functions from their integrals over<Emphasis Type="Italic">k</Emphasis>-planes

Thek-plane Radon transform assigns to a functionsf(x) on ℝ ⁿ the collection of integralsf(τ)=∫ _τ f over allk-dimensional planesτ. We give a systematic treatment of two inversion methods for this transform, namely, the method of Riesz potentials, and the method of spherical means. We develop new analytic tools which allow to invertf(τ) under minimal assumptions forf. It is assumed thatfεL ^p , 1≤p<n/k, orf is a continuous function with minimal rate of decay at infinity. In the framework of the first method, our approach employs intertwining fractional integrals associated to thek-plane transform. Following the second method, we extend the original formula of Radon for continuous functions on ℝ² tofεL ^p (ℝ ⁿ ) and all 1≤k<n. New integral formulae and estimates, generalizing those of Fuglede and Solmon, are obtained. The work was supported in part by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).     

The intersection of subgroups of finite <Emphasis Type="Italic">p</Emphasis>-groups

For a finite p-group G and a positive integer k let I _k (G) denote the intersection of all subgroups of G of order p ^k . This paper classifies the finite p-groups G with I_k(G) @ C_p^k-1{{I}_k(G)\cong C_{p^{k-1}}} for primes p > 2. We also show that for any k, α ≥ 0 with 2(α + 1) ≤ k ≤ n−α the groups G of order p ⁿ with I_k(G) @ C_p^k-a{{I}_k(G)\cong C_{p^{k-\alpha}}} are exactly the groups of exponent p ^n-α .     

On the kernel and shortest face complexes in the unit cube

Studying the extreme kernel face complexes of a given dimension, we obtain some lower estimates of the number of shortest face complexes in the n-dimensional unit cube. The number of shortest complexes of k-dimensional faces is shown to be of the same logarithm order as the number of complexes consisting of at most 2 ⁿ⁻¹ different k-dimensional faces if 1 ≤ k ≤ c · n and c < 0.5. This implies similar lower bounds for the maximum length of the kernel DNFs and the number of the shortest DNFs of Boolean functions.     

Tensor Product Representations of the Lie Superalgebra 𝔭(n) and Their Centralizers

Abstract

We construct an associative algebra A _k and show that there is a representation of A _k on V ^?k , where V is the natural 2n-dimensional representation of the Lie superalgebra 𝔭(n). We prove that A _k is the full centralizer of 𝔭(n) on V ^?k , thereby obtaining a “Schur-Weyl duality” for the Lie superalgebra 𝔭(n). This result is used to understand the representation theory of the Lie superalgebra 𝔭(n). In particular, using A _k we decompose the tensor space V ^?k , for k = 2 or 3, and show that V ^?k is not completely reducible for any k ≥ 2.     

d- Dimensional Dual Hyperovals in PG(d + n, 2) for d + 1 ≤ n ≤ 3d − 7

Assume that d ≥  4. Then there exists a d -dimensional dual hyperoval in PG(d +  n, 2) for d +  1  ≤  n ≤  3 d −  7.