Fair splittings by independent sets in sparse graphs

被引:4
作者
Black, Alexander [1 ]
Cetin, Umur [2 ]
Frick, Florian [3 ]
Pacun, Alexander [4 ]
Setiabrata, Linus [1 ]
机构
[1] Cornell Univ, Dept Math, White Hall, Ithaca, NY 14853 USA
[2] Bilkent Univ, Dept Math, TR-06800 Ankara, Turkey
[3] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[4] SUNY Stony Brook, Math Dept, Stony Brook, NY 11794 USA
关键词
CHROMATIC NUMBER; TVERBERG;
D O I
10.1007/s11856-020-1980-5
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a partition V-1 square cup V-2 square cup ... square cup V-m of the vertex set of a graph, we are interested in finding multiple disjoint independent sets that contain the correct fraction of vertices of each V-j. We give conditions for the existence of q such independent sets in terms of the topology of the independence complex. Further, we relate this question to the existence of q-fold points of coincidence for any continuous map from the independence complex to Euclidean space of a certain dimension, and to the existence of equivariant maps from the q-fold deleted join of the independence complex to a certain representation sphere of the symmetric group. As a corollary we derive the existence of q pairwise disjoint independent sets accurately representing the V-j in certain sparse graphs for q a power of a prime.
引用
收藏
页码:603 / 627
页数:25
相关论文
共 23 条
[1]  
AHARONI R., 2017, A Journey Through Discrete Mathematics, P31, DOI [10.1007/978-3-319-44479-62, DOI 10.1007/978-3-319-44479-62]
[2]  
Alishahi Meysam, 2017, ELECTRON J COMB, V24
[3]   THE LINEAR ARBORICITY OF GRAPHS [J].
ALON, N .
ISRAEL JOURNAL OF MATHEMATICS, 1988, 62 (03) :311-325
[4]   THE CHROMATIC NUMBER OF KNESER HYPERGRAPHS [J].
ALON, N ;
FRANKL, P ;
LOVASZ, L .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1986, 298 (01) :359-370
[5]   PROBABILISTIC METHODS IN COLORING AND DECOMPOSITION PROBLEMS [J].
ALON, N .
DISCRETE MATHEMATICS, 1994, 127 (1-3) :31-46
[6]  
Alon N, 2009, P AM MATH SOC, V137, P467
[7]   Optimal bounds for the colored Tverberg problem [J].
Blagojevic, Pavle V. M. ;
Matschke, Benjamin ;
Ziegler, Guenter M. .
JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 2015, 17 (04) :739-754
[8]   Tverberg plus constraints [J].
Blagojevic, Pavle V. M. ;
Frick, Florian ;
Ziegler, Guenter M. .
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2014, 46 :953-967
[9]  
Bukh B, 2017, J COMPUT GEOM, V8, P174
[10]   A local criterion for Tverberg graphs [J].
Engstrom, Alexander .
COMBINATORICA, 2011, 31 (03) :321-332