Files

Abstract

We study the maximum degree of large induced subgraphs of some highly symmetric graphs. This type of problem for Boolean hypercubes was formulated as an equivalent formulation of the Sensitivity Conjecture in the early 90s. A breakthrough result of Hao Huang in 2019 showed that for subsets $U$ of vertices of a $n$-dimensional Boolean hypercube, if $|U| > 2^{n-1}$ then $U$ induces a subgraph with maximum degree at least $\sqrt{n}$. As a corollary, this implies that the degree of a Boolean function is upper bounded by the square of its sensitivity, confirming the Sensitivity Conjecture. Huang's theorem raised a natural question --- does a similar property about the size and maximum degree of an induced subgraph hold for other graphs? In this thesis, we study this question for general Cayley graphs and the Hamming graph $H(n, 3)$. We show that for abelian Cayley graphs $G = (V, E)$, if $U \subseteq V$ has size $|U| > |V|/2$, then $U$ induces a subgraph of $G$ with maximum degree at least $\sqrt{(d+t)/2}$ where $d$ is the degree and $t$ is the number of generators of order 2. This bound on the maximum degree is tight. On the other hand, for non-abelian Cayley graphs, there are known constructions of infinite families of non-abelian Cayley graphs that contain an induced 1-regular subgraph on more than half of the vertices. Our result shows that for bipartite abelian Cayley graphs, any induced subgraph of size exceeding the independence number must have a high degree vertex. However, for non-bipartite abelian Cayley graphs, the independence number can be much smaller. In particular, for the Hamming graph $H(n, k)$, the independence number $\alpha(H(n, k))$ is only $1/k$ times the number of vertices. Moreover, $H(n, k)$ contains an induced subgraph with maximum degree 1 which has size $\alpha(H(n, k))+1$. In this thesis, we focus on the case $k = 3$. We show that there are induced subgraphs of $H(n, 3)$ with maximum degree 1 that have size larger than $\alpha(H(n, 3))+1$ but under an extra assumption, any subgraphs of $H(n, 3)$ with maximum degree 1 have size $\alpha(H(n, 3))+O(1)$. Specifically, if $U \subseteq \mathbb{Z}_3^n$ and $U$ induces a subgraph of $H(n,3)$ with maximum degree at most $1$ then 1. If $U$ is disjoint from a maximum size independent set of $H(n,3)$ then $|U| \leq 3^{n-1}+1$. Moreover, all such $U$ with size $3^{n-1}+1$ are isomorphic to each other. 2. For $n \geq 6$, there exists such a $U$ with size $|U| = 3^{n-1}+18$ and this is optimal for $n = 6$. 3. If $U \cap \{x, x+e_1, x+2e_1\} \ne \phi$ for all $x \in \mathbb{Z}_3^n$ then $|U| \le 3^{n-1} + 729$.

Details

Actions

PDF

from
to
Export
Download Full History