Report on Work in Progress in Combinatorial Extremal Theory:

Shadows, AZ-Identities, Matching

R. Ahlswede, N. Cai, N. Danh, E. Daykin, L.H. Khachatrian, and T.D. Thu

Content

[1]

T.-N. Danh and D.E. Daykin, Set cascades and vector valleys in Pascal's triangle. [pdf]

[2]

T.-N. Danh and D.E. Daykin, Sets of 0,1 vectors with minimal sets of subvectors. [pdf]

[3]

T.-N. Danh and D.E. Daykin, The structure of V-order for integer vectors. [pdf]

[4]

D.E. Daykin, A cascade proof of a finite vectors theorem. [pdf]

[5]

R. Ahlswede and N. Cai, Sets of $n$-length 0-1- sequences with minimal shadow in $(n-1)$-length sequences. [pdf]

[6]

T.D. Thu, Identities for combinatorial extremal theory. [pdf]

[7]

R. Ahlswede and L.H. Khachatrian, A counterexample to Aharoni's ``Strongly maximal matching'' conjecture. [pdf]

Preface

It has been suggested in 1988 on page 152 in project $B_1$ ``Kombinatorik von Folgenräumen'' of the SFB 343 ``Diskrete Strukturen in der Mathematik'' to study combinatorial extremal problems under the sequence-subsequence relation -- in particular also shadow problems of the Kruskal-Katona type.

In Sept. 94 David Daykin wrote to us that he and Danh had a counterexample to the optimality of the optimality of the B-G order reported in Preprint 92-036. He also mentioned that they had a solution in the binary case with a very, very complicated proof (which we never have seen). Immediately thereafter a simple proof for the binary case (and also a simple counterexample to the B-G order in the general case) was given by Ahlswede/Cai [5].

Then a new proof was given in December 1994 in [2]. The papers [1], [3], and [4] contain preparations and interesting variations on this theme.

All these contributions are reported here, because they may be useful in solving the general case.

Another stimulus for further research is to be expected from Thu's contribution [6] to AZ-identities, which shed new light on the topic of antichains.

Finally we draw attention to matching theory for infinite hypergraphs. The authors of [6] disprove a conjecture of Aharoni, which has been especially focussed upon in Erdös' recent report (Ref. [2] in [6]). A next step is now to decide upon the case of sizes of edges bounded by a finite constant.

We thank all authors for their contributions to this preprint.