TransWikia.com

Existence of a subcover with large boundary

MathOverflow Asked on November 7, 2021

Let $mathscr{C}$ be a cover of $mathbf{N}={1,2,dotsc,N}$ by finite subsets $Sin mathscr{C}$ with $2leq |S|leq K$, where we write $|S|$ for the number of elements of $S$. Assume no element of $mathbf{N}$ is contained in more than $K’$ elements of $mathscr{C}$.

Given a subset $Zsubset mathbf{N}$, we define the boundary $partial Z$ of $Z$ to be the set of elements $nin Z$ such that $n+1notin Z$. Assume that every $Sin mathscr{C}$ satisfies $|partial S|>|S|/2$.

Define a graph $Gamma$ with elements of $mathscr{C}$ as vertices, having an edge between $S,S’in mathscr{C}$ iff there are $nin S$, $n’in S’$ such that $n’in {n-1,n,n+1}$.

Under what conditions is it the case that there must be a subset $mathscr{D}subsetmathscr{C}$ such that (a) the subgraph $Gamma|_mathscr{D}$ is connected and (b) the boundary of $bigcup mathscr{D}$ is large (meaning $gg N$, say)?

(A satisfactory solution to the case $K’=1$ is given by Existence of connected component with large boundary? In brief, it is then enough for every vertex of $Gamma$ to have degree $geq 3$. The condition can be easily relaxed: for $K’=1$, it is enough for $Gamma$ to have many surviving vertices of degree $geq 3$ after we repeatedly prune all vertices of degree $1$.)

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP