Short cycles of Poncelet’s conics

Main results of this paper are the following:1. A closed N-gon interscribed between two conics exists if and only if a specially constructed polygon with a smaller number of sides (n) is closed. To verify the closure of this n-gon, we need to find a periodic solution of a dynamical system of order n. The proof is based on the connection of Poncelet’s curves and matrices that admit unitary bordering [4,9,10,16]. Application of this criterion makes sense when n?N, in particular when n≈log₂N (see Table 4 where n=m₁). So for example we may say that a polygon with 2049 sides interscribed between two circles is closed if and only if some specially constructed 11-gon is closed.2. A closed N-gon interscribed between two confocal ellipses (the billiard case) exists if and only if an N-gon interscribed between two special nested circles is closed.     

Blocking sets, k-arcs and nets of order ten

Our first main objective here is to unify two important theories in finite geometries, namely, the theories of k-arcs and blocking sets. This has a number of consequences, which we develop elsewhere. However, one consequence that we do discuss here is an improvement of Bruck's bound [1] concerning the possibility of embedment of finite nets of order n, in the controversial case when n = 10. The argument also makes use of a recent computer result of Denniston [5]. The second (related) main result involves a new combinatorial bound concerning blocking sets (Theorem 5). We are able to show that the bound is sharp by constructing a new class of geometrical examples of blocking sets in Theorem 6. See also the note added in proof.     

Quadratic degenerations of odd-orthogonal Schubert varieties

This paper is the second in a series leading to a type B_n geometric Littlewood-Richardson rule. The rule will give an interpretation of the B_n Littlewood-Richardson numbers as an intersection of two odd-orthogonal Schubert varieties and will consider a sequence of linear and quadratic deformations of the intersection into a union of odd-orthogonal Schubert varieties. This paper describes the setup for the rule and specifically addresses results for quadratic deformations, including a proof that at each quadratic degeneration, the results occur with multiplicity one. This work is strongly influenced by Vakil’s [14].     

Maximal dimensional partially ordered sets I. Hiraguchi's theorem

In this paper, I give a new proof of Hiraguchi's Theorem that the dimension of an n-element partially ordered set is at most [frcase|1/2n]. The significant feature of the proof is the lemma which states that a partially ordered set has either a cover of rank 0 or a pair of covers with elements of one incomparable with elements of the other.     

r-Qsym is free over Sym

Our main result is a proof of the Florent Hivert conjecture [F. Hivert, Local action of the symmetric group and generalizations of quasi-symmetric functions, in preparation] that the algebras of r-Quasi-Symmetric polynomials in x₁,x₂,…,xn are free modules over the ring of Symmetric polynomials. The proof rests on a theorem that reduces a wide variety of freeness results to the establishment of a single dimension bound. We are thus able to derive the Etingof-Ginzburg [P. Etingof, V. Ginzburg, On m-quasi-invariants of a Coxeter group, Mosc. Math. J. 2 (2002) 555-566] Theorem on m-Quasi-Invariants and our r-Quasi-Symmetric result as special cases of a single general principle. Another byproduct of the present treatment is a remarkably simple new proof of the freeness theorem for 1-Quasi-Symmetric polynomials given in [A.M. Garsia, N. Wallach, Qsym over Sym is free, J. Combin. Theory Ser. A 104 (2) (2003) 217-263].     

A new short proof of a theorem of Ahlswede and Khachatrian

Ahlswede and Khachatrian [R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121-138] proved the following theorem, which answered a question of Frankl and Füredi [P. Frankl, Z. Füredi, Nontrivial intersecting families, J. Combin. Theory Ser. A 41 (1986) 150-153]. Let 2?t+1?k?2t+1 and n?(t+1)(k−t+1). Suppose that F is a family of k-subsets of an n-set, every two of which have at least t common elements. If |_?F∈FF|<t, then , and this is best possible. We give a new, short proof of this result. The proof in [R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121-138] requires the entire machinery of the proof of the complete intersection theorem, while our proof uses only ordinary compression and an earlier result of Wilson [R.M. Wilson, The exact bound in the Erd?s-Ko-Rado theorem, Combinatorica 4 (1984) 247-257].     

On the subgroup distance problem

We investigate the computational complexity of finding an element of a permutation group H⊆S_n with minimal distance to a given π∈S_n, for different metrics on S_n. We assume that H is given by a set of generators. In particular, the size of H might be exponential in the input size, so that in general the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley Distance, this problem has been shown to be NP-hard, even if H is abelian of exponent two [R.G.E. Pinch, The distance of a permutation from a subgroup of S_n, in: G. Brightwell, I. Leader, A. Scott, A. Thomason (Eds.), Combinatorics and Probability, Cambridge University Press, 2007, pp. 473-479]. We present a much simpler proof for this result, which also works for the Hamming Distance, the l_p distance, Lee’s Distance, Kendall’s tau, and Ulam’s Distance. Moreover, we give an NP-hardness proof for the l_∞ distance using a different reduction idea. Finally, we discuss the complexity of the corresponding fixed-parameter and maximization problems.     

The extension to root systems of a theorem on tournaments

M. G. Kendall and B. Babington-Smith proved that if a tournament p′ is obtained from a tournament p by reversing the edges of a 3-cycle then p and p′ contain the same number of 3-cycles. This theorem is the basis of a cancellation argument used by D. Zeilberer and D. M. Bressoud in their recent proof of the q-analog of Dyson's conjecture. The theorem may be restated in terms of the root system A_n and the main result of this paper is the extension of this theorem to arbitrary root systems. As one application we give a combinatorial proof of a special case of the Macdonald conjecture for root systems using the method of Zeilberger and Bressoud. A second application is a combinatorial proof of the Weyl denominator formula.     

Cauchy problem for equations with multiple characteristics

This paper contains a proof of γ^n(χ) correctness of the noncharacteristic Cauchy problem for nonstrictly hyperbolic equations with analytic coefficients under the condition that its characteristic roots are smooth and under some additional assumptions on the lower-order terms. There are two extreme cases: (1) $\text{χ <}\text{r}\text{r}\text{? 1}$. In this case condition (0.6) is “void,” and we do not require conditions on P_s for s < m. For this case, see [3, 8]. (2) Case of constant multiplicity of characteristic roots and χ = +∞. In this case condition (0.6) implies conditions on P_s, where s = m, m ? 1,…, m ? r + 1, i.e., up to the same order as the necessary condition for C^∞-correctness [2]. Recall that in the case of equations with characteristics of constant multiplicity condition (0.6) (Levi's condition in this case) for χ = ∞ is necessary [2, 4] and sufficient [1] for C^∞-correctness.     

Once more on periodic products of groups and on a problem of A. I. Mal’tsev

A new operation of product of groups, the n-periodic product of groups for odd exponent n ≥ 665, was proposed by the author in 1976 in the paper [1]. This operation is described on the basis of the Novikov-Adyan theory introduced in the monograph [2] of the author. It differs from the classic operations of direct and free products of groups, but has all of the natural properties of these operations, including the so-called hereditary property for subgroups. Thus, the well-known problem of A. I. Mal’tsev on the existence of such new operations was solved. Unfortunately, in the paper [1], the case where the initial groups contain involutions, was not analyzed in detail. It is shown that, in the case where the initial groups contain involutions, this small gap is easily removed by an additional restriction on the choice of defining relations for the periodic product. It suffices to simply exclude products of two involutions of previous ranks from the inductive process of defining new relations for any given rank α. It is suggested that the adequacy of the given restriction follows easily from the proof of the key Lemma II.5.21 in the monograph [2]. We also mention that, with this additional restriction, all the properties of the periodic product given in [1] remain true with obvious corrections of their formulation. Moreover, under this restriction, one can consider n-periodic products for any period n ≥ 665, including even periods.     

On three-fold irregular branched coverings over closed three-braid and three-bridge knots

It is well known that every closed orientable three-manifold is given as a three-fold branched covering space branched over some knot. Then it is an interesting problem that for a given knot family what kind of manifold can be got as a three-fold irregular branched covering space. K. Murasugi showed that for a closed three-braid the manifold is a lens space of type (n,1). In this paper, we will give an another proof and an algorithm to determine n for a given knot. And for a three bridge knot, we will show that its covering space is a lens space of type (p,q), and give an algorithm to determine the pair of p, q.     

Some generalized limit theorems concerning delayed sums of random sequence

For a sequence of arbitrarily dependent m-valued random variables (Xn) n∈N , the generalized strong limit theorem of the delayed average is investigated. In our proof, we improved the method proposed by Liu [6] . As an application, we also studied some limit properties of delayed average for inhomogeneous Markov chains.     

An upper bound on the number of high-dimensional permutations

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an n×n×...×n=[n] ^d+1 array of zeros and ones in which every line contains a unique 1 entry. A line here is a set of entries of the form {(x ₁,...,x _i?1,y,x _i+1,...,x _d+1)|n≥y≥1} for some index d+1≥i≥1 and some choice of x _j ∈ [n] for all j ≠ i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number $$\left( {(1 + o(1))\frac{n} {{e^d }}} \right)^{n^d } .$$ We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Brégman’s [1] proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Schrijver’s [11] and Radhakrishnan’s [10] proofs of Brégman’s theorem.     

The crossing number of K1,3,n and K2,3,n

In this article, we will determine the crossing number of the complete tripartite graphs K_1,3,n and K_2,3,n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K_5,n. J. Combinatorial Theory 9 (1970) 315-323].     

Large semisimple groups on 16-dimensional compact projective planes are almost simple

The paper deals with the so-called Salzmann program aiming to classify special geometries according to their automorphism groups. Here, topological connected compact projective planes are considered. If finite-dimensional, such planes are of dimension 2, 4, 8, or 16. The classical example of a 16-dimensional, compact projective plane is the projective plane over the octonions with 78-dimensional automorphism group E₆(?26). A 16-dimensional, compact projective plane P admitting an automorphism group of dimension 41 or more is classical, [18] 87.5 and 87.7. For the special case of a semisimple group Δ acting on P the same result can be obtained if dim δ ≧ 37, see [16]. Our aim is to lower this bound. We show: if Δ is semisimple and dim δ ≧ 29, then P is either classical or a Moufang-Hughes plane or Δ is isomorphic to Spin₉ (?, r), r ∈ {0, 1 }. The underlying paper contains the first part of the proof showing that Δ is in fact almost simple.     

A Simplified Elementary Proof of Hadwiger's Volume Theorem

One of the most important results in geometric convexity is Hadwiger's characterization of quermassintergrals and intrinsic volumes. The importance lies in that Hadwiger's theorem provides straightforward proofs of numerous results in integral geometry such as the kinematic formulas [Santaló, L. A.: Integral Geometry and Geometric Probability, Addison-Wesley, 1976], the mean projection formulas for convex bodies [Schneider, R.: Convex Bodies: The Brunn—Minkowski Theory, Cambridge Univ. Press, 1993], and the characterization of totally invariant set functions of polynomial type [Chen, B. and Rota, G.-C.: Totally invariant set functions of polynomial type, Comm. Pure Appl. Math. 47 (1994), 187–197]. For a long time the only known proof of Hadwiger's theorem was his original one [Hadwiger, H.: Vorlesungen über Inhalt, Oberfläche and Isoperimetrie, Springer, Berlin, 1957] (long and not available in English), until a new proof was obtained by Klain [Klain, D. A.: A short proof of Hadwiger's characterization theorem, Mathematika 42 (1995), 329–339., Klain, D. A. and Rota, G.-C.: Introduction to Geometric Probability, Lezioni Lincee, Cambridge Univ. Press, 1997], using a result from spherical harmonics. The present paper provides a simplified and self-contained proof of Hadwiger's theorem.     

Eigenvalue gaps for the Cauchy process and a Poincaré inequality

A connection between the semigroup of the Cauchy process killed upon exiting a domain D and a mixed boundary value problem for the Laplacian in one dimension higher known as the mixed Steklov problem, was established in [R. Bañuelos, T. Kulczycki, The Cauchy process and the Steklov problem, J. Funct. Anal. 211 (2004) 355-423]. From this, a variational characterization for the eigenvalues λn, n?1, of the Cauchy process in D was obtained. In this paper we obtain a variational characterization of the difference between λn and λ₁. We study bounded convex domains which are symmetric with respect to one of the coordinate axis and obtain lower bound estimates for λ_∗−λ₁ where λ_∗ is the eigenvalue corresponding to the “first” antisymmetric eigenfunction for D. The proof is based on a variational characterization of λ_∗−λ₁ and on a weighted Poincaré-type inequality. The Poincaré inequality is valid for all α symmetric stable processes, 0<α?2, and any other process obtained from Brownian motion by subordination. We also prove upper bound estimates for the spectral gap λ₂−λ₁ in bounded convex domains.     

Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

Graham and Pollak [2] proved that n – 1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K_n decompose. Tverberg [6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge-disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee [4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.