The local loop lemma

DOI10.1007/S00012-020-0644-YMaRDI QIDQ2302149zbMATH OpenOpenAlexWikidataFDO

Authors Miroslav Olšák

Publication date 25 February 2020

Published in Algebra Universalis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1902.08791

zbMATH Keywords

digraphlocal loop lemmaTaylor algebra

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Equational logic, Mal'tsev conditions (08B05) Free algebras (08B20)

Abstract: We prove that an idempotent operation generates a loop from a strongly connected digraph containing directed cycles of all lengths under very mild (local) algebraic assumptions. Using the result, we reprove the existence of a weakest non-trivial idempotent equations, and that a strongly connected digraph with algebraic length 1 compatible with a Taylor term has a loop.

Review text

Let \(G=(V,E)\) be a digraph. Its edges are denoted by \((u,v)\), where \(u,v\) are vertices. A walk is a sequence of edges \([v_0, v_1,\dots,v_n]\) such that \((v_i,v_{i+1})\) for all \(i\) . A closed walk of length \(n\) is a walk where \(v_n\) = \(v_0\). A digraph is strongly connected if there is a walk from \(u\) to \(v\) for any pair of vertices \(u,v\). Let \(R\) denote the binary relation on \(G\) determined by the edges of \(G\). A graph \(G\) is called compatible with operation \(t\) if \(t\) is compatible with this relation \(R\). The aim of the paper it to prove the following result. Theorem. Consider a set \(A\) and an idempotent \(n\)-ary operation \(t\) on \(A\), a digraph \(G\) on \(A\) with vertices \(a_{ij}\) where \(i,j\) range over \({\{{1,...,n-1}\}}\) such that \(G\) is compatible with \(t\), \(G\) is either a strongly connected digraph containing directed closed walks of all lenghts with two, or \(G\) is an undirected connected non-bipartite graph, for every \(i\) there is an edge \((a_{i,j},t(a_{i,0},a_{i,1},...,a_{i,n-1}))\). Then \(G\) contains a loop. The proof of this theorem is very sofisticated and is based on the previous results by L.Barto and the author. They use Taylor terms and Taylor algebras. It is a strenghtenning of the previous results and it is the stronger result in this direction.

Recommendations

• scientific article; zbMATH DE number 1556643
• scientific article; zbMATH DE number 2070257
• Publication:3473887
• scientific article; zbMATH DE number 1103394
• The local cut lemma
• scientific article; zbMATH DE number 1377860
• Extension of local loop isomorphisms
• Local loop near-rings
• Publication:4206946
• Revisit the Lovász local lemma

Cites work

• H-coloring dichotomy revisited
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Loop conditions
• On the complexity of H-coloring
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Pseudo‐loop conditions
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The weakest nontrivial idempotent equations
• Universal algebra. Fundamentals and selected topics

Cited in

(2)

• The structure of polynomial operations associated with smooth digraphs.
• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions

This page was built for publication: The local loop lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302149)