Mathematical Logic Seminar

Completeness of the random graph

Sala 6.2.33, Ciências ULisboa (com transmissão online)

Por Ana Catarina Monteiro (University of Lisbon).

A graph with a countably infinite many vertices is said to be random if for every two disjoint sets of vertices A and B, there exists a vertex which is related with every vertex in A and none of the vertices in B. The study of random graphs was motivated by the search of the probability of a certain property occur in a graph. Fixing p E [0,1], we can think at a random graph as being obtained by starting with a set of isolated vertices and adding edges between them at random, where each edge as probability p of occurring. It might not be immediate that we can use logic to study these structures, especially because the main models for random graphs are based essentially in probability, for example, the binomial random graph or the uniform random graph (S. Janson, A. Rucinski, T. Luczak, 2000), but in fact we can. In this seminar, after describing the set of axioms of the random graph, we will prove its completeness by using the Vaught’s test, and take a few conclusions about the set of all sentences true almost surely. For that, several concepts and results in model theory will be recalled.


Transmissão via Zoom.

16h00
CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional
Logótipos Ciências ULisboa e C-Academy, títulos dos cursos

Um programa de formação avançada em Cibersegurança para a administração pública e o setor privado desenvolvido pelo Centro Nacional de Cibersegurança, no âmbito do Plano de Recuperação e Resiliência.

Logótipos Ciências ULisboa e C-Academy, títulos dos cursos

Um programa de formação avançada em Cibersegurança para a administração pública e o setor privado desenvolvido pelo Centro Nacional de Cibersegurança, no âmbito do Plano de Recuperação e Resiliência.

Logótipo do evento, sobre um fundo branco

Um evento de reunião da comunidade nacional nas diversas vertentes da informática, com a ambição de ser o fórum de eleição para a divulgação, discussão e reconhecimento de trabalhos científicos.

Imagem do evento

Extended enrolement date until July 12th.

Logótipo do Workshop

A participação na 3.ª edição do Workshop é gratuita, mediante inscrição prévia.

Are you ready for this year's edition?

Imagem do evento - título, local e data do evento

Investigação Ecológica ao Serviço da Conservação

A leading venue for presenting and discussing the latest research, industrial practice and innovations in dependable and secure computing.