On groups of type Φ

We define a group G to be of type Φ if it has the property that for every -module G, proj. G < ∞ iff proj. H G < ∞ for every finite subgroup H of G. We conjecture that the type Φ is an algebraic characterization of those groups G which admit a finite dimensional model for , the classifying space for the family of the finite subgroups of G. We also conjecture that the type Φ is equivalent to spli being finite, where spli is the supremum of the projective lengths of the injective -modules. Here we prove certain parts of these conjectures. The project is cofounded by the European Social Fund and National Resources–EPEAK II–Pythagoras. Received: 21 June 2006     

Supersaturation For Ramsey-Turán Problems

For an l-graph , the Turán number is the maximum number of edges in an n-vertex l-graph containing no copy of . The limit is known to exist [8]. The Ramsey–Turán density is defined similarly to except that we restrict to only those with independence number o(n). A result of Erdős and Sós [3] states that as long as for every edge E of there is another edge E′of for which |E∩E′|≥2. Therefore a natural question is whether there exists for which . Another variant proposed in [3] requires the stronger condition that every set of vertices of of size at least εn (0<ε<1) has density bounded below by some threshold. By definition, for every . However, even is not known for very many l-graphs when l>2. We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we construct, for each l≥3, infinitely many l-graphs for which . We also prove that the 3-graph with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies . The existence of a hypergraph satisfying was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based on different ideas and is simpler than these earlier proofs. * Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P. Sloan Research Fellowship. † Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529.     

Lifts, Discrepancy and Nearly Optimal Spectral Gap*

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l₁ norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}ⁿ with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.     

Weighted Non-Trivial Multiply Intersecting Families

Let n and r be positive integers. Suppose that a family satisfies F₁∩···∩F_r ≠∅ for all F₁, . . .,F_r ∈ and . We prove that there exists ε=ε(r) >0 such that holds for 1/2≤w≤1/2+ε if r≥13.     

Vectorspacelike representation of absolute planes

The pointset E of an absolute plane can be provided with a binary operation "+" such that (E, +) becomes a loop and for each a E \ {o} the line [a] through o and a is a commutative subgroup of (E, +). Two elements a, b E \ {o} are called independent if [a] ∩ [b] = {o} and the absolute plane is called vectorspacelike if for any two independent elements we have E = [a] + [b] := {x + y | x [a], y [b]}. If is singular then (E, +) is a commutative group and is vectorspacelike iff is Euclidean. If is a hyperbolic plane then is vectorspacelike and in the continous case if a, b are independent, each point p has a unique representation as a quasilinear combination p = α · a + μ · b where α · a [a]and β · b [b] are points, α, β real numbers such that λ (o, λ · a) = |λ|· λ (o, a) and λ (o, μ · b) = |μ|. λ(o, b) and λ is the distance function. This work was partially supported by the Research Project of MIUR (Italian Ministery of Education and University) “Geometria combinatoria e sue applicazioni” and by the research group GNSAGA of INDAM. Dedicated to Walter Benz on the occasion of his 75 ^th birthday, in friendship     

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.     

On a subalgebra of the centre of a group ring II

Let p be a prime, G a finite group with p | |G| and F a field of characteristic p. By we denote the F-subspace of the centre of the group ring FG spanned by the p-regular conjugacy class sums. J. Murray proved that is an algebra, if G is a symmetric or alternating group. This can be used for the computation of the block idempotents of FG. We proved that is an algebra if the Sylow-p-subgroups of G are abelian. Recently, Y. Fan and B. Külshammer generalized this result to blocks with abelian defect groups. Here, we show that is an algebra if the Sylow-2-subgroups of G are dihedral. Therefore and are algebras for all primes p and all prime powers q. Furthermore we prove that is an algebra for the simple Suzuki-groups Sz(q), where q is a certain power of 2 and p is an arbitrary prime dividing |Sz(q)|. Received: 18 May 2007     

A Weighted Erdős-Ginzburg-Ziv Theorem

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct so that they can be considered as sets. If S is a sequence of m+n−1 elements from a finite abelian group G of order m and exponent k, and if is a sequence of integers whose sum is zero modulo k, then there exists a rearranged subsequence of S such that . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when m = n and w_i = 1 for all i, and confirms a conjecture of Y. Caro. Furthermore, we in part verify a related conjecture of Y. Hamidoune, by showing that if S has an n-set partition A=A₁, . . .,A_n such that |w_iA_i| = |A_i| for all i, then there exists a nontrivial subgroup H of G and an n-set partition A′ =A′₁, . . .,A′_n of S such that and for all i, where w_iA_i={w_ia_i |a_i∈A_i}.     

Remarks on ample vector bundles of curve genus two

Let be an ample vector bundle of rank n – 1 on a smooth complex projective variety X of dimension n≥ 3 such that X is a -bundle over and that for any fiber F of the bundle projection . The pairs with = 2 are classified, where is the curve genus of . This allows us to improve some previous results. Received: 13 June 2006     

Asymptotic normality of a quadratic measure of orthogonal series type density estimate

LetX ₁,...,X _n be i.i.d. random variable with a common densityf. Let be an estimate off(x) based on a complete orthonormal basis {φ _k :k≧0} ofL ₂[a, b]. A Martingale central limit theorem is used to show that , where and .     

On the Similarity of Analytic Matrix Functions

Consider a domain , and two analytic matrix-valued functions functions . Consider also points and positive integers n ₁, n ₂, . . . , n _N . We are interested in the existence of an analytic function such that X(ω) is invertible, and G(ω) coincides with X(ω)F(ω)X(ω)⁻¹ up to order n _j at the point ω _j . We will see that such a function exists provided that F(ω _j ),G(ω _j ) have cyclic vectors, and the characteristic polynomials of F,G coincide up to order n _j at ω _j . This allows one to give a short proof to a result of Huang, Marcantognini and Young concerning spectral interpolation in the unit disk. The author was partially supported by a grant from the National Science Foundation. Received: September 8, 2006. Accepted: January 11, 2007.     

On a problem of Zambakhidze-Smirnov

We say that the action extension problem is solvable for a bicompact groupG if for any metricG-space and for any topological embeddingc of the orbit spaceX into a metric spaceY there exist aG-space ℤ, an invariant topological embeddingb: → ℤ, and a homeomorphismh: Y → Z such that the diagram is commutative. We prove the following theorem: for a bicompact zero-dimensional groupG, the action extension problem is solvable for the class of dense topological embeddings. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 3–11, July, 1995.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

Equidistribution of Rational Matrices in their Conjugacy Classes

Let G be a connected simply connected almost -simple algebraic group with non-compact and a cocompact congruence subgroup. For any homogeneous manifold of finite volume, and a , we show that the Hecke orbit T _a (x ₀ H) is equidistributed on as , provided H is a non-compact commutative reductive subgroup of G. As a corollary, we generalize the equidistribution result of Hecke points ([COU], [EO1]) to homogeneous spaces G/H. As a concrete application, we describe the equidistribution result in the rational matrices with a given characteristic polynomial. The second author partially supported by DMS 0333397. Received: May 2005 Revision: March 2006 Accepted: June 2006     

Properties of Auto- and Antiautomorphisms of Maximal Chain Structures and their Relations to i-Perspectivities

Let E be a non empty set, let P : = E × E, := {x × E|x ∈ E}, := {E × x|x ∈ E}, and := {C ∈ 2 ^P |∀X ∈ : |C ∩ X| = 1} and let . Then the quadruple resp. is called chain structure resp. maximal chain structure. We consider the maximal chain structure as an envelope of the chain structure . Particular chain structures are webs, 2-structures, (coordinatized) affine planes, hyperbola structures or Minkowski planes. Here we study in detail the groups of automorphisms , , , related to a maximal chain structure . The set of all chains can be turned in a group such that the subgroup of generated by the left-, by the right-translations and by ι the inverse map of is isomorphic to (cf. (2.14)).     

On estimation of a density and its derivatives

Summary Letf _n ^(p) be a recursive kernel estimate off ^(p) thepth order derivative of the probability density functionf, based on a random sample of sizen. In this paper, we provide bounds for the moments of and show that the rate of almost sure convergence of to zero isO(n ^−α), α<(r−p)/(2r+1), iff ^(r),r>p≧0, is a continuousL ₂(−∞, ∞) function. Similar rate-factor is also obtained for the almost sure convergence of to zero under different conditions onf. This work was supported in part by the Research Foundation of SUNY.     

Maximum set of edges no two covered by a clique

Leth(G) be the largest number of edges of the graphG. no two of which are contained in the same clique. ForG without isolated vertices it is proved that ifh(G)≦5, thenχ( )≦h(G), but ifh(G)=6 thenχ( ) can be arbitrarily large.     

Comparison of exact constants in Kolmogorov-type inequalities for periodic and nonperiodic functions of many variables

We investigate the correlation between the constants K(ℝⁿ) and , where

A remark on the conjecture of Erdös, Faber and Lovász

The celebrated Erd?s, Faber and Lovász Conjecture may be stated as follows: Any linear hypergraph on ν points has chromatic index at most ν. We show that the conjecture is equivalent to the following assumption: For any graph , where ν(G) denotes the linear intersection number and χ(G) denotes the chromatic number of G. As we will see for any graph G = (V, E), where denotes the complement of G. Hence, at least G or fulfills the conjecture.      

Explicit Bounded-Degree Unique-Neighbor Concentrators

Here we solve an open problem considered by various researchers by presenting the first explicit constructions of an infinite family of bounded-degree ‘unique-neighbor’ concentrators Γ; i.e., there are strictly positive constants α and ε, such that all Γ = (X,Y,E(Γ)) ∈ satisfy the following properties. The output-set Y has cardinality times that of the input-set X, and for each subset S of X with no more than α|X| vertices, there are at least ε|S| vertices in Y that are adjacent in Γ to exactly one vertex in S. Also, the construction of is simple to specify, and each has fewer than edges. We then modify to obtain explicit unique-neighbor concentrators of maximum degree 3. * Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.