Name
Abstract | ||
|---|---|---|
For a set of integers S, define (SAPk) to be the k-uniform hypergraph with vertex set S and hyperedges corresponding the set of all arithmetic progression of length k in S. Similarly, for a graph H, define (HKk) to be the (k2)-uniform hypergaph on the vertex ser E(H) with hyperedges corresponding to the edge sets of all copies of Kk in H. Also, we say that a k-uniform hypergraph has girth at least g if any h edges (1≤h<g) span at least (k−1)h+1 vertices. For all integers k and ℓ, we establish the existence of a relatively small graph H having girth k and the property that every ℓ-coloring of the edges of H yields a monochromatic copy of Ck. We also show that for all integers k,ℓ, and g, there exists a relatively small set S⊂N such that the related hypergraph (SAPk) had girth g and each ℓ-colorings of S yields a monochromatic arithmetic progression of length k. Finally, for all integers k,ℓ, and g, we establish the existence of a relatively small graph H such that the associated hypergraph (HKk) has girth g and each ℓ-coloring of the edges of H yields a monochromatic copy of Kk. Our proofs give improved (and the first explicit) numerical bounds on the size of these objects. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.endm.2015.07.076 | Electronic Notes in Discrete Mathematics |
Field | DocType | Volume |
Integer,Discrete mathematics,Graph,Combinatorics,Monochromatic color,Vertex (geometry),Constraint graph,Ramsey's theorem,Mathematics | Journal | 50 |
ISSN | Citations | PageRank |
1571-0653 | 0 | 0.34 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiêp Hàn | 1 | 39 | 8.07 |
| Troy Retter | 2 | 5 | 2.20 |
| Vojtech Rödl | 3 | 877 | 139.49 |
| Mathias Schacht | 4 | 361 | 37.90 |