<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Aptos",sans-serif;
mso-ligatures:standardcontextual;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#467886;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Aptos",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:11.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="#467886" vlink="#96607D" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">This is an announcement of Hing Yin Tsang's Dissertation Defense.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">===============================================<o:p></o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Candidate:</span></b><span style="font-family:"Arial",sans-serif"> Hing Yin Tsang<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Date:</span></b><span style="font-family:"Arial",sans-serif"> Wednesday, August 14, 2024<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Time:</span></b><span style="font-family:"Arial",sans-serif"> 10 am CST<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Location:</span></b><span style="font-family:"Arial",sans-serif"> JCL 298<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Remote Location:</span></b><span style="font-family:"Arial",sans-serif">
<a href="https://uchicago.zoom.us/j/92944301232?pwd=UA9XD8y2ulGPKqeEAtDKIavdg9P94v.1">
https://uchicago.zoom.us/j/92944301232?pwd=UA9XD8y2ulGPKqeEAtDKIavdg9P94v.1</a><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">Meeting ID: 929 4430 1232 Passcode: 453779<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Title:</span></b><span style="font-family:"Arial",sans-serif"> Induced subgraphs of highly symmetric graphs: size and maximum degree<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Abstract:</span></b><span style="font-family:"Arial",sans-serif"> 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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">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)$.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">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$ of the number of vertices. Moreover, $H(n, k)$ contains an induced subgraph with maximum degree 1 which
has size $\alpha(H(n, k))+1$.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">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 \Z_3^n$ and $U$ induces a subgraph of $H(n,3)$ with maximum degree at most 1 then<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">For $n \geq 6$, there exists such a $U$ with size $|U| = 3^{n-1}+18$ and this is optimal for $n = 6$.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif">If $U \cap \{x, x+e_1, x+2e_1\} \ne \phi$ for all $x \in \Z_3^n$ then $|U| \le 3^{n-1} + 729$.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Advisors:</span></b><span style="font-family:"Arial",sans-serif"> Aaron Potechin<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Arial",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span style="font-family:"Arial",sans-serif">Committee Members:</span></b><span style="font-family:"Arial",sans-serif"> Aaron Potechin, Janos Simon, and Madhur Tulsiani<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><b><span style="font-size:10.5pt;font-family:"Times New Roman",serif;color:black;mso-ligatures:none"><o:p> </o:p></span></b></p>
</div>
</div>
</div>
</body>
</html>