Publication

Lower bounds for Ramsey numbers of bounded degree hypergraphs

2026

Abstract

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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2026

Abstract

Official source

Related concepts (32)

Hypergraph

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, a directed hypergraph is a pair , where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of . Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain. The order of a hypergraph is the number of vertices in .

Ramsey's theorem

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices.

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.

Related publications (3)

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Chat with 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