Search

Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots ,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left({\matrix{ n \cr 2 \cr } } \right) + o\left({n^2 } \right)}.$ Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left({n^2 } \right)$ to $o\left(1 \right)$ , and also show a labeled first-order 0-1 law in the language ${\cal L}_r $ , consisting of r binary relations, one for each element of $[r]$. In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots ,r} \right\}$. Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws. [ABSTRACT FROM AUTHOR]

Given graphs T and H , the generalized Turán number ex (n , T , H) is the maximum number of copies of T in an n -vertex graph with no copies of H. Alon and Shikhelman, using a result of Erdős, determined the asymptotics of ex (n , K 3 , H) when the chromatic number of H is greater than three and proved several results when H is bipartite. We consider this problem when H has chromatic number three. Even this special case for the following relatively simple three chromatic graphs appears to be challenging. The suspension H ˆ of a graph H is the graph obtained from H by adding a new vertex adjacent to all vertices of H. We give new upper and lower bounds on ex (n , K 3 , H ˆ) when H is a path, even cycle, or complete bipartite graph. One of the main tools we use is the triangle removal lemma, but it is unclear if much stronger statements can be proved without using the removal lemma. [ABSTRACT FROM AUTHOR]

Given integers ℓ , n , the ℓ th power of the path P n is the ordered graph P n ℓ with vertex set v 1 < v 2 < ⋯ < v n and all edges of the form v i v j where | i − j | ≤ ℓ . The Ramsey number r ( P n ℓ , P n ℓ ) is the minimum N such that every 2-coloring of [ N ] 2 results in a monochromatic copy of P n ℓ . It is well-known that r ( P n 1 , P n 1 ) = ( n − 1 ) 2 + 1 . For ℓ > 1 , Balko–Cibulka–Král–Kynčl proved that r ( P n ℓ , P n ℓ ) < c ℓ n 128 ℓ and asked for the growth rate for fixed ℓ . When ℓ = 2 , we improve this upper bound substantially by proving r ( P n 2 , P n 2 ) < c n 19.5 . Using this result, we determine the correct tower growth rate of the k -uniform hypergraph Ramsey number of a ( k + 1 ) -clique versus an ordered tight path. Finally, we consider an ordered version of the classical Erdős–Hajnal hypergraph Ramsey problem, improve the tower height given by the trivial upper bound, and conjecture that this tower height is optimal. [ABSTRACT FROM AUTHOR]

A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with [ABSTRACT FROM AUTHOR]

For various k-uniform hypergraphs F, we give tight lower bounds on the number of copies of F in a k-uniform hypergraph with a prescribed number of vertices and edges. These are the first such results for hypergraphs, and extend earlier theorems of various authors who proved that there is one copy of F. A sample result is the following: Füredi-Simonovits [11] and independently Keevash-Sudakov [16] settled an old conjecture of Sós [29] by proving that the maximum number of triples in an n vertex triple system (for n sufficiently large) that contains no copy of the Fano plane is p( n)=( 2⌈n/2⌉)⌊ n/2⌋+( 2⌊n/2⌋⌈ n/2⌉). We prove that there is an absolute constant c such that if n is sufficiently large and 1 ≤ q ≤ cn2, then every n vertex triple system with p( n)+ q edges contains at least $6q\left( {\left( {_4^{\left\lfloor {n/2} \right\rfloor } } \right) + \left( {\left\lceil {n/2} \right\rceil - 3} \right)\left( {_3^{\left\lfloor {n/2} \right\rfloor } } \right)} \right)$ copies of the Fano plane. This is sharp for q≤ n/2–2. Our proofs use the recently proved hypergraph removal lemma and stability results for the corresponding Turán problem. [ABSTRACT FROM AUTHOR]

We obtain new lower bounds for the independence number of Kr-free graphs and linear k-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99-107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system is semi-bipartite if its vertex set contains a vertex subset X such that every edge of intersects X in exactly two points. It is easy to see that if is semi-bipartite, then the neighborhood of every pair of vertices in is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erdős–Kleitman–Rothschild theorem to triple systems. The proof uses the Frankl–Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints. [Copyright &y& Elsevier]

d-dimensional simplex is a collection of d+1 sets with empty intersection, every d of which have nonempty intersection. A k-uniform d-cluster is a collection of d+1 sets of size k with empty intersection and union of size at most 2 k. We prove the following result which simultaneously addresses an old conjecture of Chvátal [6] and a recent conjecture of the second author [28]. For d≥2 and ζ >0 there is a number T such that the following holds for sufficiently large n. Let G be a k-uniform set system on [ n] ={1,..., n} with ζ n< k < n/2− T, and suppose either that G contains no d-dimensional simplex or that G contains no d-cluster. Then | G|≤ % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXguY9 % gCGievaerbd9wDYLwzYbWexLMBbXgBcf2CPn2qVrwzqf2zLnharyav % P1wzZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC % 0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yq % aqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabe % qaamaaeaqbaaGcbaWaaeWaaeaafaqabeGabaaabaGaemOBa4MaeyOe % I0IaeGymaedabaGaem4AaSMaeyOeI0IaeGymaedaaaGaayjkaiaawM % caaaaa!43EB! $$ \left( {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right) $$ with equality only for the family of all k-sets containing a specific element. In the non-uniform setting we obtain the following exact result that generalises a question of Erdős and a result of Milner, who proved the case d=2. Suppose d≥2 and G is a set system on [ n] that does not contain a d-dimensional simplex, with n sufficiently large. Then | G|≤2+Σ % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXguY9 % gCGievaerbd9wDYLwzYbWexLMBbXgBcf2CPn2qVrwzqf2zLnharyav % P1wzZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC % 0xbbL8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yq % aqpepae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabe % qaamaaeaqbaaGcbaWaaeWaaeaafaqabeGabaaabaGaemOBa4MaeyOe % I0IaeGymaedabaGaemyAaKgaaaGaayjkaiaawMcaaaaa!420A! $$ \left( {\begin{array}{*{20}c} {n - 1} \\ i \\ \end{array} } \right) $$, with equality only for the family consisting of all sets that either contain some specific element or have size at most d−1. Each of these results is proved via the corresponding stability result, which gives structural information on any G whose size is close to maximum. These in turn rely on a stability theorem that we obtain using an earlier result of Frankl. [ABSTRACT FROM AUTHOR]

Let 3 ⩽k < n/2. We prove the analogue of the Erdős-Ko-Rado theorem for the random k-uniform hypergraph Gk(n, p) when k < (n/2)1/3; that is, we show that with probability tending to 1 as n→∞, the maximum size of an intersecting subfamily of Gk(n, p) is the size of a maximum trivial family. The analogue of the Erdős-Ko-Rado theorem does not hold for all p when k ⪢ n1/3. We give quite precise results for k < n1/2-ϵ. For larger k we show that the random Erdős-Ko- Rado theorem holds as long as p is not too small, and fails to hold for a wide range of smaller values of p. Along the way, we prove that every non-trivial intersecting k-uniform hypergraph can be covered by k2 - k + 1 pairs, which is sharp as evidenced by projective planes. This improves upon a result of Sanders [7]. Several open questions remain. [ABSTRACT FROM AUTHOR]

Abstract: A family of -graphs is called non-principal if its Turán density is strictly smaller than that of each individual member. For each we find two (explicit) -graphs and such that is non-principal. Our proofs use stability results for hypergraphs. This completely settles the question posed by Mubayi and Rödl [On the Turán number of triple systems, J. Combin. Theory A, 100 (2002) 135–152]. Also, we observe that the demonstrated non-principality phenomenon holds also with respect to the Ramsey–Turán density as well. [Copyright &y& Elsevier]

Let 2 ≤ q ≤min{ p, t − 1} be fixed and n → ∞. Suppose that $$\mathcal{F}$$ is a p-uniform hypergraph on n vertices that contains no complete q-uniform hypergraph on t vertices as a trace. We determine the asymptotic maximum size of $${\mathcal{F}}$$ in many cases. For example, when q = 2 and p∈{ t, t + 1}, the maximum is $$( \frac{n}{t-1})^{t-1} + o(n^{t-1})$$ , and when p = t = 3, it is $$\lfloor \frac{(n-1)^2}{4}\rfloor$$ for all n≥ 3. Our proofs use the Kruskal-Katona theorem, an extension of the sunflower lemma due to Füredi, and recent results on hypergraph Turán numbers. [ABSTRACT FROM AUTHOR]

Abstract: A minimal -cycle is a family of sets for which if and only if or and are consecutive modulo . Let be the maximum size of a family of -sets of an element set containing no minimal -cycle. Our results imply that for fixed , where . We also prove that as . This supports a conjecture of Z. Füredi [Hypergraphs in which all disjoint pairs have distinct unions, Combinatorica 4 (2–3) (1984) 161–168] on families in which no two pairs of disjoint sets have the same union. [Copyright &y& Elsevier]

Abstract: For an r-graph H, let , where the minimum is taken over all -sets of vertices of H, and is the number of vertices v such that is an edge of H. Given a family of r-graphs, the co-degree Turán number is the maximum of among all r-graphs H which contain no member of as a subhypergraph. Define the co-degree density of a family to be When , non-zero values of are known for very few finite r-graphs families . Nevertheless, our main result implies that the possible values of form a dense set in . The corresponding problem in terms of the classical Turán density is an old question of Erdős (the jump constant conjecture), which was partially answered by Frankl and Rödl [P. Frankl, V. Rödl, Hypergraphs do not jump, Combinatorica 4 (2–3) (1984) 149–159]. We also prove the existence, by explicit construction, of finite satisfying . This is parallel to recent results on the Turán density by Balogh [J. Balogh, The Turán density of triple systems is not principal, J. Combin. Theory Ser. A 100 (1) (2002) 176–180], and by the first author and Pikhurko [D. Mubayi, O. Pikhurko, Constructions of non-principal families in extremal hypergraph theory, Discrete Math. (Special issue in honor of Miklos Simonovits'' 60th birthday), in press]. [Copyright &y& Elsevier]

Abstract: Let the k-graph consist of k edges that pairwise intersect exactly in one vertex x, plus one more edge intersecting each of these edges in a vertex different from x. We prove that, for n sufficiently large, the maximum number of edges in an n-vertex k-graph containing no copy of is , which equals the number of edges in a complete k-partite k-graph with almost equal parts. This is the only extremal example. This result is a special case of our more general theorem that applies to a larger class of excluded configurations. [Copyright &y& Elsevier]

Abstract: Fix . Let be the -uniform hypergraph obtained from the complete graph by enlarging each edge with a set of new vertices. Thus has vertices and edges. We prove that the maximum number of edges in an -vertex -uniform hypergraph containing no copy of isas . This is the first infinite family of irreducible -uniform hypergraphs for each odd whose Turán density is determined. Along the way, we give three proofs of a hypergraph generalization of Turán''s theorem. We also prove a stability theorem for hypergraphs, analogous to the Simonovits stability theorem for complete graphs. [Copyright &y& Elsevier]

Abstract: It is shown that every n vertex triple system with every pair of vertices lying in at least triples contains a copy of the Fano plane. The constant is sharp. This is the first triple system for which such a (nonzero) constant is determined. [Copyright &y& Elsevier]

Abstract: Given positive integers , with , and , let be the minimum size of a family of (nonempty distinct) subsets of such that every k-subset of contains at least t members of , and every -subset of contains at most members of . For fixed k and t, we determine the order of magnitude of . We also consider related Turán numbers and , where () denotes the minimum size of a family such that every k-subset of contains at least t members of . We prove that for fixed with and . [Copyright &y& Elsevier]