A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

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.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

On the sharpness of Bruen’s bound for intersection sets in Desarguesian affine spaces

In this note we investigate the sharpness of Bruen’s bound on the size of a t-fold blocking set in \(AG(n,q)\) with respect to the hyperplanes. We give a construction for t-fold blocking sets meeting Bruen’s bound with \(t=q-n+2\) . This construction is used further to find the minimal size of a t-fold affine blocking set with \(t=q-n+1\) . We prove that for blocking sets in the geometries \(AG(n,2)\) the difference between the size of an optimal t-fold blocking set and tn exceeds any given number. In particular, we deviate infinitely from Bruen’s bound as n goes to infinity. We conclude with a construction that gives t-fold blocking sets with \(t=q-n+3\) whose size is close to the lower bounds known so far.     

On properties of integrals of the Legendre polynomial

Properties of the integrals $P_{n0} (x) = P_n (x),P_{nk} (x) = \int\limits_{ - 1}^x {P_{n,k - 1} (y)dy} $ of the Legendre polynomials P _n (x) on the base interval ?1 ≤ x ≤ 1 are systematically considered. The generating function $(1 - 2xz + z^2 )^{k - 1/2} = Q_k (x,z) + ( - 1)^k (2k - 1)!!\sum\limits_{n = k}^\infty {P_{nk} (x)z^{n + k} } $ is defined; here, Q ₀ = 0 and Q _k with k > 0 is a polynomial of degree 2k ? 1 in each of the variables x and z. A second-order differential equation is derived, an analogue of Rodrigues’ formula is obtained, and the asymptotic behavior as n → ∞ is determined. It is proved that the representation $P_{nk} (x) = (x^2 - 1)^k f_{nk} (x)$ holds if and only if n ≥ k, where f _nk is a polynomial divisible by neither x ? 1 nor x + 1. The main result is the sharp bound $|P_{nk} (\cos \theta )| < \frac{{A_k }} {{\nu ^{k + 1/2} }}\sin ^{k - 1/2} \theta ,n \geqslant k.$ Here, $\nu ^2 = \left( {n + \frac{1} {2}} \right)^2 - \left( {k^2 - \frac{1} {4}} \right)\left( {1 - \frac{4} {{\pi ^2 }}} \right),A_k = \sqrt t _k J_k (t_k ) \sim \mu _1 k^{1/6} ,\mu _1 = 0.674885, $ where t _k is the maximum of the function $\sqrt t J_k (t)$ on the half-axis t > 0 and J _k (t) is the Bessel function. The first values A _k and differences A _k ? μ₁ k ^1/6 are tabulated below as follows:      

Structural and geometric characteristics of sets of convergence and divergence of multiple Fourier series with J k -lacunary sequence of rectangular partial sums

We study multiple trigonometric Fourier series of functions f in the classes $L_p \left( {\mathbb{T}^N } \right)$ , p > 1, which equal zero on some set $\mathfrak{A}, \mathfrak{A} \subset \mathbb{T}^N , \mu \mathfrak{A} > 0$ (µ is the Lebesgue measure), $\mathbb{T}^N = \left[ { - \pi ,\pi } \right]^N$ , N ≥ 3. We consider the case when rectangular partial sums of the indicated Fourier series S _n (x; f) have index n = (n ₁, ..., n _N ) ∈ ? ^N , in which k (k ≥ 1) components on the places {j ₁, ..., j _k } = J _k ? {1, ..., N} are elements of (single) lacunary sequences (i.e., we consider multiple Fourier series with J _k -lacunary sequence of partial sums). A correlation is found of the number k and location (the “sample” J _k ) of lacunary sequences in the index n with the structural and geometric characteristics of the set $\mathfrak{A}$ , which determines possibility of convergence almost everywhere of the considered series on some subset of positive measure $\mathfrak{A}_1$ of the set $\mathfrak{A}$ .     

Large deviations of the first passage time for a random walk with semiexponentially distributed jumps

Suppose that ξ, ξ(1), ξ(2), ... are independent identically distributed random variables such that ?ξ is semiexponential; i.e., $P( - \xi \geqslant t) = e^{ - t^\beta L(t)} $ is a slowly varying function as t → ∞ possessing some smoothness properties. Let E ξ = 0, D ξ = 1, and S(k) = ξ(1) + ? + ξ(k). Given d > 0, define the first upcrossing time η ₊(u) = inf{k ≥ 1: S(k) + kd > u} at nonnegative level u ≥ 0 of the walk S(k) + kd with positive drift d > 0. We prove that, under general conditions, the following relation is valid for $u = (n) \in \left[ {0, dn - N_n \sqrt n } \right]$ : 0.1 $P(\eta + (u) > n) \sim \frac{{E\eta + (u)}}{n}P(S(n) \leqslant x) as n \to \infty $ , where x = u ? nd < 0 and an arbitrary fixed sequence N _n not exceeding $d\sqrt n $ tends to ∞. The conditions under which we prove (0.1) coincide exactly with the conditions under which the asymptotic behavior of the probability P(S(n) ≤ x) for $x \leqslant - \sqrt n $ was found in [1] (for $x \in \left[ { - \sqrt n ,0} \right]$ it follows from the central limit theorem).     

The Two-Weighted Inequalities for Sublinear Operators Generated by B Singular Integrals in Weighted Lebesgue Spaces

In this paper, the authors establish several general theorems for the boundedness of sublinear operators (B sublinear operators) satisfies the condition (1.2), generated by B singular integrals on a weighted Lebesgue spaces $L_{p,\omega,\gamma}(\mathbb{R}_{k,+}^{n})$ , where $B=\sum_{i=1}^{k} (\frac{\partial^{2}}{\partial x_{k}^{2}} + \frac{\gamma_{i}}{x_{i}}\frac{\partial}{\partial x_{i}} )$ . The condition (1.2) are satisfied by many important operators in analysis, including B maximal operator and B singular integral operators. Sufficient conditions on weighted functions ω and ω ₁ are given so that B sublinear operators satisfies the condition (1.2) are bounded from $L_{p,\omega,\gamma}(\mathbb{R}_{k,+}^{n})$ to $L_{p,\omega_{1},\gamma}(\mathbb{R}_{k,+}^{n})$ .     

Predual Spaces of Banach Completions of Orlicz-Hardy Spaces Associated with Operators

Let L be a linear operator in L ²(? ⁿ ) and generate an analytic semigroup {e ^?tL } _t??0 with kernels satisfying an upper bound of Poisson type, whose decay is measured by ??(L)??(0,??]. Let ?? on (0,??) be of upper type 1 and of critical lower type $\widetilde{p}_{0}(\omega)\in(n/(n+\theta(L)),1]$ and ??(t)=t ^?1/?? ^?1(t ^?1) for t??(0,??). In this paper, the authors first introduce the VMO-type space VMO _??,L (? ⁿ ) and the tent space $T^{\infty}_{\omega,\mathrm{v}}({\mathbb{R}}^{n+1}_{+})$ and characterize the space VMO _??,L (? ⁿ ) via the space $T^{\infty}_{\omega,\mathrm{v}}({{\mathbb{R}}}^{n+1}_{+})$ . Let $\widetilde{T}_{\omega}({{\mathbb{R}}}^{n+1}_{+})$ be the Banach completion of the tent space $T_{\omega}({\mathbb{R}}^{n+1}_{+})$ . The authors then prove that $\widetilde{T}_{\omega}({\mathbb{R}}^{n+1}_{+})$ is the dual space of $T^{\infty}_{\omega,\mathrm{v}}({\mathbb{R}}^{n+1}_{+})$ . As an application of this, the authors finally show that the dual space of $\mathrm{VMO}_{\rho,L^{\ast}}({\mathbb{R}}^{n})$ is the space B _??,L (? ⁿ ), where L ^* denotes the adjoint operator of L in L ²(? ⁿ ) and B _??,L (? ⁿ ) the Banach completion of the Orlicz-Hardy space H _??,L (? ⁿ ). These results generalize the known recent results by particularly taking ??(t)=t for t??(0,??).     

A small minimal blocking set in PG(n, p t ), spanning a (t − 1)-space, is linear

In this paper, we show that a small minimal blocking set with exponent e in PG(n, p ^t ), p prime, spanning a (t/e ? 1)-dimensional space, is an ${\mathbb{F}_{p^e}}$ -linear set, provided that p > 5(t/e)?11. As a corollary, we get that all small minimal blocking sets in PG(n, p ^t ), p prime, p > 5t ? 11, spanning a (t ? 1)-dimensional space, are ${\mathbb{F}_p}$ -linear, hence confirming the linearity conjecture for blocking sets in this particular case.     

Degenerate differential operators in weighted Hölder spaces

A differential operator ?, arising from the differential expression $$lv(t) \equiv ( - 1)^r v^{[n]} (t) + \sum\nolimits_{k = 0}^{n - 1} {p_k } (t)v^{[k]} (t) + Av(t),0 \leqslant t \leqslant 1,$$ , and system of boundary value conditions $$P_v [v] = \sum\nolimits_{k = 0}^{n_v } {\alpha _{vk} } r^{[k]} (1) = 0.v - 1, \ldots ,\mu ,0 \leqslant \mu< n$$ is considered in a Banach space E. Herev ^[k](t)=(a(t) d/dt) ^k v(t)a(t) being continuous fort?0, α(t) >0 for t > 0 and \(\int_0^1 {\frac{{dz}}{{a(z)}} = + \infty ;}\) the operator A is strongly positive in E. The estimates , are obtained for ?: n even, λ varying over a half plane.     

The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold 2

It is shown that the conjunction complexity L _k ^& (f ₂ ⁿ ) of monotone symmetric Boolean functions \(f_2^n (x_1 , \ldots ,x_n ) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_i x_j\) realized by k-self-correcting circuits in the basis B = {&, ?} asymptotically equals to (k + 2)n for growing n providing the price of a reliable conjunctor is ≥ k + 2.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

On the cohomology of the orthosymplectic superalgebra

Let $\mathfrak{F}_{\lambda}^{n}$ be the $\mathop {\mathfrak {osp}}\nolimits \,(n|2)$ -module of weighted densities on ?^1|n of weight ??. We compute the cohomology spaces $\mathrm{H}^{k}_{\mathrm{diff}}\left(\mathop {\mathfrak {osp}}\nolimits \,(n|2),\mathfrak{F}_{\lambda}^{n}\right)$ , where k=1 and n=0,1,2 or k=2 and n=0,1. We explicitly give cocycles spanning these cohomology spaces.     

Cone Dependence—A Basic Combinatorial Concept

We call A ? $ \mathbb{E} $ ⁿ cone independent of B ? $ \mathbb{E} $ ⁿ , the euclidean n-space, if no a = (a ₁,..., a _n ) ∈ A equals a linear combination of B \ {a} with non-negative coefficients. If A is cone independent of A we call A a cone independent set. We begin the analysis of this concept for the sets P(n) = {A ? {0, 1} ⁿ ? $ \mathbb{E} $ ⁿ : A is cone independent} and their maximal cardinalities c(n) ? max{|A| : A ∈ P(n)}. We show that lim _{n → ∞} $ \frac{{c\left( n \right)}}{{2^n }} $ > $\frac{1}{2}$ , but can't decide whether the limit equals 1. Furthermore, for integers 1 < k < ? ≤ n we prove first results about c _n (k, ?) ? max{|A| : A ∈ P _n (k, ?)}, where P _n (k, ?) = {A : A ? V ⁿ _k and V ⁿ _? is cone independent of A} and V ⁿ _k equals the set of binary sequences of length n and Hamming weight k. Finding c _n (k, ?) is in general a very hard problem with relations to finding Turan numbers.     

Isothermic Submanifolds

We propose an answer to a question raised by F. Burstall: Is there any interesting theory of isothermic submanifolds of ? ⁿ of dimension greater than two? We call an n-immersion f(x) in ? ^m isothermic _k if the normal bundle of f is flat and x is a line of curvature coordinate system such that its induced metric is of the form $\sum_{i=1}^{n} g_{ii}\,\mathrm{d} x_{i}^{2}$ with $\sum_{i=1}^{n} \epsilon_{i} g_{ii}=0$ , where ?? _i =1 for 1??i??n?k and ?? _i =?1 for n?k<i??n. A smooth map (f ₁,??,f _n ) from an open subset ${\mathcal{O}}$ of ? ⁿ to the space of m×n matrices is called an n-tuple of isothermic _k n-submanifolds in ? ^m if each f _i is an isothermic _k immersion, $(f_{i})_{x_{j}}$ is parallel to $(f_{1})_{x_{j}}$ for all 1??i,j??n, and there exists an orthonormal frame (e ₁,??,e _n ) and a GL(n)-valued map (a _ij ) such that $\mathrm{d}f_{i}= \sum_{j=1}^{n} a_{ij} e_{j}\,\mathrm {d} x_{j}$ for 1??i??n. Isothermic₁ surfaces in ?³ are the classical isothermic surfaces in ?³. Isothermic _k submanifolds in ? ^m are invariant under conformal transformations. We show that the equation for n-tuples of isothermic _k n-submanifolds in ? ^m is the $\frac{O(m+n-k,k)}{O(m)\times O(n-k,k)}$ -system, which is an integrable system. Methods from soliton theory can therefore be used to construct Christoffel, Ribaucour, and Lie transforms, and to describe the moduli spaces of these geometric objects and their loop group symmetries.     

Generating sets of finite singular transformation semigroups

J.M. Howie proved that $\operatorname {Sing}_{n}$ , the semigroup of all singular mappings of {1,…,n} into itself, is generated by its idempotents of defect 1 (in J. London Math. Soc. 41, 707–716, 1966). He also proved that if n≥3 then a minimal generating set for $\operatorname {Sing}_{n}$ contains n(n?1)/2 transformations of defect 1 (in Gomes and Howie, Math. Proc. Camb. Philos. Soc. 101. 395–403, 1987). In this paper we find necessary and sufficient conditions for any set for transformations of defect 1 in $\operatorname {Sing}_{n}$ to be a (minimal) generating set for $\operatorname {Sing}_{n}$ .     

Subspace Arrangements of Type B n and D n

Let ${\mathcal{D}}_{n,k} $ be the family of linear subspaces of ?ⁿ given by all equations of the form $\varepsilon _1 x_{i_1 } = \varepsilon _2 x_{i_2 } = \cdot \cdot \cdot \varepsilon _k x_{i_k } ,$ for 1 ≤ < ? ? ? < i _k ≤ i and $\left( {\varepsilon _1 ,...,\varepsilon _k } \right)\varepsilon \left\{ { + 1, - 1} \right\}^k $ Also let ${\mathcal{B}}_{n,k,h} $ be ${\mathcal{D}}_{n,k} $ enlarged by the subspaces $x_{j_1 } = x_{j_2 } = \cdot \cdot \cdot x_{j_h } = 0,$ for 1 ≤. The special cases ${\mathcal{B}}_{n,2,1} $ and ${\mathcal{D}}_{n,2} $ are well known as the reflection hyperplane arrangements corresponding to the Coxeter groups of type B _nand D _n respectively. In this paper we study combinatorial and topological properties of the intersection lattices of these subspace arrangements. Expressions for their Möbius functions and characteristic polynomials are derived. Lexicographic shellability is established in the case of ${\mathcal{B}}_{n,k,h,} 1 \leqslant h < k$ , which allows computation of the homology of its intersection lattice and the cohomology groups of the manifold $\begin{gathered} {\mathcal{D}}_{n,2} \\ M_{n,k,h,} = {\mathbb{R}}^n \backslash \bigcup {{\mathcal{B}}_{n,k,h,} } \\ \end{gathered} $ . For instance, it is shown that $H^d \left( {M_{n,k,k - 1} } \right)$ is torsion-free and is nonzero if and only if d = t(k ? 2) for some $t,0 \leqslant t \leqslant \left[ {{n \mathord{\left/ {\vphantom {n k}} \right. \kern-0em} k}} \right]$ . Torsion-free cohomology follows also for the complement in ?ⁿof the complexification ${\mathcal{B}}_{n,k,h}^C ,1 \leqslant h < k$ .     

A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

A partial orthomorphism of ${\mathbb{Z}_{n}}$ is an injective map ${\sigma : S \rightarrow \mathbb{Z}_{n}}$ such that ${S \subseteq \mathbb{Z}_{n}}$ and ??(i)?Ci ? ??(j)? j (mod n) for distinct ${i, j \in S}$ . We say ?? has deficit d if ${|S| = n - d}$ . Let ??(n, d) be the number of partial orthomorphisms of ${\mathbb{Z}_{n}}$ of deficit d. Let ??(n, d) be the number of partial orthomorphisms ?? of ${\mathbb{Z}_n}$ of deficit d such that ??(i) ? {0, i} for all ${i \in S}$ . Then ??(n, d) =???(n, d)n ²/d ² when ${1\,\leqslant\,d < n}$ . Let R _{k, n} be the number of reduced k ×?n Latin rectangles. We show that $$R_{k, n} \equiv \chi (p, n - p)\frac{(n - p)!(n - p - 1)!^{2}}{(n - k)!}R_{k-p,\,n-p}\,\,\,\,(\rm {mod}\,p)$$ when p is a prime and ${n\,\geqslant\,k\,\geqslant\,p + 1}$ . In particular, this enables us to calculate some previously unknown congruences for R _{n, n} . We also develop techniques for computing ??(n, d) exactly. We show that for each a there exists??? _a such that, on each congruence class modulo??? _a , ??(n, n-a) is determined by a polynomial of degree 2a in n. We give these polynomials for ${1\,\leqslant\,a\,\leqslant 6}$ , and find an asymptotic formula for ??(n, n-a) as n ?? ??, for arbitrary fixed a.