Problems and results in extremal combinatorics. I. (Q1417566): Difference between revisions

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.