Extremal combinatorics, graph limits and computational complexity by Noel, J

“…<p>This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. …”

List graphs and distance-consistent node labelings by Håkan Lennerstad, Mattias Eriksson

Subjects: “…graph labeling, graph distance, extremal combinatorics…”
Get full text

Information Inequalities via Submodularity and a Problem in Extremal Graph Theory by Igal Sason

Subjects: “…extremal combinatorics…”
Get full text

Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$ by John Talbot

Subjects: “…extremal combinatorics…”
Get full text

18.314 Combinatorial Analysis, Fall 2005 by Postnikov, Alexander

Subjects: Get full text

Short proofs of some extremal results II by Conlon, D, Fox, J, Sudakov, B

“…We prove several results from different areas of extremal combinatorics, including complete or partial solutions to a number of open problems. …”

Combinatorics in the exterior algebra and the Bollobás Two Families Theorem by Scott, A, Wilmer, E

“…We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hypergraphs. Using initial monomials, projections of the underlying vector space onto subspaces, and the interior product, we find analogs of local and global LYM inequalities, the Erdős–Ko–Rado theorem, and the Ahlswede–Khachatrian bound for 𝑡 -intersecting hypergraphs. …”

Explicit Construction of RIP Matrices Is Ramsey‐Hard by Gamarnik, David

“…In this short note we resolve this open question by showing that an explicit construction of a matrix satisfying the RIP in the regime n = O(log2p) and s = Θ(n1/2) implies an explicit construction of a three-colored Ramsey graph on p nodes with clique sizes bounded by O(log2p) — a question in the field of extremal combinatorics that has been open for decades. © 2019 Wiley Periodicals, Inc.…”
Get full text

Random and exact structures in combinatorics by Sah, Ashwin

“…More generally, however, such notions come into play in the study of combinatorial probability and the use of random processes in extremal combinatorics. In a broader view, randomness (and the pseudorandomness notions which resemble it along various axes) can be viewed as a type of structure in and of itself which has certain typical and global properties that may be exploited to exhibit or constrain combinatorial and probabilistic behavior. …”
Get full text

Short Proofs of Some Extremal Results by Conlon, David, Fox, Jacob, Sudakov, Benny

“…We prove several results from different areas of extremal combinatorics, giving complete or partial solutions to a number of open problems. …”
Get full text

Explicit Construction of RIP Matrices Is Ramsey‐Hard by Gamarnik, David

“…In this short note we resolve this open question by showing that an explicit construction of a matrix satisfying the RIP in the regime n = O(log2p) and s = Θ(n1/2) implies an explicit construction of a three-colored Ramsey graph on p nodes with clique sizes bounded by O(log2p) — a question in the field of extremal combinatorics that has been open for decades. © 2019 Wiley Periodicals, Inc.…”
Get full text

Ramsey numbers of cycles versus general graphs by John Haslegrave, Joseph Hyde, Jaehoon Kim, Hong Liu

Get full text

Undecidability of polynomial inequalities in weighted graph homomorphism densities by Grigoriy Blekherman, Annie Raymond, Fan Wei

“…Many problems and conjectures in extremal combinatorics concern polynomial inequalities between homomorphism densities of graphs where we allow edges to have real weights. …”
Get full text

Extremal results in sparse pseudorandom graphs by Conlon, David, Fox, Jacob, Zhao, Yufei

“…Szemeredi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. …”
Get full text

Testability of linear-invariant properties by Bhattacharyya, Arnab

Get full text

Sparse regularity and relative Szemerédi theorems by Zhao, Yufei

Get full text

An efficient container lemma by Jozsef Balogh, Wojciech Samotij

“…The hypergraph container lemma, discovered independently in 2012 by David Saxton and Andrew Thomason, and by József Balogh, Robert Morris and Wojciech Samotij, is an extremely powerful tool that has been used to solve a large number of important problems in extremal combinatorics and to give simple new proofs of many others. …”
Get full text

Invariance Principle on the Slice by Filmus, Yuval, Kindler, Guy, Mossel, Elchanan, Wimmer, Karl

“…The slice shows up in theoretical computer science (hardness amplification, direct sum testing), extremal combinatorics (Erdös-Ko-Rado theorems), and coding theory (in the guise of the Johnson association scheme). …”
Get full text

Algorithms and Algorithmic Barriers in High-Dimensional Statistics and Random Combinatorial Structures by Kizildag, Eren C.

“…Our hardness results for the stable algorithms are based on Ramsey Theory from extremal combinatorics. To the best of our knowledge, this is the first usage of Ramsey Theory to show algorithmic hardness for models with random parameters. 2. …”
Get full text

Forbidden intersection problems for families of linear maps by David Ellis, Guy Kindler, Noam Lifshitz

“…A central problem in extremal combinatorics is to determine the maximal size of a set system given constraints on the sizes of the sets in the system and on the sizes of their intersections. …”
Get full text