2019/12/03 by Dingding Dong, Dong, Dingding · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #FOS: Mathematics #Ferroelectric and Negative Capacitance Devices #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1912.01780
openalex publication_date 2019/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph G with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of G with α(G)+1 vertices, where α(G) denotes the size of the largest independent set in G? We study this question for H(n,k), the n-dimensional Hamming graph over an alphabet of size k. Generalizing a construction by Chung et al. (JCT-A, 1988), we prove that H(n,k) has an induced subgraph with more than α(H(n,k)) vertices and maximum degree at most \lceil√(n)\rceil. Chung et al. proved this statement for k=2 (the n-dimensional cube).