Difference between revisions of "Ahlswede-Daykin inequality"
From Encyclopedia of Mathematics
Ulf Rehmann (talk | contribs) m (moved Ahlswede–Daykin inequality to Ahlswede-Daykin inequality: ascii title) |
Ulf Rehmann (talk | contribs) m (typo) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | <!-- | ||
| + | a1104401.png | ||
| + | $#A+1 = 19 n = 0 | ||
| + | $#C+1 = 19 : ~/encyclopedia/old_files/data/A110/A.1100440 Ahlswede\ANDDaykin inequality, | ||
| + | Automatically converted into TeX, above some diagnostics. | ||
| + | Please remove this comment and the {{TEX|auto}} line below, | ||
| + | if TeX found to be correct. | ||
| + | --> | ||
| + | |||
| + | {{TEX|auto}} | ||
| + | {{TEX|done}} | ||
| + | |||
''four-functions inequality'' | ''four-functions inequality'' | ||
| − | An inequality in which an inequality for four functions on a finite distributive lattice applies also to additive extensions of the functions on lattice subsets. Let | + | An inequality in which an inequality for four functions on a finite distributive lattice applies also to additive extensions of the functions on lattice subsets. Let $ ( \Gamma, \prec ) $ |
| + | be a finite [[Distributive lattice|distributive lattice]] (see also [[FKG inequality|FKG inequality]]), such as the power set of a finite set ordered by proper inclusion. For subsets $ A $, | ||
| + | $ B $ | ||
| + | of $ \Gamma $, | ||
| + | define $ A \lor B = \{ {a \lor b } : {a \in A, b \in B } \} $ | ||
| + | and $ A \wedge B = \{ {a \wedge b } : {a \in A, b \in B } \} $. | ||
| + | If $ A $ | ||
| + | or $ B $ | ||
| + | is empty, $ A \lor B = A \wedge B = \emptyset $. | ||
| + | Given $ f : \Gamma \rightarrow \mathbf R $, | ||
| + | let $ f ( A ) = \sum _ {a \in A } f ( a ) $. | ||
| − | The Ahlswede–Daykin inequality says that if | + | The Ahlswede–Daykin inequality says that if $ f _ {1} $, |
| + | $ f _ {2} $, | ||
| + | $ f _ {3} $, | ||
| + | and $ f _ {4} $ | ||
| + | map $ \Gamma $ | ||
| + | into $ [ 0, \infty ) $ | ||
| + | such that | ||
| − | + | $$ | |
| + | f _ {1} ( a ) f _ {2} ( b ) \leq f _ {3} ( a \lor b ) f _ {4} ( a \wedge b ) \textrm{ for all } a, b \in \Gamma, | ||
| + | $$ | ||
then | then | ||
| − | + | $$ | |
| + | f _ {1} ( A ) f _ {2} ( B ) \leq f _ {3} ( A \lor B ) f _ {4} ( A \wedge B ) \textrm{ for all } A, B \subseteq \Gamma . | ||
| + | $$ | ||
See [[#References|[a1]]] or [[#References|[a2]]], [[#References|[a4]]], [[#References|[a7]]] for a proof. | See [[#References|[a1]]] or [[#References|[a2]]], [[#References|[a4]]], [[#References|[a7]]] for a proof. | ||
Latest revision as of 19:25, 4 April 2020
four-functions inequality
An inequality in which an inequality for four functions on a finite distributive lattice applies also to additive extensions of the functions on lattice subsets. Let $ ( \Gamma, \prec ) $ be a finite distributive lattice (see also FKG inequality), such as the power set of a finite set ordered by proper inclusion. For subsets $ A $, $ B $ of $ \Gamma $, define $ A \lor B = \{ {a \lor b } : {a \in A, b \in B } \} $ and $ A \wedge B = \{ {a \wedge b } : {a \in A, b \in B } \} $. If $ A $ or $ B $ is empty, $ A \lor B = A \wedge B = \emptyset $. Given $ f : \Gamma \rightarrow \mathbf R $, let $ f ( A ) = \sum _ {a \in A } f ( a ) $.
The Ahlswede–Daykin inequality says that if $ f _ {1} $, $ f _ {2} $, $ f _ {3} $, and $ f _ {4} $ map $ \Gamma $ into $ [ 0, \infty ) $ such that
$$ f _ {1} ( a ) f _ {2} ( b ) \leq f _ {3} ( a \lor b ) f _ {4} ( a \wedge b ) \textrm{ for all } a, b \in \Gamma, $$
then
$$ f _ {1} ( A ) f _ {2} ( B ) \leq f _ {3} ( A \lor B ) f _ {4} ( A \wedge B ) \textrm{ for all } A, B \subseteq \Gamma . $$
See [a1] or [a2], [a4], [a7] for a proof.
The inequality is very basic and is used in proofs of other inequalities (cf. [a2], [a3], [a4], [a5], [a7]), including the FKG inequality [a6] and the Fishburn–Shepp inequality [a3], [a8].
See also Correlation inequalities; Holley inequality.
References
| [a1] | R. Ahlswede, D.E. Daykin, "An inequality for the weights of two families, their unions and intersections" Z. Wahrscheinlichkeitsth. verw. Gebiete , 43 (1978) pp. 183–185 |
| [a2] | B. Bollobás, "Combinatorics" , Cambridge Univ. Press (1986) |
| [a3] | P.C. Fishburn, "A correlational inequality for linear extensions of a poset" Order , 1 (1984) pp. 127–137 |
| [a4] | P.C. Fishburn, "Correlation in partially ordered sets" Discrete Appl. Math. , 39 (1992) pp. 173–191 |
| [a5] | P.C. Fishburn, P.G. Doyle, L.A. Shepp, "The match set of a random permutation has the FKG property" Ann. of Probab. , 16 (1988) pp. 1194–1214 |
| [a6] | C.M. Fortuin, P.N. Kasteleyn, J. Ginibre, "Correlation inequalities for some partially ordered sets" Comm. Math. Phys. , 22 (1971) pp. 89–103 |
| [a7] | R.L. Graham, "Applications of the FKG inequality and its relatives" , Proc. 12th Internat. Symp. Math. Programming , Springer (1983) pp. 115–131 |
| [a8] | L.A. Shepp, "The XYZ conjecture and the FKG inequality" Ann. of Probab. , 10 (1982) pp. 824–827 |
How to Cite This Entry:
Ahlswede-Daykin inequality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ahlswede-Daykin_inequality&oldid=22009
Ahlswede-Daykin inequality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Ahlswede-Daykin_inequality&oldid=22009
This article was adapted from an original article by P.C. Fishburn (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article