Transformations of polar Grassmannians preserving certain intersecting relations

Let Π be a polar space of rank n≥3. Denote by \({\mathcal{G}}_{k}(\varPi)\) the polar Grassmannian formed by singular subspaces of Π whose projective dimension is equal to k. Suppose that k is an integer not greater than n?2 and consider the relation \({\mathfrak{R}}_{i,j}\) , 0≤i≤j≤k+1, formed by all pairs \((X,Y)\in{\mathcal{G}}_{k}(\varPi)\times{\mathcal{G}}_{k}(\varPi)\) such that dim _p (X ^⊥∩Y)=k?i and dim _p (X∩Y)=k?j (X ^⊥ consists of all points of Π collinear to every point of X). We show that every bijective transformation of \({\mathcal{G}}_{k}(\varPi)\) preserving \({\mathfrak{R}}_{1,1}\) is induced by an automorphism of Π, except the case where Π is a polar space of type D _n with lines containing precisely three points. If k=n?t?1, where t is an integer satisfying n≥2t≥4, we show that every bijective transformation of \({\mathcal{G}}_{k}(\varPi)\) preserving \({\mathfrak{R}}_{0,t}\) is induced by an automorphism of Π.     

Reeb Graphs: Approximation and Persistence

Given a continuous function f:X→? on a topological space X, its level set f ^?1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph, which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H ₁-homology of the Reeb graph from P. It takes O(nlogn) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm for computing the rank of H ₁(M) from point data. The best-known previous algorithm for this problem takes O(n ³) time for point data. The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H ₁-homology for the Reeb graphs in $O(n n_{e}^{3})$ time, where n is the size of the 2-skeleton and n _e is the number of edges in K.     

Longest Partial Transversals in Plexes

A k-protoplex of order n is a partial latin square of order n such that each row and column contains precisely k entries and each symbol occurs precisely k times. If a k-protoplex is completable to a latin square, then it is a k-plex. A 1-protoplex is a transversal. Let \({\phi_k}\) denote the smallest order for which there exists a k-protoplex that contains no transversal, and let \({{{\phi_k}^{*}}}\) denote the smallest order for which there exists a k-plex that contains no transversal. We show that \({k \leqslant \phi_k = {{\phi_k}^{*}} \leqslant k+1}\) for all \({k \geqslant 6}\) . Given a k-protoplex P of order n, we define T(P) to be the size of the largest partial transversal in P. We explore upper and lower bounds for T(P). Aharoni et al. have conjectured that \({T(P) \geqslant (k-1)n/k}\) . We find that $$T(P) > max \{ k(1-n^{-1/2}), k-n/(n-k), n-O (nk^{-1/2}log^{3/2} k)\}$$ . In the special case of 3-protoplexes, we improve the lower bound for T(P) to 3n/5.     

More on monochromatic-rainbow Ramsey type theorems

An edge colored graph is called a rainbow if no two of its edges have the same color. Let ? and $\mathcal{G}$ be two families of graphs. Denote by $RM({\mathcal{H}},\mathcal{G})$ the smallest integer R, if it exists, having the property that every coloring of the edges of K _R by an arbitrary number of colors implies that either there is a monochromatic subgraph of K _R that is isomorphic to a graph in ? or there is a rainbow subgraph of K _R that is isomorphic to a graph in $\mathcal{G}$ . ${\mathcal{T}}_{n}$ is the set of all trees on n vertices. ${\mathcal{T}}_{n}(k)$ denotes all trees on n vertices with diam(T _n (k))≤k. In this paper, we investigate $RM({\mathcal{T}}_{n},4K_{2})$ , $RM({\mathcal{T}}_{n},K_{1,4})$ and $RM({\mathcal{T}}_{n}(4),K_{3})$ .     

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.     

On the zero distribution of the Riesz transforms of power series

Рассматривается последовательность преобразований Рисс а степенного ряда $$f(z) = \sum\limits_{v = 0}^\infty {\alpha _v z^n } ,$$ задаваемая формулой $$\sigma _n (z) = \sum\limits_{k = 0}^\infty {{\textstyle{{Pk} \over {P_n }}}s_k (z)} ,$$ гдеs _k (z) — частная сумма порядкаk рядаf, a {p _k } — комплексная послед овательность, для которой $$P_n = \sum\limits_{k = 0}^n {p_k \ne 0, n = 0,1,2,... .}$$ Показано, что число ну лей полиномовσ _n в кру ге ¦z¦ <R связано при определе нных условиях лакунарнос ти с порядком роста {σ_n} и с их сверхсходимостью.     

Set-coloring of Edges and Multigraph Ramsey Numbers

Edge-colorings of multigraphs are studied where a generalization of Ramsey numbers is given. Let ${M_n^{(r)}}$ be the multigraph of order n, in which there are r edges between any two different vertices. Suppose q ₁, q ₂, . . . , q _k and r are positive integers, and q _i ≥ 2(1 ≤ i ≤ k), k > r. Let the multigraph Ramsey number ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ be the minimum positive integer n such that in any k-edge coloring of ${M_n^{(r)}}$ (every edge is colored with one among k given colors, and edges between the same pair of vertices are colored with different colors), there must be ${i \in \{1,2,\ldots,k\}}$ such that ${M_n^{(r)}}$ has such a complete subgraph of order q _i , of which all the edges are in color i. By Ramsey’s theorem it is easy to show ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ exists for given q ₁ ,q ₂, . . . , q _k and r. Lower and upper bounds for some multigraph Ramsey numbers are given.     

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.     

Disproof of the neighborhood conjecture with implications to SAT

We study a special class of binary trees. Our results have implications on Maker/Breaker games and SAT: We disprove a conjecture of Beck on positional games and construct an unsatisfiable k-CNF formula with few occurrences per variable, thereby improving a previous result by Hoory and Szeider and showing that the bound obtained from the Lovász Local Lemma is tight up to a constant factor. A (k, s)-CNF formula is a boolean formula in conjunctive normal form where every clause contains exactly k distinct literals and every variable occurs in at most s clauses. The (k, s)-SAT problem is the satisfiability problem restricted to (k, s)-CNF formulas. Kratochvíl, Savický and Tuza showed that for every k≥3 there is an integer f(k) such that every (k, f(k))-CNF formula is satisfiable, but (k, f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvíl, Savický and Tuza also gave the best known lower bound $f(k) = \Omega \left( {\tfrac{{2^k }} {k}} \right)$ , which is a consequence of the Lovász Local Lemma. We prove that, in fact, $f(k) = \Theta \left( {\tfrac{{2^k }} {k}} \right)$ , improving upon the best known upper bound $O\left( {(\log k) \cdot \tfrac{{2^k }} {k}} \right)$ by Hoory and Szeider. Finally we establish a connection between the class of trees we consider and a certain family of positional games. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph $\mathcal{F}$ , with Maker going first. Maker’s goal is to completely occupy a hyperedge and Breaker tries to prevent this. The maximum neighborhood size of a hypergraph $\mathcal{F}$ is the maximal s such that some hyperedge of $\mathcal{F}$ intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of $\mathcal{F}$ is smaller than 2 ^n?1 ? 1 then Breaker has a winning strategy. We disprove this conjecture by establishing, for every n≥3, the existence of an n-uniform hypergraph with maximum neighborhood size 3·2 ^n?3 where Maker has a winning strategy. Moreover, we show how to construct, for every n, an n-uniform hypergraph with maximum degree at most $\frac{{2^{n + 2} }} {n}$ where Maker has a winning strategy. In addition we show that each n-uniform hypergraph with maximum degree at most $\frac{{2^{n - 2} }} {{en}}$ has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.     

Unitary SK1 of semiramified graded and valued division algebras

We prove formulas for SK₁(E, τ), which is the unitary SK₁ for a graded division algebra E finite-dimensional and semiramified over its center T with respect to a unitary involution τ on E. Every such formula yields a corresponding formula for SK₁(D, ρ) where D is a division algebra tame and semiramified over a Henselian valued field and ρ is a unitary involution on D. For example, it is shown that if ${\sf{E} \sim \sf{I}_0 \otimes_{\sf{T}_0}\sf{N}}$ where I ₀ is a central simple T ₀-algebra split by N ₀ and N is decomposably semiramified with ${\sf{N}_0 \cong L_1\otimes_{\sf{T}_0} L_2}$ with L ₁, L ₂ fields each cyclic Galois over T ₀, then $${\rm SK}_1(\sf{E}, \tau) \,\cong\ {\rm Br}(({L_1}\otimes_{\sf{T}_0} {L_2})/\sf{T}_0;\sf{T}_0^\tau)\big/ \left[{\rm Br}({L_1}/\sf{T}_0;\sf{T}_0^\tau)\cdot {\rm Br}({L_2}/\sf{T}_0;\sf{T}_0^\tau) \cdot \langle[\sf{I}_0]\rangle\right].$$      

Convolutions of random measures on compact groups

LetG be a compact group andM ₁(G) be the convolution semigroup of all Borel probability measures onG with the weak topology. We consider a stationary sequence {μ _n } _n=?∞ ^+∞ of random measures μ _n =μ _n (ω) inM ₁(G) and the convolutions $$v_{m,n} (\omega ) = \mu _m (\omega )* \cdots *\mu _{n - 1} (\omega ), m< n$$ and $$\alpha _n^{( + k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n,n + i} (\omega ),} \alpha _n^{( - k)} (\omega ) = \frac{1}{k}\sum\limits_{i = 1}^k {v_{n - i,n} (\omega )} $$ We describe the setsA _m ⁺ (ω) andA _n ⁺ (ω) of all limit points ofv _m,n(ω) asm→?∞ orn→+∞ and the setA _∞(ω) of its two-sided limit points for typical realizations of {μ _n (ω)} _n=?∞ ^+∞ . Using an appropriate random ergodic theorem we study the limit random measures ρ _n ^(±) (ω)=lim _k→∞ α _n ^(±k) (ω).     

Smallest Set-Transversals of k-Partitions

We asymptotically solve an open problem raised independently by Sterboul (Colloq Math Soc J Bolyai 3:1387–1404, 1973), Arocha et al. (J Graph Theory 16:319–326, 1992) and Voloshin (Australas J Combin 11:25–45, 1995). For integers n ≥ k ≥ 2, let f(n, k) denote the minimum cardinality of a family ${\mathcal H}$ of k-element sets over an n-element underlying set X such that every partition ${X_1\cup\cdots\cup X_k=X}$ into k nonempty classes completely partitions some ${H\in\mathcal H}$ ;  that is, ${|H\cap X_i|=1}$ holds for all 1 ≤ i ≤ k. This very natural function—whose defining property for k = 2 just means that ${\mathcal H}$ is a connected graph—turns out to be related to several extensively studied areas in combinatorics and graph theory. We prove general estimates from which ${ f(n,k) = (1+o(1))\, \tfrac{2}{n}\,{n\choose k}}$ follows for every fixed k, and also for all k = o(n ^1/3), as n → ∞. Further, we disprove a conjecture of Arocha et al. (1992). The exact determination of f(n,k) for all n and k appears to be far beyond reach to our present knowledge, since e.g. the equality ${f(n,n-2)={n-2\choose 2}-{\rm ex}(n,\{C_3,C_4\})}$ holds, where the last term is the Turán number for graphs of girth 5.     

Vector bundles over iterated suspensions of stunted real projective spaces

Let $X^{k}_{m,n}=\Sigma^{k} (\mathbb{R}\mathbb{P}^{m}/\mathbb{R}\mathbb{P}^{n})$ . In this note we completely determine the values of k, m, n for which the total Stiefel–Whitney class w(ξ)=1 for any vector bundle ξ over  $X^{k}_{m,n}$ .     

Limiting Behavior of High Order Correlations for Simple Random Sampling

For ${N = 1, 2,\ldots,}$ let S _N be a simple random sample of size n = n _N from a population A _N of size N, where ${0 \leq n \leq N}$ . Then with f _N =  n/N, the sampling fraction, and 1 _A the inclusion indicator that ${A \in S_N}$ , for any ${H \subset A_N}$ of size ${k \geq 0}$ , the high order correlations $${\rm Corr}(k) = E \big(\mathop{\Pi}\limits_{A \in H} ({\bf 1}_A - f_N )\big)$$ depend only on k, and if the sampling fraction ${f_N \rightarrow f}$ as ${N \rightarrow \infty}$ , then $$N^{k/2}{\rm Corr}(k) \rightarrow [f (f - 1)]^{k/2}EZ^{k}, k \,{\rm even}$$ and $$N^{(k+1)/2}{\rm Corr}(k) \rightarrow [f (f - 1)]^{(k-1)/2}(2f - 1)\frac{1}{3}(k - 1)EZ^{k+1}, k \,{\rm odd}$$ where Z is a standard normal random variable. This proves a conjecture given in [2].     

On Some Ramsey Numbers for Quadrilaterals Versus Wheels

For given graphs G ₁ and G ₂, the Ramsey number R(G ₁, G ₂) is the least integer n such that every 2-coloring of the edges of K _n contains a subgraph isomorphic to G ₁ in the first color or a subgraph isomorphic to G ₂ in the second color. Surahmat et al. proved that the Ramsey number ${R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}$ . By using asymptotic methods one can obtain the following property: ${R(C_4, W_n) \leq n + \sqrt{n}+o(1)}$ . In this paper we show that in fact ${R(C_4, W_n) \leq n + \sqrt{n-2}+1}$ for n ≥ 11. Moreover, by modification of the Erd?s-Rényi graph we obtain an exact value ${R(C_4, W_{q^2+1}) = q^2 + q + 1}$ with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C ₄, W _n ) for 14 ≤ n ≤ 17.     

On some properties of trigonometric series with monotone decreasing coefficients

В статье рассматрива ются одномерные и дву мерные тригонометрические ряды с моно-тонными коэффициентами. Дает ся пример двойного тригонометрическог о ряда (1) $$\mathop \sum \limits_{n,k = 1}^\infty a_{nk} \sin nx\sin ky,$$ , коэффициенты которо го монотонны поk и поп, любая последовательность \(\{ S_{n_k m_k } (x,y)\} _{k = 1}^\infty\) прямоугольных части чных сумм ряда (1), где min(n _k ,m _k )→∞ приk→∞, расходится по чти всюду на (0,n)². Кроме того, изучается мера множеств нулей ф ункций (2) $$f(x) = \frac{{a_0 }}{2} + \mathop \sum \limits_{n = 1}^{a_0 } a_n \cos nx\tilde f(x) = \mathop \sum \limits_{n = 1}^\infty a_n \sin nx,$$ , гдеа _n ↓ приn→ ∞, и доказ ьшается несколько те орем о скорости убывания ко эффициентовa _n рядов (2), если все част ичные суммыS _n (f,x) или \(S_n (\tilde f,x)\) дляn=1,2,... неотрицате ль-ны на (0,n).     

Random systems of equations in free abelian groups

We study the solvability of random systems of equations on the free abelian group ? ^m of rank m. Denote by SAT(? ^m , k, n) and \(SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)\) the sets of all systems of n equations of k unknowns in ? ^m satisfiable in ? ^m and ? ^m respectively. We prove that the asymptotic density \(\rho \left( {SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)} \right)\) of the set \(SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)\) equals 1 for n ≤ k and 0 for n > k. As regards, SAT(? ^m , k, n) for n < k, some new estimates are obtained for the lower and upper asymptotic densities and it is proved that they lie between (Π _j=k?n+1 ^k ζ(j))^?1 and \(\left( {\tfrac{{\zeta (k + m)}} {{\zeta (k)}}} \right)^n\) , where ξ(s) is the Riemann zeta function. For n ≤ k, a connection is established between the asymptotic density of SAT(? ^m , k, n) and the sums of inverse greater divisors over matrices of full rank. Starting from this result, we make a conjecture about the asymptotic density of SAT(? ^m , n, n). We prove that ρ(SAT(? ^m , k, n)) = 0 for n > k.     

Locales as spectral spaces

A frame is a complete distributive lattice that satisfies the infinite distributive law ${b \wedge \bigvee_{i \in I} a_i = \bigvee_{i \in I} b \wedge a_i}$ b ∧ ? i ∈ I a i = ? i ∈ I b ∧ a i . The lattice of open sets of a topological space is a frame. The frames form a category Fr. The category of locales is the opposite category Fr ^op . The category BDLat of bounded distributive lattices contains Fr as a subcategory. The category BDLat is anti-equivalent to the category of spectral spaces, Spec (via Stone duality). There is a subcategory of Spec that corresponds to the subcategory Fr under the anti-equivalence. The objects of this subcategory are called locales, the morphisms are the localic maps; the category is denoted by Loc. Thus locales are spectral spaces. The category Loc is equivalent to the category Fr ^op . A topological approach to locales is initiated via the systematic study of locales as spectral spaces. The first task is to characterize the objects and the morphisms of the category Spec that belong to the subcategory Loc. The relationship between the categories Top (topological spaces), Spec and Loc is studied. The notions of localic subspaces and localic points of a locale are introduced and studied. The localic subspaces of a locale X form an inverse frame, which is anti-isomorphic to the assembly associated with the frame of open and quasi-compact subsets of X.     

The h,k-equal Partition Lattice is EL-shellable when h \geq k

It has been shown that the h, k-equal partition lattice \(\tilde \Pi_n^{h, k}\) is EL-shellable when h?<?k. We produce an EL-shelling for \(\tilde \Pi_n^{h, k}\) when n?≥?h?≥?k?≥?2 and observe that, in this shelling, there are no weakly decreasing chains. This shows that \(\tilde \Pi_n^{h, k}\) is contractible for such values of h and k, which can also be seen by the fact that \(\tilde \Pi_n^{h, k}\) is noncomplemented.     

Subsets of PG(n,2) and Maximal Partial Spreads in PG(4,2)

Put θ _n = # {points in PG(n,2)} and φ _n = #{lines in PG(n,2)}. Let ψ be anypoint-subset of PG(n,2). It is shown thatthe sum of L = #{internal lines of ψ} and L′= #{external lines of ψ} is the same for all ψ having the same cardinality:[6pt] Theorem A If k is defined by k = |ψ| ? θ _{n ? 1}, then $$L + L' = \phi _{n - 1} + k(k - 1)/2.$$ (The generalization of this to subsets of PG(n,3) is also obtained.) Let $\mathcal{S}$ be a partial spreadof lines in PG(4,2) and let N denote the number of reguli contained in $\mathcal{S}$ .Use of Theorem A gives rise to a simple proof of:[6pt] Theorem B If $\mathcal{S}$ is maximal then one of the followingholds: (i) $\left| \mathcal{S} \right| = 5,{\text{ }}N = 10;{\text{ }}$ (ii) $\left| \mathcal{S} \right| = 7,{\text{ }}N = 4;{\text{ }}$ (iii) $\left| \mathcal{S} \right| = 9,{\text{ }}N = 4.$ If (i) holds then $\mathcal{S}$ is spread in a hyperplane.It is shown that possibility (ii) is realized by precisely threeprojectively distinct types of partial spread. Explicit examplesare also given of four projectively distinct types of partialspreads which realize possibility (iii). For one of these types,type X, the four reguli have a common line. It isshown that those partial spreads in PG(4,2) of size 9 which arise, by a simple construction, from a spreadin PG(5,2), are all of type X.