Abstract We discuss in the paper following problem: Given a function given Baire class, into “how many” (in terms of cardinal numbers) functions lower classes can it be decomposed? The decomposition is understood here sense set-theoretical union.

Abstract For the only known universal best choice algorithm for partially ordered sets with cardinality and unknown order (proposed by J. Preater) we improve estimation of lower bound its chance success from hitherto constant 1/8 to 1/4. We also show that this result is possible algorithm, i.e., 1/4 cannot be further improved. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008

We consider a version of the secretary problem where each candidate has an identical twin. The aim, as in classical problem, is to choose with largest possible probability top candidate, i.e., one best twins. find optimal stopping time for such choice, success yields, and their asymptotic behavior.

For a class <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of subsets set alttext="upper Z"> <mml:mi>Z</mml:mi> encoding="application/x-tex">Z</mml:annotation>...

We show that for all positive natural numbers m, n the following two sentences are equivalent: (i) 2NO 1 we present, using notions of classical mathematical analysis, a sentence (Pn equivalent to 2to theory ZFC + = Nn is consistent (whenever consistent). Solovay's result implies as well 2No > N, (w denotes here order type set numbers). The N1 called Continuum Hypothesis, and its independence results from work K. G6del P. J. Cohen. (On proclaims there exists an onto function f: Rn __ Rn+m (R...

The relative rank (S : U) of a subsemigroup U semigroup S is the minimum size set V ⊆ such that together with generates whole S. As consequence result Sierpiński, it follows for ⩽ TX, monoid all self-maps an infinite X, rank(TX either 0, 1 or 2, uncountable. In this paper, ranks OX) are considered, where X countably partially ordered and OX endomorphism X. We show 2 if only either: there exists at least one element in which greater than, less number elements X; has |X| connected components....

We consider the following on-line decision problem. The vertices of a directed path known length are being observed one by in some random order selector. At time t selector examines tth vertex and knows graph induced that have been already examined. selector's aim is to choose currently examined maximizing probability this "uppermost" one, i.e., only does not an outgoing edge. An optimal algorithm for such choice (in other words, stopping time) given. For cardinality n considered, $p_n$...

In this paper we explore the extent to which algebraic structure of a monoid<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"><mml:semantics><mml:mi>M</mml:mi><mml:annotation encoding="application/x-tex">M</mml:annotation></mml:semantics></mml:math></inline-formula>determines topologies on<inline-formula encoding="application/x-tex">M</mml:annotation></mml:semantics></mml:math></inline-formula>that are compatible with its...

If $X$ is a metric space, then $\mathcal {C}_{X}$ and {L}_X$ denote the semigroups of continuous Lipschitz mappings, respectively, from to itself. The relative rank modulo {L}_{X}$ least cardinality any set $U\setminus \mathcal where $U$ generates {C}_{X}$. For large class separable spaces we prove that uncountable. When Baire space $\mathbb {N}^{\mathbb {N}}$, this $\aleph _{1}$. A part paper emerged discussions about necessity assumptions imposed on aforementioned results.

We consider a secretary type problem where an administrator who has only one on-line choice in m consecutive searches to choose the best candidate of them.

Previous article Next Repeated Degrees in Random Uniform HypergraphsPaul Balister, Béla Bollobás, Jenö Lehel, and Michał MoraynePaul Moraynehttps://doi.org/10.1137/100785156PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractWe prove that a random $3$-uniform or $4$-uniform hypergraph of order $n$ the probability some two vertices have same degree tends one as $n\to\infty$.1. P. B. Bollobás, J. M. Morayne, Hypergraph Irregularity, submitted.Google...

for the number of multiplications to get D in triangular form. There will then be n (of diagonal entries) compute det(D), requiring 0(n4) multiplications. As before, we do not consider more sophisticated algorithms computing determinants. We remark that there is an algorithm V. Strassen uses divide-and-conquer reduce but with a similar order magnitude. A situation holds computation each (n 1)-minors D. Since are 1 such minors, multiplicative complexity 1)0(n4) = 0(n5) constant no than 1/3....

We examine the evolution of best choice algorithm and probability its success from a directed path to linear order same cardinality through $k$th powers path, $1 \leq k<n$. The vertices power known length $n$ are exposed one by selector in some random permutation. At any time can see graph induced that have already come. selector's aim is choose online maximal vertex (i.e., with no outgoing edges). It shown $p_n$ for optimal satisfies $p_n = \Theta(n^{-1/(k+1)})$. also consider case when...

A random walk that carries information starts at 0 and moves inside the set of integers Z. When reaches a new point this obtains information. given Vf containing is considered to be friendly stations its complement Vh = Z hostile stations. An observer who knows partition into signal only if station informed. There are two kinds signal: from ones. This whole knowledge about possesses. Thus observer’s time measured by number informed The can stop newly wins n there have been no one or least...