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.     

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 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²).     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.

     

An intersection theorem for four sets

Fix integers n,r?4 and let F denote a family of r-sets of an n-element set. Suppose that for every four distinct A,B,C,D∈F with |A∪B∪C∪D|?2r, we have A∩B∩C∩D≠∅. We prove that for n sufficiently large, , with equality only if _?F∈FF≠∅. This is closely related to a problem of Katona and a result of Frankl and Füredi [P. Frankl, Z. Füredi, A new generalization of the Erd?s-Ko-Rado theorem, Combinatorica 3 (3-4) (1983) 341-349], who proved a similar statement for three sets. It has been conjectured by the author [D. Mubayi, Erd?s-Ko-Rado for three sets, J. Combin. Theory Ser. A, 113 (3) (2006) 547-550] that the same result holds for d sets (instead of just four), where d?r, and for all n?dr/(d−1). This exact result is obtained by first proving a stability result, namely that if |F| is close to then F is close to satisfying _?F∈FF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erd?s and Simonovits for graphs.     

Hasse principle for classical groups over function fields of curves over number fields

In (Letter to J.-P. Serre, 12 June 1991) Colliot-Thélène conjectures the following: Let F be a function field in one variable over a number field, with field of constants k and G be a semisimple simply connected linear algebraic group defined over F. Then the map has trivial kernel, denoting the set of places of k.The conjecture is true if G is of type 1A∗, i.e., isomorphic to SL₁(A) for a central simple algebra A over F of square free index, as pointed out by Colliot-Thélène, being an immediate consequence of the theorems of Merkurjev-Suslin [S1] and Kato [K]. Gille [G] proves the conjecture if G is defined over k and F=k(t), the rational function field in one variable over k. We prove that the conjecture is true for groups G defined over k of the types 2A∗, B_n, C_n, D_n (D₄ nontrialitarian), G₂ or F₄; a group is said to be of type 2A∗, if it is isomorphic to SU(B,τ) for a central simple algebra B of square free index over a quadratic extension k′ of k with a unitary k′|k involution τ.     

On a conjecture of Wilf

Let n and k be natural numbers and let S(n,k) denote the Stirling numbers of the second kind. It is a conjecture of Wilf that the alternating sum

     

On the transversal number and VC-dimension of families of positive homothets of a convex body

Let F be a family of positive homothets (or translates) of a given convex body K in Rⁿ. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number τ(F) of F in terms of n and the independence number ν(F). This question is motivated by a problem of Grünbaum [L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 101-180]. Our bound is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan [S.-J. Kim, K. Nakprasit, M.J. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Math. 306 (18) (2006) 2166-2173], which was of order nⁿ. By a lower bound, we show that the right order of magnitude is exponential in n.Next, we consider another measure of complexity, the Vapnik-?ervonenkis dimension of F. We prove that vcdim(F)≤3 if n=2 and is infinite for some F if n≥3. This settles a conjecture of Grünbaum [B. Grünbaum, Venn diagrams and independent families of sets, Math. Mag. 48 (1975) 12-23]: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in Rⁿ is n+1. This conjecture was disproved by Naiman and Wynn [D.Q. Naiman, H.P. Wynn, Independent collections of translates of boxes and a conjecture due to Grünbaum, Discrete Comput. Geom. 9 (1) (1993) 101-105] who constructed a counterexample of dual VC-dimension . Our result implies that no upper bound exists.     

On face numbers of manifolds with symmetry

Necessary conditions on the face numbers of Cohen-Macaulay simplicial complexes admitting a proper action of the cyclic group of a prime order are given. This result is extended further to necessary conditions on the face numbers and the Betti numbers of Buchsbaum simplicial complexes with a proper -action. Adin's upper bounds on the face numbers of Cohen-Macaulay complexes with symmetry are shown to hold for all (d−1)-dimensional Buchsbaum complexes with symmetry on n?3d−2 vertices. A generalization of Kühnel's conjecture on the Euler characteristic of 2k-dimensional manifolds and Sparla's analog of this conjecture for centrally symmetric 2k-manifolds are verified for all 2k-manifolds on n?6k+3 vertices. Connections to the Upper Bound Theorem are discussed and its new version for centrally symmetric manifolds is established.     

The maximum size of hypergraphs without generalized 4-cycles

Let fr(n) be the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain four distinct edges A, B, C, D with A∪B=C∪D and A∩B=C∩D=∅. This problem was stated by Erd?s [P. Erd?s, Problems and results in combinatorial analysis, Congr. Numer. 19 (1977) 3-12]. It can be viewed as a generalization of the Turán problem for the 4-cycle to hypergraphs.Let . Füredi [Z. Füredi, Hypergraphs in which all disjoint pairs have distinct unions, Combinatorica 4 (1984) 161-168] observed that ?r?1 and conjectured that this is equality for every r?3. The best known upper bound ?r?3 was proved by Mubayi and Verstraëte [D. Mubayi, J. Verstraëte, A hypergraph extension of the bipartite Turán problem, J. Combin. Theory Ser. A 106 (2004) 237-253]. Here we improve this bound. Namely, we show that for every r?3, and ?₃?13/9. In particular, it follows that ?r→1 as r→∞.     

Asymptotic bounds for permutations containing many different patterns

We say that a permutation σ∈Sn contains a permutation π∈Sk as a pattern if some subsequence of σ has the same order relations among its entries as π. We improve on results of Wilf, Coleman, and Eriksson et al. that bound the asymptotic behavior of pat(n), the maximum number of distinct patterns of any length contained in a single permutation of length n. We prove that by estimating the amount of redundancy due to patterns that are contained multiple times in a given permutation. We also consider the question of k-superpatterns, which are permutations that contain all patterns of a given length k. We give a simple construction that shows that Lk, the length of the shortest k-superpattern, is at most . This may lend evidence to a conjecture of Eriksson et al. that .     

Unavoidable patterns

Let Fk denote the family of 2-edge-colored complete graphs on 2k vertices in which one color forms either a clique of order k or two disjoint cliques of order k. Bollobás conjectured that for every ?>0 and positive integer k there is n(k,?) such that every 2-edge-coloring of the complete graph of order n?n(k,?) which has at least edges in each color contains a member of Fk. This conjecture was proved by Cutler and Montágh, who showed that n(k,?)<⁴k/?. We give a much simpler proof of this conjecture which in addition shows that n(k,?)<?−ck for some constant c. This bound is tight up to the constant factor in the exponent for all k and ?. We also discuss similar results for tournaments and hypergraphs.     

A generalization of Gruenhage's example

We construct, assuming the continuum hypothesis, an example of nonmetrizable n-dimensional Cantor manifold Xn(n∈N) with the following properties: 1) is hereditarily separable for all k∈N; 2) is perfectly normal for every k∈N; 3) the space F(Xn) is hereditarily normal for every seminormal functor F that preserves weights and one-to-one points and such that sp(F)={1,k}; in particular, and λ₃Xn are hereditarily normal. This example is a generalization of famous Gruenhage's example given in Gruenhage and Nyikos (1993) [4].     

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].     

Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G₁=(V,E₁),…,G_k=(V,E_k)} on the same vertices V, a set S⊂V is a maximal common connected set of F if the subgraphs of G_i,1?i?k, induced by S are connected in all G_i and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F. This problem has many practical applications, notably in computational biology. Let n=|V| and . For k?2, an algorithm in O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359-372]. In this paper, we improve this bound to O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple time algorithm.     

Self-correspondences of the generic fibre of Lefschetz pencils and the Leray filtration

In this paper we give a detailed analysis of the interaction between homological self-correspondences of the general fibre Y/k(t) of the Lefschetz fibration of a Lefschetz pencil on a smooth projective variety X/k, and the Leray filtration of ρ. We derive the result that, if the standard conjecture B(Y) holds, then the operator is algebraic, where is defined as the inverse of L on LPn−1(X) and 0 on LkPj(X) for (1,n−1)≠(k,j); in the course of our proof we see that, under the above assumption, the Künneth projectors for i≠n−1,n,n+1 are algebraic.     

On the Turán number for the hexagon

A long-standing conjecture of Erd?s and Simonovits is that ex(n,C_2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that