Publication

Lower bounds for Ramsey numbers of bounded degree hypergraphs

2026

Résumé

We prove that, for all k≥3, and any integers Δ,n with n≥Δ, there exists a k-uniform hypergraph on n vertices with maximum degree at most Δ whose 4-color Ramsey number is at least twk(ckΔ)⋅n, for some constant ck>0, where twk denotes the tower function. For k≥4, this is tight up to the constant ck and for k=3 it is known to be tight up to a factor of log⁡Δ on top of the tower. Our bound extends a well-known result of Graham, Rödl and Ruciński for graphs and answers a question of Conlon, Fox and Sudakov from 2009 for four colors.

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2026

Résumé

Source officielle

Concepts associés (32)

Hypergraphe

Les hypergraphes sont des objets mathématiques généralisant la notion de graphe. Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe). Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey.

Théorème de Ramsey

En mathématiques, et plus particulièrement en combinatoire, le théorème de Ramsey, dû à Frank Ramsey (en 1930), est un théorème fondamental de la théorie de Ramsey. Il affirme que pour tout n, tout graphe complet suffisamment grand dont les arêtes sont colorées contient des sous-graphes complets de taille n d'une seule couleur. En théorie des ensembles, une de ses généralisations, le théorème de Ramsey infini, permet de définir un type particulier de grand cardinal.

Hall-type theorems for hypergraphs

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others. Hall's marriage theorem provides a condition guaranteeing that a bipartite graph (X + Y, E) admits a perfect matching, or - more generally - a matching that saturates all vertices of Y. The condition involves the number of neighbors of subsets of Y.

Afficher plus

Publications associées (3)

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Chattez avec Graph Search

Beyond spectral gap (extended): The role of the topology in decentralized learning

Preemptive open shop scheduling with multiprocessors: polynomial cases and applications

Randomization in the two-parameter optimal stopping problem : combinatorial, probabilistic and infinitesimal methods