Problems and results in extremal combinatorics. I.

DOI10.1016/S0012-365X(03)00227-9zbMath1033.05060MaRDI QIDQ1417566

Noga Alon

Publication date: 5 January 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

surveyextremal problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Symmetric functions and generalizations (05E05) Extremal combinatorics (05Dxx)

Related Items

Johnson–Lindenstrauss Embeddings with Kronecker Structure, Increasing paths in edge-ordered graphs: the hypercube and random graph, On graphs and algebraic graphs that do not contain cycles of length 4, A lower bound on the order of the largest induced forest in planar graphs with high girth, Independent transversals in locally sparse graphs, Short proofs of some extremal results. II., Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering, Sparser Johnson-Lindenstrauss Transforms, Counting and packing Hamilton cycles in dense graphs and oriented graphs, Almost-equidistant sets, On the distance concentration awareness of certain data reduction techniques, Lower bounds on the low-distortion embedding dimension of submanifolds of \(\mathbb{R}^n\), On the correlation measures of subsets, A nonlinear approach to dimension reduction, Graphs of low average degree without independent transversals, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Induced forests in some distance-regular graphs, Nearly-linear monotone paths in edge-ordered graphs, Two are better than one: fundamental parameters of frame coherence, Representation and coding of signal geometry, A note on acyclic number of planar graphs, Smaller Gershgorin disks for multiple eigenvalues of complex matrices, Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time, On variants of the Johnson–Lindenstrauss lemma, On deterministic sketching and streaming for sparse recovery and norm estimation, Hadamard products and moments of random vectors, Most edge‐orderings of K_n have maximal altitude, Large induced forests in planar graphs with girth 4, A superadditivity and submultiplicativity property for cardinalities of sumsets, Small Sample Spaces Cannot Fool Low Degree Polynomials, On the induced matching problem, Discrete uncertainty principles and sparse signal processing, Improved linear embeddings via Lagrange duality, Problems and results in extremal combinatorics. II, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Perturbed Identity Matrices Have High Rank: Proof and Applications, Low Distortion Metric Embedding into Constant Dimension, Dimensionality reduction with subgaussian matrices: a unified theory, Short Proofs of Some Extremal Results, CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS, Almost isometries and orthogonality, Large induced forests in triangle-free planar graphs, On packing Hamilton cycles in \(\varepsilon\)-regular graphs, Altitude of regular graphs with girth at least five, On the size of incoherent systems, Intrinsic Complexity and Scaling Laws: From Random Fields to Random Vectors, Sets of unit vectors with small subset sums, Rectangles Are Nonnegative Juntas, Impossibility of dimension reduction in the nuclear norm, Optimal Bounds for Johnson-Lindenstrauss Transformations, No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited, Local embeddings of metric spaces, Short proofs of some extremal results III, Large Induced Forests in Graphs, On covering graphs by complete bipartite subgraphs, Fast dimension reduction using Rademacher series on dual BCH codes, On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$, Sampling, Metric Entropy, and Dimensionality Reduction, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular subgraphs of almost regular graphs
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Extremal problems for transversals in graphs with bounded degree
• The number of matchings in random regular graphs and bipartite graphs
• Matching theory
• Large induced degenerate subgraphs
• The linear arboricity of graphs
• On constructive methods in the theory of colour-critical graphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• On complete subgraphs of \(r\)-chromatic graphs
• Independent transversals in \(r\)-partite graphs
• Counting 1-factors in regular bipartite graphs
• Transitive edge coloring of graphs and dimension of lattices
• Some properties of graphs of diameters
• Increasing paths in edge ordered graphs
• A Note on Vertex List Colouring
• Large induced forests in sparse graphs
• Extensions of Lipschitz mappings into a Hilbert space
• The strong chromatic number of a graph
• Complete Subgraphs of r-partite Graphs
• CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS
• Some Combinatorial Theorems on Monotonicity
• Covering a Three-Dimensional set with Sets of Smaller Diameter
• Asymptotically optimal tree-packings in regular graphs
• Large monotone paths in graphs with bounded degree
• Ramsey-type theorems with forbidden subgraphs