Hou Tin Chau

Maximum degree of induced subgraphs of the Kneser graph

In 2019, Huang proved the Sensitivity Conjecture in the following graph-theoretic form: if F is a set of vertices in the n-dimensional hypercube graph Q_n, with |F| = 2^{n-1} +1 (one more than the independence number of Q_n), then the subgraph induced by F has maximum degree at least n^{1/2}. We consider the analogous problem for sets of vertices in the Kneser graph K(n, k), i.e. the graph whose vertices are the k-element subsets of {1, 2, ..., n}, and where two k-element sets are joined by an edge if and only if they are disjoint. Using spectral graph theory, we show that if n > 10000 s^5 k, then the minimal maximum degree of an m-vertex induced subgraph of K(n, k) exhibits s 'jumps' as m increases. For some values of n, k, and m, we also determine the exact minimum and all m-vertex subsets that attain the minimum. Joint work with David Ellis, Ehud Friedgut, and Noam Lifshitz.