On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

For a given permutation matrix P, let fP(n) be the maximum number of 1-entries in an n×n(0,1)-matrix avoiding P and let SP(n) be the set of all n×n permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that cP:=limn→∞fP(n)/n is finite, while the Stanley-Wilf conjecture asserts that is finite.In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture.We focus on the values of the Stanley-Wilf limit (sP) and the Füredi-Hajnal limit (cP). We improve the reduction and obtain which decreases the general upper bound on sP from sP?constconstO(klog(k)) to sP?constO(klog(k)) for any k×k permutation matrix P. In the opposite direction, we show .For a lower bound, we present for each k a k×k permutation matrix satisfying cP=Ω(k²).     

All 113 and 123-configurations are rational

Summary A conjecture of Grünbaum states that everyn ³ -configuration in the real plane can also be realized in the rational plane. We prove this conjecture forn 12 by computing rational coordinates for all 31 types of 11³ -configurations and all 228 types of 12³- configurations in the classification of Daublebsky.Researc hsupported by the Institute for Mathematics and its Applications, Minneapolis, with funds provided by the National Science Foundation.     

The Hopf conjecture for positively curved manifolds with discrete abelian group actions

Let M be a closed even n-manifold of positive sectional curvature. The main result asserts that the Euler characteristic of M is positive, if M admits an isometric -action with prime p?p(n) (a constant depending only on n) and k satisfies any one of the following conditions: (i) and n≠12, 18 or 20; (ii) , and n≡0 mod 4 with n≠12 or 20; (iii) , and n≡0,4 or 12 mod 20 with n≠20. This generalizes some results in [T. Püttmann, C. Searle, The Hopf conjecture for manifolds with low cohomogeneity or high symmetry rank, Proc. Amer. Math. Soc. 130 (2002) 163-166; X. Rong, Positively curved manifolds with almost maximal symmetry rank, Geom. Dedicata 59 (2002) 157-182; X. Rong, X. Su, The Hopf conjecture for positively curved manifolds with abelian group actions, Comm. Cont. Math. 7 (2005) 121-136].     

Erd?s-Ko-Rado for three sets

Fix integers k?3 and n?3k/2. Let F be a family of k-sets of an n-element set so that whenever A,B,C∈F satisfy |A∪B∪C|?2k, we have A∩B∩C≠∅. We prove that with equality only when ?_F∈FF≠∅. This settles a conjecture of Frankl and Füredi [2], who proved the result for n?k²+3k.     

Two results on homogeneous Hessian nilpotent polynomials

Let z=(z₁,…,z_n) and , the Laplace operator. A formal power series P(z) is said to be Hessian Nilpotent (HN) if its Hessian matrix is nilpotent. In recent developments in [M. de Bondt, A. van den Essen, A reduction of the Jacobian conjecture to the symmetric case, Proc. Amer. Math. Soc. 133 (8) (2005) 2201-2205. [MR2138860]; G. Meng, Legendre transform, Hessian conjecture and tree formula, Appl. Math. Lett. 19 (6) (2006) 503-510. [MR2170971]. See also math-ph/0308035; W. Zhao, Hessian nilpotent polynomials and the Jacobian conjecture, Trans. Amer. Math. Soc. 359 (2007) 249-274. [MR2247890]. See also math.CV/0409534], the Jacobian conjecture has been reduced to the following so-called vanishing conjecture (VC) of HN polynomials: for any homogeneous HN polynomialP(z) (of degreed=4), we haveΔ^mP^m+1(z)=0for anym?0. In this paper, we first show that the VC holds for any homogeneous HN polynomial P(z) provided that the projective subvarieties Z_P and Z_σ2 of CPⁿ⁻¹ determined by the principal ideals generated by P(z) and , respectively, intersect only at regular points of Z_P. Consequently, the Jacobian conjecture holds for the symmetric polynomial maps F=z−∇P with P(z) HN if F has no non-zero fixed point w∈Cⁿ with . Secondly, we show that the VC holds for a HN formal power series P(z) if and only if, for any polynomial f(z), Δ^m(f(z)P(z)^m)=0 when m?0.     

A note on a conjecture by Füredi

In [Z. Füredi, Turán type problems, in: Surveys in Combinatorics, Guildford, 1991, in: London Math. Soc. Lecture Note Ser., vol. 166, Cambridge Univ. Press, Cambridge, 1991, pp. 253-300, MR1161467 (93d:05072)], Füredi raised a conjecture about the maximum size of L-intersecting families. In this note, we address a variant of this conjecture. In particular, we show that for any Steiner triple system S on [k], there exist a family F of k-sets on [n] with |F|=Ω(n2+?) and such that for every F₀∈F the family is isomorphic to S.     

n-Torsion of Brauer groups as relative Brauer groups of abelian extensions

It is now known [H. Kisilevsky, J. Sonn, Abelian extensions of global fields with constant local degrees, Math. Res. Lett. 13 (4) (2006) 599-607; C.D. Popescu, Torsion subgroups of Brauer groups and extensions of constant local degree for global function fields, J. Number Theory 115 (2005) 27-44] that if F is a global field, then the n-torsion subgroup of its Brauer group Br(F) equals the relative Brauer group Br(Ln/F) of an abelian extension Ln/F, for all n∈Z?1. We conjecture that this property characterizes the global fields within the class of infinite fields which are finitely generated over their prime fields. In the first part of this paper, we make a first step towards proving this conjecture. Namely, we show that if F is a non-global infinite field, which is finitely generated over its prime field and ?≠char(F) is a prime number such that μ?²⊆F^×, then there does not exist an abelian extension L/F such that . The second and third parts of this paper are concerned with a close analysis of the link between the hypothesis μ?²⊆F^× and the existence of an abelian extension L/F such that , in the case where F is a Henselian valued field.     

Index formulas for higher order Loewner vector fields

Let be the Cauchy-Riemann operator and f be a Cn real-valued function in a neighborhood of 0 in R² in which for all z≠0. In such cases, is known as a Loewner vector field due to its connection with Loewner's conjecture that the index of such a vector field is bounded above by n. The n=2 case of Loewner's conjecture implies Carathéodory's conjecture that any C²-immersion of S² into R³ must have at least two umbilics. Recent work of F. Xavier produced a formula for computing the index of Loewner vector fields when n=2 using data about the Hessian of f. In this paper, we extend this result and establish an index formula for for all n?2. Structurally, our index formula provides a defect term, which contains geometric data extracted from Hessian-like objects associated with higher order derivatives of f.     

Twisted first homology groups of the automorphism group of a free group

The automorphism group and outer automorphism group of a free group F_n of rank n act on the abelianized group H of F_n and the dual group H^* of H. The twisted first homology groups of and with coefficients in H and H^* are calculated.     

Plücker environments, wiring and tiling diagrams, and weakly separated set-systems

For the ordered set [n] of n elements, we consider the class Bn of bases B of tropical Plücker functions on ²[n] such that B can be obtained by a series of so-called weak flips (mutations) from the basis formed by the intervals in [n]. We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on an n-zonogon. Based on the generalized tiling representation, we then prove that each weakly separated set-system in ²[n] having maximum possible size belongs to Bn, yielding the affirmative answer to one conjecture due to Leclerc and Zelevinsky. We also prove an analogous result for a hyper-simplex .     

Diameters of 3-sphere quotients

Let G⊂O(4) act isometrically on S³. In this article we calculate a lower bound for the diameter of the quotient spaces S³/G. We find it to be , which is exactly the value of the lower bound for diameters of the spherical space forms. In the process, we are also able to find a lower bound for diameters for the spherical Aleksandrov spaces, Sn/G, of cohomogeneities 1 and 2, as well as for cohomogeneity 3 (with some restrictions on the group type). This leads us to conjecture that the diameter of Sn/G is increasing as the cohomogeneity of the group G increases.     

A matroid invariant via the K-theory of the Grassmannian

Let G(d,n) denote the Grassmannian of d-planes in Cn and let T be the torus n(C^∗)/diag(C^∗) which acts on G(d,n). Let x be a point of G(d,n) and let be the closure of the T-orbit through x. Then the class of the structure sheaf of in the K-theory of G(d,n) depends only on which Plücker coordinates of x are nonzero - combinatorial data known as the matroid of x. In this paper, we will define a certain map of additive groups from K^○(G(d,n)) to Z[t]. Letting gx(t) denote the image of , gx behaves nicely under the standard constructions of matroid theory, such as direct sum, two-sum, duality and series and parallel extensions. We use this invariant to prove bounds on the complexity of Kapranov's Lie complexes [M. Kapranov, Chow quotients of Grassmannians I, Adv. Soviet Math. 16 (2) (1993) 29-110], Hacking, Keel and Tevelev's very stable pairs [P. Hacking, S. Keel, E. Tevelev, Compactification of the moduli space of hyperplane arrangements, J. Algebraic Geom. 15 (2006) 657-680] and the author's tropical linear spaces when they are realizable in characteristic zero [D. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (4) (2008) 1527-1558]. Namely, in characteristic zero, a Lie complex or the underlying (d−1)-dimensional scheme of a very stable pair can have at most strata of dimensions n−i and d−i, respectively. This prove the author's f-vector conjecture, from [D. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (4) (2008) 1527-1558], in the case of a tropical linear space realizable in characteristic 0.     

Minimizing a monotone concave function with laminar covering constraints

Let V be a finite set with |V|=n. A family F⊆2^V is called laminar if for all two sets X,Y∈F, X∩Y≠∅ implies X⊆Y or X⊇Y. Given a laminar family F, a demand function , and a monotone concave cost function , we consider the problem of finding a minimum-cost such that x(X)?d(X) for all X∈F. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in O(n²q) time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family F, where q is the time required for the computation of F(x) for any . We also prove that if F is given by an oracle, then it takes Ω(n²q) time to solve the problem, which implies that our O(n²q) time algorithm is optimal in this case. Furthermore, we propose an algorithm if F is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires Ω(2^n/2q) time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form.     

A description of continued fraction expansions of quadratic surds represented by polynomials

The principal thrust of this investigation is to provide families of quadratic polynomials , where e_k²−f_k²C=n (for any given nonzero integer n) satisfying the property that for any , the period length of the simple continued fraction expansion of is constant for fixed k and lim_k→∞?_k=∞. This generalizes, and completes, numerous results in the literature, where the primary focus was upon |n|=1, including the work of this author, and coauthors, in Mollin (Far East J. Math. Sci. Special Vol. 1998, Part III, 257-293; Serdica Math. J. 27 (2001) 317) Mollin and Cheng (Math. Rep. Acad. Sci. Canada 24 (2002) 102; Internat Math J 2 (2002) 951) and Mollin et al. (JP J. Algebra Number Theory Appl. 2 (2002) 47).