Edgar Gilbert
Encyclopedia
Edgar Nelson Gilbert was an American mathematician and coding theorist
, a longtime researcher at Bell Laboratories whose accomplishments include the Gilbert–Varshamov bound in coding theory
, the Gilbert–Elliott model of bursty errors in signal transmission, and the Erdős–Rényi model
for random graph
s.
, graduating in 1943. He taught mathematics briefly at the University of Illinois at Urbana–Champaign but then moved to the Radiation Laboratory
at the Massachusetts Institute of Technology
, where he designed radar
antenna
s from 1944 to 1946. He finished a Ph.D. in physics at MIT in 1948, with a dissertation entitled Asymptotic Solution of Relaxation Oscillation Problems under the supervision of Norman Levinson
, and took a job at Bell Laboratories where he remained for the rest of his career. He retired in 1996.
between codewords (a parameter that controls the number of errors that can be corrected). The main idea is that in a maximal
code (one to which no additional codeword can be added), the Hamming balls of the given distance must cover the entire codespace, so the number of codewords must at least equal the total volume of the codespace divided by the volume of a single ball. For 30 years, until the invention of Goppa codes in 1982, codes constructed in this way were the best ones known.
The Gilbert–Elliott model, developed by Gilbert in 1960 and E. O. Elliot in 1963, is a mathematical model for the analysis of transmission channels in which the errors occur in bursts. It posits that the channel may be in either of two different states, with different error rates, that errors occur independently of each other once the state is known, and that the changes from one state to the other are governed by a Markov chain
. It is "very convenient and often used" in the analysis of modern communications systems such as data links to mobile telephones.
s is the Erdős–Rényi model
, in which edges are chosen randomly for a fixed set of vertices. It was introduced in two forms in 1959 by Gilbert, Paul Erdős
, and Alfréd Rényi
. In Gilbert's form, each potential edge is chosen to be included in the graph or excluded from it, independently of the other edges, with probability . Thus, the expected number of edges is , but the actual number of edges can vary randomly and all graphs have a nonzero probability of being selected. In contrast, in the model introduced by Erdős and Rényi, the graph is chosen uniformly at random among all -edge graphs; the number of edges is fixed, but the edges are not independent of each other, because the presence of an edge in one position is negatively correlated with the presence of an edge in a different position. Although these two models end up having similar theories, the model is often more convenient to work with due to the independence of its edges.
In the mathematics of shuffling playing card
s, the Gilbert–Shannon–Reeds model, developed in 1955 by Gilbert and Claude Shannon and independently in unpublished work in 1981 by Jim Reeds, is a probability distribution on permutations of a set of items that, according to experiments by Persi Diaconis
, accurately models human-generated riffle shuffles. In this model, a deck of cards is split at a point chosen randomly according to a binomial distribution, and the two parts are merged
together with the order of merging chosen uniformly at random among all possible mergers. Equivalently, it is the inverse of a permutation formed by choosing independently at random for each card whether to put it into one of two piles (maintaining the original order of the cards within each pile), and then stacking the two piles on top of each other.
Gilbert tessellations are a mathematical model of crack formation
introduced by Gilbert in 1967. In this model, fractures begin at a set of random points, with random orientations, chosen according to a Poisson process
, and then grow at a constant rate until they terminate by running into previously formed cracks.
in which each edge is given both a cost and a capacity, and a matrix of flow amounts between different pairs of terminal vertices; the task is to find a subnetwork of minimum cost whose capacities are sufficient to support a flow with the given flow amounts between any pair of terminals. When the flow amounts are all equal, this reduces to the classical Steiner tree problem.
Gilbert discovered Costas array
s independently of and in the same year as Costas, and is also known for his work with John Riordan
on counting necklaces
in combinatorics
. He has Erdős number
2 due to his research with Erdős' co-authors Fan Chung
, Ron Graham
, and Jack van Lint
on partitions of rectangles into smaller rectangles.
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, a longtime researcher at Bell Laboratories whose accomplishments include the Gilbert–Varshamov bound in coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, the Gilbert–Elliott model of bursty errors in signal transmission, and the Erdős–Rényi model
Erdos–Rényi model
In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
for random graph
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
s.
Biography
Gilbert was born in 1923 in Woodhaven, New York. He did his undergraduate studies in physics at Queens College, City University of New YorkQueens College, City University of New York
Queens College, located in Flushing, Queens, New York City, is one of the senior colleges of the City University of New York. It is also the fifth oldest of the City University's twenty-three institutions of higher learning. The college's seventy seven acre campus is located in the heart of the...
, graduating in 1943. He taught mathematics briefly at the University of Illinois at Urbana–Champaign but then moved to the Radiation Laboratory
Radiation Laboratory
The Radiation Laboratory, commonly called the Rad Lab, was located at the Massachusetts Institute of Technology in Cambridge, Massachusetts and functioned from October 1940 until December 31, 1945...
at the Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
, where he designed radar
Radar
Radar is an object-detection system which uses radio waves to determine the range, altitude, direction, or speed of objects. It can be used to detect aircraft, ships, spacecraft, guided missiles, motor vehicles, weather formations, and terrain. The radar dish or antenna transmits pulses of radio...
antenna
Antenna (radio)
An antenna is an electrical device which converts electric currents into radio waves, and vice versa. It is usually used with a radio transmitter or radio receiver...
s from 1944 to 1946. He finished a Ph.D. in physics at MIT in 1948, with a dissertation entitled Asymptotic Solution of Relaxation Oscillation Problems under the supervision of Norman Levinson
Norman Levinson
Norman Levinson was an American mathematician. Some of his major contributions were in the study of Fourier transforms, complex analysis, non-linear differential equations, number theory, and signal processing. He worked closely with Norbert Wiener in his early career...
, and took a job at Bell Laboratories where he remained for the rest of his career. He retired in 1996.
Coding theory
The Gilbert–Varshamov bound, proved independently in 1952 by Gilbert and in 1957 by Rom Varshamov, is a mathematical theorem that guarantees the existence of error-correcting codes that have a high transmission rate as a function of their length, alphabet size, and Hamming distanceHamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
between codewords (a parameter that controls the number of errors that can be corrected). The main idea is that in a maximal
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
code (one to which no additional codeword can be added), the Hamming balls of the given distance must cover the entire codespace, so the number of codewords must at least equal the total volume of the codespace divided by the volume of a single ball. For 30 years, until the invention of Goppa codes in 1982, codes constructed in this way were the best ones known.
The Gilbert–Elliott model, developed by Gilbert in 1960 and E. O. Elliot in 1963, is a mathematical model for the analysis of transmission channels in which the errors occur in bursts. It posits that the channel may be in either of two different states, with different error rates, that errors occur independently of each other once the state is known, and that the changes from one state to the other are governed by a Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
. It is "very convenient and often used" in the analysis of modern communications systems such as data links to mobile telephones.
Probability theory
Central to the theory of random graphRandom graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
s is the Erdős–Rényi model
Erdos–Rényi model
In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
, in which edges are chosen randomly for a fixed set of vertices. It was introduced in two forms in 1959 by Gilbert, Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, and Alfréd Rényi
Alfréd Rényi
Alfréd Rényi was a Hungarian mathematician who made contributions in combinatorics, graph theory, number theory but mostly in probability theory.-Life:...
. In Gilbert's form, each potential edge is chosen to be included in the graph or excluded from it, independently of the other edges, with probability . Thus, the expected number of edges is , but the actual number of edges can vary randomly and all graphs have a nonzero probability of being selected. In contrast, in the model introduced by Erdős and Rényi, the graph is chosen uniformly at random among all -edge graphs; the number of edges is fixed, but the edges are not independent of each other, because the presence of an edge in one position is negatively correlated with the presence of an edge in a different position. Although these two models end up having similar theories, the model is often more convenient to work with due to the independence of its edges.
In the mathematics of shuffling playing card
Playing card
A playing card is a piece of specially prepared heavy paper, thin cardboard, plastic-coated paper, cotton-paper blend, or thin plastic, marked with distinguishing motifs and used as one of a set for playing card games...
s, the Gilbert–Shannon–Reeds model, developed in 1955 by Gilbert and Claude Shannon and independently in unpublished work in 1981 by Jim Reeds, is a probability distribution on permutations of a set of items that, according to experiments by Persi Diaconis
Persi Diaconis
Persi Warren Diaconis is an American mathematician and former professional magician. He is the Mary V. Sunseri Professor of Statistics and Mathematics at Stanford University....
, accurately models human-generated riffle shuffles. In this model, a deck of cards is split at a point chosen randomly according to a binomial distribution, and the two parts are merged
Merge algorithm
Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. This is well-suited for machines with tape drives...
together with the order of merging chosen uniformly at random among all possible mergers. Equivalently, it is the inverse of a permutation formed by choosing independently at random for each card whether to put it into one of two piles (maintaining the original order of the cards within each pile), and then stacking the two piles on top of each other.
Gilbert tessellations are a mathematical model of crack formation
Fracture
A fracture is the separation of an object or material into two, or more, pieces under the action of stress.The word fracture is often applied to bones of living creatures , or to crystals or crystalline materials, such as gemstones or metal...
introduced by Gilbert in 1967. In this model, fractures begin at a set of random points, with random orientations, chosen according to a Poisson process
Poisson process
A Poisson process, named after the French mathematician Siméon-Denis Poisson , is a stochastic process in which events occur continuously and independently of one another...
, and then grow at a constant rate until they terminate by running into previously formed cracks.
Other contributions
Gilbert did important work on the Steiner tree problem in 1968, formulating it in a way that unified it with network flow problems. In Gilbert's model, one is given a flow networkFlow network
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
in which each edge is given both a cost and a capacity, and a matrix of flow amounts between different pairs of terminal vertices; the task is to find a subnetwork of minimum cost whose capacities are sufficient to support a flow with the given flow amounts between any pair of terminals. When the flow amounts are all equal, this reduces to the classical Steiner tree problem.
Gilbert discovered Costas array
Costas array
In mathematics, a Costas array can be regarded geometrically as a set of n points lying on the squares of a n×n checkerboard, such that each row or column contains only one point, and that all of the n/2 displacement vectors between each pair of dots are distinct...
s independently of and in the same year as Costas, and is also known for his work with John Riordan
John Riordan
John Riordan was an American mathematician and the author of major early works in combinatorics, particularly Introduction to Combinatorial Analysis and Combinatorial Identities.- Life :...
on counting necklaces
Necklace (combinatorics)
In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent...
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 ,...
. He has Erdős number
Erdos number
The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
2 due to his research with Erdős' co-authors Fan Chung
Fan Chung
Fan Rong K Chung Graham , known professionally as Fan Chung, is a mathematician who works mainly in the areas of spectral graph theory, extremal graph theory and random graphs, in particular...
, Ron Graham
Ron Graham
Ron Graham may refer to:*Ronald Graham , American mathematician*Ronald Graham , RAF Air Vice-Marshal*Ron Graham , Australian actor*Ronny Graham , American actor-See also:...
, and Jack van Lint
Jack van Lint
Jacobus Hendricus van Lint was a Dutch mathematician, professor at the Eindhoven University of Technology, of which he was rector magnificus from 1991 till 1996....
on partitions of rectangles into smaller rectangles.