Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

On the Spectrum of Steiner (v,k,t) Trades (II)

 A (v,k,t) trade T=T ₁−T ₂ of volume m consists of two disjoint collections T ₁ and T ₂ each containing m blocks (k-subsets) such that each t-subset is contained in the same number of blocks in T ₁ and T ₂. If each t-subset occurs at most once in T ₁, then T is called a Steiner (k,t) trade. In this paper, we continue our investigation of the spectrum S(k,2); that is, the set of allowable volumes of Steiner (k,t) trades when t=2. By using the concept of linked trades, we show that 2k+1∈S(k,2) precisely when k∈{3, 4, 7}. Received: February 28, 1997     

Domino tilings of rectangles with fixed width

Let t(k,n) denote the number of ways to tile a 1 × n rectangle with 1 × 2 rectangles (called dominoes). We show that for each fixed k the sequence t_k=(t(k,0), t(k,1),…) satisfies a difference equation (linear, homogeneous, and with constant coefficients). Furthermore, a computational method is given for finding this difference equation together with the initial terms of the sequence. This gives rise to a new way to compute t(k,n) which differs completely with the known Pfaffian method. The generating function of t_k is a rational function F_k, and F_k is given explicitly for k=1,…,8. We end with some conjectures concerning the form of F_k based on our computations.     

The Ramsey numbers for disjoint unions of trees

For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel W_m or a complete graph K_m. We show that if n?3, then R(kS_n,W₄)=(k+1)n for k?2, even n and R(kS_n,W₄)=(k+1)n-1 for k?1 and odd n. We also show that .     

Hypersurfaces containing flat subspaces

Lek k be an infinite field and suppose m.i. and n are positive integers such that t m We study the subset of k[x ₁,x ₂, … x_m ] which consists of 0 and the homogeneous members t of f of k[x ₁,x ₂, … x_m ] of fixed degree n such that there exists homogeneous F ₁, F ₂, … F_t in k[x ₁,x ₂, … x_m ] of degree one and homogenous g ₁ g ₂, …g_t , in k[x ₁,x ₂, … x_m ] such that f(x) = F ₁(x)g ₁(x) + F ₂(x)g ₂(x) + … + F _t (x)g _t (x) for each x in k ^m. In case k is algebrarcally closed we are able to prove that this set is an algebraic variety. Consequently. if k is also of characteristic 0 then we are able to prove that certain collections of symmetric k-valued multilinear functions are algebraic varieties.     

Game saturation of intersecting families

We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = {1, 2, …, n} alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsat_F(II _n,k ) and gsat_S(II _n,k ), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that $\Omega _k (n^{k/3 - 5} ) \leqslant gsat_F (\mathbb{I}_{n,k} ),gsat_S (\mathbb{I}_{n,k} ) \leqslant O_k (n^{k - \sqrt {k/2} } )$ .     

Allowable Interval Sequences and Line Transversals in the Plane

Given a family F of n pairwise disjoint compact convex sets in the plane with non-empty interiors, let T(k) denote the property that every subfamily of F of size k has a line transversal, and T the property that the entire family has a line transversal. We illustrate the applicability of allowable interval sequences to problems involving line transversals in the plane by proving two new results and generalizing three old ones. Two of the old results are Klee??s assertion that if F is totally separated then T(3) implies T, and the following variation of Hadwiger??s Transversal Theorem proved by Wenger and (independently) Tverberg: If F is ordered and each four sets of F have some transversal which respects the order on F, then there is a transversal for all of F which respects this order. The third old result (a consequence of an observation made by Kramer) and the first of the new results (which partially settles a 2008 conjecture of Eckhoff) deal with fractional transversals and share the following general form: If F has property T(k) and meets certain other conditions, then there exists a transversal of some m sets in F, with k<m<n. The second new result establishes a link between transversal properties and separation properties of certain families of convex sets.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

The Ramsey number r(H, K _n ) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c _k,t is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359, 2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m ^γ ), where 1 < γ < 2. Then r(H,K_n) ￡ c_H ([(n)/(lnn)])^1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c _H is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000).     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

On the distribution of sociable numbers

For a positive integer n, define s(n) as the sum of the proper divisors of n. If s(n)>0, define s₂(n)=s(s(n)), and so on for higher iterates. Sociable numbers are those n with sk(n)=n for some k, the least such k being the order of n. Such numbers have been of interest since antiquity, when order-1 sociables (perfect numbers) and order-2 sociables (amicable numbers) were studied. In this paper we make progress towards the conjecture that the sociable numbers have asymptotic density 0. We show that the number of sociable numbers in [1,x], whose cycle contains at most k numbers greater than x, is o(x) for each fixed k. In particular, the number of sociable numbers whose cycle is contained entirely in [1,x] is o(x), as is the number of sociable numbers in [1,x] with order at most k. We also prove that but for a set of sociable numbers of asymptotic density 0, all sociable numbers are contained within the set of odd abundant numbers, which has asymptotic density about 1/500.     

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

Twisted inner products and contraction inequalities on spaces of contravariant and covariant tensors

Given positive integers n and p, and a complex finite dimensional vector space V, we let S_n,p(V) denote the set of all functions from V×V×?×V-(n+p copies) to C that are linear and symmetric in the first n positions, and conjugate linear symmetric in the last p positions. Letting κ=min{n,p} we introduce twisted inner products, [·,·]_s,t,1?s,t?κ, on S_n,p(V), and prove the monotonicity condition [F,F]_s,t?[F,F]_u,v is satisfied when s?u?κ,t?v?κ, and F∈S_n,p(V). Using the monotonicity condition, and the Cauchy-Schwartz inequality, we obtain as corollaries many known inequalities involving norms of symmetric multilinear functions, which in turn imply known inequalities involving permanents of positive semidefinite Hermitian matrices. New tensor and permanental inequalities are also presented. Applications to partial differential equations are indicated.     

The visually distinct configurations of k sets

Two sets of sets, C₀ and C₁, are said to be visually equivalent if there is a 1-1 mapping m from C₀ onto C₁ such that for every S, T?C₀, S ∩ T=0 if and only if m(S)∩ m(T)=0 and S?T if and only if m(S)?m(T). We find estimates for V(k), the number of equivalence classes of this relation on sets of k sets, for finite and infinite k. Our main results are that for finite k, $\text{1}\text{2}\text{k}{}^2\text{-k log k <log V (k)<ak}{}^2\text{+βk+log k}$, where α and β are approximately 0.7255 and 2.5323 respectively, and there is a set N of cardinality $\text{1}\text{2}\text{(k}{}^2\text{+k)}$ such that there are V(k) visually distinct sets of k subsets of N.     

On intersecting families of finite sets

Let X = [1, n] be a finite set of cardinality n and let $\text{F}$ be a family of k-subsets of X. Suppose that any two members of $\text{F}$ intersect in at least t elements and for some given positive constant c, every element of X is contained in less than c |$\text{F}$| members of $\text{F}$. How large |$\text{F}$| can be and which are the extremal families were problems posed by Erdös, Rothschild, and Szemerédi. In this paper we answer some of these questions for n > n₀(k, c). One of the results is the following: let $\text{t = 1,}\text{3}\text{7}\text{< c <}\text{1}\text{2}$. Then whenever $\text{F}$ is an extremal family we can find a 7-3 Steiner system $\text{B}$ such that $\text{F}$ consists exactly of those k-subsets of X which contain some member of $\text{B}$.