360:
all points in the first generation ignoring any previously found and continue this process until it dies out. The associated branching process is one where the mean number of offspring is a
Poisson random variable with intensity equal to the mean degree in the original RGG (πλR). From here only standard branching process techniques need be applied to obtain a lower bound. Furthermore, Gilbert showed that by reframing the problem into one about bond percolation, an upper bound for the giant component can obtained. The method consists of discritizing the plane such that any two nodes in adjacent squares are connected; and allowing each square to represents an edge on the lattice. By construction, if there is a giant component in the bond percolation problem then there must be a giant component in the RGG.
152:, 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
317:(RGG), or Gilbert Disk model) where points are placed on the infinite plane using a suitable Point Process and nodes connect if and only if they are within some critical connection range R; wireless communication networks were suggested as the main the application for this work. From this formulation a simple result follows that for a stationary
350:
with density λ the expected degree of each node is the number of points found within the connectivity range, namely, πλR. A natural question to ask after formulating such a graph is what is the critical mean degree to ensure there is a giant component; in essence this question gave rise to the field
290:
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
359:
Gilbert was able to provide an initial lower bound for the critical mean degree (equivalently the critical transmission range). By choosing an arbitrary point in the process (call this the zeroth generation), find all points within a connection distance R (first generation). Repeat the process for
384:
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
140:
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
239:-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 properties, the
369:
1227:
1165:
The colossal book of mathematics: classic puzzles, paradoxes, and problems : number theory, algebra, geometry, probability, topology, game theory, infinity, and other topics of recreational mathematics
1217:
1222:
904:
Petrausch, Stefan; Sörgel, Wolfgang; Kaup, André (2004), "Serially connected channels: Capacity and video streaming application scenario for separate and joint channel coding",
348:
74:
1242:
70:
1207:
1202:
778:
1237:
1172:
1133:
982:
913:
861:
827:
748:
82:
265:
301:
introduced by
Gilbert in 1967. In this model, fractures begin at a set of random points, with random orientations, chosen according to a
201:
form, each potential edge is chosen to be included in the graph or excluded from it, independently of the other edges, with probability
282:, accurately models human-generated riffle shuffles. In this model, a deck of cards is split at a point chosen randomly according to a
218:, but the actual number of edges can vary randomly and all graphs have a nonzero probability of being selected. In contrast, in the
156:. It is "very convenient and often used" in the analysis of modern communications systems such as data links to mobile telephones.
128:, proved independently in 1952 by Gilbert and in 1957 by Rom Varshamov, is a mathematical theorem that guarantees the existence of
1232:
1147:
906:
5th
International ITG Conference on Source and Channel Coding (SCC): January 14–16, 2004, Erlangen : Conference Record
738:
1009:
878:
766:
670:
529:
438:
413:
397:
352:
1045:
Gray, N. H.; Anderson, J. B.; Devine, J. D.; Kwasnik, J. M. (1976), "Topological properties of random crack networks",
125:
38:
1247:
272:
and independently in unpublished work in 1981 by Jim Reeds, is a probability distribution on permutations of a set of
169:
50:
136:
between codewords (a parameter that controls the number of errors that can be corrected). The main idea is that in a
149:
46:
1212:
393:
108:
17:
401:
1128:, Annals of Discrete Mathematics (North-Holland Mathematics Studies), vol. 53, Elsevier, pp. 80–83,
142:
314:
730:
318:
283:
129:
324:
1197:
1192:
569:
373:
294:
78:
66:
305:, and then grow at a constant rate until they terminate by running into previously formed cracks.
1073:
1062:
1028:
956:
701:
644:
585:
929:
853:
847:
183:
607:
Gilbert, E. N. (1967), "Random plane networks and needle-shaped crystals", in Noble, B. (ed.),
92:
from 1944 to 1946. He finished a Ph.D. in physics at MIT in 1948, with a dissertation entitled
1168:
1129:
978:
909:
857:
823:
744:
356:
101:
34:
1121:
1102:
1054:
1018:
948:
887:
693:
636:
577:
538:
503:
447:
133:
1072:
Schreiber, Tomasz; Soja, Natalia (2010). "Limit theory for planar
Gilbert tessellations".
302:
287:
137:
97:
89:
313:
In 1961, Gilbert introduced the random plane network (more commonly referred to now as a
799:
Varshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes",
573:
1160:
1004:
891:
542:
451:
279:
269:
233:
model introduced by Erdős and Rényi, the graph is chosen uniformly at random among all
1186:
1066:
960:
876:
Elliott, E. O. (1963), "Estimates of error rates for codes on burst-noise channels",
734:
674:
417:
405:
179:
132:
that have a high transmission rate as a function of their length, alphabet size, and
42:
30:
389:
381:
261:
165:
153:
54:
678:
254:
model is often more convenient to work with due to the independence of its edges.
385:
flow amounts are all equal, this reduces to the classical
Steiner tree problem.
977:, Princeton Studies in Complexity, Princeton University Press, pp. 36–37,
1023:
1000:
952:
843:
508:
779:"Edgar Nelson Gilbert Obituary: View Edgar Gilbert's Obituary by Star-Ledger"
762:
666:
409:
258:
933:
560:
Gilbert, E. N. (1965), "Latin squares which contain no repeated digrams",
377:
298:
1058:
1032:
737:(2000), "Time-slot allocation in wireless TDMA", in Gelenbe, E. (ed.),
705:
648:
589:
1106:
697:
640:
581:
975:
Small Worlds: The
Dynamics of Networks Between Order and Randomness
1078:
104:
where he remained for the rest of his career. He retired in 1996.
86:
29:(July 25, 1923 – June 15, 2013) was an American mathematician and
145:
in 1982, codes constructed in this way were the best ones known.
436:
Gilbert, E. N. (1952), "A comparison of signalling alphabets",
1228:
Massachusetts
Institute of Technology School of Science alumni
1095:
Journal of the
Society for Industrial and Applied Mathematics
740:
System
Performance Evaluation: Methodologies and Applications
178:
vertices. It was introduced in two forms in 1959 by Gilbert,
820:
Error correction Coding: Mathematical Methods and Algorithms
527:
Gilbert, E. N. (1960), "Capacity of a burst-noise channel",
73:, graduating in 1943. He taught mathematics briefly at the
609:
Applications of Undergraduate Mathematics in Engineering
172:, in which edges are chosen randomly for a fixed set of
376:
in 1968, formulating it in a way that unified it with
94:
Asymptotic Solution of Relaxation Oscillation Problems
1007:(1992), "Tracking the dovetail shuffle to its lair",
818:
Moon, Todd K. (2005), "The Gilbert–Varshamov Bound",
420:
on partitions of rectangles into smaller rectangles.
327:
1218:Queens College, City University of New York alumni
1093:Gilbert, Edgar N (1961). "Random Plane Networks".
342:
846:(2003), "The Gilbert–Varshamov Bound revisited",
69:. He did his undergraduate studies in physics at
49:of bursty errors in signal transmission, and the
627:Gilbert, E. N. (1968), "Steiner minimal trees",
1223:University of Illinois Urbana-Champaign faculty
657:
618:
598:
551:
518:
485:
460:
427:
476:
380:problems. In Gilbert's model, one is given a
291:stacking the two piles on top of each other.
8:
71:Queens College, City University of New York
1167:, W. W. Norton & Company, p. 18,
75:University of Illinois at Urbana–Champaign
1148:An independent discovery of Costas arrays
1077:
1022:
822:, John Wiley and Sons, pp. 409–410,
507:
473:, Technical Memorandum, Bell Laboratories
392:independently of and in the same year as
334:
330:
329:
326:
494:Gilbert, E. N. (1959), "Random graphs",
278:items that, according to experiments by
207:. Thus, the expected number of edges is
908:, Margret Schneider, pp. 271–278,
720:
852:, Cambridge University Press, p.
849:Fundamentals of Error-Correcting Codes
396:, and is also known for his work with
995:
993:
83:Massachusetts Institute of Technology
7:
1243:Mathematicians from New York (state)
107:He died following a fall in 2013 at
679:"Tiling rectangles with rectangles"
629:SIAM Journal on Applied Mathematics
268:, developed in 1955 by Gilbert and
1150:, Aaron Sterling, October 9, 2011.
892:10.1002/j.1538-7305.1963.tb00955.x
733:; Gilbert, E. N.; Whiting, P. A.;
543:10.1002/j.1538-7305.1960.tb03959.x
452:10.1002/j.1538-7305.1952.tb01393.x
37:whose accomplishments include the
23:American mathematician (1923–2013)
14:
496:Annals of Mathematical Statistics
16:For the Kittitian cricketer, see
343:{\displaystyle \mathbb {R} ^{2}}
743:, CRC Press, pp. 203–214,
1208:American probability theorists
1203:American information theorists
1:
1238:People from Woodhaven, Queens
1010:Annals of Applied Probability
879:Bell System Technical Journal
767:Mathematics Genealogy Project
530:Bell System Technical Journal
439:Bell System Technical Journal
353:continuum percolation theory
297:are a mathematical model of
65:Gilbert was born in 1923 in
477:Bayer & Diaconis (1992)
266:Gilbert–Shannon–Reeds model
33:, a longtime researcher at
1264:
941:Publicationes Mathematicae
15:
973:Watts, Duncan J. (2003),
953:10.5486/PMD.1959.6.3-4.12
660:
621:
601:
554:
521:
488:
463:
430:
164:Central to the theory of
109:Basking Ridge, New Jersey
96:under the supervision of
18:Edgar Gilbert (cricketer)
1126:The Steiner Tree Problem
1124:; Winter, Pawel (1992),
286:, and the two parts are
143:algebraic geometry codes
1233:Scientists at Bell Labs
1024:10.1214/aoap/1177005705
842:Huffman, William Cary;
509:10.1214/aoms/1177706098
469:Gilbert, E. N. (1955),
408:. He collaborated with
309:Random geometric graphs
126:Gilbert–Varshamov bound
39:Gilbert–Varshamov bound
727:Author biography from
344:
315:random geometric graph
257:In the mathematics of
130:error-correcting codes
77:but then moved to the
801:Dokl. Akad. Nauk SSSR
611:, New York: Macmillan
424:Selected publications
345:
319:Poisson point process
295:Gilbert tessellations
284:binomial distribution
150:Gilbert–Elliott model
47:Gilbert–Elliott model
1047:Mathematical Geology
934:"On random graphs I"
763:Edgar Nelson Gilbert
686:Mathematics Magazine
374:Steiner tree problem
325:
100:, and took a job at
85:, where he designed
79:Radiation Laboratory
27:Edgar Nelson Gilbert
574:1965SIAMR...7..189G
471:Theory of Shuffling
388:Gilbert discovered
364:Other contributions
67:Woodhaven, New York
1248:Network scientists
1059:10.1007/BF01031092
673:; Shearer, J. B.;
669:; Gilbert, E. N.;
370:did important work
340:
160:Probability theory
1174:978-0-393-02023-6
1135:978-0-444-89098-6
984:978-0-691-11704-1
915:978-3-8007-2802-2
863:978-0-521-78280-7
829:978-0-471-64800-0
750:978-0-8493-2357-7
713:
712:
656:
655:
617:
616:
597:
596:
550:
549:
517:
516:
484:
483:
459:
458:
357:branching process
170:Erdős–Rényi model
102:Bell Laboratories
51:Erdős–Rényi model
35:Bell Laboratories
1255:
1213:Coding theorists
1178:
1177:
1157:
1151:
1145:
1139:
1138:
1117:
1111:
1110:
1090:
1084:
1083:
1081:
1069:
1042:
1036:
1035:
1026:
997:
988:
987:
970:
964:
963:
947:(3–4): 290–297,
938:
925:
919:
918:
901:
895:
894:
886:(5): 1977–1997,
873:
867:
866:
839:
833:
832:
815:
809:
808:
796:
790:
789:
787:
786:
775:
769:
760:
754:
753:
725:
708:
683:
658:
651:
619:
612:
599:
592:
552:
545:
537:(5): 1253–1265,
519:
512:
511:
502:(4): 1141–1144,
486:
474:
461:
454:
428:
349:
347:
346:
341:
339:
338:
333:
277:
253:
238:
232:
217:
206:
200:
177:
134:Hamming distance
1263:
1262:
1258:
1257:
1256:
1254:
1253:
1252:
1183:
1182:
1181:
1175:
1161:Gardner, Martin
1159:
1158:
1154:
1146:
1142:
1136:
1119:
1118:
1114:
1107:10.1137/0109045
1092:
1091:
1087:
1071:
1044:
1043:
1039:
1005:Diaconis, Persi
999:
998:
991:
985:
972:
971:
967:
936:
927:
926:
922:
916:
903:
902:
898:
875:
874:
870:
864:
841:
840:
836:
830:
817:
816:
812:
798:
797:
793:
784:
782:
777:
776:
772:
761:
757:
751:
728:
726:
722:
718:
709:
698:10.2307/2690096
681:
675:van Lint, J. H.
667:Chung, F. R. K.
665:
652:
641:10.1137/0116001
626:
613:
606:
593:
582:10.1137/1007035
559:
546:
526:
513:
493:
480:
468:
455:
435:
426:
366:
328:
323:
322:
311:
303:Poisson process
299:crack formation
273:
240:
234:
219:
208:
202:
187:
186:. In Gilbert's
173:
162:
122:
117:
98:Norman Levinson
63:
31:coding theorist
24:
21:
12:
11:
5:
1261:
1259:
1251:
1250:
1245:
1240:
1235:
1230:
1225:
1220:
1215:
1210:
1205:
1200:
1195:
1185:
1184:
1180:
1179:
1173:
1152:
1140:
1134:
1122:Richards, Dana
1120:Hwang, Frank;
1112:
1101:(4): 533–543.
1085:
1053:(6): 617–628,
1037:
1017:(2): 294–313,
989:
983:
965:
920:
914:
896:
868:
862:
834:
828:
810:
791:
781:. Obits.nj.com
770:
755:
749:
735:Winkler, P. M.
731:Coffman, E. G.
729:Borst, S. C.;
719:
717:
714:
711:
710:
692:(5): 286–291,
664:
662:
654:
653:
625:
623:
615:
614:
605:
603:
595:
594:
568:(2): 189–198,
558:
556:
548:
547:
525:
523:
515:
514:
492:
490:
482:
481:
475:. As cited by
467:
465:
457:
456:
446:(3): 504–522,
434:
432:
425:
422:
365:
362:
337:
332:
310:
307:
280:Persi Diaconis
270:Claude Shannon
161:
158:
121:
118:
116:
113:
62:
59:
22:
13:
10:
9:
6:
4:
3:
2:
1260:
1249:
1246:
1244:
1241:
1239:
1236:
1234:
1231:
1229:
1226:
1224:
1221:
1219:
1216:
1214:
1211:
1209:
1206:
1204:
1201:
1199:
1196:
1194:
1191:
1190:
1188:
1176:
1170:
1166:
1162:
1156:
1153:
1149:
1144:
1141:
1137:
1131:
1127:
1123:
1116:
1113:
1108:
1104:
1100:
1096:
1089:
1086:
1080:
1075:
1068:
1064:
1060:
1056:
1052:
1048:
1041:
1038:
1034:
1030:
1025:
1020:
1016:
1012:
1011:
1006:
1002:
996:
994:
990:
986:
980:
976:
969:
966:
962:
958:
954:
950:
946:
942:
935:
931:
924:
921:
917:
911:
907:
900:
897:
893:
889:
885:
881:
880:
872:
869:
865:
859:
855:
851:
850:
845:
838:
835:
831:
825:
821:
814:
811:
806:
802:
795:
792:
780:
774:
771:
768:
764:
759:
756:
752:
746:
742:
741:
736:
732:
724:
721:
715:
707:
703:
699:
695:
691:
687:
680:
676:
672:
671:Graham, R. L.
668:
663:
659:
650:
646:
642:
638:
634:
630:
624:
620:
610:
604:
600:
591:
587:
583:
579:
575:
571:
567:
563:
557:
553:
544:
540:
536:
532:
531:
524:
520:
510:
505:
501:
497:
491:
487:
478:
472:
466:
462:
453:
449:
445:
441:
440:
433:
429:
423:
421:
419:
418:Jack van Lint
415:
411:
407:
406:combinatorics
403:
399:
395:
391:
390:Costas arrays
386:
383:
379:
375:
371:
363:
361:
358:
355:. By using a
354:
335:
320:
316:
308:
306:
304:
300:
296:
292:
289:
285:
281:
276:
271:
267:
263:
262:playing cards
260:
255:
251:
247:
243:
237:
230:
226:
222:
215:
211:
205:
198:
194:
190:
185:
181:
176:
171:
167:
166:random graphs
159:
157:
155:
151:
146:
144:
139:
135:
131:
127:
120:Coding theory
119:
114:
112:
110:
105:
103:
99:
95:
91:
88:
84:
80:
76:
72:
68:
60:
58:
56:
55:random graphs
52:
48:
44:
43:coding theory
40:
36:
32:
28:
19:
1164:
1155:
1143:
1125:
1115:
1098:
1094:
1088:
1050:
1046:
1040:
1014:
1008:
974:
968:
944:
940:
923:
905:
899:
883:
877:
871:
848:
837:
819:
813:
804:
800:
794:
783:. Retrieved
773:
758:
739:
723:
689:
685:
632:
628:
608:
565:
561:
534:
528:
499:
495:
470:
443:
437:
400:on counting
398:John Riordan
387:
382:flow network
378:network flow
367:
312:
293:
274:
256:
249:
245:
241:
235:
228:
224:
220:
216:− 1)/2
213:
209:
203:
196:
192:
188:
184:Alfréd Rényi
174:
163:
154:Markov chain
147:
123:
106:
93:
64:
26:
25:
1198:2013 deaths
1193:1923 births
1001:Bayer, Dave
928:Erdős, P.;
844:Pless, Vera
635:(1): 1–29,
562:SIAM Review
1187:Categories
785:2013-06-21
716:References
414:Ron Graham
180:Paul Erdős
1079:1005.0023
1067:119949515
961:253789267
930:RĂ©nyi, A.
807:: 739–741
410:Fan Chung
402:necklaces
259:shuffling
61:Biography
1163:(2001),
932:(2022),
677:(1982),
368:Gilbert
115:Research
90:antennas
1033:2959752
765:at the
706:2690096
649:2099400
590:2027267
570:Bibcode
372:on the
168:is the
138:maximal
81:at the
1171:
1132:
1065:
1031:
981:
959:
912:
860:
826:
747:
704:
647:
588:
416:, and
394:Costas
288:merged
264:, the
182:, and
45:, the
1074:arXiv
1063:S2CID
1029:JSTOR
957:S2CID
937:(PDF)
702:JSTOR
682:(PDF)
645:JSTOR
586:JSTOR
87:radar
1169:ISBN
1130:ISBN
979:ISBN
910:ISBN
858:ISBN
824:ISBN
745:ISBN
661:CGG.
622:G68.
602:G67.
555:G65.
522:G60.
489:G59.
464:G55.
431:G52.
148:The
124:The
53:for
1103:doi
1055:doi
1019:doi
949:doi
888:doi
854:541
805:117
694:doi
637:doi
578:doi
539:doi
504:doi
448:doi
404:in
351:of
321:in
41:in
1189::
1097:.
1070:;
1061:,
1049:,
1027:,
1013:,
1003:;
992:^
955:,
943:,
939:,
884:42
882:,
856:,
803:,
700:,
690:55
688:,
684:,
643:,
633:16
631:,
584:,
576:,
564:,
535:39
533:,
500:30
498:,
444:31
442:,
412:,
248:,
227:,
210:pn
195:,
111:.
57:.
1109:.
1105::
1099:9
1082:.
1076::
1057::
1051:8
1021::
1015:2
951::
945:6
890::
788:.
696::
639::
580::
572::
566:7
541::
506::
479:.
450::
336:2
331:R
275:n
252:)
250:p
246:n
244:(
242:G
236:M
231:)
229:M
225:n
223:(
221:G
214:n
212:(
204:p
199:)
197:p
193:n
191:(
189:G
175:n
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.