Intersection theorems under dimension constraints

Ahlswede R, Aydinian H, Khachatrian LH (2006)
Journal of Combinatorial Theory, Series A 113(3): 483-519.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
Abstract / Bemerkung
In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0 <= t, k <= n determine or estimate the maximum number of (0, 1)-vectors in a k-dimensional subspace of the Euclidean n-space R-n, such that the inner product ('' intersection '') of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0, 1)-vectors of the same weight omega. The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used. In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint. In Part II, we study the restricted case and solve the problem for t = 1 and k < 2 omega, and also for any fixed 1 <= t <= omega and k large. (c) 2005 Elsevier Inc. All rights reserved.
Stichworte
combinatorial extremal problems; diametric; problem; dimension constraint; weighted intersection problem; intersection theorems
Erscheinungsjahr
2006
Zeitschriftentitel
Journal of Combinatorial Theory, Series A
Band
113
Ausgabe
3
Seite(n)
483-519
ISSN
0097-3165
Page URI
https://pub.uni-bielefeld.de/record/1599920

Zitieren

Ahlswede R, Aydinian H, Khachatrian LH. Intersection theorems under dimension constraints. Journal of Combinatorial Theory, Series A. 2006;113(3):483-519.
Ahlswede, R., Aydinian, H., & Khachatrian, L. H. (2006). Intersection theorems under dimension constraints. Journal of Combinatorial Theory, Series A, 113(3), 483-519. doi:10.1016/j.jcta.2005.04.009
Ahlswede, R., Aydinian, H., and Khachatrian, L. H. (2006). Intersection theorems under dimension constraints. Journal of Combinatorial Theory, Series A 113, 483-519.
Ahlswede, R., Aydinian, H., & Khachatrian, L.H., 2006. Intersection theorems under dimension constraints. Journal of Combinatorial Theory, Series A, 113(3), p 483-519.
R. Ahlswede, H. Aydinian, and L.H. Khachatrian, “Intersection theorems under dimension constraints”, Journal of Combinatorial Theory, Series A, vol. 113, 2006, pp. 483-519.
Ahlswede, R., Aydinian, H., Khachatrian, L.H.: Intersection theorems under dimension constraints. Journal of Combinatorial Theory, Series A. 113, 483-519 (2006).
Ahlswede, Rudolf, Aydinian, Haratyun, and Khachatrian, Levon H. “Intersection theorems under dimension constraints”. Journal of Combinatorial Theory, Series A 113.3 (2006): 483-519.