History of infinity in set theory
Saeed Seyed Agha Banihashemi, Dept. of Math and IT School of International Relation, Ambassador of I.R.Iran in Hungary ,Stefania ut 97 1143 Budapest
Coauthors: no
In this article I am to talk about the history of infinity. As we know history of mathematical symbol can help us in teaching, applications and research to do our job better. After talking about how infinity invented, I will talk about on infinite set theory.
Universal minimal flows for groups of automorphisms of homogeneous relational structures
Dana Bartosova, Charles University in Prague, University of Toronto
Universal minimal flows are objects of topological dynamics of major interest. We use ultrafilter flows and Ramsey theorems for classes of finite structures to give a simple computation of universal minimal flows of dense subgroups of groups of automorphisms of homogeneous relational structures, it means closed subgroups of permutation groups. In particular, we show that the universal minimal flows for the group of homeomorphisms of w^{*} and the group of trivial homeomorphisms of w^{*} are the same in the realm of ZFC. This work unifies and generalizes proofs of Glasner and Weiss, Glasner and Gutman and Pestov and generalizes results of Kechris, Pestov and Todorcevic on countable structures and Balcar and Franek on discrete groups.
On Hajnal's Triangle Free Game
Csaba Biro, University of Louisville
Coauthors: Paul Horn, D. Jacob Wildstrom
Hajnal's triangle free game starts on the empty graph on n vertices. Two players take turns in adding edges to the graph while keeping the graph triangle free. In Hajnal's original game, the player who could not make a valid move lost the game. Füredi, Reimer, and Seress proposed a variation, in which the goal of one of the players is to prolong the game, and the goal of the other player is to finish the game as soon as possible. They proved that the game will last at least on the order of nlogn steps. On the other hand, an unpublished result by Erdös states that the game will last at most n^{2}/5 steps. In this paper we make a slight improvement on Erdös's upper bound and we discuss related problems.
Measures on Bell space
Piotr BorodulinNadzieja, Instytut Matematyczny, Wrocław University, Poland
Coauthors: Mirna D?amonja
We show that there is a compact space which is separable, which does not have a countable pibase and which carries only separable measures. This is a modification of an example due to Murray Bell [1]. Some consequences of the existence of such a space will be presented.
[1] M. Bell, G_{k} subspaces of hyadic spaces, PAMS 104/2 (1988)
Cardinal functions F_{q}(X) and t_{q}(X) for Hclosed spaces
Andrei Catalioto, University of Messina (Italy)
Coauthors: Filippo Cammaroto (University of Messina) 
Jack Porter (University of Kansas)
In this article, starting with results and answering questions by Cammaroto and Kocinac in 1993, we prove that t_{q}(X) = t_{q}(X_{s}) = t(X_{s}) = F_{q}(X) = F_{q}(X_{s}) = F(X_{s}) for every Hclosed and Urysohn space and we present some useful examples to study the full relations between cardinal functions t, t_{q}, F and F_{q} in the context of Hclosed and Urysohn spaces.
Also, we construct an Hclosed space H for which F_{q}(H) < t_{q}(H).
References:
[1] A.V. Arhangel'skii, On bicompacta hereditarily satisfying Suslin's condition. Tightness and free sequences,
Soviet Math. Dokl., 12 (1971), 12531257.
[2] F. Cammaroto, A. Catalioto and J. Porter, Cardinal functions F_{q}(X) and t_{q}(X) for Hclosed spaces (2011), preprint.
[3] F. Cammaroto and Lj.D. Kocinac, On qtightness, Facta Universitatis (Nis), Ser. Math. Inform.
8 (1993), 7785.
[4] F. Cammaroto and Lj.D. Kocinac, A note on qtightness, Rend. Circ. Mat. Palermo, Ser II 42 (1993), 129134.
[5] I. Juhász, Cardinal Functions in Topology  Ten Years Later, Math. Centre Tracts 123, Amsterdam, 1980.
[6] J.R. Porter and R.G. Woods, Extensions and absolutes of Hausdorff spaces, SpringerVerlag, 1988.
Note: q = theta (greek letter).
On hypergraph cliques with chromatic number 3
D.D. Cherkashin, SaintPetersburg State University
Coauthors: A.M. Raigorodskii
In this work, we deal with an extremal combinatorial problem going back to P. Erdös and L. Lovász.
Let H = (V, E) be an n uniform hypergraph. We say that H is a clique, if its edges are pairwise intersecting. In 1973
Erdös and Lovász noticed that the chromatic number c(H) of any clique H equals either 2 or 3. They also
observed that in the case of c(H) = 3 , one certainly has E ≤ n^{n} . Thus, the following definition has been
motivated:

Theorem 1 (P. Erdös, L. Lovász). The inequalities hold
n!
ć
č
1
+
1
+ ...+
1
ö
ř
\leqslantM(n) ≤ n^{n}.
Almost nothing better has been done during the last 35 years.
At the same time, another quantity r(n) was introduced by Lovász:


We discovered a new upper bound for the initial value M(n) .
Theorem 2. There exists a constant c > 0 such that
M(n) ≤ c n^{n[1/2]} lnn.
In our talk, we shall present this result and some other similar assertions.
^{1}This work was supported by the grants of RFBR N 090100294 and of the President of the Russian Federation N MD8390.2010.1, NSH8784.2010.1.
^{2}SaintPetersburg State University, Mathematics and Mechanics Faculty.
^{3}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes; Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis; Yandex research laboratories.
Canonization Theorems on Ramsey spaces and their application to the Tukey theory of ultrafilters
Natasha Dobrinen, University of Denver
Coauthors: Stevo Todorcevic,
CNRS University of Paris 7
We present canonization theorems for countable colorings on fronts on new topological Ramsey spaces. These Ramsey spaces generalize the Ellentuck space and are built to correspond to some forcings of Laflamme which add weakly Ramsey ultrafilters and weaker variations. The canonization theorems start with the ErdosRado canonization theorem and build to obtain canonization theorems which are the analogs of the ErdosRado theorem and the PudlakRodl theorem for these Ramsey spaces. These canonization theorems are then applied to characterize the Tukey types of ultrafilters below the Laflamme ultrafilters in terms of the RudinKeisler ordering.
Some cardinal invariants related to analytic quotients
Jana Flaskova, University of West Bohemia in Pilsen
We investigate cardinal invariants of the quotient algebra P(N)/W where W is the van der Waerden ideal  an ideal on the set of the natural numbers N which consists of the sets which do not contain arbitrarily long arithmetic progressions. We prove, in particular, that the pseudointersection number of P(N)/W is the same as the standard pseudointersection number defined for P(N)/fin, and almost disjointness number of P(N)/W is less or equal to the standard cardinal characteristics of the continuum with the same name.
Combinatorics and Large Cardinals
SyDavid Friedman, Kurt Goedel Research Center, University of Vienna
Andras Hajnal is renowned for his fundamental contributions to infinitary combinatorics, a field which lies at the heart of set theory. In this talk I will discuss some aspects of this field in the context of large cardinals. In the nonGCH setting I'll consider the behaviour of the generalised continuum function as well as cardinal characteristics associated to graph complexity, dominating families, the cofinality of the symmetric group and the tree property. In the GCH setting I'll discuss Jensen's Diamond, Square and Morass principles as well as forms of Gödel condensation. Additional topics concern the number of normal measures on a measurable cardinal and the impact of definability on combinatorial properties.
Classifying Ergodic Measure Preserving Transformations
Matthew Foreman, University of California, Irvine
In 1931 von Neumann proposed the project of classifying ergodic measure preserving transformations. This talk will describe how the tools of descriptive set theory can be used to show that such a classification is impossible, even for diffeomorphisms of the torus. The word "impossible" will be rigorously defined. The method of proof uses finite combinatorial arguments (randomization techniques) to build approximations of diffeomorphisms, thus illustrating another connection between the finitary techniques and set theory.
Quasiselective and weakly Ramsey ultrafilters
Marco Forti, Dipart. Matematica Applicata "U. Dini", Universita` di Pisa
Recall that an ultrafilter U on N is
selective iff
every finite colouring of [N]^{2} has a homogeneous set U in
U
iff every function is nondecreasing on some U in U.
Natural weakenings of these properties led to the (inequivalent) notions of weakly
Ramsey and of quasiselective ultrafilter:
 U is weakly Ramsey (shortly WR)
if for
every finite colouring of [N]^{2} there is U in U s.t.
[U]^{2}
has only two colours (see [1]).
 U is fquasiselective (shortly fQS) if every g ≤ f is nondecreasing on some set U in U. U is quasiselective (shortly QS) if it is idQS (see [2]).
All WR and all fQS ultrafilters are Ppoints, so the following results are nontrivial only when such ultrafilters exist. However mild hypotheses, like CH or MA, suffice in making all these classes rich and distinct (see [1, 2]).
Theorem 1. Let U be a nonprincipal
ultrafilter.
1. If U is fQS, then
there exists U in U s.t.
x+f(x) < y for all x < y in U.
2. If g is increasing modulo U, then
U is (f○g)QS if and only if
gU is fQS.
3.
If U is fQS, then fU is QS, and U is
selective if and only if it is rapid.
Let U be nonselective, let I_{n}=[a_{n}, b_{n}] be any interval partition witnessing the nonselectivity of U, and for x ∈ I_{n} put a^{U}(x)=U∩[a_{n}, x), b^{U}(x)=U∩ [x, b_{n}], c^{U}(x)=U∩[a_{n}, b_{n}], e^{U}(x)=U∩[0, x], and S^{U}={f  f 11 on U}
Let A^{U}, B^{U}, C^{U}, E^{U}, and S^{U} be the cuts of the ultrapower N^{N}_{U} whose right parts are generated by {a^{U}  U ∈ U }, {b^{U}  U ∈ U }, {c^{U}  U ∈ U }, {e^{U}  U ∈ U}, and {S^{U}  U ∈ U } respectively.
Let F_{U} be the cut of the ultrapower N^{N}_{U} whose left part is generated by F_{U}={f  U fQS}. Then, independently of the chosen interval partition,
Theorem 2. Let U be a nonprincipal nonselective
ultrafilter.
1. If U is fQS,
then


In particular a WR ultrafilter U is QS if and only if the identity is less than the cut C^{U}. More generally, we obtain a complete specification of the "quasiselectivity" properties of WR ultrafilters:
Corollary
Let U be a nonprincipal nonselective WR ultrafilter.
Then
(i) U is fQS for some f iff N ≠ C^{U}, or equivalently iff
U is not rapid;
(ii) U is fQS for some f
increasing modulo
U if and only if
A^{U} ≠ C^{U};
(iii) U is isomorphic to a QS ultrafilter
if and only if
A^{U} ≠ B^{U}.
[1] A. BLASS, Ultrafilter mappings and their Dedekind cuts, Trans. Amer. Math Soc., 188 (1974), 327340.
[2] A. BLASS, M. DI NASSO, M. FORTI, Quasiselective ultrafilters and asymptotic numerosities, submitted.
Some Properties of Multidimensional Intersection Matrices
Armenak Gasparyan, PSI RAS, PereslavlZalesskii
Given two finite sets X, Y and two families of their subsets F={U_{i}, U_{i} ⊆ X}, G={V_{j}, V_{j} ⊆ X}, the intersection matrix of F and G is a (m×n)matrix A=(a_{ij}), where m= F, n= G, and a_{ij}= U_{i}∩V_{j}, i=1, ... m, j=1, ... n. More generally, let p be a positive integer, p ≥ 2, and let X_{1}, ... , X_{p} are given finite sets. For each r, r ∈ {1, ... , p}, we choose arbitrarily an n_{r}element family F_{r}={U^{(r)}_{ir}, U^{(r)}_{ir} ⊆ X_{r}}, and for chosen families define a pdimensional n_{1}×...×n_{p}matrix A_{p}=∥a_{i1... ip}∥, i_{r}=1, ... , n_{r}, r=1, ... , p , that we call intersection matrix of F, F=(F_{1}, ... , F_{p}), in which a_{i1... \ip}=X_{i1}∩...∩X_{ip}.
The talk is devoted to the study of algebraic and combinatorial properties of matrices A_{s}, s=1, ... , p. Particularly, in case F_{1}=... = F_{p} or in more complex cases if F is dropped into groups of equal families, we are interested in positivity properties of higher order algebraic forms with A_{s}(F) as their coefficient matrices. We consider also some intersection matrices corresponding to another notions of intersection coming from different areas.
Clopen graphs and their finite induced subgraphs
Stefan Geschke, Hausdorff Center for Mathematics, Bonn
A graph G on a Polish space X is clopen if its edge relation is a subset of X^{2}\{(x, x):x ∈ X} that is both closed and open.
From the perspective of descriptive set theory, clopen graphs are the least complex definable graphs. Cardinal invariants such as clique number and chromatic number are degenerate for clopen graphs in the sense that they are either countable or equal to 2^{ℵ0}.
A cardinal invariant that is not degenerate is the cochromatic number, the least size of a family of cliques and independent sets that covers all vertices. Cochromatic numbers of clopen graphs on Polish spaces came up in the context of planar convexity. It turns out that the the cochromatic number of a clopen graph is largely determined by its finite induced subgraphs.
Definition 1. For a graph G let age(G) denote the class of all finite graphs isomorphic to induced subgraphs of G. If the set V(G) of vertices of G is a topological space, let the hereditary age hage(G) be the class of all finite graphs that have induced copies in all nonempty open subsets of V(G). G is selfsimilar if hage(G)=age(G).
Definition 2. Let G and F be graphs. A map f:V(G)→ V(F) is modular if for all v, w ∈ V(G) with f(v) ≠ f(w), {v, w} is an edge in G iff {f(v), f(w)} is an edge in F. A graph G whose set V(G) of vertices is a topological space is modular profinite if it is the limit of an inverse system of finite graphs with modular bonding maps.
Definition 3. For a class C of finite graphs let cl(C) denote the closure of C under isomorphism, induced subgraphs, and substitution. C is closed if C=cl(C). A class C is finitely generated if there is a finite set F of finite graphs such that C ⊆ cl(F).
The smallest nontrivial closed class of finite graphs is the class C_{min} of P_{4}free graphs, i.e., finite graphs that do not have an induced path on four vertices. This class is generated by the edge and the nonedge. The largest closed class is the class C_{max} of all finite graphs.
Theorem 4. a) For every clopen graph G on a Polish space, hage(G) is a closed class of finite graphs.
b) For every nontrivial closed class C of finite graphs there is a modular profinite graph G_{C} of countable weight such that C=hage(G_{C})=age(G_{C}).
c) G_{Cmax} is a universal modular profinite graph of countable weight.
Theorem 5. a) If G is a clopen graph on a Polish space, then the cochromatic number of G is no larger than the cochromatic number of G_{age(G)}. If G is a selfsimilar, then the two cochromatic numbers are the same.
b) If G is a clopen graph on a Polish space and age(G) is finitely generated, then the cochromatic number of G and G_{Cmin} are the same.
These results continue previous research of Goldstern, Kojman, and the author.
Pósa's Conjecture and Related Problems
H. A. Kierstead, Arizona State University
Coauthors: Phong Châu and Louis DeBiasio
Conjecture 1 Every graph G with d(G) ≥ [2/3]V(G) contains the square of a hamiltonian cycle.
Pósa's Conjecture remains open, but there has been significant progress. In 1996 G. Fan and the speaker proved a path version of the conjecture. In the same year, Komlós, Sárközy and Szemerédi proved that Pósa's Conjecture, and a more general conjecture of Seymour, hold for all graphs that have sufficiently many vertices. This was one of the first applications of the RegularityBlowup Method, and as such, only applies to extremely large graphs. Recently, Levitt, Sárközy and Szemerédi demonstrated a way to avoid the RegularityBlowup method. Using some of these ideas as well as older results, Châu, DeBiasio, and the speaker have shown that Pósa's Conjecture holds for all graphs with at least 200 million vertices.
This talk will survey progress on Pósa's Conjecture and related questions.
On the chromatic generalization of the ErdösSzekeres problem with various numbers of internal points
Vitaliy Koshelev, Moscow Institute of Physics and Technology
In 1935 P. Erdös and G. Szekeres proposed the following problem, which is now classical and one of the most famous in combinatorial geometry: determine, for any n ≥ 3 , the smallest number g(n) such that in every set of g(n) points in R^{2} in general position, one can find n vertices of a convex ngon.
Recall that a set of points in the plane is in general position, if any three of its elements do not lie in a straight line.
Many generalizations and related problems have been proposed and many researchers studied them. In particular, empty convex polygons were considered. Moreover, numbers of interior points were counted. Also, special point sets were investigated as well as colored sets, etc.
In this talk, we deal with the following important generalization: determine, for any n_{1} ≥ 3, n_{2} ≥ 3, k_{1} ≥ 0, k_{2} ≥ 0, the minimum number h(n_{1}, k_{1};n_{2}, k_{2}) (the minimum number h_{nc}(...)) such that in any twocolored set X of at least h(n_{1}, k_{1};n_{2}, k_{2}) (of at least h_{nc}(...)) points in general position in R^{2} , there exists either a subset of cardinality n_{1} whose elements form the set of vertices of a convex (of a nonconvex) polygon C_{1} of color 1 with the property (C_{1}\∂C_{1})∩X ≤ k_{1}, or a subset of cardinality n_{2} whose elements form the set of vertices of a convex (of a nonconvex) polygon C_{2} of color 2 with the property (C_{2}\∂C_{2})∩X ≤ k_{2}.
Note that this problem may be proposed for another number of colors. Our Theorems 1  3 relate to the onecolor case of the problem (so the number of arguments of the quantity h becomes equal to 2).
Theorem 1. If n ≥ 7 , then for even and odd values of n , respectively, the following quantities do not exist: h(n, C_{n7}^{(n7)/2}1), h(n, 2C_{n8}^{(n8)/2}1).
Theorem 2. If n ≥ 6, then h(n, (((n3))  (⌈(n3)/2⌉)) é[n/2] ù) > 2^{n2}+1.
Theorem 3. The exact equalities hold: h(6, ≥ 2)=17, h(6, 1)=18.
Note that Theorem 3 gives the exact values of some of our quantities, which is important. It has a computerbased proof.
The convex version of the problem under consideration was proposed in 2003 by Devillers, Hurtado, Károlyi, and Seara. They proved that h(3, 0;3, 0)=9 and that the quantities h(5, 0;3, 0) and h(3, 0;3, 0;3, 0) (here we have threecolored sets) do not exist. Therefore, the values h( ≥ 5, 0; ≥ 3, 0) and h( ≥ 3, 0; ≥ 3, 0; ≥ 3, 0) do not exist too. The question about the existence and the exact value of h(4, 0;4, 0) is open.
It was known that h(4, 0;4, 0) ≥ 36. We present a new lower bound (and the corresponding point set) for this value: h(4, 0;4, 0) ≥ 46. It is easy to see that h(3, 0;4, 0) ≤ h(6, 0) and, consequently, this value exists. A lower bound for it is h(3, 0;4, 0) ≥ 22.
Aichholzer, Hackl, Huemer, Hurtado, and Vogtenhuber studied the nonconvex version of the problem. They proved an upper bound for h_{nc}(4, 0;4, 0): h_{nc}(4, 0;4, 0) ≤ 2520.
It was known that h_{nc}(4, 0;4, 0) ≥ 18. We present a new lower bound h_{nc}(4, 0;4, 0) ≥ 20.
Moreover, we find many exact values for h(n_{1}, k_{1};n_{2}, k_{2}) with n_{1}, n_{2} ≤ 4 and various k_{1}, k_{2}. For example, h_{nc}(4, 1;4, 1)=11, h_{nc}(4, 0;4, 1)=15, h_{nc}(4, 0;3, 0)=14, and h(4, 0;3, 1)=h(4, 1;3, 0)=14.
Footnotes:
^{1}This work was supported by the grants of RFBR N 090100294 and of the President of the Russian Federation N MD8390.2010.1.
^{2}Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis.
The HajnalSzemer\' edi Theorem: Extensions and variations
Alexandr Kostochka, University of Illinois, Urbana, USA and Sobolev Institute of Mathematics, Novosibirsk, Russia
Coauthors: Hal Kierstead
An equitable coloring of a graph G is a proper coloring of vertices of G such that the sizes of color classes differ by at most 1. In 1970, Hajnal and Szemer\' edi proved that every graph with maximum degree at most r has an equitable coloring with r+1 colors. This theorem confirmed a conjecture by Erdös and extended a previous result by Corradi and Hajnal. The theorem has numerous applications in combinatorics and other areas of mathematics.
In recent years, there were new results relating to the HajnalSzemer\' edi Theorem in the following directions: the Oretype version of the theorem, the ChenLihWu Conjecture on equitable colorings of a graph G with D(G) colors, algorithmic versions of the theorem, the list version of the theorem. The aim of the talk is to review the new results on these topics obtained using the approach developed by H. Kierstead and the speaker. This is joint work with H. Kierstead.
The chromatic number of a normed space
Andrey B. Kupavskii, Moscow State University, Mechanics and Mathematics Faculty, Department of Number Theory
This work is dealt with the classical problem of finding the value c(R^{n}) which is equal to the minimum number of colors needed to paint all the points in R^{n} so that any two points at distance 1 apart receive different colors. The value c(R^{n}) is called the chromatic number of the Euclidean space. The quantity 1 is called, in turn, the forbidden distance.
A variant of the problem has been proposed for spaces R^{n}_{K} with norms induced by arbitrary centrally symmetric convex bodies K (here the forbidden distance equals 1, too). In 2008 Z. Füredi and J.H. Kang obtained the estimate c(R^{n}_{K}) ≤ c n(lnn) 5^{n} with some constant c, which does not depend on K. In our paper, we improve this result.
Theorem 1. Let R^{n}_{K} be a normed space. Then
where d = ln4 + 1.
c(R^{n}_{K}) ≤
(lnn + lnlnn+d+o(1))
·4^{n},
We can improve this theorem even further in the case of any l_{p}space R^{n}_{p}.
Theorem 2. Let R^{n}_{p} be an l_{p}space. Then c(R^{n}_{p}) ≤ 2^{(1+cp +dn)n}, where d_{n}→ 0 as n→∞, and c_{p} < 1 for p > 2 and c_{p}→ 0 as p→∞.
To prove these theorems, we use some covering and packing techniques, which is similar to the one developed by P. Erdös and C.A. Rogers. In addition, we prove a theorem concerning the chromatic numbers of spaces with segments of forbidden distances. We define c(R^{n}_{K}, A') as the minimum number of colors which are needed to paint all the points in R^{n} so that any two points at distance x, x ∈ A', apart receive different colors. Let A' = [1, l]. Then the following theorem holds true.
Theorem 3. Let R^{n}_{K} be a normed space.
The work is done under the financial support of the grant 090100294 of the Russian Foundation for Basic Research and the grant MD8390.2010.1 of the Russian President.
^{1}This work was supported by the grants of RFBR N 090100294 and of the President of the Russian Federation N MD8390.2010.1.
^{2}Moscow State University, Mechanics and Mathematics Faculty, Department of Number Theory.
Partitions and trees
Jean A Larson, University of Florida
This talk will sketch how to combine the good sequences of Galvin, the tree representations by Schipperus of countable ordinals, and the method of walks by Todorcevic into a representation of countable ordinals useful for proving partition relations, and survey some open problems on partitions.
DeltaOpen Sets and Mappings in Topological Spaces
Raja Mohammad Latif, Department of Mathematics and Statistics, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia
Coauthors: Saeid Jafari,
College of Vestsjaelland South
Herrestraede 11, 4200 Slagelse, Denmark
In 1968 Velicko introduced the concepts of δclosure and δinterior operations. We introduce and study properties of δderived, δborder, δfrontier and δexterior of a set using the concept of δopen sets and study also other properties of the wellknown notions of δclosure and δinterior. We also introduce some new classes of topological spaces in terms of the concept of δDsets and investigate some of their fundamental properties. Moreover, we investigate and study some further properties of the wellknown notions of δclosure and δinterior of a set in a topological space. We also introduce δR₀ space and study its characteristics. We also introduce δcontinuous, δopen, δirresolute, δclosed, preδcontinuous, preδopen, preδclosed and preδirresolute mappings and investigate properties and characterizations of these new types of mappings.
References
1.M. Caldas, D.N. Georgian, S. Jafari and T. Noiri, More on δsemiopen sets, Note di Mathematica, 22(2) (2003/2004), 113126.
2.J. Cao, M. Ganster, I. Reilly and M. Steiner, δclosure, θclosure, and generalized closed sets, Applied General Topology, 6(1) (2005), 7986.
3.E. Ekici, (δpre, s)continuous functions, Bulletin of the Malaysian Mathematical Sciences Society, Second Series 27(2004), no. 2, 237251.
4.E. Ekici, On δsemiopen sets and a generalization of functions, Bol. Soc. Mat. (38) vol. 23 (12) (2005), 7384.
5.A. Kilicman, Z. Salleh, Some results on (δpre, s)continuous functions, International Journal Math. Mat. Sci. 2006(2006), 111.
6.T. Noiri, On δcontinuous functions, J. Korean Math. Soc., 16 (1980), 161166.
7.J.H. Park, B. Y. Lee and M.J. Son, On δsemiopen sets in topological space, J. Indian Acad. Math., 19(1), (1997), 5967.
8.S. Raychaudhuri and M.N. Mukherjee, On δalmost continuity and δpreopen sets, Bulletin of the Institute of Mathematics, Academia Sinica 21 (1993), no. 4, 357366.
9.M. Saleh, Some applications of δsets to Hclosed spaces, Q & A Topology 17(1999), 203211.
10.M. Saleh, On super and δcontinuities, Mathematics and Mathematics Education, World Scientific, 2002, 281291.
11.N.V. Velicko, Hclosed topological spaces, Mat. Sb., 98112; English transl. (2), in Amer. Math. Soc. Transl., 78(1968), 102118.
We prove the following
Set and Collection Lemma (2011) If Y is a collection of maximum
independent sets of G, then there is a matching

Based on this finding we give alternative proofs for a number of wellknown lemmata including :
Clique Collection Lemma (András Hajnal, 1965) If G is a
collection of maximum cliques in G, then

Maximum Stable Set Lemma (Claude Berge, 1985) An independent set X is maximum if and only if every independent set S disjoint from X can be matched into X.
A generalization of Roitman's theorem for cardinal sequences
Juan Carlos Martínez, Facultat de Matemŕtiques, Universitat de Barcelona
Coauthors: Lajos Soukup
By an LCS space, we mean a locally compact, Hausdorff, scattered space. If X is an LCS space and a is an ordinal, we denote by I_{a}(X) the a^{th}CantorBendixson level of X, i.e. I_{a}(X) = set of isolated points of X\∪{I_{b}(X): b < a}. The reduced height of X is defined as ht^{}(X) = the least ordinal a such that I_{a}(X) is finite. Then, the cardinal sequence of X is defined as the sequence formed by the cardinals I_{a}(X) for a < ht^{}(X).
Many authors have studied the possible cardinal sequences that can arise as the cardinal sequence of an LCS (equivalently, a superatomic Boolean algebra). By a classical result shown by Roitman in [3], it is consistent with ZFC that there is an LCS X such that ht^{}(X) = w_{1} + 1, I_{a}(X) = w for every a < w_{1} and I_{w1}(X) = w_{2}.
Then, we shall present the following generalization of Roitman's theorem proved in [2].
Theorem. Suppose that k, l are infinite cardinals such that k^{++} < l, k^{ < k}=k and 2^{k} = k^{+}. Then for each ordinal h with k^{+} ≤ h < k^{++} and cf(h) = k^{+}, in some cardinalpreserving generic extension there is an LCS space X such that ht^{}(X) = h+ 1, I_{a}(X) = k for every a < h and I_{h}(X) = l.
Several combinatorial notions are needed to prove the above theorem, in particular the notion of a strongly unbounded function introduced by Koszmider in [1].
[2] J.C Martínez and L. Soukup, Superatomic Boolean algebras constructed from strongly unbounded functions, preprint.
[3] J. Roitman, A very thin thick superatomic Boolean algebra, Algebra Universalis 21 (1985), 137142.
Step Up, Here Come Erdös and Hajnal!
János Pach, Rényi Institute and EPFL
It is hard to find any important problem in Ramsey theory to which
Erdös and Hajnal did not make a substantial contribution. In this
talk, we show how their classic "steppingup" approach can be
applied to the following question. For any sequence of positive
integers j_{1} < j_{2} < ... < j_{n}, the ktuples (j_{i}, j_{i +1}, ..., j_{i + k1}), i=1, 2, ..., n  k+1, are said to form a
monotone path of length n. Given any integers n ≥ k ≥ 2
and q ≥ 2, what is the smallest number N with the property that
no matter how we color all kelement subsets of [N]={1, 2, ..., N} with q colors, we can always find a monochromatic monotone
path of length n? Denoting this minimum by N_{k}(q, n), it follows
from the 1935 "Happy Ending" paper of Erdös and Szekeres that
N_{2}(q, n)=(n1)^{q}+1 and N_{3}(2, n) = ((2n 4)  (n2)) + 1. We
apply the ideas of Erdös and Hajnal to show that

Forcing related convergences of sequences on complete Boolean algebras
Aleksandar Pavlović, Department of Mathematics and Informatics, University of Novi Sad, Serbia
Coauthors: Miloš S. Kurilić
(Department of Mathematics and Informatics, University of Novi Sad, Serbia)
Let convergences l_{i} : B^{w} →P(B), 0 ≤ i ≤ 4, on a complete Boolean algebra B be defined in the following way. For a sequence x=〈x_{n} : n ∈ w〉 in B and the corresponding Bname for a subset of w, let l_{i}(x)={ ∥ t_{x} is infinite∥} if b_{i}(x)=1_{B}, and empty set otherwise, where b_{0} (x)=∥ t_{x} is finite or cofinite∥, b_{1} (x)=∥ t_{x} is old∥, b_{2} (x)=∥ t_{x} is not unsupported∥, b_{3} (x)=∥ t_{x} is not a splitting real∥ and b_{4} (x)=1_{B}.
Then l_{0} is a generalization of the convergence on the Cantor cube, also known as algebraic convergence and it generates the sequential topology on B. On the other hand, l_{4} is a generalization of the convergence on the Aleksandrov cube.
Although all convergences are different on each Boolean algebra producing splitting reals, each convergence l_{i}, 1 ≤ i ≤ 4 generate the same topology. If B is a Maharam algebra, then this topology together with its dual produces the sequential topology, generated by the convergence l_{0}.
Hypertournamentsscores and losing scores
Shariefuddin Pirzada, King Fahd University of Petroleum and Minerals
We discuss various necesssary and sufficient conditions for the lists of nonnegative integers in nondecreasing order to be the losing score lists and score lists of some hypertournament. We also discuss such analogous results for bipartite and multipartite hypertournaments.
Thin coideals
Igor Protasov, Kyiv University
A family H of infinite subsets of w = {0, 1, ...} is coideal if
In spirit of [1], H is
Given a group G of permutations of w, a subset M ⊂ w is called Gthin if, for every g ∈ G, the set

Every Pcoideal and every Qcoideal is thin. In particular, each Ppoint and each Qpoint in w^{*} is a Tpoint. Under CH, there is a Tpoint which is neither P, nor Qpoint. But I do not know if a Tpoint can be constructed without additional to ZFC assumptions.
A motivation to study thin coideals is coming from asymptology [2] where thin subsets play the part of convergent sequences.
[2] I.Protasov, M.Zarichnyi. General Asymptology, Math. Stud. Monogr. Ser., vol. 12, VNTL Publisher, Lviv, 2007.
On dividing sets into parts of smaller diameters
Andrei M. Raigorodskii, Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes; Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis; Yandex research la
Coauthors: Vera V. Bulankina, Vladislav P. Filimonov, Andrey B. Kupavskiy
In 1933 K. Borsuk proposed the following problem: Find the minimum number f(m) of parts of smaller diameter, into which an arbitrary bounded nonsingleton set in R^{m} can be partitioned. Borsuk conjectured that f(m) = m+1 . Although this conjecture had been widely believed, it was disproved in 1993 by J. Kahn and G. Kalai.
Many important variants of Borsuk's problem are now considered. One of them is due to H. Lenz. In 1956 he introduced a function
d_{n} = d_{n}(F) , which is defined for any bounded nonsingleton set F ⊂ R^{m} as follows:

Lenz asked for the values of d_{n}^{m} = sup_{F ⊂ Rm} d_{n}(F) , where the supremum is taken over all sets F of diameter 1.
Now, the most studied case is that of m = 2 . For example, it is known that

The case of m = 3 was also considered by different authors. In particular, the quantity d_{n}(S^{2}) was thoroughly investigated by H. Hadwiger and A. Heppes, where S^{2} is the twodimensional sphere in R^{3} . On the other hand, in 1982 Lassak showed that d_{5}^{3} \leqslant √{[(35 + √{73})/48]} = 0.9524... In our talk, we shall present an improvement to this estimate.
Finally, we shall discuss an analog of the function d_{n} . Indeed, let

Footnotes:
^{1}This work was supported by the grants of RFBR N 090100294 and of the President of the Russian Federation N MD8390.2010.1, NSH8784.2010.1.
^{2}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes.
^{3}Moscow State University, Mechanics and Mathematics Faculty, Department of Optimal Control.
^{4}Moscow State University, Mechanics and Mathematics Faculty, Department of Number Theory.
^{5}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes; Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis; Yandex research laboratories.
On Schur's Theorem on Arithmetic Progressions
Anastasia Rozovskaya, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Coauthors: Dmitry A. Shabanov, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Department of Probability Theory, email: shabanov@mech.math.msu.su
Anastasia Rozovskaya^{1}^{, }^{2}, Dmitry A. Shabanov^{3}^{, }^{4},
The talk deals with a Ramseytype problem in additive combinatorics. In 1927 I. Schur proved (see []) the following theorem.
Theorem 1 (I. Schur) For every r ≥ 2 and n ≥ 3 there exists the minimum number S(n, r) such that any rcoloring of the initial set of positive integers [S(n, r)]={1, 2, , ..., S(n, r)} contains a monochromatic arithmetic progression of length n together with its difference.
This theorem historically was one of the first generalizations of the famous theorem of Van der Waerden. Recall that the van der Waerden number W(n, r) (n ≥ 3, r ≥ 2) is the smallest integer N such that in any rcoloring of the set {1, 2, ..., N} there exists a monochromatic arithmetic progression of length n. Van der Waerden's theorem states that W(n, r) is finite for all n ≥ 3, r ≥ 2.
For large n and all r, it is known that
 (1) 
Our main result gives a new lower bound for the value S(n, r) from Schur's theorem.
Theorem 2 For all n ≥ 3, r ≥ 3, the following inequality holds
where c is an absolute constant.
S(n, r) ≥ c
r^{n}
, (2)
Since S(n, r) ≥ W(n, r), from (1) we have the inequality S(n, r) ≥ r^{n1}n^{o(1)}. So, our new result (2) improves (1) in the case r ≥ √n.
The proof of Theorem 2 is based on the random recoloring method in hypergraph coloring theory.
^{1}Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, email: anarozovski@gmail.com
^{2}This work was supported by Russian Foundation of Fundamental Research (grant 470; 090100294, grant 470; 110100759 072;) and by the grant of the President of Russian Federation MK3429.2010.1
^{3}Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Department of Probability Theory, email: shabanov@mech.math.msu.su
^{4}This work was supported by Russian Foundation of Fundamental Research (grant 470; 090100294), Program of Support of Leading Scientific Schools (grant 470; NSH8784.2010.1) and by the grant of the President of Russian Federation MK3429.2010.1
On Certain Finite Graphs Without Large Complete and Empty Subgraphs which are Universal
Gábor Sági, Rényi Institute, Budapest
In [] Erdös and Hajnal asked the following question: is it true, that for any finite graph
G there exists a constant c=c(G) such that if H is any finite graph on n vertices that does not
contain complete or empty subgraphs of size n^{c} then G is isomorphic to an (induced) subgraph of H? For certain classes of graphs, the answer is known to be true, for
recent related results, see e.g. []. However, the
original question in its full generality is still open.
We will describe further classes of finite graphs for
which the question can be answered affirmatively. Our method is
based on the study of natural measures defined on ultraproducts
of finite graphs. Particularly, we will show, that (assuming some
further technical conditions) if G is a finite graph and
H is an ultraproduct of certain special finite graphs
equipped with the natural ultraproduct measure such that each
complete or empty subgraph of H has measure 0, then
G can be embedded into H (as an induced
subgraph).
NonPpoints and forcing
Shelah Saharon, The Hebrew University, Rutgers University
We define a property of a (nonprincipal) ultrafilter on N , i.e. a point of b( N ) very far from Ppoints. We first under reasonable conditions, prove its existence and its being an ultrafilter being preserved, i.e. continue to generate an ultrafilter, under some forcing and suitable CS iterations. We then prove that consistently such a point generated by ℵ_{1} sets exist while no Ppoint exists, answering a question of Nyikos.
Universal ultrahomogeneous metric spaces
Norbert SAUER, University of Calgary
Universal ultrahomogeneous metric spaces
A metric space M is ultrahomogeneous if for every isometry f of a finite subspace of M to a finite subspace of M there exists an isometry f* of M onto M, (that is, an element of the isometry group of M), which extends f. Let spec(M), the spectrum of M, denote the set of distances between points in M. The metric space M is universal if it is ultrahomogeneous and isometrically embeds every finite metric space F with spec(F) a subset of spec(M).
Results and problems relating to the following questions will be discussed:
J. LopezAbad and L. Nguyen Van Thé, The oscillation stability problem for the Urysohn sphere: A combinatorial approach, Topology Appl. 155 Issue 14 (2008) 15161530.
L. Nguyen Van Thé, N. Sauer, The Urysohn Sphere is oscillation stable, Goemetric and Functional Analysis 19 Issue 2 (2009) 536557.
N. Sauer, Vertex partitions of metric spaces with finite distance sets, Discrete Mathematics submitted.
N. Sauer, Approximating universal metric spaces, manuscript.
The diameter of symmetric groups
Ákos Seress, The Ohio State University and The University of Western Australia
For a finite group G, the diameter of G is defined as the maximum of the diameters of all Cayley graphs of G. A 25 yearold conjecture states that the diameter of the full symmetric group S_{n} is polynomial in n.
We shall review the attempts to prove this conjecture. Although the formulation of the problem is algebraic, the methods are mostly combinatorial.
On the Erdös  Hajnal problem in the case of three colors
Dmitry A. Shabanov, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Department of Probability Theory
In 1961 P. Erdös and A. Hajnal (see []) stated the following combinatorial problem: find the value m(n, r) equal to the minimum possible number of edges in an nuniform hypergraph which is not rcolorable.
First nontrivial bounds for m(n, 2) were obtained by P. Erdös (see [], []), who used a simple probabilistic method. Similar inequalities hold for any possible number r of colors:
 (1) 

The value of m(n, r) has also been studied by several researchers. In 2004 A. V. Kostochka found (see []) a strong asymptotic lower bound for m(n, r) in the case when r is very small in comparison with n. He showed that if r < √{1/8ln(lnn/2)}, then
 (2) 
Our main result gives a new lower bound for the value m(n, r).
Theorem 1
For all n ≥ 3, r ≥ 3, the following inequality holds
m(n, r) ≥
1
n^{1/2} r^{n1}. (3)
It is easy to see that our result (3) improves first bound (1) for all r ≥ 3, n ≥ 4. It also provides the best lower bound for m(n, 3). In comparison with previous result (2) we have an improvement by a factor √{lnn}. The proof of Theorem * is based on the method of random recoloring.
^{1}Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Department of Probability Theory, email: shabanov@mech.math.msu.su
^{2}This work was supported by Russian Foundation of Fundamental Research (grant š 090100294), Program of Support of Leading Scientific Schools (grant š NSH8784.2010.1) and by the grant of the President of Russian Federation MK3429.2010.1
A game on Boolean algebras
Boris Sobot, Department of Mathematics and Informatics, University of Novi Sad, Serbia
Coauthors: Milo? Kurilić, Department of Mathematics and Informatics, University of Novi Sad, Serbia
The game G_{ls } (k) is played on a complete Boolean algebra B, by two players, White and Black, in kmany moves (where k is an infinite cardinal). At the beginning White chooses a nonzero element p ∈ B. In the ath move White chooses p_{a} ∈ (0, p)_{B} and Black responds choosing i_{a} ∈ {0, 1}. White wins the play iff ∧_{b ∈ k}∨_{a ≥ b}p_{a}^{ia}=0, where p_{a}^{0}=p_{a} and p_{a}^{1}=p\p_{a}.
The corresponding game theoretic properties of c.B.a.'s are investigated. So, Black has a winning strategy (w.s.) if k ≥ p(B) or if B contains a k^{+}closed dense subset. On the other hand, if White has a w.s., then k ∈ [h_{2}(B), p(B)). The existence of w.s. is characterized in a combinatorial way and in terms of forcing. In particular, if 2^{ < k}=k ∈ Reg and forcing by B preserves the regularity of k, then White has a w.s. iff the power 2^{k} is collapsed to k in some extension. It is shown that, under the GCH, for each set S ⊆ Reg there is a c.B.a. B such that White (respectively, Black) has a w.s. for each infinite cardinal k ∈ S (resp. k ∉ S). Also it is shown consistent that for each k ∈ Reg there is a c.B.a. on which the game G_{ls } (k) is undetermined.
Rainbow Colourings
Lajos Soukup, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences
Given a function f:[X]^{n}→ X we say that a subset Y ⊂ X is a rainbow subset for f provided that f\restriction[Y]^{n} is injective. A typical question was a problem of Erdös: Assume that a colouring f:[w_{1}]^{2}→ 3 establishes the partition relation w_{1}\not→[w_{1}]^{2}_{3}. Is there a rainbow triangle for f?
We survey some old results and presents some theorems.
Long Arithmetic Progressions in Sumsets
Endre Szemerédi, Alféd Rényi Institute of Mathematics
Let A ⊂ [1, n] be a set of integers. Let S(A) = {a_{i1}+a_{i2}+...+a_{ik}; a_{ij} ∈ A } be the set of sums of subsets of A. It has been proved that there exists a large c such that if A > c √n then S(A) contains an arithmetic progression of length n. We are going to prove that if A > 4 √n then S(A) contains an arithmetic progression of length n. We are going to try to describe some ideas how 4 might be reduced to 2 which would be the optimal value.
On densest sets avoiding unit distance in spaces of small dimension
Mariya V. Titova, Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes
Coauthors: Andrei B. Kupavskii, Andrei M. Raigorodskii
We derive new lower bounds on the classical value m_{1}(R^{n}), n=3, ..., 6. Let us remind that the upper density of a measurable set A ⊆ R^{n} is

Let us consider a measurable set that avoids unit distance. The extreme density which such set can have is

The notion m_{1}(R^{n}) has been studied because of its relation to the measurable chromatic number of the Euclidean space c^{m} (R^{n}). This is the minimum number of colors needed to paint all the points in R^{n} in such a way that any two points at unit distance apart receive different colors and so that points receiving the same color form Lebesgue measurable sets.
Since the inequality c^{m} (R^{n}) ≥ 1/m_{1}(R^{n}) certainly holds, upper bounds on m_{1}(R^{n}) are lower bounds on the measurable chromatic number c^{m} (R^{n}). The best known upper bounds on m_{1}(R^{n}), n=2, ..., 24, were obtained by F. M. de Oliveira Filho, F. Vallentin (2008). The best lower bound on m_{1}(R^{2}) is due to H. T. Croft and is 0.2293. We obtain new lower bounds on m_{1}(R^{n}), n=3, ..., 6:
Theorem 1 The following inequalities hold:
m_{1}(R^{3}) ≥ 0.09877, m_{1}(R^{5}) ≥ 0.01833,
m_{1}(R^{4}) ≥ 0.04413, m_{1}(R^{6}) ≥ 0.00806.
I our talk, we shall present a history of the problem. Then, we shall briefly exhibit our method for proving Theorem 1. Finally, we shall discuss some related questions of geometric Ramsey theory which can be partially solved with the help of Theorem 1.
Footnotes:
^{1}This work was supported by the grants of RFBR N 090100294 and of the President of the Russian Federation N MD8390.2010.1, NSH8784.2010.1.
^{2}Moscow State University, Mechanics and Mathematics Faculty, Department of Number Theory.
^{3}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes; Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis; Yandex research laboratories.
^{4}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics and Random Processes.
A combinatorial analysis of the uncoditional basic sequence problem
Stevo Todorcevic
Coauthors: J. LopezAbad
We analyze properties of cardinals k that guarantee that normed spaces of density k must contain infinite basic unconditional sequence.
Stationary reflection and two cardinal tree properties
Boban Velickovic
Department of Mathematics, University of Paris 7.
Reflection principles are a way of transfering large cardinal properties to small cardinals. We consider several versions of stationary and semi stationary reflection and their consequences. In particular, we show that semi stationary set reflection implies the Singular Cardinal Hypothesis, the failure of weak square, etc. We also investigate a connection with two cardinal tree properties which were recently introduced by Weiss and prove that it follows from stationary or semi stationary reflection augmented with a weak form of Martin's Axiom. Using the approach recently developed by Viale and Weiss we conclude that any standard method to obtain (semi) stationary set reflection together with MA(Cohen) requires at least a strongly compact cardinal.
This is joint work with H. Sakai (Kobe University).
Asymmetric partition relations in the countably infinite case.
Thilo Weinert, Hausdorff Research Institute for Mathematics
A characterization of a partition relation between finite multiples of omega^2, finite multiples of omega^2 and natural numbers is given. Additionally we are going to discuss the simplest example, R(omega^2 * 2, 3), i.e. the minimal ordinal number alpha such that alpha > (omega^2 * 2, 3)^2 holds true.
In our talk, we shall consider connectivity properties of a certain set of random distance graphs.
Let n=4k, k ∈ N, N = C_{n}^{n/2}. Consider the complete distance graph G_{N}=(V_{N}, E_{N}), where

On the one hand, the consideration of such graph is motivated by the Borsuk partition problem and by the NelsonHadwiger problem on coloring R^{n} . On the other hand, this graph is in close relation with coding theory: its maximum cliques form Hadamard matrices, and its independent sets correspond to collections of finite sets with forbidden intersections.
Let us define a series of probabilistic spaces


We shall say that a random graph satisfies some property asymptotically almost surely (a.a.s.), if the probability mass of the set of all the graphs, which satisfy this property, tends to 1 as N→ ∞.
The following theorem concerns threshold probability of connectivity of the graph G^{dist}(N, p).
Theorem 1. Let p_{*} = [(√{p})/(2√{2ln2})][((lnN)^{3/2})/N]. We have two cases:
a) if p ≥ c p_{*} and c > 1, then a random graph in the space G^{dist}(N, p) is a.a.s. connected;
b) if p ≤ c p_{*} and c < 1, then a random graph in the space G^{dist}(N, p) is a.a.s. disconnected.
Theorem 2 concerns threshold probability of the emergence of a giant component in the graph G^{dist}(N, p).
Theorem 2. Let p_{**} = [(√{p})/(2√{2ln2})][((lnN)^{1/2})/N]. We have two cases:
a) if p ≤ c p_{**} and c < 1, then a random graph in the space G^{dist}(N, p) a.a.s. consists of components such that a number of vertices in each component equals O(lnN);
b) if p ≥ c p_{**} and c > 1, then a random graph in the space G^{dist}(N, p) a.a.s. contains a giant component of size W(N), and all other vertices are contained in components of size O(lnN).
In our talk, we shall present some other related results as well as some ideas of the proofs.
Footnotes:
^{1}This work was supported by the grant of RFBR N 090100294.
^{2}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics.
Borel Conjecture and dual Borel Conjecture (and other variants of the Borel Conjecture)
Wolfgang Wohofsky, Vienna University of Technology
Coauthors: Martin Goldstern (Vienna University of Technology),
Jakob Kellner (KGRC, University of Vienna),
Saharon Shelah (Hebrew University of Jerusalem; Rutgers University)
The Borel Conjecture (BC) says that there are no uncountable strong measure zero sets, whereas the dual Borel Conjecture (dBC) is the analogous statement about strongly meager sets. In 1976, Laver showed the consistency of BC; Carlson showed that dBC is consistent.
Together with Martin Goldstern, Jakob Kellner and Saharon Shelah, I have been working on the following theorem: It is consistent that BC and dBC hold simultaneously. In my talk, I will give an overview of the proof.
Moreover, I will discuss another variant of the Borel Conjecture, which I call the Marczewski Borel Conjecture (MBC). It says that there are no uncountable sets which can be translated away from each Marczewski null set. Is MBC consistent? I will present a connection between MBC and the class of translationinvariant sigmaideals which are dense in Sacks forcing (which I call "Sacks dense ideals").
Website: http://www.wohofsky.eu/math/
On connectivity of random distance graphs of special type
Andrey R. Yarmukhametov, Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics
In our talk, we shall consider connectivity properties of a certain set of random distance graphs.
Let n=4k, k ∈ N, N = C_{n}^{n/2}. Consider the complete distance graph G_{N}=(V_{N}, E_{N}), where

On the one hand, the consideration of such graph is motivated by the Borsuk partition problem and by the NelsonHadwiger problem on coloring R^{n} . On the other hand, this graph is in close relation with coding theory: its maximum cliques form Hadamard matrices, and its independent sets correspond to collections of finite sets with forbidden intersections.
Let us define a series of probabilistic spaces


We shall say that a random graph satisfies some property asymptotically almost surely (a.a.s.), if the probability mass of the set of all the graphs, which satisfy this property, tends to 1 as N→ ∞.
The following theorem concerns threshold probability of connectivity of the graph G^{dist}(N, p).
Theorem 1. Let p_{*} = [(√{p})/(2√{2ln2})][((lnN)^{3/2})/N]. We have two cases:
a) if p ≥ c p_{*} and c > 1, then a random graph in the space G^{dist}(N, p) is a.a.s. connected;
b) if p ≤ c p_{*} and c < 1, then a random graph in the space G^{dist}(N, p) is a.a.s. disconnected.
Theorem 2 concerns threshold probability of the emergence of a giant component in the graph G^{dist}(N, p).
Theorem 2. Let p_{**} = [(√{p})/(2√{2ln2})][((lnN)^{1/2})/N]. We have two cases:
a) if p ≤ c p_{**} and c < 1, then a random graph in the space G^{dist}(N, p) a.a.s. consists of components such that a number of vertices in each component equals O(lnN);
b) if p ≥ c p_{**} and c > 1, then a random graph in the space G^{dist}(N, p) a.a.s. contains a giant component of size W(N), and all other vertices are contained in components of size O(lnN).
In our talk, we shall present some other related results as well as some ideas of the proofs.
^{1}This work was supported by the grant of RFBR N 090100294.
^{2}Moscow State University, Mechanics and Mathematics Faculty, Department of Mathematical Statistics.
On zeroone laws for random graphs
Mаksim E. Zhukovskii, Moscow State University, Mechanics and Mathematics Faculty, Department of Probability Theory; Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis
In this talk, we shall discuss various questions concerning zeroone laws for random graphs in the ErdösRényi model G(N, p) .
In 1969 Y.V. Glebskii, D.I. Kogan, M.I. Liagonkii, and V.A. Talanov proved the following wellknown statement.
Theorem 1. Let a function p=p(N) satisfy, for any a > 0, two conditions: pN^{a}→∞ as N→∞ and (1p)N^{a}→∞ as N→∞. Let A be a property of a graph, which can be expressed in the language of the FirstOrder theory of graphs. Then, in the model G(N, p) , the probability of A tends either to zero or to one. In other words, either the property or its complement holds "almost surely".
Theorem 1 describes a law, under which the random graph G(N, p) falls. This law is, for natural reasons, called zeroone law. In 1976 R. Fagin independently discovered the same law. Note that p=N^{a}, with an arbitrary fixed a > 0 , does not satisfy the conditions of Theorem 1. In 1988 S. Shelah and J.H. Spencer removed this gap.
Theorem 2. Let p=N^{a}, where a ∈ (0, 1) is an irrational number. Then the random graph G(N, p) follows the zeroone law.
It is easy to see that for all rational values of a ∈ (0, 1) , Theorem 2 is false.
There are many results devoted to this subject. For example, in 1987 P.G. Kolaitis, H.J. Prömel, and B.L. Rothschild established similar zeroone laws for K_{l}free graphs; in 1988 S. Shelah and J.H. Spencer proved some zeroone laws when p=o(N^{a}) for any a ∈ (0, 1); in 2007 Y. Gurevich found a zeroone law for graphs with infinite sets of vertices.
All the abovementioned zeroone laws concerned only FirstOrder properties of graphs. Let L be the set of such properties. One may also consider properties, which can be expressed by formulas with infinite numbers of conjunctions and disjunctions. The class of such properties is denoted by L_{∞}. In 1997 M. McArtur stated some zeroone laws for the set of properties L^{k}_{∞} ⊂ L_{∞}, which are expressed by formulas with quantifier depth bounded by a number k. We call such zeroone laws zeroone klaws.
Thus, it is interesting to consider the class L^{k} ⊂ L containing all the properties, which can be expressed by formulas with quantifier depth bounded by k (sentences are again finite as opposed to L^{k}_{∞}). Recently we obtained a complete result, which describes the asymptotic behaviour of the probabilities of such properties of the random graph G(N, N^{a}), a ∈ (0, 1/(k2)].
Theorem 3. Let p=N^{a} and k ≥ 3. If
0 < a < [1/(k2)], then G(N, p) satisfies the zeroone
klaw. If a = [1/(k2)], then G(N, p) does not satisfy
the zeroone klaw.
The proof of our theorem is based on a nontrivial generalization of the graph extensions studied in 1990 by J.H. Spencer. We introduced the concept of a neutral pair of graphs and proved for it some results similar to the results of J.H. Spencer.
In the talk, we shall discuss our approach as well as some other related questions.
^{1}This work was supported by the grants of RFBR N 090100294 and of the President of the Russian Federation N MD8390.2010.1.
^{2}Moscow State University, Mechanics and Mathematics Faculty, Department of Probability Theory; Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Department of Data Analysis.