A Common Generalization to Theorems on Set Systems with <Emphasis Type="Italic">L</Emphasis>-intersections

In this paper, we provide a common generalization to the well-known Erdös–Ko–Rado Theorem, Frankl–Wilson Theorem, Alon–Babai–Suzuki Theorem, and Snevily Theorem on set systems with L-intersections. As a consequence, we derive a result which strengthens substantially the well-known theorem on set systems with k-wise L-intersections by Füredi and Sudakov [J. Combin. Theory, Ser. A, 105, 143–159 (2004)]. We will also derive similar results on L-intersecting families of subspaces of an n-dimensional vector space over a finite field F _q , where q is a prime power.     

Ergodic theorems for coset spaces

We study in this paper the validity of the Mean Ergodic Theorem along left Følner sequences in a countable amenable group G. Although the Weak Ergodic Theorem always holds along any left Følner sequence in G, we provide examples where the Mean Ergodic Theorem fails in quite dramatic ways. On the other hand, if G does not admit any ICC quotients, e.g., if G is virtually nilpotent, then the Mean Ergodic Theorem holds along any left Følner sequence. In the case when a unitary representation of a countable amenable group is induced from a unitary representation of a “sufficiently thin” subgroup, we show that the Mean Ergodic Theorem holds for the induced representation along any left Følner sequence. Furthermore, we show that every countable (infinite) amenable group L embeds into a countable (not necessarily amenable) group G which admits a unitary representation with the property that for any left Følner sequence (F_n) in L, there exists a sequence (s_n) in G such that the Mean (but not the Weak) Ergodic Theorem fails in a rather strong sense along the (right-translated) sequence (F_ns_n) in G. Finally, we provide examples of countable (not necessarily amenable) groups G with proper, infinite-index subgroups H, so that the Pointwise Ergodic Theorem holds for averages along any strictly increasing and nested sequence of finite subsets of the coset G/H.     

Large triangle-free subgraphs in graphs withoutK 4

It is shown that for arbitrary positive there exists a graph withoutK ₄ and so that all its subgraphs containing more than 1/2 + portion of its edges contain a triangle (Theorem 2). This solves a problem of Erdös and Neetil. On the other hand it is proved that such graphs have necessarily low edge density (Theorem 4).Theorem 3 which is needed for the proof of Theorem 2 is an analog of Goodman's theorem [8], it shows that random graphs behave in some respect as sparse complete graphs.Theorem 5 shows the existence of a graph on less than 10¹² vertices, withoutK ₄ and which is edge-Ramsey for triangles.     

Virtual boundaries of Hadamard spaces with admissible actions of higher rank

In this paper, we prove that every conformal minimal immersion of an open Riemann surface into \({\mathbb {R}}^n\) for \(n\ge 5\) can be approximated uniformly on compacts by conformal minimal embeddings (see Theorem 1.1). Furthermore, we show that every open Riemann surface carries a proper conformal minimal embedding into \({\mathbb {R}}^5\) (see Theorem 1.2). One of our main tools is a Mergelyan approximation theorem for conformal minimal immersions to \({\mathbb {R}}^n\) for any \(n\ge 3\) which is also proved in the paper (see Theorem 5.3).     

On the manipulability of competitive equilibrium rules in many-to-many buyer–seller markets

We analyze the manipulability of competitive equilibrium allocation rules for the simplest many-to-many extension of Shapley and Shubik’s (Int J Game Theory 1:111–130, 1972) assignment game. First, we show that if an agent has a quota of one, then she does not have an incentive to manipulate any competitive equilibrium rule that gives her her most preferred competitive equilibrium payoff when she reports truthfully. In particular, this result extends to the one-to-many (respectively, many-to-one) models the Non-Manipulability Theorem of the buyers (respectively, sellers), proven by Demange (Strategyproofness in the assignment market game. École Polytechnique, Laboratoire d’Économetrie, Paris, 1982), Leonard (J Polit Econ 91:461–479, 1983), and Demange and Gale (Econometrica 55:873–888, 1985) for the assignment game. Second, we prove a “General Manipulability Theorem” that implies and generalizes two “folk theorems” for the assignment game, the Manipulability Theorem and the General Impossibility Theorem, never proven before. For the one-to-one case, this result provides a sort of converse of the Non-Manipulability Theorem.     

Computability-theoretic and proof-theoretic aspects of partial and linear orderings

Szpilrajn’s Theorem states that any partial orderP=〈S,<p〉 has a linear extensionP=〈S,<L〉. This is a central result in the theory of partial orderings, allowing one to define, for instance, the dimension of a partial ordering. It is now natural to ask questions like “Does a well-partial ordering always have a well-ordered linear extension?” Variations of Szpilrajn’s Theorem state, for various (but not for all) linear order typesτ, that ifP does not contain a subchain of order typeτ, then we can chooseL so thatL also does not contain a subchain of order typeτ. In particular, a well-partial ordering always has a well-ordered extension.We show that several effective versions of variations of Szpilrajn’s Theorem fail, and use this to narrow down their proof-theoretic strength in the spirit of reverse mathematics.     

Spaces of lower semicontinuous set-valued maps I

We introduce a lower semicontinuous analog, L ^?(X), of the well-studied space of upper semicontinuous set-valued maps with nonempty compact interval images. Because the elements of L ^?(X) contain continuous selections, the space C(X) of real-valued continuous functions on X can be used to establish properties of L ^?(X), such as the two interrelated main theorems. The first of these theorems, the Extension Theorem, is proved in this Part I. The Extension Theorem says that for binormal spaces X and Y, every bimonotone homeomorphism between C(X) and C(Y) can be extended to an ordered homeomorphism between L ^?(X) and L ^?(Y). The second main theorem, the Factorization Theorem, is proved in Part II. The Factorization Theorem says that for binormal spaces X and Y, every ordered homeomorphism between L ^?(X) and L ^?(Y) can be characterized by a unique factorization.