Una generalización equilibrada del teorema de Hall

Deje que e sean conjuntos, y sea una partición de . Me gustaría demostrar que existe una distribución sobre cuyo marginal es uniforme sobre , y tal que la distribución sobre inducida por tiene una gran entropía (el esta última distribución se define asignando a cada la masa de probabilidad total de los elementos de debajo de ). Podemos usar la siguiente condición:$X$$Y$$\mathcal{B}$$X \times Y$$\mathcal{D}$$X \times Y$$X$$\mathcal{B}$$\mathcal{D}$$B∈\mathcal{B}$$B$$\mathcal{D}$

Considere el gráfico bipartito cuyos lados son y , de modo que para cada haya un borde en (múltiples bordes posibles). Luego, cada conjunto de 's de tamaño al menostiene al menosvecinos en G.$G$$X$$\mathcal{B}$$(x,y) \in B$$(x,B)$$G$$x$$\frac{3}{4}|X|$$\frac{1}{100}|B|$

Le agradecería si alguien pudiera referirme a un teorema relevante. Esta pregunta puede verse en cierto sentido como una generalización del teorema de Hall, donde la condición anterior es una condición de relajación de Hall, y donde en lugar de obtener una coincidencia perfecta, obtenemos un conjunto de bordes cuya subgrafía correspondiente es más o menos regular.

Antecedentes : la motivación para estas preguntas proviene de la complejidad de la comunicación. En el contexto de la complejidad de la comunicación, dos jugadores, Alice y Bob, obtienen entradas e respectivamente, e interactúan para calcular alguna función . Aquí, cada conjunto consiste en pares que producen la misma transcripción de comunicación entre Alice y Bob, y me gustaría demostrar que, bajo alguna condición, uno puede encontrar una distribución sobre tal que Alice obtenga una entrada distribuida uniformemente, y tal que la entropía de la transcripción bajo la distribución sea grande.$x$$y$$f(x,y)$$B \in \mathcal{B}$$(x,y)$$X \times Y$

Puede examinar el concepto de factores y especialmente el teorema de Tutte sobre la existencia de factores . Puede encontrar la Proposición 2 de este documento relevante.$f$$f$