English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The goal of this paper is to present a simple introduction to the theory of flag algebras developed by Razborov, as well as illustrate this theory’s power for obtaining results in extremal combinatorics. In this paper, we investigate a density problem in tournaments. Resumo. O objetivo deste trabalho é apresentar uma introdução acessı́vel à teoria das álgebras de flags desenvolvida por Razborov, bem como ilustrar a aplicabilidade desta teoria para obter resultados em combinatória extremal. Neste trabalho, lidamos com um problema de densidade em torneios. Introdução Neste trabalho, apresentamos uma breve introdução à teoria de álgebras de flag, desenvolvida por Razborov [Razborov 2007], que tem sido utilizada em diversos problemas de combinatória extremal. Para ilustrar a aplicabilidade dessa teoria, apresentamos um resultado para torneios [Coregliano et al. 2015, Parente 2016] obtido utilizando técnicas da teoria de álgebra de flags. Um torneio é um digrafo T = (V,A) tal que, para cada par não-ordenado de vértices {u, v}, temos que exatamente um dentre (u, v) e (v, u) pertence a A (veja a Figura 1). O problema que estudamos é o seguinte. Seja T um torneio com t vértices. Queremos calcular o seguinte valor: maxTn∈Tn p(T, Tn), onde Tn é o conjunto de todos os torneios com n vértices e p(T, Tn) é o número de cópias de T em Tn dividido por ( n t ) . Note que p(T, Tn) é a probabilidade de, ao sortearmos um conjunto S de t vértices de Tn, obtermos um digrafo Tn[S] isomorfo a T . Dizemos que p(T, Tn) é a densidade de T em Tn. Ou seja, queremos saber qual é a densidade máxima de T considerando todos os torneios em n vértices. Em combinatória extremal, é comum lidarmos com versões assintóticas dos problemas investigados. No nosso caso, isso significa que queremos calcular o valor limn→∞maxTn∈Tn p(T, Tn). Neste trabalho, utilizamos álgebras de flag para mostrar que lim n→∞ max Tn∈Tn p(R, Tn) = 1/16, (1) The first author is supported by FAPESP grant (2016/24041-6) and this article was produced as part of the activities of FAPESP Research, Innovation and Dissemination Center for Neuromathematics (grant 2013/ 07699-0 , S.Paulo Research Foundation). The second author is Partially supported by FAPESP grant (Processo 2013/03447-6). Figura 1. Torneio R: um torneio em 5 vértices. onde R é o torneio na Figura 1. A prova completa do resultado está disponı́vel em [Coregliano et al. 2015, Parente 2016]. Destacamos que uma caracterı́stica de grande interesse no uso das álgebras de flags é a fácil utilização de resolvedores de programas semidefinidos para a obtenção de cotas superiores para os valores que queremos calcular.

Utilizando álgebras de flags para problemas de combinatória extremal