Search ResultsShowing 1-4 of 4
-
2-Colored Matchings in a 3-Colored K^{3}_{12}
Neal Bushaw et al.Comments: 5 pages. Summary paper of a problem solved at the Emlektabla Conference 2010. Reference added and small note made about the previous conjecturesCategories: math.COKeywords: pairwise vertex disjoint edges, smallest test case, ramsey-type results, uniform hypergraph, monochromatic matchingsTags: conference paperLet $K_{n}^{r}$ denote the complete $r$-uniform hypergraph on $n$ vertices. A matching $M$ in a hypergraph is a set of pairwise vertex disjoint edges. Recent Ramsey-type results rely on lemmas about the size of monochromatic matchings. A starting point for this study comes from a well-known result of Alon, Frankl, and Lov\'asz (1986). Our motivation is to find the smallest $n$ such that every $t$-coloring of $K_{n}^{r}$ contains an $s$-colored matching of size $k$. It has been conjectured that in every coloring of the edges of $K_n^r$ with 3 colors there is a 2-colored matching of size at least $k$ provided that $n \geq kr + \lfloor \frac{k-1}{r+1} \rfloor$. The smallest test case is when $r=3$ and $k=4$. We prove that in every 3-coloring of the edges of $K_{12}^3$ there is a 2-colored matching of size 4.
-
Graph coloring manifolds
Comments: 19 pages; revised section 3; to appear in "Contemporary Mathematics"Journal: Algebraic and Geometric Combinatorics, 51--69, Contemp. Math., 423, Amer. Math. Soc., Providence, RI, 2006Keywords: graph coloring manifolds, class comprises examples, hom complex construction, rich class, stiefel manifoldsTags: journal articleWe introduce a new and rich class of graph coloring manifolds via the Hom complex construction of Lovasz. The class comprises examples of Stiefel manifolds, series of spheres and products of spheres, cubical surfaces, as well as examples of Seifert manifolds. Asymptotically, graph coloring manifolds provide examples of highly connected, highly symmetric manifolds.
-
arXiv:math/0406118 (Published 2004-06-07)
Homotopy types of box complexes
Comments: 11 pagesJournal: Combinatorica, 27 (2007), no. 6, 669-682.Keywords: box complexes, homotopy types, lovaszs original bound, chromatic number, topological lower boundsTags: journal articleIn [MZ04] Matousek and Ziegler compared various topological lower bounds for the chromatic number. They proved that Lovasz's original bound [L78] can be restated as $\chr G \geq \ind (\B(G)) +2$. Sarkaria's bound [S90] can be formulated as $\chr G \geq \ind (\B_0(G)) +1$. It is known that these lower bounds are close to each other, namely the difference between them is at most 1. In this paper we study these lower bounds, and the homotopy types of box complexes. Some of the results was announced in [MZ04].
-
arXiv:math/0310339 (Published 2003-10-21)
Box complexes, neighborhood complexes, and the chromatic number
Comments: 8 pages, 1 figureJournal: Journal of Combinatorial Theory, Series A 108 (2004), pp. 159-168.Keywords: chromatic number, neighborhood complexes, box complexes, simplicial complexes, knesers conjectureTags: journal articleLovasz's striking proof of Kneser's conjecture from 1978 using the Borsuk--Ulam theorem provides a lower bound on the chromatic number of a graph. We introduce the shore subdivision of simplicial complexes and use it to show an upper bound to this topological lower bound and to construct a strong Z_2-deformation retraction from the box complex (in the version introduced by Matousek and Ziegler) to the Lovasz complex. In the process, we analyze and clarify the combinatorics of the complexes involved and link their structure via several ``intermediate'' complexes.