Saharon Shelah, The Hebrew University of Jerusalem and Rutgers University
"Random graphs: a stronger logic, but with the zero one law , III"
Time: 5:00 PM
Location: Hill 705
Abstract: THE TALK CONTINUES.......This is based on paper [1077] We like to find a logic stronger than first order such that: on the one hand it satisfies the 0-1 law, e.g. for the random graph $cG_{n,1/2}$ and on the other hand there is a formula $varphi(x)$ such that for no first order $psi(x)$ do we have: for every random enough $G_{n,1/2}$ are the formulas $varphi(x),psi(x)$ equivalent in it. We do it adding a quantifier on graph $bQ_{old t}$, i.e. have a class of finite graphs closed under isomorphisms and being able to say that if $(varphi_0(x,ar c),varphi_1(x_0,x_1,ar c))$ a pair of formulas with parameter define a graph in $cG_{n,1/2}$, hen , we can form a formula $psi(ar y)$ such $psi(ar c)$ says that the graph belongs $K_{ar{old t}}$. Presently we do it for random enough $ar{old t}$. In later versions we shall do it for $K_{old t} = {H:H$ a non-2-weak graph with number of cliques with $log log(|H|)$ nodes$}$ is one of $1,2,ldots lfloor sqrt{loglog(|H|)} floor$ modulo $lfloor loglog(|H|) floor$.
Past Talks
Monday, September 26th
Saharon Shelah, The Hebrew University of Jerusalem and Rutgers University
"Random graphs: a stronger logic, but with the zero one law , II"
Time: 5:00 PM
Location: Hill 705
Abstract: THE TALK CONTINUES.......This is based on paper [1077]
We like to find a logic stronger than first order such that: on the one hand it satisfies the 0-1 law, e.g. for the random graph $cG_{n,1/2}$ and on the other hand there is a formula $varphi(x)$ such that for no first order $psi(x)$ do we have: for every random enough $G_{n,1/2}$ are the formulas $varphi(x),psi(x)$ equivalent in it. We do it adding a quantifier on graph $bQ_{old t}$, i.e. have a class of finite graphs closed under isomorphisms and being able to say that if $(varphi_0(x,ar c),varphi_1(x_0,x_1,ar c))$ a pair of formulas with parameter define a graph in $cG_{n,1/2}$, hen , we can form a formula $psi(ar y)$ such $psi(ar c)$ says that the graph belongs $K_{ar{old t}}$. Presently we do it for random enough $ar{old t}$. In later versions we shall do it for $K_{old t} = {H:H$ a non-2-weak graph with number of cliques with $log log(|H|)$ nodes$}$ is one of $1,2,ldots lfloor sqrt{loglog(|H|)} floor$ modulo $lfloor loglog(|H|) floor$.
Monday, September 19th
Saharon Shelah, The Hebrew University of Jerusalem and Rutgers University
"Random graphs: a stronger logic, but with the zero one law , I"
Time: 5:00 PM
Location: Hill 705
Abstract: This is based on paper [1077]
We like to find a logic stronger than first order such that: on the
one hand it satisfies the 0-1 law, e.g. for the random graph
$cG_{n,1/2}$ and on the other hand there is a
formula $varphi(x)$ such that for no first order $psi(x)$ do we have:
for every random enough $G_{n,1/2}$ are the formulas
$varphi(x),psi(x)$ equivalent in it. We do it adding a quantifier
on graph $bQ_{old t}$, i.e. have a class of finite graphs closed
under isomorphisms and being able to say that if $(varphi_0(x,ar
c),varphi_1(x_0,x_1,ar c))$ a pair of formulas with parameter
define a graph in $cG_{n,1/2}$, hen , we can form a
formula $psi(ar y)$ such $psi(ar c)$
says that the graph belongs $K_{ar{old t}}$.
Presently we do it for random enough $ar{old t}$. In
later versions we shall do it for $K_{old t} = {H:H$ a non-2-weak
graph with number of cliques with $log log(|H|)$ nodes$}$
is one of $1,2,ldots lfloor
sqrt{loglog(|H|)}
floor$ modulo $lfloor loglog(|H|)
floor$.
This page was last updated on February 09, 2016 at 10:04 am and is maintained by webmaster@math.rutgers.edu.
For questions regarding courses and/or special permission, please contact
ugoffice@math.rutgers.edu.