A stronger rainbow degree-sequence conjecture for bipartite graphs

About 10 years old · traced to

Let FiF_i, i≤ki\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)=∣Fi∣r_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

∑i≤jr→i>j(j−1)n\sum_{i\leq j}\overrightarrow{r}_i>j(j-1)n

for every j≤kj\leq k, then there exists a permutation π:[k]→[k]\pi:[k]\to[k] such that

∑i≤ja→iπ(i)>j(j−1)\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).

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.