Search Results

You are looking at 1 - 3 of 3 items for

  • Author or Editor: Attila Sali x
Clear All Modify Search

Let forb(m, F) denote the maximum number of columns possible in a (0, 1)-matrix A that has no repeated columns and has no submatrix which is a row and column permutation of F. We consider cases where the configuration F has a number of columns that grows with m. For a k × l matrix G, define s · G to be the concatenation of s copies of G. In a number of cases we determine forb(m, mα · G) is Θ(mk). Results of Keevash on the existence of designs provide constructions that can be used to give asymptotic lower bounds. An induction idea of Anstee and Lu is useful in obtaining upper bounds.

Restricted access

In this paper we show that there are at least 2110  non-isomorphic 11-doilies, that is, there are many non-isomorphic symmetric, non-simple, non-monotone 11-Venn diagrams, with "many" vertices. We do not achieve the maximum vertex set size, 2046, but we approach it closely, improving from the previous 462 in [10] to 1837. The doilies constructed here cannot be constructed by either of the methods of [10] or [6]. The main purpose of this paper is not to publish these attractive diagrams but to inspire new studies by raising ideas, methods, questions, and conjectures, hoping for results analogous to those generated in [10]. These ideas connect two seemingly distant areas of mathematics: a special area of combinatorial geometry, namely, certain families of simple closed Jordan curves in the plane, and the study of ranked partially ordered sets or posets.

Restricted access

The present paper continues the work begun by Anstee, Ferguson, Griggs, Kamoosi and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0, 1)-matrix with no repeated columns. Let F be a k × (0, 1)-matrix (the forbidden configuration). Assume A is an m × n simple matrix which has no submatrix which is a row and column permutation of F. We define forb (m, F) as the largest n, which would depend on m and F, so that such an A exists.Define F abcd as the (a + b + c + d) × 2 matrix consisting of a rows of [11], b rows of [10], c rows of [01] and d rows of [00]. With the exception of F 2110, we compute forb (m; F abcd) for all 4 × 2 F abcd. A number of cases follow easily from previous results and general observations. A number follow by clever inductions based on a single column such as forb (m; F 1111) = 4m − 4 and forb (m; F 1210) = forb (m; F 1201) = forb (m; F 0310) = ( 2 m )+m+ 2 (proofs are different). A different idea proves forb (m; F 0220) = ( 2 m ) + 2m − 1 with the forbidden configuration being related to a result of Kleitman. Our results suggest that determining forb (m; F 2110) is heavily related to designs and we offer some constructions of matrices avoiding F 2110 using existing designs.

Restricted access