In this talk we study a natural generalization of the classical \eps-net problem (Haussler-Welzl 1987), which we call 'the \eps-t-net problem': Given a hypergraph on n vertices and parameters t and \eps , find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least \eps n contains a set in S. When t=1, this corresponds to the \eps-net problem.
Title: A randomized construction of high girth regular graphs
Abstract: We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k > 2$ and $0 < c < 1$ be fixed. Let $n$ be even and set $g = c \log_{k-1} (n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long as the smallest degree $\delta (G)<k$, choose, uniformly at random, two vertices $u,v \in V(G)$ of degree $\delta(G)$ whose distance is at least $g-1$. If there are no such vertex pairs, abort. Otherwise, add the edge $uv$ to $E(G)$.
Abstract: It has long been known that two independent copies of the infinite Erdos-Renyi graph G(\infty,p) are almost surely isomorphic. The resulting graph is called the Rado graph. If the vertices are in a metric space and only nearby vertices may be connected, a similar result may or may not hold, depending on fine details of the underlying metric space. We present new results in the case where the metric space is a circle.
Using the axiom of choice one can construct set of reals which are
pathological in some sense. Similar constructions can be produce such
"pathological" subsets of any non trivial Polish space (= a complete
separable metric space).
A "pathological set" can be a non measurable set , a set which does
not have the property of Baire (namely it is not a Borel set modulo a
rst category set).
A subset of the innite subsets of natural numbers,
can be considered to be "pathological" if it is a counter example to
Using the axiom of choice one can construct set of reals which are
pathological in some sense. Similar constructions can be produce such
"pathological" subsets of any non trivial Polish space (= a complete
separable metric space).
A "pathological set" can be a non measurable set , a set which does
not have the property of Baire (namely it is not a Borel set modulo a
rst category set).
A subset of the innite subsets of natural numbers,
can be considered to be "pathological" if it is a counter example to
Eliana Bariga will speak about Definably compact semialgebraic groups over real closed fields.
Abstract: Semialgebraic groups over a real closed field can be seen as a generalization of the semialgebraic groups over the real field, and also as a particular case of the groups definable in an o-minimal structure.
January 16, 12:00-13:00, Seminar room 209, Manchester building.
Abstract: I plan to show a proof of the statement "residually-finite-by-residually-finite extensions are weakly sofic". The proof is based on characterization of weakly sofic groups by solvability of equations over groups. It looks different from other proofs of soficity and weak soficity. I plan to discuss relations of equations on and over groups with soficity in some details.
OAntongiulio Fornasiero will speak about definable and interpretable groups and fields in the p-adics.
Abstract: A. Pillay showed that every definable group in the p-adics has a canonical topology and differential structure, and deduced that every definable field is either finite or a finite extension of Q_p. In a joint work with J. de la Nuez Gonzalez we extend the analysis to interpretable fields, and show that they are either countable or finite extensions of Q_p.
