Asymptotic properties of hypergraphs and channels

Lire la thèse

 

Comprendre les propriétés des objets dans le cadre d'une opération de produit naturel est un thème central en mathématiques, en informatique et en physique. Des exemples de tels objets de base incluent les canaux de communication bruyants en théorie de l'information, les problèmes de calcul en complexité algébrique et les graphes en mathématiques discrètes. Dans cette thèse, nous étudions la croissance asymptotique de propriétés pertinentes pour les puissances de tels objets. Les premiers objets que nous considérons sont des hypergraphes munis de l'opération de produit fort et la propriété d'intérêt est le nombre d'indépendance. La croissance asymptotique du nombre d'indépendance d'un hypergraphe est connue sous le nom de capacité de Shannon. Nous introduisons une méthode générale pour minorer la capacité de Shannon des hypergraphes via des dégénérescences combinatoires, une notion issue de l'étude de la multiplication matricielle en théorie de la complexité algébrique. Cela nous permet d'obtenir les bornes inférieures les plus connues pour de multiples problèmes combinatoires, y compris le problème du coin et son application dans la complexité de la communication. Les tenseurs sont les seconds objets considérés. Nous pouvons les équiper du produit tensoriel et la propriété d'intérêt est le sous-rang symétrique. Le sous-rang symétrique est une notion que nous introduisons motivée par les limitations des méthodes de tenseur actuelles pour borner la capacité de Shannon des hypergraphes. Nous prouvons des relations et séparations précises entre sous-rang et sous-rang symétrique. Nous prouvons également que pour les tenseurs symétriques, le sous-rang et le sous-rang symétrique sont asymptotiquement égaux. Cela prouve l'analogue de sous-rang asymptotique d'une conjecture connue sous le nom de conjecture de Comon dans la théorie des tenseurs. Enfin, nous étudions la croissance de la divergence entre les puissances tensorielles des canaux quantiques. En exploitant les symétries, nous proposons des algorithmes efficaces pour approximer la divergence asymptotique des canaux entre canaux. Comme application, nous obtenons des bornes améliorées sur les capacités des canaux quantiques.