A Ramsey‐type problem and the Turán numbers*

For each n and k, we examine bounds on the largest number m so that for any k‐coloring of the edges of K_n there exists a copy of K_m whose edges receive at most k?1 colors. We show that for , the largest value of m is asymptotically equal to the Turá number , while for any constant then the largest m is asymptotically larger than that Turá number. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 120–129, 2002     

On Turán problems for Cartesian products of graphs

Let be disjoint sets of sizes and . Let be a family of quadruples, having elements from and from , such that any subset with and contains one of the quadruples. We prove that the smallest size of is as . We also solve asymptotically a more general two‐partite Turán problem for quadruples.     

Weighted covering numbers of convex sets

In this paper we define the notions of weighted covering number and weighted separation number for convex sets, and compare them to the classical covering and separation numbers. This sheds new light on the equivalence of classical covering and separation. We also provide a formula for computing these numbers via a limit of classical covering numbers in higher dimensions.     

Asymptotic Bounds for General Covering Designs

Given five positive integers and t where and a t‐ general covering design is a pair where X is a set of n elements (called points) and a multiset of k‐subsets of X (called blocks) such that every p‐subset of X intersects at least λ blocks of in at least t points. In this article we continue the work carried out by Etzion, Wei, and Zhang [Des. Codes Cryptogr. 5 (1995), 217–239] on the asymptotic covering density of general covering designs. We will present combinatorial constructions leading to new upper bounds on the asymptotic covering density of 4‐(n, 4, 6, 1) general covering designs and 4‐ general covering designs with . The new bound on the asymptotic covering density of 4‐(n, 4, 6, 1) general covering designs is equivalent to a new lower bound for the Turán density .     

Generalized covering designs and clique coverings

Inspired by the “generalized t‐designs” defined by Cameron [P. J. Cameron, Discrete Math 309 (2009), 4835–4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:378‐406, 2011     

The lotto numbers L(n,3,p,2)

An (n,k,p,t)‐lotto design is an n‐set N and a set of k‐subsets of N (called blocks) such that for each p‐subset P of N, there is a block for which . The lotto number L(n,k,p,t) is the smallest number of blocks in an (n,k,p,t)‐lotto design. The numbers C(n,k,t) = L(n,k,t,t) are called covering numbers. It is easy to show that, for n ≥ k(p ? 1), For k = 3, we prove that equality holds if one of the following holds:

• (i) n is large, in particular
• (ii)
• (iii) 2 ≤ p ≤ 6.

© 2006 Wiley Periodicals, Inc. J Combin Designs 14: 333–350, 2006     

Group divisible covering designs with block size four

Group divisible covering designs (GDCDs) were introduced by Heinrich and Yin as a natural generalization of both covering designs and group divisible designs. They have applications in software testing and universal data compression. The minimum number of blocks in a k‐GDCD of type $g^u$ is a covering number denoted by $C(k,g^u)$. When $k=3$, the values of $C(3,g^u)$ have been determined completely for all possible pairs $(g,u)$. When $k=4$, Francetić et al. constructed many families of optimal GDCDs, but the determination remained far from complete. In this paper, two specific 4‐IGDDs are constructed, thereby completing the existence problem for 4‐IGDDs of type ${(g,h)}^u$. Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for $(g,u)$ whose status remains undetermined arise when $g\equiv 7mod12$ and $u\equiv 3mod6$, when $g\equiv 11,14,17,23mod24$ and $u\equiv 5mod6$, and in several small families for which one of g and u is fixed.     

Lagrangian densities of linear forests and Turán numbers of their extensions

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. However, determining the Lagrangian density of a hypergraph is not an easy task even for a “simple” hypergraph. For example, to determine the Lagrangian density of $K_4^3$ is equivalent to determine the Turán density of $K_4^3$ (a long standing conjecture of Turán). Hefetz and Keevash studied the Lagrangian density of the 3‐uniform matching of size 2. Pikhurko determined the Lagrangian density of a 4‐uniform tight path of length 2 and this led to confirm the conjecture of Frankl and Füredi on the Turán number of the $r$‐uniform generalized triangle for the case $r=4$. It is natural and interesting to consider Lagrangian densities of other “basic” hypergraphs. In this paper, we determine the Lagrangian densities for a class of 3‐uniform linear forests. For positive integers $s$ and $t$, let $P_{s,t}$ be the disjoint union of a 3‐uniform linear path of length $s$ and $t$ pairwise disjoint edges. In this paper, we determine the Lagrangian densities of $P_{s,t}$ for any $t$ and $s=2$ or 3. Applying a modified version of Pikhurko's transference argument used by Brandt, Irwin, and Jiang, we obtain the Turán numbers of their extensions.     

Estimates of covering numbers of convex sets with slowly decaying orthogonal subsets

Covering numbers of precompact symmetric convex subsets of Hilbert spaces are investigated. Lower bounds are derived for sets containing orthogonal subsets with norms of their elements converging to zero sufficiently slowly. When these sets are convex hulls of sets with power-type covering numbers, the bounds are tight. The arguments exploit properties of generalized Hadamard matrices. The results are illustrated by examples from machine learning, neurocomputing, and nonlinear approximation.     

Bounds on Turán determinants

Let μ denote a symmetric probability measure on [−1,1] and let (p_n) be the corresponding orthogonal polynomials normalized such that p_n(1)=1. We prove that the normalized Turán determinant Δ_n(x)/(1−x²), where , is a Turán determinant of order n−1 for orthogonal polynomials with respect to . We use this to prove lower and upper bounds for the normalized Turán determinant in the interval −1<x<1.     

Combinatorial coverings from geometries over principal ideal rings

A t-(v, k, λ) covering is an incidence structure with v points, each block incident on exactly k points, such that every set of t distinct points is incident on at least λ blocks. By considering certain geometries over finite principal ideal rings, we construct infinite families of t-(v, k, λ) coverings having many interesting combinatorial properties. © 1999 John & Sons, Inc. J Combin Designs 7: 247–268, 1999     

Triangles in C 5-free graphs and hypergraphs of girth six

We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$\left(1+o\left(1\right)\right)\frac{1}{3\sqrt{2}}{n}^{3∕2}.$$ We show a connection to $r$-uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced-$C_4$-free and $C_5$-free graph.     

On even-cycle-free subgraphs of the hypercube

It is shown that the size of any C4k+2-free subgraph of the hypercube Qn, k?3, is o(e(Qn)).     

On the Minimal Number of Even Submatrices of 0-1 Matrices

An asymptotic formula for the minimum possible number of even p x q submatrices of an m x n 0-1 matrix A is obtained. It is shown that if Ais considered random and pq is even, then the distributionof the number of the even p x q submatricesof A is highly skewed to the right, the left endpointof the distribution being very close to its mean, while its rightendpoint is twice the mean. A relation to Turán numbersis indicated.     

The chromatic numbers of double coverings of a graph

If we fix a spanning subgraph H of a graph G, we can define a chromatic number of H with respect to G and we show that it coincides with the chromatic number of a double covering of G with co-support H. We also find a few estimations for the chromatic numbers of H with respect to G.     

On non-strong jumping numbers and density structures of hypergraphs

Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number α∈[0,1) is a jump for r-uniform graphs if there exists a constant c>0 such that for any family F of r-uniform graphs, if the Turán density of F is greater than α, then the Turán density of F is at least α+c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0,1) is a jump for graphs. Erd?s also showed that every number in [0,r!/r^r) is a jump for r-uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in [r!/r^r,1) for r-uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept-strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps.     

Mantel's theorem for random hypergraphs

A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle‐free subgraph of K_n is bipartite. A sparse version of Mantel's Theorem is that, for sufficiently large p, every maximum triangle‐free subgraph of G(n, p) is w.h.p. bipartite. Recently, DeMarco and Kahn proved this for for some constant K, and apart from the value of the constant this bound is best possible. We study an extremal problem of this type in random hypergraphs. Denote by F₅, which is sometimes called the generalized triangle, the 3‐uniform hypergraph with vertex set and edge set . One of the first results in extremal hypergraph theory is by Frankl and Füredi, who proved that the maximum 3‐uniform hypergraph on n vertices containing no copy of F₅ is tripartite for n > 3000. A natural question is for what p is every maximum F₅‐free subhypergraph of w.h.p. tripartite. We show this holds for for some constant K and does not hold for . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 48, 641–654, 2016     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002