4,611 research outputs found
A bound for Dickson's lemma
No full textWe consider a special case of Dickson's lemma: for any two functions on
the natural numbers there are two numbers such that both and
weakly increase on them, i.e., and . By a
combinatorial argument (due to the first author) a simple bound for such
is constructed. The combinatorics is based on the finite pigeon hole principle
and results in a descent lemma. From the descent lemma one can prove Dickson's
lemma, then guess what the bound might be, and verify it by an appropriate
proof. We also extract (via realizability) a bound from (a formalization of)
our proof of the descent lemma.
Keywords: Dickson's lemma, finite pigeon hole principle, program extraction
from proofs, non-computational quantifiers
Szemer\u27edi\u27s regularity lemma revisited
No full textSzemer\u27edi\u27s regularity lemma is a basic tool in graph theory, and also plays an important role in additive combinatorics, most notably in proving Szemer\\u27edi\u27s theorem on arithmetic progressions . In this note we revisit this lemma from the perspective of probability theory and information theory instead of graph theory, and observe a variant of this lemma which introduces a new parameter . This stronger version of the regularity lemma was iterated in a recent paper of the author to reprove
the analogous regularity lemma for hypergraphs
Politica della qualità e rispetto delle norme: il problema dell’accreditamento delle strutture sanitarie
No full textWiener's lemma
No full textIn this thesis we study Wiener’s lemma. The classical version of the lemma, whose realm is a Banach algebra, asserts that the pointwise inverse of a nonzero function with absolutely convergent Fourier expansion, also possesses an absolutely convergent Fourier expansion. The main purpose of this thesis is to investigate the validity inalgebras endowed with a quasi-norm or a p-norm.As a warmup, we prove the classical version of Wiener’s lemma using elemen-tary analysis. Furthermore, we establish results in Banach algebras concerning spectral theory, maximal ideals and multiplicative linear functionals and present a proof Wiener’s lemma using Banach algebra techniques. Let ν be a submultiplicative weight function satisfying the Gelfand-Raikov-Shilov condition. We show that if a nonzero function f has a ν-weighted absolutely convergent Fourier series in a p-normed algebra A. Then 1/f also has a ν-weightedabsolutely convergent Fourier series in A
Wiener's lemma
No full textIn this thesis we study Wiener’s lemma. The classical version of the lemma, whose realm is a Banach algebra, asserts that the pointwise inverse of a nonzero function with absolutely convergent Fourier expansion, also possesses an absolutely convergent Fourier expansion. The main purpose of this thesis is to investigate the validity inalgebras endowed with a quasi-norm or a p-norm.As a warmup, we prove the classical version of Wiener’s lemma using elemen-tary analysis. Furthermore, we establish results in Banach algebras concerning spectral theory, maximal ideals and multiplicative linear functionals and present a proof Wiener’s lemma using Banach algebra techniques. Let ν be a submultiplicative weight function satisfying the Gelfand-Raikov-Shilov condition. We show that if a nonzero function f has a ν-weighted absolutely convergent Fourier series in a p-normed algebra A. Then 1/f also has a ν-weightedabsolutely convergent Fourier series in A
Remarks on the proof of a generalized Hartogs Lemma
No full textThis paper is an outgrowth of a paper by the first author on a generalized Hartogs Lemma. We complete the discussion of the nonlinear ∂̅ problem ∂f/∂z̅ = ψ(z,f(z)). We also simplify the proofs by a different choice of Banach spaces of functions
Sperner's Lemma
No full textIn this article we introduce and prove properties of simplicial complexes in real linear spaces which are necessary to formulate Sperner's lemma. The lemma states that for a function f , which for an arbitrary vertex v of the barycentric subdivision B of simplex K assigns some vertex from a face of K which contains v, we can find a simplex S of B which satisfies f (S) = K (see [10])
Fatou’s lemma in several dimensions
No full textIn this note the following generalization of Fatou’s lemma is proved: Lemma. Let
(
f
n
)
n
−
1
∞
({f_n})_{n - 1}^\infty
be a sequence of integrable functions on a measure space
S
S
with values in
R
+
d
R_ + ^d
, the nonnegative orthant of a
d
d
-dimensional Euclidean space, for which
∫
f
n
→
a
∈
R
+
d
\int {{f_n} \to a \in R_ + ^d}
. Then there exists an integrable function
f
f
, from
S
S
to
R
+
d
R_ + ^d
, such that a.e.
f
(
s
)
f(s)
is a limit point of
(
f
n
(
s
)
)
n
−
1
∞
({f_n}(s))_{n - 1}^\infty
and
∫
f
≦
a
\int {f \leqq a}
.</p
Context awareness for e-Tourism: An adaptive mobile application
No full textThe Italian towns have a cultural heritage that often do not succeed in being completely enhanced. The natural, artistic and cultural resources present in the Italian towns, above all the smallest ones, many times remain hidden and are not enjoyed by the tourists. In this paper, it is introduced an Adaptive Context Aware app able to support a tourist inside a town. The system can guide the tourist in the discovery of a town proposing him/her resources and services mainly interesting for the user according to his/her interests and the position where he/she is. The objective is reached through the use of a system of description of the context through a graphical formalism named Context Dimension Tree. The App collects information also from social environments adapting the proposed itinerary taking into account the communities and the interests of the user. The entire approach has been tested inside the town of Salerno with very interesting results
From Farkas’ lemma to linear programming: An exercise in diagrammatic algebra
No full textFarkas’ lemma is a celebrated result on the solutions of systems of linear inequalities, which finds application pervasively in mathematics and computer science. In this work we show how to formulate and prove Farkas’ lemma in diagrammatic polyhedral algebra, a sound and complete graphical calculus for polyhedra. Furthermore, we show how linear programs can be modeled within the calculus and how some famous duality results can be proved
- …
