Lattices of partial sums
In this paper we introduce and study a class of partially ordered sets that can be interpreted as partial sums of indeterminate real numbers. An important example of these partially ordered sets, is the classical Young lattice Y of the integer partitions. In this context, the sum function associated...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2014 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2014
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/153329 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Lattices of partial sums / G. Chiaselotti, T. Gentile, P.A. Oliverio // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 171–185. — Бібліогр.: 23 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-153329 |
|---|---|
| record_format |
dspace |
| spelling |
Chiaselotti, G. Gentile, T. Oliverio, P.A. 2019-06-14T03:21:25Z 2019-06-14T03:21:25Z 2014 Lattices of partial sums / G. Chiaselotti, T. Gentile, P.A. Oliverio // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 171–185. — Бібліогр.: 23 назв. — англ. 1726-3255 2010 MSC:Primary: 06A06, Secondary: 06A07, 05A17. https://nasplib.isofts.kiev.ua/handle/123456789/153329 In this paper we introduce and study a class of partially ordered sets that can be interpreted as partial sums of indeterminate real numbers. An important example of these partially ordered sets, is the classical Young lattice Y of the integer partitions. In this context, the sum function associated to a specific assignment of real values to the indeterminate variables becomes a valuation on a distributive lattice. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Lattices of partial sums Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Lattices of partial sums |
| spellingShingle |
Lattices of partial sums Chiaselotti, G. Gentile, T. Oliverio, P.A. |
| title_short |
Lattices of partial sums |
| title_full |
Lattices of partial sums |
| title_fullStr |
Lattices of partial sums |
| title_full_unstemmed |
Lattices of partial sums |
| title_sort |
lattices of partial sums |
| author |
Chiaselotti, G. Gentile, T. Oliverio, P.A. |
| author_facet |
Chiaselotti, G. Gentile, T. Oliverio, P.A. |
| publishDate |
2014 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
In this paper we introduce and study a class of partially ordered sets that can be interpreted as partial sums of indeterminate real numbers. An important example of these partially ordered sets, is the classical Young lattice Y of the integer partitions. In this context, the sum function associated to a specific assignment of real values to the indeterminate variables becomes a valuation on a distributive lattice.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/153329 |
| citation_txt |
Lattices of partial sums / G. Chiaselotti, T. Gentile, P.A. Oliverio // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 171–185. — Бібліогр.: 23 назв. — англ. |
| work_keys_str_mv |
AT chiaselottig latticesofpartialsums AT gentilet latticesofpartialsums AT oliveriopa latticesofpartialsums |
| first_indexed |
2025-11-25T23:08:43Z |
| last_indexed |
2025-11-25T23:08:43Z |
| _version_ |
1850581515379933184 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 18 (2014). Number 2, pp. 171–185
© Journal “Algebra and Discrete Mathematics”
Lattices of partial sums
Giampiero Chiaselotti, Tommaso Gentile,
Paolo Antonio Oliverio
Communicated by V. V. Kirichenko
Abstract. In this paper we introduce and study a class
of partially ordered sets that can be interpreted as partial sums
of indeterminate real numbers. An important example of these
partially ordered sets, is the classical Young lattice Y of the integer
partitions. In this context, the sum function associated to a specific
assignment of real values to the indeterminate variables becomes a
valuation on a distributive lattice.
Introduction
In the present paper we build a formal order context within which we
examine the analogies that arise between combinatorial sum problems
on multisets of real numbers and combinatorial set problems. Our con-
struction provides a class of distributive lattices that we will call partial
sums lattices. The elements of these lattices correspond to indeterminate
partial sums of real numbers and any effective assignment of real values to
such indeterminate becomes a valuation on these lattices (classical results
concerning the valuations on a distributive lattice and their links with
Euler characteristic and Mobius function can be found in [10–12,20]). For
a wide range of extremal combinatorial problems concerning partial sums
on real numbers we refer to [2, 14–18]. In particular, a beautiful example
of similarity between combinatorial sum problems and combinatorial set
2010 MSC: Primary: 06A06, Secondary: 06A07, 05A17.
Key words and phrases: Distributive Lattices, Real Partial Sums, Integer Par-
titions.
172 Lattices of partial sums
problems is a still unsolved conjecture raised in [16], which has a dual
formulation (in terms of partial sums on multi-sets of real numbers) of
the famous theorem of Erdös-Ko-Rado [9]. This conjecture and related
problems have been studied in [2–8,14,17–19,21,23]. In [16] have been
raised several combinatorial problems concerning partial sums on multi-
sets of n real numbers, and it is interesting to observe as such problems
have a strict analogy with corresponding problems concerning families
of subsets of the set of indexes {1, . . . , n} (see [3, 4, 16, 23] for a more
detailed description of some such analogies). If n is a positive integer we
set [n] = {1, . . . , n}. We denote by P([n]) the power set of [n] and we set
Pk([n]) = {A ∈ P([n]) : |A| = k}, for each k = 0, 1, . . . , n. In this context
we call indexes the element of [n]. Let xn, . . . , x1 be n indeterminate real
numbers (not necessarily distinct) such that
xn > xn−1 > · · · > x2 > x1 (1)
Our basic motivation is to investigate the analogies between order proper-
ties on the subsets of indexes A ∈ P([n]) and on the partial sums
∑
i∈A xi,
where each xi (i ∈ A) satisfies (1). For example, it is obviously false that
if A, B ∈ P([n]) and A ⊆ B then
∑
i∈A xi 6
∑
i∈B xi, since in (1) can
also be negative numbers. We refine then the previous question as follows.
Let us suppose that our indeterminate real numbers satisfy the condition
xn > xn−1 > · · · > x2 > x1 > 0 (2)
Then, under the hypothesis (2), it is true that if A, B ∈ P([n]) and A ⊆ B
then
∑
i∈A xi 6
∑
i∈B xi. But the reverse implication is not true, i.e. if for
each assignment of real values in (2) we have that
∑
i∈A xi 6
∑
i∈B xi, then
not necessarily A ⊆ B. For example, for each assignment that satisfies
(2) we have x2 > x1, but {2} + {1}. We ask therefore the following
question: does there exist a partial order ⊑ on P([n]) such that A ⊑ B iff
∑
i∈A xi 6
∑
i∈B xi for each assignment of n real values that satisfies (2)?
More generally, if
xn > · · · > xn−r+1 > 0 > xn−r > · · · > x1 > 0 (3)
does there exist a partial order ⊑ on P([n]) such that A ⊑ B iff
∑
i∈A xi 6
∑
i∈B xi for each assignment of n real values that satisfies (3)?
In this paper we reformulate and study the previous question in a
more general form, when i.e. the set [n] of the indexes is substituted with
an arbitrary total ordered set I and with an its fixed partition (I+, I−)
G. Chiaselotti, T. Gentile, P. A. Oliverio 173
in two blocks: the elements of I+ will be thought of as "positive" indexes
and that of I− of as "negative" indexes. In such an abstract context we
obtain a class of posets, which we call partial sums posets on I. On such
posets we define a particular class of order-preserving maps which are the
natural generalizations of the partial sums
∑
i∈A xi, when A is a subset
of [n] and we study some basic properties of such maps. The class of
the partial sums posets includes, as particular cases, the classical Young
lattice Y of all the the integer partitions ordered by means of the inclusion
of the corresponding Young diagrams, and other sublattices of Y. For
example, the lattice M(n) of all the integer partitions having all distinct
parts and maximum part at most n, or, also, the lattice L(m, n) of all the
integer partitions with at most m parts and maximum part not exceeding
n (both these lattices were introduced by Stanley in [22]).
1. A quasi-order for partial sums
Let I a totally ordered set with order �. If λ, λ′ ∈ I, we set λ ≺ λ′ if
λ � λ′ and λ 6= λ′; moreover, we write in an equivalent way λ′ ≻ λ instead
of λ ≺ λ′ and λ′ � λ instead of λ � λ′. We fix a set partition (I+, I−)
of I with two disjoint subsets I+ and I− such that λ ≻ γ if λ ∈ I+ and
γ ∈ I− (we admit the possibility that one of such subsets is empty). The
elements of I are called indexes, those of I+ positive indexes and those
of I− negative indexes. Let {xλ : λ ∈ I+} ∪ {yγ : γ ∈ I−} a family of
indeterminate real numbers with running indexes in I. We assume that
xλ > xλ′ > 0 > yγ > yγ′ (4)
if λ, λ′ ∈ I+ with λ ≻ λ′ and if γ, γ′ ∈ I− with γ ≻ γ′. We refer to (4) as
to the (I+, I−)-initial conditions. We denote by M(I) the family of the
finite multisets of I.
Definition 1. We say that a function f : I → R realizes the (I+, I−)-
initial conditions if: the assignment xλ = f(λ) when λ ∈ I+ and yγ = f(γ)
when γ ∈ I−, satisfies the inequalities in (4). We denote by Φ(I+, I−) the
set of all the functions that realize the (I+, I−)-initial conditions.
We introduce now the concept of partial sums order on I.
Definition 2. A partial sums order on I that realizes the (I+, I−)-initial
conditions (briefly a (I|I+, I−)-partial sums order) is a partial order ⊑
on M(I) such that if A, B ∈ M(I) then
A ⊑ B ⇐⇒
∑
α∈A
f(α) 6
∑
β∈B
f(β) for each f ∈ Φ(I+, I−) (5)
174 Lattices of partial sums
A partial sums poset on I that realizes the initial conditions (I+, I−)
(briefly a (I|I+, I−)-partial sums poset) is an induced sub-poset (T, ⊑)
of (M(I), ⊑), for some subset T of M(I), where ⊑ is a (I|I+, I−)-partial
sums order. If (T, ⊑) is a lattice, we say that (T, ⊑) is a (I|I+, I−)-partial
sums lattice. If the partition (I+, I−) of I is clear from the context, we
only say that (T, ⊑) is a I-partial sums poset.
The aim of this section is to build explicitly a quasi-order which will
induce a (I|I+, I−)-partial sums order on an arbitrary totally ordered set
I. We now introduce a new symbol o and we formally assume that λ ≻ o
if λ ∈ I+ and o ≻ γ if γ ∈ I−. We set Io = I ∪ {o}. Of course Io is also a
totally ordered set with the obvious extension of the relation ≻ to Io.
Definition 3. Let q and p be two non-negative integers. A Io-string w
with balance (q, p) is a finite sequence of the form (λq, . . . , λ1|γ1, . . . , γp),
where λq, . . . , λ1 ∈ I+ ∪ {o}, γp, . . . , γ1 ∈ I− ∪ {o} and λq � · · · � λ1,
γ1 � · · · � γp. The elements λq, . . . , λ1, γ1, . . . , γp are called indexes of w.
A Io-string w is a Io-string having balance (q, p), for some non-negative
integers q and p.
When I+ is a subset of the real interval (0, +∞) and I− is a sub-
set of the real interval (−∞, 0), we assume the following convention. If
w = (λq, . . . , λ1|γ1, . . . , γp) is a Io-string, we also write w in the form
λq . . . λ1|µ1 . . . µp, where µj is the absolute value of γj , for j = 1, . . . , p.
For example, with 44o|oo11 we mean (4, 4, o|o, o, −1, −1), whereas the
Io-string (44, o|o, o, −11) will be write as (44)o|oo(11).
We denote by M(Io) the set of all the Io-strings. We call λq, . . . , λ1
the non-negative indexes of w and γ1, . . . , γp the non-positive indexes
of w; also, we call positive indexes of w the elements λi with λi ≻ o
and negative indexes of w the elements γj with γj ≺ o. We assume that
q = 0 [p = 0] iff there are no non-negative [non-positive] indexes of w; in
particular, it results that p = 0 and q = 0 iff w is the empty string, that
we denote by (|). If (w = λq, . . . , λ1|γ1, . . . , γp), we set w+ = λq . . . λ1|
and w− = |µ1 . . . µp.
If w is a Io-string, we denote by {w � o} [{w ≻ o}] the multi-set of
all the non-negative [positive] indexes of w, by {w � o} [{w ≺ o}] the
multi-set of all the non-positive [negative] indexes of w and by {w} the
multi-set of all the indexes of w (i.e. {w} = {w � o} ∪ {w � o}). We
denote respectively with |w|�, |w|�, |w|≻, |w|≺ the cardinality of {w � o},
{w � o}, {w ≻ o}, {w ≺ o}. We call the ordered couple (|w|≻, |w|≺) the
signature of w and we note that (|w|�, |w|�) is exactly the balance of w .
G. Chiaselotti, T. Gentile, P. A. Oliverio 175
For example, if I = Z\{0}, I+ = Z+, I− = Z− and w = 444221ooo|o11333,
then {w � o} = {43, 22, 11, o3}, {w � o} = {o1, (−1)2, (−3)3}, {w ≻ o} =
{43, 22, 11}, {w � o} = {(−1)2, (−3)3}, w has balance (|w|�, |w|�) = (9, 6)
and signature (|w|≻, |w|≺) = (6, 5). In the sequel, two Io-strings w =
(λq, . . . , λ1|γ1, . . . , γp) and w′ = (λ′
q′ , . . . , λ′
1|γ′
1, . . . , γ′
p′) are considered
equals (and we shall write w = w′) if and only if q = q′, p = p′ and λi = λ′
i,
µj = µ′
j for i = 1, . . . , q and j = 1, . . . , p. Therefore, for example, the two
Io-strings (λ2, λ1, o, o, o|γ1, γ2) and (λ2, λ1, o, o|o, γ1, γ2) are considered
different between them in our context. If w is a Io-string having signature
(t, s) and balance (q, p), then w has the form
w = (λq, . . . , λq−t+1, λq−t, . . . λ1|γ1, . . . , γp−s, γp−s+1, . . . , γp) (6)
where λq � · · · � λq−t+1 ≻ 0 ≻ γp−s+1 � · · · � γp, λq−t = . . . = λ1 = o
and γ1 = . . . = γp−s = o. We also write w in (6) in the following form:
w = (λq, . . . , λq−t+1, oq−t|op−s, γp−s+1, . . . , γp) (7)
If w is a Io-string as in (7), we call reduced Io-string of w the following
Io-string:
w∗ = (λq, . . . , λq−t+1|γp−s+1 . . . γp) (8)
If W is a subset of M(Io), we set W∗ = {w∗ : w ∈ W}. Then it is obvious
that we can identify the set M(I) with the set M(Io)∗. Let us note that
{w ≻ o} = {w∗ ≻ o} and {w ≺ o} = {w∗ ≺ o}.
If U is a subset Io-strings, we say that U is uniform if all the Io-strings
in U have the same balance; in particular, if all the Io-strings in U
have balance (q, p), we also say that U is (q, p)-uniform. If v1, . . . , vk are
Io-strings, we say that they are uniform [(q, p)-uniform] if the subset
U = {v1, . . . , vk} is uniform [(q, p)-uniform]. If F is a finite subset of
Io-strings, we define a way to make uniform all the Io-strings in F : we
set qF = max{|v|� : v ∈ F}, pF = max{|v|� : v ∈ F}; moreover, if
v = (λq, . . . , λ1|γ1, . . . , γp) ∈ F we also set
vF = (λq, . . . , λ1, oqF −q|opF −p, γ1, . . . , γp)
and F = {vF : v ∈ F}. Then F is (qF , pF )-uniform and |F | 6 |F |. If F is
uniform we note that vF = v for each v ∈ F , hence F = F . We call F the
uniform closure of F . When F is clear from the context we simply write
v instead of vF . In particular, if v and w are two Io-strings, when we
write v and w without further specification, we always mean vF and wF ,
where F = {v, w}. We observe that if v and w are two uniform Io-strings
176 Lattices of partial sums
then v = v and w = w; moreover, for each finite subset F ⊆ P such that
w ∈ F we have {w ≻ 0} = {wF ≻ 0} and {w ≺ 0} = {wF ≺ 0}.
If u = (λq, . . . , λ1|γ1 . . . γp) and u′ = (λ′
q, . . . , λ′
1|γ′
1, . . . , γ′
p) are two
uniform Io-strings, we set:
u 0 u′ ⇐⇒ λi � λ′
i and γj � γ′
j (9)
for all i = 1, . . . , q and j = 1, . . . , p.
We also set
u △ u′ = (min{λq, λ′
q}, . . . , min{λ1, λ′
1}| min{γ1, γ′
1}, . . . , min{γp, γ′
p})
and
u ▽ u′ = (max{λq, λ′
q}, . . . , max{λ1, λ′
1}| max{γ1, γ′
1}, . . . , max{γp, γ′
p}).
Let us introduce now a quasi-order ⊑ (i.e. a reflexive and transitive
binary relation) on the set M(Io) of all the Io-strings.
Definition 4. If v, w ∈ M(Io), we set
v ⊑ w if v 0 w. (10)
In particular, if v and w are uniform, then v ⊑ w iff v 0 w.
The following result is simple but useful:
Proposition 1. ⊑ is a quasi-order on the set M(Io). Moreover, if v, w ∈
M(Io) the following conditions are equivalent:
(i) v ⊑ w.
(ii) There exists a finite subset F of M(Io) containing v and w such
that vF 0 wF .
(iii) For each finite subset F of M(Io) containing v and w we have
vF 0 wF .
(iv) v∗ ⊑ w∗.
Proof. It is immediate to verify that the relation ⊑ is a quasi-order. The
unique implication that requires some comment is (ii) ⇒ (iii). For this, it
is enough to observe that if {v, w} ⊆ H ⊆ F , with H and F both finite,
then vH 0 wH if and only if vF 0 wF .
G. Chiaselotti, T. Gentile, P. A. Oliverio 177
2. Abstract partial sums posets
We consider now the equivalence relation on M(Io) induced from the
quasi-order ⊑, i.e. if v and w are two Io-strings in M(Io), we set
v ∼ w ⇐⇒ v ⊑ w and w ⊑ v (11)
The proof of the following result is immediate from the above definitions.
Proposition 2. (i) If v and w are two Io-strings, then v = w if and
only if v and w are uniform and v ∼ w.
(ii) If F is a finite subset of M(Io) such that v, w ∈ F , then v ∼ w if
and only if vF = wF .
(iii) If F is a finite subset of M(Io) such that v ∈ F then v ∼ vF .
(iv) If v is a Io-string then v ∼ v∗.
If F is any subset of M(Io), we can consider on the quotient set F/ ∼
the usual partial order induced by ∼, which will be denoted by .. We
recall that . is defined as follows: if Z, Z ′ ∈ F/ ∼ then
Z . Z ′ ⇐⇒ v ⊑ v′ (12)
for any/all v, w ∈ F such that v ∈ Z and v′ ∈ Z ′.
If w ∈ F , in some case we set [w]F∼ = {v ∈ F : v ∼ w}, that is the
equivalence class of w in F/ ∼.
Remark 1. If F ⊆ H ⊆ M(Io) we can consider F/ ∼ as a subset of H/ ∼
through the identification of [v]F∼ with [v]H∼ , for each v ∈ F . Therefore, if
F ⊆ H ⊆ M(Io) we always can assume that (F/ ∼ ,.) is a sub-poset of
(H/ ∼ ,.).
The next definition describes a type of subsets of Io-strings which
shall permit us to find several partial sums lattices.
Definition 5. We say that a subset F ⊆ M(Io) is lattice-inductive if for
each finite subset F ⊆ F it results that:
(i) F ⊆ F ;
(ii) if v, w ∈ F , then vF △ wF ∈ F and vF ▽ wF ∈ F .
Let us note that obviously M(Io) is lattice-inductive. The relevance
of the lattice-inductive subsets of P is established in the following result.
178 Lattices of partial sums
Theorem 1. Let F a lattice-inductive subset of M(Io). Then (F/ ∼ ,.)
is a distributive lattice.
Proof. To prove that (F/ ∼) is a lattice, we take two equivalence classes
[v]F∼ and [w]F∼ in (F/ ∼) and we define the following operations: [v]F∼ ∧
[w]F∼ = [v △ w]F∼ and [v]F∼ ∨ [w]F∼ = [v ▽ w]F∼. It easy to see that the
operations ∧ and ∨ are well defined because they do not depend on
the choice of representatives in the respective equivalence classes and
that [v]F∼ ∧ [w]F∼ . [v]F∼, [v]F∼ ∧ [w]F∼ . [w]F∼. Let now [z]∼ ∈ F/ ∼
such that [z]F∼ . [v]F∼ and [z]F∼ . [w]F∼. We set F = {v, w, z}. Then:
([z]F∼ . [v]F∼ and [z]F∼ . [w]F∼) ⇐⇒ (by definition of .) (z ⊑ v and
z ⊑ w) ⇐⇒ (by Proposition 1 (iii)) zF 0 vF and zF 0 wF ⇐⇒ (by
definition of 0 and of △) zF 0 vF △ wF ⇐⇒ (since the Io-strings are
uniform) zF ⊑ vF △ wF ⇐⇒ (by definition of . and by Proposition 2
(iii)) [z]F∼ = [zF ]F∼ . [vF △ wF ]F∼. Now, since [vF △ wF ]F∼ = (by definition
of ∧) [vF ]F ∧ [wF ]F = (by Proposition 2 (iii)) [v]F∼ ∧ [w]F∼, it follows that
[z]F∼ . [v]F∼ ∧ [w]F∼. This proves that the operation ∧ defines effectively
the inf in (F/ ∼,.). In the same way we can proceed for the operation ∨
in the sup-case. Finally, let us note that the distributivity holds because
the operations △ and ▽ are defined on the components of the uniform
Io-strings.
Since M(Io) is obviously lattice-inductive, it follows that:
Corollary 1. (M(Io)/ ∼ ,.) is a distributive lattice.
When F is finite and uniform is simple to verify if F is lattice-inductive:
Corollary 2. Let F a finite uniform subset of M(Io), then F is lattice-
inductive if and only if whenever v, w ∈ F also v △ w ∈ F and v ▽ w ∈ F
Let us observe that if v ∈ F , by Proposition 2 (iv) we can always
choose v∗ as a representative for the equivalence class [v]F∼. In such a
way we identify the quotient set F/ ∼ with the subset F∗ of M(Io), and
we shall write F/ ∼≡ F∗. Therefore, if F ⊆ M(Io), Z, Z ′ are two any
equivalence classes in F/ ∼ and v, v′ are two any elements in F such that
v ∈ Z, v′ ∈ Z ′, the order (12) will have the following equivalent form (by
Proposition 1 (iv)):
Z . Z ′ ⇐⇒ v∗ ⊑ v′
∗ (13)
Hence, taking into account the conventions established in (13), we can
always think that on each quotient set F/ ∼ the partial order . is
identified with ⊑, therefore:
G. Chiaselotti, T. Gentile, P. A. Oliverio 179
Remark 2. If F ⊆ M(Io) we shall identify the quotient poset (F/ ∼,.)
with (F∗, ⊑), and this means that we shall consider (F/ ∼,.) as a sub-
poset of (M(Io)∗, ⊑) ≡ (M(I), ⊑).
In particular, if F coincides with M(Io) then
(M(Io)/ ∼,.) ≡ (M(Io)∗, ⊑) ≡ (M(I), ⊑) (14)
If f ∈ Φ(I+, I−) we define the function f̃ : Io → R setting
f̃(α) =
{
f(α) if α ∈ I
0 if α = o
Definition 6. If f ∈ Φ(I+, I−), we denote by
∑
f the function
∑
f :
M(Io) → R such that
∑
f (w) =
∑
α∈{w} f̃(α) for each w ∈ M(Io), and
we call
∑
f the sum function of f .
Let us note that if w ∈ M(Io) then
∑
f (w) =
∑
α∈{w∗} f(α).
The next is the main result of this section.
Theorem 2. (i) The partial order ⊑ on M(I) in (14) is a (I|I+, I−)-
partial sums order.
(ii) If F is a subset of M(Io), then (F∗, ⊑) is a (I|I+, I−)-partial sums
poset.
(iii) If F is a lattice-inductive subset of M(Io), then (F∗, ⊑) is a dis-
tributive (I|I+, I−)-partial sums lattice.
Proof. (i) By Proposition 1 (iii) it is sufficient to prove that if w and w′
are two uniform Io-strings then
w ⊑ w′ ⇐⇒
∑
f
(w) 6
∑
f
(w′) (15)
Let w = (λq, . . . , λ1|γ1, . . . , γp) and w′ = (λ′
q, . . . , λ′
1|γ′
1, . . . , γ′
p) two uni-
form Io-strings. If w ⊑ w′, by (9) we have λi � λ′
i and γj � γ′
j for
all i = 1, . . . , q and j = 1, . . . , p. Therefore, if f ∈ Φ(I+, I−), from the
hypothesis that f realizes the (I+, I−)-initial conditions and by definition
of
∑
f , we obtain
∑
f (w) 6
∑
f (w′).
We assume now that
∑
f (w) 6
∑
f (w′) for each f ∈ Φ(I+, I−) and
that the condition w ⊑ w′ is false. This means that there exists some
i ∈ {1, . . . , q} such that λi ≻ λ′
i or some j ∈ {1, . . . , p} such that γj ≻ γ′
j .
Let us suppose first that there exists i ∈ {1, . . . , q} such that λi ≻ λ′
i and
180 Lattices of partial sums
we assume that i is maximal among all the positive integers l ∈ {1, . . . , q}
such that λl ≻ λ′
l, therefore
λq � · · · � λi+1 � λi ≻ λ′
i � λ′
i−1 � · · · � λ′
1 ; λ′
q � λq, . . . , λ′
i+1 � λi+1
(16)
We consider now the following function :
f(α) :=
−1 if α ∈ I−
0 if α ∈ I+ and α ≺ λi
+1 if α ∈ I+ and α � λi
Then f ∈ Φ(I+, I−) and by (16) it follows that
∑
f (w) > (q − i + 1) +
∑
16j6p f̃(γj) > (q−i)+
∑
16j6p f̃(γj) = (q−i)+
∑
16j6p f̃(γ′
j) =
∑
f (w′),
that is a contradiction.
We can suppose then λi � λ′
i for all i = 1, . . . , q, so there exists
j ∈ {1, . . . , p} such that γj ≻ γ′
j and we assume that j is minimal among
all the positive integers l ∈ {1, . . . , p} such that γl ≻ γ′
l, therefore
γ1 � · · · � γj−1 � γj ≻ γ′
j � γ′
j+1 � · · · � γ′
p ; γ′
1 � γ1, . . . , γ′
j−1 � γj−1
(17)
We must now distinguish two cases. First we suppose that γj = o. In this
case we consider the following function:
h(α) :=
{
0 if α ∈ I+
−1 if α ∈ I−
Then h ∈ Φ(I+, I−) and by (17) it follows that
∑
h(w) > (−1)(p − j) >
(−1)(p − j + 1) =
∑
h(w′), that is a contradiction. We assume now that
γj ≺ o. In this case we consider the following function:
g(α) :=
+1 if α ∈ I+
−1 if α ∈ I− and α � γj
−2 if α ∈ I− and α ≺ γj
Then g ∈ Φ(I+, I−) and by (17) we have:
∑
g
(w) >
∑
16l6j−1
g̃(γl) + (−1) +
∑
j+16l6p
g̃(γl)
>
∑
16l6j−1
g̃(γl) + (−2) +
∑
j+16l6p
g̃(γl)
=
∑
16l6j−1
g̃(γ′
l) + g̃(γ′
j) +
∑
j+16l6p
g̃(γl)
>
∑
16l6j−1
g̃(γ′
l) + (−2) + (−2)(p − j) =
∑
g
(w′)
G. Chiaselotti, T. Gentile, P. A. Oliverio 181
that is a contradiction. This complete the proof of (i). Parts (ii) and (iii)
are direct consequence of Remark 2 and Theorem 1.
We establish now some direct consequences of the previous theorem.
Corollary 3. (M(I), ⊑) is a distributive (I|I+, I−)-partial sums lattice.
Proof. We take F = M(Io). Since F is lattice-inductive, by Theorem 2
(iii) it follows that (M(Io)∗, ⊑) is a distributive (I|I+, I−)-partial sums
lattice. The result follows then by (14).
Corollary 4. The classical Young lattice Y of the integer partitions is a
distributive partial sums lattice.
Proof. In the particular case I = N, I+ = N and I− = ∅ we have
Y = M(I) and the partial order on Y is exactly ⊑. Hence the thesis
follows from the previous corollary.
We recall now the definition of the lattice L(m, n) introduced by
Stanley in [22]: if m and n are two positive integers, L(m, n) is the
sub-lattice of Y of all the integer partitions with at most m parts and
maximum part not exceeding n.
Corollary 5. L(m, n) is a distributive partial sums lattice.
Proof. We take I = {n > n − 1 > · · · > 1}, I+ = I and I− = ∅. We
consider the subset F of M(Io) whose elements are the Io-strings w such
that |w|> = m. Then F is lattice-inductive and F∗ = L(m, n). Hence the
thesis follows by (iii) of the previous theorem.
Corollary 6. If F is a subset of M(Io) and f ∈ Φ(I+, I−), the restricted
sum function
∑
f : F∗ → R is order-preserving.
Proof. It follows from the definition of (I|I+, I−)-partial sums poset and
by Theorem 2 (ii).
In terms of partial sums on a numerable quantity of real variables, we
must take I− = Z− = {−1, −2, −3, . . . } and I+ = Z+ = {1, 2, 3, . . . }. In
this case, (4) becomes
. . . > xr > xr−1 > . . . > x1 > 0 > y1 > y2 > . . . (18)
In this case, if w = (λt, . . . , λ1|µ1, . . . , µs) ∈ M(I), we set
∑
(w) =
xλt
+ · · · + xλ1
+ yµ1
+ · · · + yµs
. Then, by the Theorem 2 we can to
182 Lattices of partial sums
think the partial order ⊑ on M(I) as the natural order induced from the
linear systems inequalities (18) on the partial sum of the real variables
. . . xr, xr−1, . . . , x1, y1, . . . , yq, . . . In other terms, if we formally identify
the signed partitions w and w′ respectively with the indeterminate real
partial sums
∑
(w) and
∑
(w′), then the result of the Theorem 2 tell us
that w ⊑ w′ if and only if the real inequality
∑
(w) 6
∑
(w′) holds and it
can be deduced by using only the inequalities in (18). We can therefore
use a more suggestive terminology and to think the signed partition
lattice (M(I), ⊑) as a lattice of indeterminate partial sums take over
a numerable quantity of real variables . . . xr, xr−1, . . . , x1, y1, . . . , yq, . . .
that satisfy (18). Using this interpretation a finite piece of the Hasse
diagram of M(I) is the following:
2y2
x1 + 2y2 y1 + y2
x2 + 2y2
2x1 + 2y2 x1 + y1 + y2 y2
2y1
x2 + x1 + 2y2
x2 + y1 + y2 2x1 + y1 + y2 x1 + y2 x1 + 2y1
y1
. . . . . .
A particularly relevant lattice-inductive subset of M(Io) is the subset of
all the Io-strings without repeated negative indexes and without repeated
positive indexes. We denote such a subset by S(Io).
Theorem 3. S(Io) is lattice-inductive.
Proof. Let F be a finite subset of S(Io) and let w ∈ F , then, by definition
of F , there exists v ∈ F such that w = vF . Since v is also an element of
S(Io), it has no repeated negative or positive indexes, therefore also vF
has no repeated negative or positive indexes, since vF is built by adding
only eventual further o’s to v. Hence w ∈ S(Io), and this shows that
F ⊆ S(Io).
Let now v, v′ ∈ F , and w = vF = (λq, . . . , λ1|γ1, . . . , γp), w′ = v′F =
(λ′
q, . . . , λ′
1|γ′
1, . . . , γ′
p), then w, w′ ∈ F ⊆ S(Io). We must to prove that
w △ w′ ∈ S(Io) and w ▽ w′ ∈ S(Io). We show only that w △ w′ ∈ S(Io)
because the proof that w ▽ w′ ∈ S(Io) is similar. Let w′′ = w ▽ w′, with
G. Chiaselotti, T. Gentile, P. A. Oliverio 183
w′′ = (λ′′
q , . . . , λ′′
1|γ′′
1 , . . . , γ′′
p ). Let us suppose by absurd that w′′ /∈ S(Io);
by definition of S(Io) this means that there exist two positive indexes
or two negative indexes in w′′ that must be equal. We can assume that
there exist λ′′
k and λ′′
l such that k > l and λ′′
k = λ′′
l ≻ o (the case when
λ′′
k = λ′′
l ≺ o is analogue). Since λ′′
k = λ′′
l and w′′ ∈ M(Io), we have
λ′′
k = λ′′
k−1 = · · · = λ′′
l+1 = λ′′
l (19)
We note that λl ≻ o and λ′
l ≻ o because λ′′
l ≻ o, therefore, since w, w′ ∈
S(Io), by definition of S(Io) it follows that
λk ≻ λk−1 ≻ · · · ≻ λl+1 ≻ λl (20)
and
λ′
k ≻ λ′
k−1 ≻ · · · ≻ λ′
l+1 ≻ λ′
l (21)
We assume now that λ′′
k = λk. Then, if λ′′
k−1
= λk−1, by (19) we have
λk = λk−1, that contradicts (20). Therefore it must be λ′′
k−1
= λ′
k−1
. Then
by (19) it follows that λk = λ′
k−1
and hence, by (20), λ′
k−1
≻ λk−1, but
this contradicts the equality λ′′
k−1
= min{λk−1, λ′
k−1
} = λ′
k−1
. On the
other side, also the equality λ′′
k = λ′
k leads to an absurd if we use (19)
and (21). This complete the proof.
Obviously we can identify S(Io)∗ with the subset of M(I) whose
elements are the finite subsets (i.e. the finite multi-sets without repeated
elements) of I, that we denote by S(I). Therefore, by the previous propo-
sition it follows that (S(I), ⊑) ≡ (S(Io)∗, ⊑) is a distributive (I|I+, I−)-
partial sums lattice. We recall now the definition of the Stanley lattice
M(n) (see [22]): M(n) is the sub-lattice of the Young lattice Y whose
elements are the integer partitions having all distinct parts and whose
maximum is at most n, where n is an arbitrary positive integer. We have
then:
Corollary 7. M(n) is a distributive partial sums lattice.
Proof. If we take I = {n, n − 1, . . . , 1}, I+ = I and I− = ∅, then M(n)
coincides exactly with S(Io)∗. Hence the thesis is a direct consequences
of the previous theorem.
If n > r > 0 are two integers, we can take I = {r > · · · > 1 > −1 >
· · · > −(n − r)}, (I+ = {r, . . . , 1} and I− = {−1, . . . , −(n − r)}). In this
case S(Io)∗ coincides with the lattice S(n, r) introduced in [3] and [4] in
184 Lattices of partial sums
order to study some extremal combinatorial sum problems. As observed
in [8], S(n, r) is isomorphic to the direct product M(r) × M(n − r)∗.
We recall now the definition of valuation on an arbitrary lattice X.
If X is a lattice, a map η : X → R is called a valuation on X if for all
a, b ∈ X: η(a ∧ b) + η(a ∨ b) = η(a) + η(b).
Proposition 3. Let F be a lattice-inductive subset of M(Io) and f ∈
Φ(I+, I−). Then the restricted sum function
∑
f : F∗ → R is a valuation
on (F∗, ⊑).
Proof. Since the partial order ⊑ is made on the components of the Io-
strings, the result follows.
In [20] was shown that a valuation on a distributive lattice is uniquely
determined by the values that it takes on the join-irreducible elements
of the lattice, therefore, in our case, this means that
∑
f is uniquely
determined by the values that it takes on the join-irreducible elements of
the distributive lattice F∗.
References
[1] K. Alladi, P. Erdös and J.D. Vaaler, Multiplicative functions and small divi-
sors, Analytic Number Theory and Diophantine Problems, Vol. 70, Progress in
Mathematics, Birkhäuser, Boston, MA, 1987, pp. 1–13.
[2] T. Bier and N. Manickam, The first distribution invariant of the Johnson-scheme,
SEAMS Bull. Math., 11 (1987), 61–68.
[3] C. Bisi and G. Chiaselotti, A class of lattices and boolean functions related to the
Manickam-Miklös-Singhi Conjecture, Adv. Geom. 13, Issue 1, (2013), 1–27.
[4] C. Bisi and G. Chiaselotti, Extension results for boolean maps and a class of
systems of linear inequalities e-print arXiv:1012.5486 (2010), 1–22
[5] G. Chiaselotti, On a problem concerning the weight functions, European J. Combin.,
23 (2002), 15–22.
[6] G. Chiaselotti, G. Infante, G. Marino, New results related to a conjecture of
Manickam and Singhi. European J. Combin. 29 (2008), n. 2, 361–368.
[7] G. Chiaselotti, G. Marino, C. Nardi, A minimum problem for finite sets of real
numbers with nonnegative sum, J. Appl. Math, 2012 (2012), Article ID 847958,
15 pages.
[8] K. Engel and C. Nardi, Solution of a problem on non-negative subset sums,
European J. Combin., 33, (2012), 1253–1256.
[9] P. Erdös, C. Ko and R. Rado Intersection theorems for systems of finite sets.
Quart. J. Math. Oxford Ser. (2), 12 (1961), 313–320.
[10] L. Geissinger, Valuations on distributive lattices.I. Arch. Mat (1973), no. 24,
230–239
G. Chiaselotti, T. Gentile, P. A. Oliverio 185
[11] L. Geissinger, Valuations on distributive lattices.II. Arch. Mat (1973), no. 24,
337–345
[12] L. Geissinger, Valuations on distributive lattices.III. Arch. Mat (1973), no. 24,
475–481
[13] G. O. H. Katona, A simple proof of the Erdös-Ko-Rado theorem. J. Combinatorial
Theory Ser. B, 13 (1972), 183–184.
[14] N. Manickam, First distribution invariants of association shemes, Ph. D. Thesis,
The Ohio State University, (1986).
[15] N. Manickam, W -complement d-spreads, Singleton systems, European J. Combin.,
8 (4) (1987), 437–439.
[16] N. Manickam and D. Miklos, On the number of non–negative partial sums of a
non–negative sum, Colloq. Math. Soc. Janos Bolyai, 52 (1987), 385–392.
[17] N.Manickam, Distribution Invariants of Association Schemes, Congress Numeran-
tum, 61 (1988), 121–131.
[18] N. Manickam, First distributed sets in the association scheme of bilinear forms,
Colloq. Math. Soc. Janos Bolyai, 60 (1991), 465–468.
[19] G. Marino and G. Chiaselotti, A method to count the positive 3-subsets in a set
of real numbers with non-negative sum, European J. Combin., 23 (2002), 619–629.
[20] G.C. Rota, On the combinatorics of the Euler characteristic, Studies in Pure Math.,
Ac.Press, London, 1971, 221–233.
[21] S. Srinivasan, On an Arithmetical Inequality II, Contemporary Mathematics,
American Mathematical Society, Vol. 210, Providence, RI, 1998, pp. 299–301.
[22] R.P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property
SIAM J. Alg. Disc. Meth., 1 (1980), 168–184.
[23] M. Tyomkyn, An improved bound for the Manickam-Miklós-Singhi conjecture,
European J. Combin., 33 (1), (2012), 27–32.
Contact information
G. Chiaselotti,
T. Gentile,
P. A. Oliverio
Dipartimento di Matematica, Universitá della
Calabria, Via Pietro Bucci, Cubo 30B, 87036
Arcavacata di Rende (CS), Italy.
E-Mail(s): chiaselotti@unical.it,
gentile@mat.unical.it,
oliverio@unical.it
Received by the editors: 03.10.2012
and in final form 06.06.2013.
|