Problems and results in extremal combinatorics. I.
type: Item
instance of: scholarly article
title: Problems and results in extremal combinatorics. I.
zbMATH Open document ID: 1033.05060
DOI: 10.1016/S0012-365X(03)00227-9
author: Noga Alon
published in: Discrete Mathematics
publication date: 2004-01-05T00:00:00Z
review text: Selected open problems and results in a variety of areas in extremal combinatorics are surveyed. The results which are partitioned into eight sections including sections on intersections of set systems, independent transversals in multipartite graphs, induced acyclic subgraphs in sparse graphs, and ranks of perturbations of identity matrices. An example of an open problem and corresponding result in the section on regular graphs is the following conjecture, which is verified for \(k \leq 2\). For every integer \(k \geq 1\) and every real \(\varepsilon > 0\), there is an \(r_0 = r_0(k,\varepsilon)\) such that for \(r > r_0\), every \(r\)-regular graph on \(n\) vertices contains a \(k\)-regular subgraph on at least \((1 - \varepsilon)n\) vertices. Another example is the conjecture that every planar, bipartite graph on \(n\) vertices contains an induced acyclic subgraph on at least \(5n/8\) vertices. It is shown that there exists an absolute positive constant \(b\) such that every bipartite graph with \(n\) vertices and average degree at most \(d \geq 1\) will have an induced acyclic subgraph on at least \((1/2 + e^{-bd^2})n\) vertices.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05Dxx
Mathematics Subject Classification ID: 05E05
zbMATH DE Number: 2021220
zbMATH Keywords: extremal problems
zbMATH Keywords: survey
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: The linear arboricity of graphs
cites work: The strong chromatic number of a graph
cites work: Regular subgraphs of almost regular graphs
cites work: Large induced degenerate subgraphs
cites work: Large induced forests in sparse graphs
cites work: Ramsey-type theorems with forbidden subgraphs
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Q3852212
cites work: The number of matchings in random regular graphs and bipartite graphs
cites work: Q4100117
cites work: On complete subgraphs of \(r\)-chromatic graphs
cites work: Q4044717
cites work: Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
cites work: Some Combinatorial Theorems on Monotonicity
cites work: Some properties of graphs of diameters
cites work: Covering a Three-Dimensional set with Sets of Smaller Diameter
cites work: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
cites work: CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS
cites work: Increasing paths in edge ordered graphs
cites work: Q3237949
cites work: Transitive edge coloring of graphs and dimension of lattices
cites work: A note on vertex list colouring
cites work: Complete Subgraphs of r-partite Graphs
cites work: Extensions of Lipschitz mappings into a Hilbert space
cites work: Q4255576
cites work: Q4071752
cites work: Asymptotically optimal tree-packings in regular graphs
cites work: Q5726070
cites work: Q3880849
cites work: Matching theory
cites work: On constructive methods in the theory of colour-critical graphs
cites work: Counting 1-factors in regular bipartite graphs
cites work: Extremal problems for transversals in graphs with bounded degree
cites work: Q4083463
cites work: Independent transversals in \(r\)-partite graphs
cites work: Large monotone paths in graphs with bounded degree
description: scientific article; zbMATH DE number 2021220