On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

Boolean Lattices: Ramsey Properties and Embeddings

A subposet Q ^′ of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q ^′ such that x ≤ y in P iff f(x) ≤ f(y) in Q. For posets P, P ^′, let the poset Ramsey number R(P, P ^′) be the smallest N such that no matter how the elements of the Boolean lattice Q _N are colored red and blue, there is a copy of P with all red elements or a copy of P ^′ with all blue elements. We provide some general bounds on R(P, P ^′) and focus on the situation when P and P ^′ are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of Q _n in Q _N and for a multicolor version of a poset Ramsey number.     

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset P, denoted \(\dim (P)\), is the least positive integer d for which P is the intersection of d linear extensions of P. The maximum dimension of a poset P with \(|P|\le 2n+1\) is n, provided \(n\ge 2\), and this inequality is tight when P contains the standard example \(S_n\). However, there are posets with large dimension that do not contain the standard example \(S_2\). Moreover, for each fixed \(d\ge 2\), if P is a poset with \(|P|\le 2n+1\) and P does not contain the standard example \(S_d\), then \(\dim (P)=o(n)\). Also, for large n, there is a poset P with \(|P|=2n\) and \(\dim (P)\ge (1-o(1))n\) such that the largest d so that P contains the standard example \(S_d\) is o(n). In this paper, we will show that for every integer \(c\ge 1\), there is an integer \(f(c)=O(c^2)\) so that for large enough n, if P is a poset with \(|P|\le 2n+1\) and \(\dim (P)\ge n-c\), then P contains a standard example \(S_d\) with \(d\ge n-f(c)\). From below, we show that \(f(c)={\varOmega }(c^{4/3})\). On the other hand, we also prove an analogous result for fractional dimension, and in this setting f(c) is linear in c. Here the result is best possible up to the value of the multiplicative constant.     

Dimension and Matchings in Comparability and Incomparability Graphs

We develop some new inequalities for the dimension of a finite poset. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d=3, then there is a matching of size d in the comparability graph of P. There is no analogue of this result for cover graphs, as we show that there is a poset P of dimension d for which the maximum matching in the cover graph of P has size \(O(\log d)\). On the other hand, there is a dual result in which the role of chains and antichains is reversed, as we show that there is also a matching of size d in the incomparability graph of P. The proof of the result for comparability graphs has elements in common with Perles’ proof of Dilworth’s theorem. Either result has the following theorem of Hiraguchi as an immediate corollary: \(\dim (P)\le |P|/2\) when |P|=4.     

On vanishing coefficients of algebraic power series over fields of positive characteristic

Let K be a field of characteristic p>0 and let f(t ₁,…,t _d ) be a power series in d variables with coefficients in K that is algebraic over the field of multivariate rational functions K(t ₁,…,t _d ). We prove a generalization of both Derksen’s recent analogue of the Skolem–Mahler–Lech theorem in positive characteristic and a classical theorem of Christol, by showing that the set of indices (n ₁,…,n _d )∈? ^d for which the coefficient of \(t_{1}^{n_{1}}\cdots t_{d}^{n_{d}}\) in f(t ₁,…,t _d ) is zero is a p-automatic set. Applying this result to multivariate rational functions leads to interesting effective results concerning some Diophantine equations related to S-unit equations and more generally to the Mordell–Lang Theorem over fields of positive characteristic.     

Face numbers and the fundamental group

We resolve a conjecture of Kalai asserting that the g ₂-number of any (finite) simplicial complex Δ that represents a normal pseudomanifold of dimension d ≥ 3 is at least as large as \(\left( {\begin{array}{*{20}{c}} {d + 2} \\ 2 \end{array}} \right)m\left( \Delta \right)\), where m(Δ) denotes the minimum number of generators of the fundamental group of Δ. Furthermore, we prove that a weaker bound, \({h_2}\left( \Delta \right) \geqslant \left( {\begin{array}{*{20}{c}} {d + 1} \\ 2 \end{array}} \right)m\left( \Delta \right)\), applies to any d-dimensional pure simplicial poset Δ all of whose faces of co-dimension ≥ 2 have connected links. This generalizes a result of Klee. Finally, for a pure relative simplicial poset Ψ all of whose vertex links satisfy Serre’s condition (S _r ), we establish lower bounds on h ₁(Ψ),...,h _r (Ψ) in terms of the μ-numbers introduced by Bagchi and Datta.     

On structural decompositions of finite frames

A frame in an n-dimensional Hilbert space H _n is a possibly redundant collection of vectors {f _i } _i∈I that span the space. A tight frame is a generalization of an orthonormal basis. A frame {f _i } _i∈I is said to be scalable if there exist nonnegative scalars {c _i } _i∈I such that {c _i f _i } _i∈I is a tight frame. In this paper we study the combinatorial structure of frames and their decomposition into tight or scalable subsets by using partially-ordered sets (posets). We define the factor poset of a frame {f _i } _i∈I to be a collection of subsets of I ordered by inclusion so that nonempty J?I is in the factor poset iff {f _j } _j∈J is a tight frame for H _n . We study various properties of factor posets and address the inverse factor poset problem, which inquires when there exists a frame whose factor poset is some given poset P. We then turn our attention to scalable frames and present partial results regarding when a frame can be scaled to have a given factor poset; in doing so we present a bridge between erasure resilience (as studied via prime tight frames) and scalability.     

Vanishing power values of commutators with derivations

Let R be a prime ring of char R ≠ 2, let d be a nonzero derivation of R, and let ρ be a nonzero right ideal of R such that [[d(x)x ⁿ , d(y)] _m , [y, x] _s ] ^t = 0 for all x, y ? ρ, where n ≥ 1, m ≥ 0, s ≥ 0, and t ≥ 1 are fixed integers. If [ρ, ρ]ρ ≠ 0 then d(ρ)ρ = 0.     

The barycenter property for robust and generic diffeomorphisms

Let f:M~d→M~d(d≥2) be a diffeomorphism on a compact C~∞ manifold on M.If a diffeomorphism f belongs to the C~1-interior of the set of all diffeomorphisms having the barycenter property,then f is Ω-stable.Moreover,if a generic diffeomorphism f has the barycenter property,then f is Ω-stable.We also apply our results to volume preserving diffeomorphisms.     

On the Complexity of Multivalued Logic Functions over Some Infinite Basis

Under study is the complexity of the realization of k-valued logic functions (k ≥ 3) by logic circuits in the infinite basis consisting of the Post negation (i.e., the function (x + 1) mod k) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds of complexity, which differ from one another at most by 1 and have the form 3 log₃(d(f)+ 1)+O(1), where d(f) is the maximal number of the decrease of the value of f taken over all increasing chains of tuples of values of the variables. We find the exact value of the corresponding Shannon function which characterizes the complexity of the most complex function of a given number of variables.     

On the Complexity and Depth of Embedded in Boolean Cube Circuits That Implement Boolean Functions

A class of circuits of functional elements over the standard basis of the conjunction, disjunction, and negation elements is considered. For each circuit Σ in this class, its depth D(Σ) and dimension R(Σ) equal to the minimum dimension of the Boolean cube allowing isomorphic embedding Σ are defined. It is established that for n = 1, 2,… and an arbitrary Boolean function f of n variables there exists a circuit Σ_f for implementing this function such that R(Σ_f) ? n ? log₂ log₂n + O(1) and D(Σ_f) ? 2n ? 2 log₂ log₂n + O(1). It is proved that for n = 1, 2,… almost all functions of n variables allow implementation by circuits of the considered type, whose depth and dimension differ from the minimum values of these parameters (for all equivalent circuits) by no more than a constant and asymptotically no more than by a factor of 2, respectively.     

Explicit symplectic multidimensional exponential fitting modified Runge-Kutta-Nyström methods

This paper is concerned with multidimensional exponential fitting modified Runge-Kutta-Nyström (MEFMRKN) methods for the system of oscillatory second-order differential equations q″(t)+Mq(t)=f(q(t)), where M is a d×d symmetric and positive semi-definite matrix and f(q) is the negative gradient of a potential scalar U(q). We formulate MEFMRKN methods and show clearly the relationship between MEFMRKN methods and multidimensional extended Runge-Kutta-Nyström (ERKN) methods proposed by Wu et al. (Comput. Phys. Comm. 181:1955–1962, 2010). Taking into account the fact that the oscillatory system is a separable Hamiltonian system with Hamiltonian \(H(p,q)=\frac{1}{2}p^{T}p+ \frac{1}{2}q^{T}Mq+U(q)\), we derive the symplecticity conditions for the MEFMRKN methods. Two explicit symplectic MEFMRKN methods are proposed. Numerical experiments accompanied demonstrate that our explicit symplectic MEFMRKN methods are more efficient than some well-known numerical methods appeared in the scientific literature.     

Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V ₁,…V _t such that for all i the subtournament T[V _i] induced on T by V _i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k ⁷ t ⁴) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t ⁵) suffices.     

Pattern Avoidance in Poset Permutations

We extend the concept of pattern avoidance in permutations on a totally ordered set to pattern avoidance in permutations on partially ordered sets. The number of permutations on P that avoid the pattern p is denoted A v _P (p). We extend a proof of Simion and Schmidt to show that A v _P (132)=A v _P (123) for any poset P, and we exactly classify the posets for which equality holds.     

Equiconvergence of expansions in multiple Fourier series and in fourier integrals with “lacunary sequences of partial sums”

We investigate the equiconvergence on T^N = [?π, π)^N of expansions in multiple trigonometric Fourier series and in the Fourier integrals of functions f ∈ L_p(T^N) and g ∈ L_p(R^N), p > 1, N ≥ 3, g(x) = f(x) on T^N, in the case where the “partial sums” of these expansions, i.e., S_n(x; f) and J_α(x; g), respectively, have “numbers” n ∈ Z^N and α ∈ R^N (n_j = [α_j], j = 1,..., N, [t] is the integral part of t ∈ R¹) containing N ? 1 components which are elements of “lacunary sequences.”     

Quasiplanar Diagrams and Slim Semimodular Lattices

For elements x and y in the (Hasse) diagram D of a finite bounded poset P, x is on the left of y, written as x λ y, if x and y are incomparable and x is on the left of all maximal chains through y. Being on the right, written as x ? y, is defined analogously. The diagram D is quasiplanar if λ and ? are transitive and for any pair (x,y) of incomparable elements, if x is on the left of some maximal chain through y, then x λ y. A planar diagram is quasiplanar, and P has a quasiplanar diagram iff its order dimension is at most 2. We are interested in diagrams only up to similarity. A finite lattice is slim if it is join-generated by the union of two chains. The main result gives a bijection between the set of (the similarity classes of) finite quasiplanar diagrams and that of (the similarity classes of) planar diagrams of finite slim semimodular lattices. This bijection allows one to describe finite posets of order dimension at most 2 by finite slim semimodular lattices, and conversely. As a corollary, we obtain that there are exactly (n?2)! quasiplanar diagrams of size n.     

Global asymptotic stability for half-linear differential systems with generalized almost periodic coefficients

The following system considered in this paper:

$$x' = -\,e(t)x + f(t)\phi_{p^*}(y), \qquad y'= -\,(p-1)g(t)\phi_p(x) - (p-1)h(t)y,$$

where \({p > 1, p^* > 1 (1/p + 1/p^* = 1)}\) and \({\phi_q(z) = |z|^{q-2}z}\) for q = p or q = p ^*. This system is referred to as a half-linear system. The coefficient f(t) is assumed to be bounded, but the coefficients e(t), g(t) and h(t) are not necessarily bounded. Sufficient conditions are obtained for global asymptotic stability of the zero solution. Our results can be applied to not only the case that the signs of f(t) and g(t) change like the periodic function but also the case that f(t) and g(t) irregularly have zeros. Some suitable examples are included to illustrate our results.

     

On the 1/3–2/3 Conjecture

Let (P, ≤) be a finite poset (partially ordered set), where P has cardinality n. Consider linear extensions of P as permutations x₁x₂?x_n in one-line notation. For distinct elements x, y ∈ P, we define ?(x ? y) to be the proportion of linear extensions of P in which x comes before y. For \(0\leq \alpha \leq \frac {1}{2}\), we say (x, y) is an α-balanced pair if α ≤ ?(x ? y) ≤?1 ? α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension 2. We also consider various posets which satisfy the stronger condition of having a 1/2-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length 2. Various questions for future research are posed.     

Invariable generation of prosoluble groups

A group G is invariably generated by a subset S of G if G = 〈s^g(s) | s ∈ S〉 for each choice of g(s) ∈ G, s ∈ S. Answering two questions posed by Kantor, Lubotzky and Shalev in [8], we prove that the free prosoluble group of rank d ≥ 2 cannot be invariably generated by a finite set of elements, while the free solvable profinite group of rank d and derived length l is invariably generated by precisely l(d ? 1) + 1 elements.     

On the sum of the L1 influences of bounded functions

Let f: {-1, 1}ⁿ → [-1, 1] have degree d as a multilinear polynomial. It is well-known that the total influence of f is at most d. Aaronson and Ambainis asked whether the total L₁ influence of f can also be bounded as a function of d. Ba?kurs and Bavarian answered this question in the affirmative, providing a bound of O(d³) for general functions and O(d²) for homogeneous functions. We improve on their results by providing a bound of d² for general functions and O(d log d) for homogeneous functions. In addition, we prove a bound of d/(2p) + o(d) for monotone functions, and provide a matching example.