Results 1 to 10 of about 291 (171)
Universal limit theorems in graph coloring problems with connections to extremal combinatorics [PDF]
Annals of Applied Probability, 2017 This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs. These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?).
Bhaswar B. Bhattacharya +2 more
exaly +8 more sources
Information Inequalities via Submodularity and a Problem in Extremal Graph Theory [PDF]
Entropy, 2022 The present paper offers, in its first part, a unified approach for the derivation of families of inequalities for set functions which satisfy sub/supermodularity properties.
Igal Sason
doaj +2 more sources
Probabilistic and extremal studies in additive combinatorics [PDF]
, 2022 The results in this thesis concern extremal and probabilistic topics in number theoretic settings. We prove sufficient conditions on when certain types of integer solutions to linear systems of equations in binomial random sets are distributed normally, results on the typical approximate structure of pairs of integer subsets with a given sumset ...
Maximilian Wötzel
openalex +5 more sources
Graphical designs and extremal combinatorics
Linear Algebra and its Applications, 2020 A graphical design is a proper subset of vertices of a graph on which many eigenfunctions of the Laplacian operator have mean value zero. In this paper, we show that extremal independent sets make extremal graphical designs, that is, a design on which the maximum possible number of eigenfunctions have mean value zero.
Konstantin Golubev
openalex +6 more sources
A path forward: Tropicalization in extremal combinatorics
Advances in Mathematics, 2022 Many important problems in extremal combinatorics can be be stated as proving a pure binomial inequality in graph homomorphism numbers, i.e., proving that hom$(H_1,G)^{a_1}\cdots$hom$(H_k,G)^{a_k}\geq$hom$(H_{k+1},G)^{a_{k+1}}\cdots$hom$(H_m,G)^{a_m}$ holds for some fixed graphs $H_1,\dots,H_m$ and all graphs $G$.
Grigoriy Blekherman, Annie Raymond
openalex +4 more sources
Problems and results in extremal combinatorics—II [PDF]
Discrete Mathematics, 2007 Extremal Combinatorics is among the most active topics in Discrete Mathematics, dealing with problems that are often motivated by questions in other areas, including Theoretical Computer Science and Information Theory. This paper contains a collection of problems and results in the area, including solutions or partial solutions to open problems ...
Noga Alon
openalex +6 more sources
Two problems in extremal combinatorics
, 2021 In this thesis, we focus on two problems in extremal graph theory. Extremal graph theory consists of all problems related to optimizing parameters defined on graphs. The concept of ``editing'' appears in many key results and techniques in extremal graph theory, either as a means to account for error in structural results, or as a quantity to minimize ...
Alex Neal Riasanovsky
openalex +6 more sources
High dimensional Hoffman bound and applications in extremal combinatorics [PDF]
Algebraic Combinatorics, 2022 The n-th tensor power of a graph with vertex set V is the graph on the vertex set V n, where two vertices are connected by an edge if they are connected in each coordinate. One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of ...
Yuval Filmus +2 more
openalex +5 more sources
Refuting conjectures in extremal combinatorics via linear programming [PDF]
Journal of Combinatorial Theory, Series A, 2019 We apply simple linear programming methods and an LP solver to refute a number of open conjectures in extremal combinatorics.
Adam Zsolt Wagner
+7 more sources
PPP-Completeness and Extremal Combinatorics
, 2022 Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implici" means that the ...
Romain Bourneuf +4 more
openalex +6 more sources