تقرير
Balanced independent sets in graphs omitting large cliques
| العنوان: | Balanced independent sets in graphs omitting large cliques |
|---|---|
| المؤلفون: | Laflamme, Claude, Lopez, Andres A., Soukup, Daniel T., Woodrow, Robert |
| سنة النشر: | 2016 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Mathematics - Logic, 05C55, 05C63, 05C69, 03E02 |
| الوصف: | Our goal is to investigate a close relative of the independent transversal problem in the class of infinite $K_n$-free graphs: we show that for any infinite $K_n$-free graph $G=(V,E)$ and $m\in \mathbb N$ there is a minimal $r=r(G,m)$ such that for any balanced $r$-colouring of the vertices of $G$ one can find an independent set which meets at least $m$ colour classes in a set of size $|V|$. Answering a conjecture of S. Thomass\'e, we express the exact value of $r(H_n,m)$ (using Ramsey-numbers for finite digraphs), where $H_n$ is Henson's countable universal homogeneous $K_n$-free graph. In turn, we deduce a new partition property of $H_n$ regarding balanced embeddings of bipartite graphs: for any finite bipartite $G$ with bipartition $A,B$, if the vertices of $H_n$ are partitioned into two infinite classes then there is an induced copy of $G$ in $H_n$ such that the images of $A$ and $B$ are contained in different classes. Comment: 23 pages, minor changes, version submitted to JCTB |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1611.06142 |
| رقم الأكسشن: | edsarx.1611.06142 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |