A stronger rainbow degree-sequence conjecture for bipartite graphs

From papers

Let FiF_i, iki\leq k, be subgraphs of Kn,nK_{n,n}, and let A=(aij)A=(a_{ij}) be the k×nk\times n matrix whose entry aija_{ij} is the degree of vjv_j in FiF_i. Let ri(A)r_i(A) be the sum of the ii-th row, so that ri(A)=Fir_i(A)=|F_i|. For sequences, write a\overrightarrow{a} for the rearrangement of aa in non-decreasing order, and compare sequences componentwise after rearrangement. Stronger rainbow degree-sequence conjecture. If

ijri>j(j1)n\sum_{i\leq j}\overrightarrow{r}_i>j(j-1)n

for every jkj\leq k, then there exists a permutation π:[k][k]\pi:[k]\to[k] such that

ijaiπ(i)>j(j1)\sum_{i\leq j}\overrightarrow{a}_{i\pi(i)}>j(j-1)

for every jj. This strengthens the preceding theorem by requiring simultaneous inequalities for the rearranged selected columns, rather than only the componentwise lower bound represented by (1,2,,k)(1,2,\ldots,k).

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ron Aharoni and David Howard, “A rainbow r-partite version of the Erdős-Ko-Rado theorem”, arXiv:1605.06752 (2016).

Solutions 0

No solutions have been posted yet.