𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independent Arithmetic Progressions in Clique-Free Graphs on the Natural Numbers

✍ Scribed by David S. Gunderson; Imre Leader; Hans Jürgen Prömel; Vojtěch Rödl

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
179 KB
Volume
93
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if G is a K r -free graph on N, there is an independent set in G which contains an arbitrarily long arithmetic progression together with its difference. This is a common generalization of theorems of Schur, van der Waerden, and Ramsey. We also discuss various related questions regarding (m, p, c)-sets and parameter words.

📜 SIMILAR VOLUMES

Constraints on the number of maximal ind
Constraints on the number of maximal independent sets in graphs
✍ Jiuqiang Liu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 387 KB 👁 2 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G__. Let __i(G)__ denote the number of maximal independent sets of __G__. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of m

On the Maximum Number of Independent Cyc
On the Maximum Number of Independent Cycles in a Bipartite Graph
✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

On the Density of Subgraphs in a Graph w
On the Density of Subgraphs in a Graph with Bounded Independence Number
✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(