At most how many edges can an ordered graph of n vertices have if it does not contain a fixed forbidden ordered subgraph H? It is not hard to give an asymptotically tight answer to this question, unless H is a bipartite graph in which every vertex belonging to the first part precedes all vertices belonging to the second. In this case, the question can be reformulated as an extremal problem for zero-one matrices avoiding a certain pattern (submatrix) P. We disprove a general conjecture of Furedi and Hajnal related to the latter problem, and replace it by some weaker alternatives. We verify our conjectures in a few special cases when P is the adjacency matrix of an acyclic graph and discuss the same question when the forbidden patterns are adjacency matrices of cycles. Our results lead to a new proof of the fact that the number of times that the unit distance can occur among n points in the plane is O(n(4/3)).
展开▼
