Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices

We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have been known:(1) The bijection between maximal chains in the antichain lattice A(P) and the linear extensions of P.(2) The bijection between maximal chains in the lattice of maximal antichains A_M(P) and minimal interval extensions of P.We discuss two approaches to associate interval orders with chains in A(P). This leads to new bijections generalizing Bijections 1 and 2. As a consequence, we characterize the chains corresponding to weak-order extensions and minimal weak-order extensions of P.Seeking for a way of representing interval reductions of P by chains we came upon the separation lattice S(P). Chains in this lattice encode an interesting subclass of interval reductions of P. Let S_M(P) be the lattice of maximal separations in the separation lattice. Restricted to maximal separations, the above bijection specializes to a bijection which nicely complements 1 and 2.(3) A bijection between maximal chains in the lattice of maximal separations S_M(P) and minimal interval reductions of P.     

A pattern avoidance criterion for free inversion arrangements

We show that the hyperplane arrangement of a coconvex set in a finite root system is free if and only if it is free in corank 4. As a consequence, we show that the inversion arrangement of a Weyl group element w is free if and only if w avoids a finite list of root system patterns. As a key part of the proof, we use a recent theorem of Abe and Yoshinaga to show that if the root system does not contain any factors of type C or F, then Peterson translation of coconvex sets preserves freeness. This also allows us to give a Kostant–Shapiro–Steinberg rule for the coexponents of a free inversion arrangement in any type.     

Some new researches on the general connectivity index of benzenoid systems

Given H a benzenoid system, we find an expression of the general connectivity index, denoted by ?? _?? (H), in terms of inlet features and internal vertex features of H. As a consequence, the extremal n-benzenoid systems with maximal general connectivity index ?? _?? are completely characterized. Moreover, by constructing a combinatorial bijection, we prove that the linear chain L _n is the unique extremal n-benzenoid system with minimal general connectivity index ?? _?? if and only if ??>?? ^?, where ?? ^? is the positive root of the equation 2×6 ^x ?9 ^x =0.     

Antichain sequences

For any finite partially ordered set S we display a dual transportation system of linear inequalities, and a bijection A(x) from the maximal integer-valued solutions x of this system onto the maximal sequences of k antichains in S. This provides a simple translation to a dual transportation problem of the problem: find a maximum weight union of k antichains.Research supported by the Natural Sciences and Engineering Research of Canada.     

The Ramsey number of paths with respect to wheels

For graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of order n contains G or the complement of F contains H. For the path P_n and the wheel W_m, it is proved that R(P_n,W_m)=2n-1 if m is even, m?4, and n?(m/2)(m-2), and R(P_n,W_m)=3n-2 if m is odd, m?5, and n?(m-1/2)(m-3).     

Differential operators for Siegel-Jacobi forms

For any positive integers n and m, H_(n,m):= H_n× C~(m,n) is called the Siegel-Jacobi space, with the Jacobi group acting on it. The Jacobi forms are defined on this space. We compute the Chern connection of the Siegel-Jacobi space and use it to obtain derivations of Jacobi forms. Using these results, we construct a series of invariant differential operators for Siegel-Jacobi forms. Also two kinds of Maass-Shimura type differential operators for H_(n,m) are obtained.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.     

Optimal calibration for multiple testing against local inhomogeneity in higher dimension

Based on two independent samples X ₁, . . . , X _m and X _m+1, . . . , X _n drawn from multivariate distributions with unknown Lebesgue densities p and q respectively, we propose an exact multiple test in order to identify simultaneously regions of significant deviations between p and q. The construction is built from randomized nearest-neighbor statistics. It does not require any preliminary information about the multivariate densities such as compact support, strict positivity or smoothness and shape properties. The properly adjusted multiple testing procedure is shown to be sharp-optimal for typical arrangements of the observation values which appear with probability close to one. The proof relies on a new coupling Bernstein type exponential inequality, reflecting the non-subgaussian tail behavior of a combinatorial process. For power investigation of the proposed method a reparametrized minimax set-up is introduced, reducing the composite hypothesis ??p?=?q?? to a simple one with the multivariate mixed density (m/n)p?+?(1 ? m/n)q as infinite dimensional nuisance parameter. Within this framework, the test is shown to be spatially and sharply asymptotically adaptive with respect to uniform loss on isotropic H?lder classes. The exact minimax risk asymptotics are obtained in terms of solutions of the optimal recovery.     

Extremal edge problems for graphs with given hyperoctahedral automorphism group

For k > 1, let H_k denote the hyperoctahedral group S_k[S₂] of order 2^kk!. An (H_k, n)- graph is a graph on n vertices with automorphism group abstractly isomorphic to H_k. For each k an (H_k, n)-graph exists precisely when n ? 2k; for each n ? 2k the minimum and maximum number of edges possible for such graphs are determined. The analogous results for connected (H_k, n)-graphs are also obtained.     

Pitchfork bifurcations of invariant manifolds

A pitchfork bifurcation of an (m−1)-dimensional invariant submanifold of a dynamical system in Rm is defined analogous to that in R. Sufficient conditions for such a bifurcation to occur are stated and existence of the bifurcated manifolds is proved under the stated hypotheses. For discrete dynamical systems, the existence of locally attracting manifolds M₊ and M₋, after the bifurcation has taken place is proved by constructing a diffeomorphism of the unstable manifold M. Techniques used for proving the theorem involve differential topology and analysis. The theorem is illustrated by means of a canonical example.     

Intersection theorems for group divisible difference sets

Let D be an (m,n;k;λ₁,λ₂)-group divisible difference set (GDDS) of a group G, written additively, relative to H, i.e. D is a k-element subset of G, H is a normal subgroup of G of index m and order n and for every nonzero element g of G,?{(d₁,d₂)?,d₁,d₂?D,d₁?d₂=g}? is equal to λ₁ if g is in H, and equal to λ₂ if g is not in H. Let H₁,H₂,…,H_m be distinct cosets of H in G and S_i=D∩H_i for all i=1,2,…,m. Some properties of S₁,S₂,…,S_m are studied here. Table 1 shows all possible cardinalities of S_i's when the order of G is not greater than 50 and not a prime. A matrix characterization of cyclic GDDS's with λ₁=0 implies that there exists a cyclic affine plane of even order, say n, only if n is divisible by 4 and there exists a cyclic (n?1,$\text{1}\text{2}$n?1,$\text{1}\text{4}$n?1)-difference set.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

Asymptotic observers for a class of evolution equations. A nonlinear approach

We consider in a Hilbert space H the system (E_u) = x = uAx+B(x); y = 〈x. c〉_H, where the control u ε L^∞([0, + ∞[, ℝ⁺) multiplies a possibly unbounded m-dissipative linear operator A. The operator B is nonlinear dissipative, and y stands for the output of the system. We prove, in this nonlinear framework, the existence of a suitable Luenberger-like observer. For this purpose, we show that the usual notions of regularly persistent inputs proposed in [7] or [4] are the appropriate concepts that allow one to generalize the main results of [9] and [8] or [7] for bilinear systems to our nonlinear general system: For each regularly persistent input, the estimation error of the observer converges weakly to zero. If in addition A generates a compact semigroup, the estimation error converges strongly to zero. A prototype of such a system is the heat exchanger system described in [9] or [8].     

Congruence Criteria for Finite Subsets of Quaternionic Elliptic and Quaternionic Hyperbolic Spaces

We investigate congruence classes of m-tuples of points in the quaternionic elliptic space ?P ⁿ . We establish a canonical bijection between the set of congruence classes of m-tuples of points in ?P ⁿ and the set of equivalence classes of positive semidefinite Hermitian m×m matrices of rank at most n+1 with the 1's on the diagonal. We show that with each m-tuple of points in ?P ⁿ is associated a tuple of points on the real unit sphere S ². Then we get that the congruence class of an m-tuple of points in ?P ⁿ is determined by the congruence classes of all its triangles and by the direct congruence class of the associated tuple on the sphere S ² provided that no pair of points of the m-tuple has distance π/2. Finally we carry out the same kind of investigation for the quaternionic hyperbolic space ?H ⁿ . Most of the results are completely analogous, although there are also some interesting differences.     

A minimization problem concerning subsets of a finite set

Let F be the set of subsets of a finite set S, and for H ? F, let H′ denote the elements of F which are contained in some element of H. Given integers m_l and m_l+1 does there exist a subset H of F consisting of exactly m_ll-element subsets of S and m_l+1 (l+1)-element subsets of S such that no two elements of H are related by set-wise inclusion, and if such sets H do exist what the smallest |(l?1)(H′)| can be, where |(l?1)(H′)| is the number of (l?1)-element subsets of S in H′? A generalization of this problem, which was posed by G. Katona, is solved in this paper with the help of the generalized Macaulay theorem [2].     

On the size of maximal antichains and the number of pairwise disjoint maximal chains

Fix integers n and k with n≥k≥3. Duffus and Sands proved that if P is a finite poset and n≤|C|≤n+(n−k)/(k−2) for every maximal chain in P, then P must contain k pairwise disjoint maximal antichains. They also constructed a family of examples to show that these inequalities are tight. These examples are two-dimensional which suggests that the dual statement may also hold. In this paper, we show that this is correct. Specifically, we show that if P is a finite poset and n≤|A|≤n+(n−k)/(k−2) for every maximal antichain in P, then P has k pairwise disjoint maximal chains. Our argument actually proves a somewhat stronger result, and we are able to show that an analogous result holds for antichains.     

Maximal subgroups of the Coxeter group W(H4) and quaternions

The largest finite subgroup of O(4) is the non-crystallographic Coxeter group W(H₄) of order 14,400. Its derived subgroup is the largest finite subgroup W(H₄)/Z₂ of SO(4) of order 7200. Moreover, up to conjugacy, it has five non-normal maximal subgroups of orders 144, two 240, 400 and 576. Two groups [W(H₂) × W(H₂)] ⋊ Z₄ and W(H₃) × Z₂ possess non-crystallographic structures with orders 400 and 240 respectively. The groups of orders 144, 240 and 576 are the extensions of the Weyl groups of the root systems of SU(3) × SU(3), SU(5) and SO(8) respectively. We represent the maximal subgroups of W(H₄) with sets of quaternion pairs acting on the quaternionic root systems.     

Quantum scattering near the lowest Landau threshold for a Schrödinger operator with a constant magnetic field

For fixed magnetic quantum number m results on spectral properties and scattering theory are given for the three-dimensional Schrödinger operator with a constant magnetic field and an axisymmetrical electric potential V. In various, mostly singular settings, asymptotic expansions for the resolvent of the Hamiltonian H _m+H_om+V are deduced as the spectral parameter tends to the lowest Landau threshold. Furthermore, scattering theory for the pair (H _m, H _om) is established and asymptotic expansions of the scattering matrix are derived as the energy parameter tends to the lowest Landau threshold.     

A Note on Generalized Lagrangians of Non-uniform Hypergraphs

Set \(A\subset {\mathbb N}\) is less than \(B\subset {\mathbb N}\) in the colex ordering if m a x(A△B)∈B. In 1980’s, Frankl and Füredi conjectured that the r-uniform graph with m edges consisting of the first m sets of \({\mathbb N}^{(r)}\) in the colex ordering has the largest Lagrangian among all r-uniform graphs with m edges. A result of Motzkin and Straus implies that this conjecture is true for r=2. This conjecture seems to be challenging even for r=3. For a hypergraph H=(V,E), the set T(H)={|e|:e∈E} is called the edge type of H. In this paper, we study non-uniform hypergraphs and define L(H) a generalized Lagrangian of a non-uniform hypergraph H in which edges of different types have different weights. We study the following two questions: 1. Let H be a hypergraph with m edges and edge type T. Let C _m,T denote the hypergraph with edge type T and m edges formed by taking the first m sets with cardinality in T in the colex ordering. Does L(H)≤L(C _m,T ) hold? If T={r}, then this question is the question by Frankl and Füredi. 2. Given a hypergraph H, find a minimum subhypergraph G of H such that L(G) = L(H). A result of Motzkin and Straus gave a complete answer to both questions if H is a graph. In this paper, we give a complete answer to both questions for {1,2}-hypergraphs. Regarding the first question, we give a result for {1,r ₁,r ₂,…,r _l }-hypergraph. We also show the connection between the generalized Lagrangian of {1,r ₁,r ₂,? ,r _l }-hypergraphs and {r ₁,r ₂,? ,r _l }-hypergraphs concerning the second question.