A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

Vector representable matroids of given rank with given automorphism group

A simple way of associating a matroid of prescribed rank with a graph is shown. The matroids so constructed are representable over any sufficiency large field. Their use is demonstrated by the following result: Given an integer k?3 and a function G associating a group with each subset of a set S, there is a matroid M(E), representable over any sufficiently large field, such that E ? S, and for any T ?/ S, the rank of M/Tis k, and the automorphine group of MT is isomorphic to G(T).     

Sets in Abelian groups with distinct sums of pairs

A subset S={s₁,…,sk} of an Abelian group G is called an St-set of size k if all sums of t different elements in S are distinct. Let s(G) denote the cardinality of the largest S₂-set in G. Let v(k) denote the order of the smallest Abelian group for which s(G)?k. In this article, bounds for s(G) are developed and v(k) is determined for k?15 by computing s(G) for Abelian groups of order up to 183 using exhaustive backtrack search with isomorph rejection.     

Module derivation problem for inverse semigroups

The derivation problem for a locally compact group G asserts that each bounded derivation from L ¹(G) to L ¹(G) is implemented by an element of M(G). Recently a simple proof of this result was announced. We show that basically the same argument with some extra manipulations with idempotents solves the module derivation problem for inverse semigroups, asserting that for an inverse semigroup S with set of idempotents E and maximal group homomorphic image G _S , if E acts on S trivially from the left and by multiplication from the right, any bounded module derivation from ? ¹(S) to ? ¹(G _S ) is inner.     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

On the equivalence of the Euler-Pommier operators in spaces of analytic functions

In the space A (θ) of all one-valued functions f(z) analytic in an arbitrary region G ? ? (0 ∈ G) with the topology of compact convergence, we establish necessary and sufficient conditions for the equivalence of the operators L ₁=α _n z ⁿ Δ ⁿ + ... + α₁ zΔ+α₀ E and L ₂= z ⁿ a _n (z)Δ ⁿ + ... + za ₁(z)Δ+a ₀(z)E, where δ: (Δ?)(z)=(f(z)-?(0))/z is the Pommier operator in A(G), n ∈ ?, α _n ∈ ?, a _k (z) ∈ A(G), 0≤k≤n, and the following condition is satisfied: Σ _j=s ^n?1 α _j+1 ∈ 0, s=0,1,...,n?1. We also prove that the operators z ^s+1Δ+β(z)E, β(z) ∈ A _R , s ∈ ?, and z ^s+1 are equivalent in the spaces A _R, 0?R?-∞, if and only if β(z) = 0.     

Realizing cohomology classes as Euler classes

For a space X, let E _k (X), E _k ^s (X) and E _k ^?? (X) denote respectively the set of Euler classes of oriented k-plane bundles over X, the set of Euler classes of stably trivial k-plane bundles over X and the spherical classes in H ^k (X; ?). We prove some general facts about the sets E _k (X), E _k ^s (X) and E _k ^?? (X). We also compute these sets in the cases where X is a projective space, the Dold manifold P(m, 1) and obtain partial computations in the case that X is a product of spheres.     

Multiplicative models for configuration spaces of algebraic varieties

Fulton and MacPherson (Ann. Math. 139 (1994) 183) found a Sullivan dg-algebra model for the space of n-configurations of a smooth complex projective variety X. K?í? (Ann. Math. 139 (1994) 227) gave a simpler model, E_n(H), depending only on the cohomology ring, H?H^*X.We construct an even simpler and smaller model, J_n(H). We then define another new dg-algebra, E_n(H^°), and use J_n(H) to prove that E_n(H^°) is a model of the space of n-configurations of the non-compact punctured manifold X^°, when X is 1-connected. Following an idea of Drinfel’d (Leningrad Math. J. 2 (1991) 829), we put a simplicial bigraded differential algebra structure on {E_n(H^°)}_n?0.     

Central limit theorems for C(S)-valued random variables

Let C(S) be the space of real-valued continuous functions on a compact metric space S. Let {X_n, n ? 1} be a sequence of independent identically distributed C(S)-valued random variables with mean zero and sup_t?sE[X₁²(t)] = 1. We show that the measures induced by ($\text{X}{}_1\text{+ ··· + X}{}_{\mathrm{n}}\text{) n}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}$ converge weakly to a Gaussian measure on C(S) under different conditions on X₁, one of which consolidates and extends results of Strassen and Dudley, Giné, and Dudley. Our method of proof is different from the methods employed by these authors.     

Waldhausen's theory of k-fold end structures: a survey

Let R⁺ be the space of nonnegative real numbers. F. Waldhausen defines a k-fold end structure on a space X as an ordered k-tuple of continuous maps x_f:X → R⁺, 1 ? j ? k, yielding a proper map x:X → (R⁺)^k. The pairs (X,x) are made into the category E^k of spaces with k-fold end structure. Attachments and expansions in E^k are defined by induction on k, where elementary attachments and expansions in E⁰ have their usual meaning. The category E^k/Z consists of objects (X, i) where i: Z → X is an inclusion in E^k with an attachment of i(Z) to X, and the category E^k6Z consists of pairs (X,i) of E^k/Z that admit retractions X → Z. An infinite complex over Z is a sequence X = {X₁ ? X₂ ? … ? X_n …} of inclusions in E^k6Z. The abelian grou p S₀(Z) is then defined as the set of equivalence classes of infinite complexes dominated by finite ones, where the equivalence relation is generated by homotopy equivalence and finite attachment; and the abelian group S₁(Z) is defined as the set of equivalence classes of X₁, where X ∈ E^k/Z deformation retracts to Z. The group operations are gluing over Z. This paper presents the Waldhausen theory with some additions and in particular the proof of Waldhausen's proposition that there exists a natural exact sequence 0 → S₁(Z × R)→^πS₀(Z) by utilizing methods of L.C. Siebenmann. Waldhausen developed this theory while seeking to prove the topological invariance of Whitehead torsion; however, the end structures also have application in studying the splitting of a noncompact manifold as a product with R[1].     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

Topology of random clique complexes

In a seminal paper, Erd?s and Rényi identified a sharp threshold for connectivity of the random graph G(n,p). In particular, they showed that if p?logn/n then G(n,p) is almost always connected, and if p?logn/n then G(n,p) is almost always disconnected, as n→∞.The clique complexX(H) of a graph H is the simplicial complex with all complete subgraphs of H as its faces. In contrast to the zeroth homology group of X(H), which measures the number of connected components of H, the higher dimensional homology groups of X(H) do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erd?s-Rényi Theorem.We study here the higher homology groups of X(G(n,p)). For k>0 we show the following. If p=n^α, with α<−1/k or α>−1/(2k+1), then the kth homology group of X(G(n,p)) is almost always vanishing, and if −1/k<α<−1/(k+1), then it is almost always nonvanishing.We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of a spheres.     

Super s-restricted edge-connectivity of vertex-transitive graphs

Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k5 and girth g5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.     

Removing circuits in 3-connected binary matroids

For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M?X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.     

Matroids with given restrictions and contractions

If M is a matroid on a set S and if X is a subset of S, then there are two matroids on X induced by M: namely, the restriction and the contraction of M onto X. Necessary and sufficient conditions are obtained for two matroids on the same set to be of this form and an analogous result is obtained when (X₁,…, X_t) is a partition of S. The corresponding results when all the matroids are binary are also obtained.     

Conditional limit theorems for exponential families and finite versions of de Finetti's theorem

Consider an exponential familyP _λ which is maximal, smooth, and has uniformly bounded standardized fourth moments. Consider a sequenceX ₁,X ₂,... of i.i.d. random variables with parameter λ. LetQ _nsk be the law ofX ₁,...,X _k given thatS _n=X ₁+...+X _n=s. Choose λ so thatE _λ(X ₁)=s/n. Ifk andn→∞ butk/n→0, then $$\parallel Q_{nsk} - P_\lambda ^k \parallel = \gamma \frac{k}{n} + o\left( {\frac{k}{n}} \right)$$ where γ=1/2E{|1?Z ²|} andZ isN(0,1). The error term is uniform ins, the value ofS _n. Similar results are given fork/n→θ and for mixtures of theP _λ ^k . Versions of de Finetti's theorem follow.     

A new result on Davenport constant

Let G be a finite abelian group of order n and Davenport constant D(G). Let S=⁰h(S)_∏g∈Ggvg(S)∈F(G) be a sequence with a maximal multiplicity h(S) attained by 0 and t=|S|?n+D(G)−1. Then 0∈k_∑(S) for every 1?k?t+1−D(G). This is a refinement of the fundamental result of Gao [W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103].     

Simplicial cells in arrangements and mutations of oriented matroids

We investigate the combinatorial and topological properties of simplicial cells in arrangements of (pseudo)hyperplanes, using their interpretations in terms of oriented matroids. Simplicial cells have various applications in computational geometry due to the fact that for an arrangement in general position they are in one-to-one correspondence to local changes (mutations) of its combinatorial type. Several characterizations for mutations of oriented matroids, and their relation to geometric realizability questions are being discussed.We give two short proofs for a result of Shannon [30] that every arrangement of n hyperplanes in E ^d has at least n simplicial cells, this bound being sharp for every n and d. The concatenation operation, a construction introduced by Lawrence and Weinberg [21], will be used to generate a large class of representable oriented matroids with this minimal number of mutations.A homotopy theorem is proved, stating that any two arrangements in general position can be transformed into each other be a sequence of representability preserving mutations. Finally, we give an example of an oriented matroid on eight elements with only seven mutations. As a corollary we obtain a new proof for the non-polytopality of the smallest non-polytopal matroid sphere M ⁹ ₉₆₃.Supported, in part, by an Alfred P. Sloane Doctoral Dissertation Fellowship.     

Graph partition into K 3s and K 4s

Let s and k be two integers with 0≤s≤k and let G be a simple graph of order n≥3s+4(k?s)+3. In this paper we prove that if σ ₂(G)≥3(n?s)/2+k?2, then G ? sK ₃+(k?s)K ₄. We also show that the degree condition is sharp in some sense.     

The number of reachable pairs in a digraph

For a digraph G, let R(G) (respectively, R^(k)(G)) be the number of ordered pairs (u,v) of vertices of G such that u≠v and v is reachable from u (respectively, reachable from u by a path of length ?k). In this paper, we study the range S_n of R(G) and the range of R^(k)(G) as G varies over all possible digraphs on n vertices. We give a sufficient condition and a necessary condition for an integer to belong to S_n. These determine the set S_n for all n?208. We also determine for k?4 and show that whenever n?k+(k+1)^0.57+2, for arbitrary k.