Search

We produce an edge-coloring of the complete 3-uniform hypergraph on n vertices with [ABSTRACT FROM AUTHOR]

Let $\mathcal{F}$ be a family of r-uniform hypergraphs. The chromatic threshold of $\mathcal{F}$ is the infimum of all non-negative reals c such that the subfamily of $\mathcal{F}$ comprising hypergraphs H with minimum degree at least $c \binom{| V(H) |}{r-1}$ has bounded chromatic number. This parameter has a long history for graphs (r = 2), and in this paper we begin its systematic study for hypergraphs.Łuczak and Thomassé recently proved that the chromatic threshold of the so-called near bipartite graphs is zero, and our main contribution is to generalize this result to r-uniform hypergraphs. For this class of hypergraphs, we also show that the exact Turán number is achieved uniquely by the complete (r + 1)-partite hypergraph with nearly equal part sizes. This is one of very few infinite families of non-degenerate hypergraphs whose Turán number is determined exactly. In an attempt to generalize Thomassen's result that the chromatic threshold of triangle-free graphs is 1/3, we prove bounds for the chromatic threshold of the family of 3-uniform hypergraphs not containing {abc, abd, cde}, the so-called generalized triangle.In order to prove upper bounds we introduce the concept of fibre bundles, which can be thought of as a hypergraph analogue of directed graphs. This leads to the notion of fibre bundle dimension, a structural property of fibre bundles that is based on the idea of Vapnik–Chervonenkis dimension in hypergraphs. Our lower bounds follow from explicit constructions, many of which use a hypergraph analogue of the Kneser graph. Using methods from extremal set theory, we prove that these Kneser hypergraphs have unbounded chromatic number. This generalizes a result of Szemerédi for graphs and might be of independent interest. Many open problems remain. [ABSTRACT FROM PUBLISHER]

For s ⩾ 4, the 3-uniform tight cycle C3s has vertex set corresponding to s distinct points on a circle and edge set given by the s cyclic intervals of three consecutive points. For fixed s ⩾ 4 and s ≢ 0 (mod 3), we prove that there are positive constants a and b with 2at < r(C3s,K3t ) < 2bt2 log t. The lower bound is obtained via a probabilistic construction. The upper bound for s > 5 is proved by using supersaturation and the known upper bound for r(K34,K3t ), while for s = 5 it follows from a new upper bound for r(K3-5 ,K3t ) that we develop. [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]

Chung and Graham began the systematic study of k-uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs. One feature that became apparent in the early work on k-uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990's. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,762-800, 2015 [ABSTRACT FROM AUTHOR]

A k-path is a hypergraph P k = { e 1 , e 2 , … , e k } such that | e i ∩ e j | = 1 if | j − i | = 1 and e i ∩ e j = ∅ otherwise. A k-cycle is a hypergraph C k = { e 1 , e 2 , … , e k } obtained from a ( k − 1 ) -path { e 1 , e 2 , … , e k − 1 } by adding an edge e k that shares one vertex with e 1 , another vertex with e k − 1 and is disjoint from the other edges. Let ex r ( n , G ) be the maximum number of edges in an r -graph with n vertices not containing a given r -graph G . We prove that for fixed r ≥ 3 , k ≥ 4 and ( k , r ) ≠ ( 4 , 3 ) , for large enough n : ex r ( n , P k ) = ex r ( n , C k ) = ( n r ) − ( n − ⌊ k − 1 2 ⌋ r ) + { 0 if k is odd ( n − ⌊ k − 1 2 ⌋ − 2 r − 2 ) if k is even and we characterize all the extremal r -graphs. We also solve the case ( k , r ) = ( 4 , 3 ) , which needs a special treatment. The case k = 3 was settled by Frankl and Füredi. This work is the next step in a long line of research beginning with conjectures of Erdős and Sós from the early 1970s. In particular, we extend the work (and settle a conjecture) of Füredi, Jiang and Seiver who solved this problem for P k when r ≥ 4 and of Füredi and Jiang who solved it for C k when r ≥ 5 . They used the delta system method, while we use a novel approach which involves random sampling from the shadow of an r -graph. [ABSTRACT FROM AUTHOR]