Extremal problems for linear orders on [n]
p |
| |
| Authors: | R Svarc V Rödl B Wysocka |
| |
| Institution: | (1) Department of Applied Mathematics, Charles Univ., Prague, Czech Republic;(2) Department of Mathematics and Computer Science, Emory University, 30322 Atlanta, GA, USA;(3) Department of Mathematics, University of North Carolina at Greensboro, 27412, NC, USA |
| |
| Abstract: | Let  be a product order on n]
p
i.e. for A, B  n]
p
, 1 a
1<a
2<...<a
p
º-n and 1<-b
1<b
2<...<b
p
<-n we have AB iff a
i<-b
i for all i=1, 2,..., p. For a linear extension < of (ordering n]
p
as
) let F
<
n],p
(m) count the number of A
i
's, i<-m such that 1A
i. Clearly,
![$$F_{n],p}^ < (m) \leqslant F_{n],p}^{ < _l } (m)$$](/content/n155184h1486u705/11083_2004_Article_BF00389836_TeX2GIFIE2.gif)
for every m and <, where <l denotes the lexicographic order on n]
p
. In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that
![$$F_{n],p}^{ < _c } (m) \leqslant F_{n],p}^ < (m)$$](/content/n155184h1486u705/11083_2004_Article_BF00389836_TeX2GIFIE3.gif)
holds for any linear extension < of .This project together with 2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850. |
| |
| Keywords: | Primary: 06A05 06A06 secondary: 05C35 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
