Avraham Trahtman
Encyclopedia
Avraham Trahtman is a mathematician at Bar-Ilan University
(Israel
). In 2007, Trahtman solved a problem in combinatorics
that had been open for 37 years, the Road Coloring Conjecture
posed in 1970.
.. The problem arose in the subfield of symbolic dynamics
, an abstract part of the field of dynamical systems. The road coloring problem was raised by R. L. Adler and L. W. Goodwyn from the United States, and the Israeli mathematician B. Weiss... The proof used results from earlier work..
in 1966, and repeated immediately by Anatoly Maltsev
and Shevrin. The problem was solved by Trahtman 17 years later in 1983.
In the theory of varieties
of semigroups and universal algebra
s the problem of existence of covering elements in the lattice
of varieties was posed by Evans in 1971. The positive solution of the problem was found by Trahtman. He also found a six-element semigroup that generates a variety with a continuum of subvarieties, and varieties of semigroups having no irreducible base of identities.
The theory of locally testable automata
can be based on the theory of varieties of locally testable semigroups. Trahtman found the precise estimation on the order of local testability of finite automata.
There are results in theoretical mechanics and in the promising area of extracting moisture from the air mentioned in "New Scientist
".
Bar-Ilan University
Bar-Ilan University is a university in Ramat Gan of the Tel Aviv District, Israel.Established in 1955, Bar Ilan is now Israel's second-largest academic institution. It has nearly 26,800 students and 1,350 faculty members...
(Israel
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
). In 2007, Trahtman solved a problem in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
that had been open for 37 years, the Road Coloring Conjecture
Road coloring conjecture
In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network...
posed in 1970.
Road coloring problem posed and solved
Trahtman's solution to the road coloring problem was accepted in 2007 and published in 2009 by the Israel Journal of MathematicsIsrael Journal of Mathematics
Israel Journal of Mathematics is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem .Founded in 1963, as a continuation of the Bulletin of the Research Council of Israel , the journal publishes articles on all areas of mathematics.The journal is indexed by...
.. The problem arose in the subfield of symbolic dynamics
Symbolic dynamics
In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics given by the shift operator...
, an abstract part of the field of dynamical systems. The road coloring problem was raised by R. L. Adler and L. W. Goodwyn from the United States, and the Israeli mathematician B. Weiss... The proof used results from earlier work..
Cerny conjecture
The problem of estimating the length of synchronizing word has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture. In 1964 Jan Černý conjectured that (n-1)2 is the upper bound for the length of the shortest synchronizing word for any n-state complete DFA (a DFA with complete state transition graph). If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number n of states) for which the shortest reset words have this length. The best upper bound known is n(7n2+6n-16)/48, far from the lower bound. The conjecture holds in many partial cases, see for instanceOther work
The problem of the finite basis question for semigroups of order less than six in the theory of semigroups was posed by Alfred TarskiAlfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
in 1966, and repeated immediately by Anatoly Maltsev
Anatoly Maltsev
Anatoly Ivanovich Maltsev was born in Misheronsky, near Moscow, and died in Novosibirsk, USSR. He was a mathematician noted for his work on the decidability of various algebraic groups...
and Shevrin. The problem was solved by Trahtman 17 years later in 1983.
In the theory of varieties
Variety (universal algebra)
In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
of semigroups and universal algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
s the problem of existence of covering elements in the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
of varieties was posed by Evans in 1971. The positive solution of the problem was found by Trahtman. He also found a six-element semigroup that generates a variety with a continuum of subvarieties, and varieties of semigroups having no irreducible base of identities.
The theory of locally testable automata
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
can be based on the theory of varieties of locally testable semigroups. Trahtman found the precise estimation on the order of local testability of finite automata.
There are results in theoretical mechanics and in the promising area of extracting moisture from the air mentioned in "New Scientist
New Scientist
New Scientist is a weekly non-peer-reviewed English-language international science magazine, which since 1996 has also run a website, covering recent developments in science and technology for a general audience. Founded in 1956, it is published by Reed Business Information Ltd, a subsidiary of...
".
External links
- Trahtman's page at Bar-Ilan University's Website
- Trahtman's Curriculum Vitae
- Trahtman's paper (in PDF format)
- "63-year-old solves riddle from 1970" on MSNBC
- "Encyclopedia - Britannica Online Encyclopedia", article: Avraham Trahtman
- "MacTutor History of Mathematics. Trahtman biography"
- "Israeli Mathematicians, Adi Shamir, Giulio Racah, Saharon Shelah, Zlil Sela, Robert Aumann, Michael O. Rabin, Oded Schramm, Avraham Trahtman, Llc Books, 2010"
- "A Mathematical Medley Fifty Easy Pieces on Mathematics. George G. Szpiro"