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. (Here R(r, s) signifies an integer that depends on both r and s.)
In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger connected, so-called spanning clusters. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles Network theory and Percolation.
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.
In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.
Béla Bollobás FRS is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory, and percolation. He was strongly influenced by Paul Erdős from the age of 14.
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.
Ben Joseph Green FRS is a British mathematician, specialising in combinatorics and number theory. He is the Waynflete Professor of Pure Mathematics at the University of Oxford.
In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.
In mathematics, a Littlewood polynomial is a polynomial all of whose coefficients are +1 or −1. Littlewood's problem asks how large the values of such a polynomial must be on the unit circle in the complex plane. The answer to this would yield information about the autocorrelation of binary sequences. They are named for J. E. Littlewood who studied them in the 1950s.
Van H. Vu is a Vietnamese mathematician and the Percey F. Smith Professor of Mathematics at Yale University.
Richard Alejandro Arratia is a mathematician noted for his work in combinatorics and probability theory.
The bipartite realization problem is a classical decision problem in graph theory, a branch of combinatorics. Given two finite sequences and of natural numbers with , the problem asks whether there is a labeled simple bipartite graph such that is the degree sequence of this bipartite graph.
Katalin Marton was a Hungarian mathematician, born in Budapest.
Tamar Debora Ziegler is an Israeli mathematician known for her work in ergodic theory, combinatorics and number theory. She holds the Henry and Manya Noskwith Chair of Mathematics at the Einstein Institute of Mathematics at the Hebrew University.
Wojciech Samotij is a Polish mathematician and a full professor at the School of Mathematical Sciences at the Tel Aviv University. He is known for his work in combinatorics, additive number theory, Ramsey theory and graph theory.
József Balogh is a Hungarian-American mathematician, specializing in graph theory and combinatorics.
A Bohemian matrix family is a set of matrices whose entries are members of a fixed, finite, and discrete set, referred to as the "population". The term "Bohemian" was first used to refer to matrices with entries consisting of integers of bounded height, hence the name, derived from the acronym BOunded HEight Matrix of Integers (BOHEMI). The majority of published research on these matrix families studies populations of integers, although this is not strictly true of all possible Bohemian matrices. There is no single family of Bohemian matrices. Instead, a matrix can be said to be Bohemian with respect to a set from which its entries are drawn. Bohemian matrices may possess additional structure. For example, they may be Toeplitz matrices or upper Hessenberg matrices.
The bunkbed conjecture is a statement in percolation theory, a branch of mathematics that studies the behavior of connected clusters in a random graph. The conjecture is named after its analogy to a bunk bed structure. It was first posited by Pieter Kasteleyn in 1985. A preprint giving a proposed counterexample to the conjecture was posted on the arXiv in October 2024 by Nikita Gladkov, Igor Pak and Alexander Zimin.
