43:
603:
594:. Intuitively, if the Cheeger constant is small but positive, then there exists a "bottleneck", in the sense that there are two "large" sets of vertices with "few" links (edges) between them. The Cheeger constant is "large" if any possible division of the vertex set into two subsets has "many" links between those two subsets.
866:
1109:
1224:
578:
1254:, and this is highly undesirable in practical terms. We would only need one of the computers on the ring to fail, and network performance would be greatly reduced. If two non-adjacent computers were to fail, the network would split into two disconnected components.
987:
656:
998:
332:
1354:
119:
is a numerical measure of whether or not a graph has a "bottleneck". The
Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected
910:
1120:
412:
661:
610:
In applications to theoretical computer science, one wishes to devise network configurations for which the
Cheeger constant is high (at least, bounded away from zero) even when
385:
1386:
1426:
1406:
1582:
Donetti, Luca; Neri, Franco; Muñoz, Miguel A (2006-08-07). "Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that".
918:
861:{\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}
1104:{\displaystyle \partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},}
227:
1276:
1702:
86:
64:
1219:{\displaystyle {\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ as }}N\to \infty .}
878:
573:{\displaystyle h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.}
116:
1469:
591:
1464:
1707:
57:
51:
30:
This article is about the
Cheeger constant in graph theory. For a different use in Riemannian geometry, see
1454:
68:
1449:
1437:
1656:
1601:
340:
136:
121:
1553:
Montenegro, Ravi; Tetali, Prasad (2006). "Mathematical
Aspects of Mixing Times in Markov Chains".
1680:
1646:
1625:
1591:
1362:
1637:
Lackenby, Marc (2006). "Heegaard splittings, the virtually Haken conjecture and
Property (τ)".
1672:
1617:
1570:
1411:
1664:
1609:
1562:
1539:
1433:
129:
31:
1613:
1263:
650:
clockwise around the ring. Mathematically, the vertex set and the edge set are given by:
1660:
1605:
982:{\displaystyle A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.}
1474:
1391:
1267:
584:
1696:
1544:
1527:
1459:
143:
133:
1684:
1629:
602:
17:
1429:
626:
146:
1250:. Consequently, we would regard a ring network as highly "bottlenecked" for large
1523:
1436:
of the graph. The
Cheeger inequality is a fundamental result and motivation for
1270:
relate the eigenvalue gap of a graph with its
Cheeger constant. More explicitly
327:{\displaystyle \partial A:=\{\{x,y\}\in E(G)\ :\ x\in A,y\in V(G)\setminus A\}.}
100:
1668:
1676:
1621:
1574:
125:
1596:
1566:
1266:
as it is a way to measure the edge expansion of a graph. The so-called
1349:{\displaystyle 2h(G)\geq \lambda \geq {\frac {h^{2}(G)}{2\Delta (G)}}}
1651:
601:
1262:
The
Cheeger constant is especially important in the context of
1229:
This example provides an upper bound for the
Cheeger constant
36:
905:{\displaystyle \left\lfloor {\tfrac {N}{2}}\right\rfloor }
205:
denote the collection of all edges going from a vertex in
1584:
Journal of
Statistical Mechanics: Theory and Experiment
1555:
Foundations and Trends in Theoretical Computer Science
1198:
1174:
1049:
1026:
956:
887:
529:
1414:
1394:
1365:
1279:
1123:
1001:
921:
881:
659:
415:
343:
230:
128:. The graph theoretical notion originated after the
27:
Measure of whether or not a graph has a "bottleneck"
622:(the number of computers in the network) is large.
1420:
1400:
1380:
1348:
1218:
1103:
981:
904:
860:
572:
379:
326:
1505:
431:
161:be an undirected finite graph with vertex set
849:
761:
8:
1090:
1078:
844:
832:
826:
808:
796:
784:
778:
766:
726:
690:
374:
362:
356:
344:
318:
255:
243:
240:
583:The Cheeger constant is strictly positive
1650:
1595:
1543:
1532:Journal of Combinatorial Theory, Series B
1413:
1393:
1364:
1311:
1304:
1278:
1197:
1173:
1164:
1153:
1145:
1138:
1127:
1124:
1122:
1048:
1025:
1000:
955:
920:
912:of these computers in a connected chain:
886:
880:
848:
847:
760:
759:
743:
674:
660:
658:
557:
540:
528:
520:
512:
468:
460:
453:
442:
439:
414:
342:
337:Note that the edges are unordered, i.e.,
229:
87:Learn how and when to remove this message
142:The Cheeger constant is named after the
50:This article includes a list of general
1486:
1388:is the maximum degree for the nodes in
312:
1493:
7:
1366:
1331:
1210:
1132:
1002:
447:
231:
56:it lacks sufficient corresponding
25:
1528:"Isoperimetric numbers of graphs"
636:computers, thought of as a graph
1614:10.1088/1742-5468/2006/08/P08007
41:
380:{\displaystyle \{x,y\}=\{y,x\}}
183:. For a collection of vertices
1375:
1369:
1340:
1334:
1323:
1317:
1292:
1286:
1243:, which also tends to zero as
1207:
1191:
1154:
1146:
1139:
1128:
749:
736:
680:
667:
558:
554:
548:
541:
521:
513:
500:
494:
469:
461:
454:
443:
425:
419:
309:
303:
270:
264:
130:Cheeger isoperimetric constant
1:
1545:10.1016/0095-8956(89)90029-4
1506:Montenegro & Tetali 2006
598:Example: computer networking
1724:
1381:{\displaystyle \Delta (G)}
29:
1703:Computer network analysis
1669:10.1007/s00222-005-0480-x
1639:Inventiones mathematicae
1421:{\displaystyle \lambda }
625:For example, consider a
643:. Number the computers
209:to a vertex outside of
71:more precise citations.
1455:Algebraic connectivity
1422:
1402:
1382:
1350:
1220:
1105:
983:
906:
875:to be a collection of
862:
607:
574:
381:
328:
213:(sometimes called the
1590:(08): P08007–P08007.
1450:Spectral graph theory
1438:spectral graph theory
1423:
1403:
1383:
1351:
1221:
1106:
984:
907:
863:
605:
575:
382:
329:
122:networks of computers
1412:
1392:
1363:
1277:
1268:Cheeger inequalities
1258:Cheeger Inequalities
1121:
999:
919:
879:
657:
413:
341:
228:
113:isoperimetric number
18:Isoperimetric number
1661:2006InMat.164..317L
1606:2006JSMTE..08..007D
1508:, pp. 237–354.
1496:, pp. 274–291.
606:Ring network layout
137:Riemannian manifold
1567:10.1561/0400000003
1418:
1398:
1378:
1346:
1216:
1202:
1183:
1101:
1058:
1035:
979:
965:
902:
896:
858:
856:
608:
570:
538:
377:
324:
1401:{\displaystyle G}
1344:
1201:
1189:
1182:
1159:
1057:
1034:
964:
895:
537:
484:
478:
474:
281:
275:
97:
96:
89:
16:(Redirected from
1715:
1708:Graph invariants
1688:
1654:
1633:
1599:
1597:cond-mat/0605565
1578:
1549:
1547:
1509:
1503:
1497:
1491:
1434:Laplacian matrix
1427:
1425:
1424:
1419:
1407:
1405:
1404:
1399:
1387:
1385:
1384:
1379:
1355:
1353:
1352:
1347:
1345:
1343:
1326:
1316:
1315:
1305:
1253:
1249:
1242:
1225:
1223:
1222:
1217:
1203:
1199:
1190:
1188:
1184:
1175:
1165:
1160:
1158:
1157:
1149:
1143:
1142:
1131:
1125:
1110:
1108:
1107:
1102:
1097:
1093:
1074:
1070:
1063:
1059:
1050:
1040:
1036:
1027:
988:
986:
985:
980:
975:
971:
970:
966:
957:
911:
909:
908:
903:
901:
897:
888:
874:
867:
865:
864:
859:
857:
853:
852:
765:
764:
748:
747:
679:
678:
649:
642:
635:
621:
589:
579:
577:
576:
571:
566:
562:
561:
544:
539:
530:
524:
516:
482:
476:
475:
473:
472:
464:
458:
457:
446:
440:
406:, is defined by
405:
394:
389:Cheeger constant
386:
384:
383:
378:
333:
331:
330:
325:
279:
273:
220:
212:
208:
204:
197:
182:
171:
160:
105:Cheeger constant
92:
85:
81:
78:
72:
67:this article by
58:inline citations
45:
44:
37:
32:Cheeger constant
21:
1723:
1722:
1718:
1717:
1716:
1714:
1713:
1712:
1693:
1692:
1691:
1636:
1581:
1552:
1522:
1518:
1513:
1512:
1504:
1500:
1492:
1488:
1483:
1446:
1410:
1409:
1390:
1389:
1361:
1360:
1327:
1307:
1306:
1275:
1274:
1264:expander graphs
1260:
1251:
1244:
1239:
1230:
1169:
1144:
1126:
1119:
1118:
1044:
1021:
1020:
1016:
1015:
1011:
997:
996:
951:
932:
928:
917:
916:
882:
877:
876:
872:
855:
854:
752:
739:
730:
729:
683:
670:
655:
654:
644:
641:
637:
630:
611:
600:
592:connected graph
587:
459:
441:
438:
434:
411:
410:
396:
392:
339:
338:
226:
225:
218:
210:
206:
199:
184:
173:
162:
158:
155:
93:
82:
76:
73:
63:Please help to
62:
46:
42:
35:
28:
23:
22:
15:
12:
11:
5:
1721:
1719:
1711:
1710:
1705:
1695:
1694:
1690:
1689:
1645:(2): 317–359.
1634:
1579:
1561:(3): 237–354.
1550:
1538:(3): 274–291.
1519:
1517:
1514:
1511:
1510:
1498:
1485:
1484:
1482:
1479:
1478:
1477:
1475:Expander graph
1472:
1467:
1462:
1457:
1452:
1445:
1442:
1417:
1397:
1377:
1374:
1371:
1368:
1357:
1356:
1342:
1339:
1336:
1333:
1330:
1325:
1322:
1319:
1314:
1310:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1259:
1256:
1237:
1227:
1226:
1215:
1212:
1209:
1206:
1200: as
1196:
1193:
1187:
1181:
1178:
1172:
1168:
1163:
1156:
1152:
1148:
1141:
1137:
1134:
1130:
1112:
1111:
1100:
1096:
1092:
1089:
1086:
1083:
1080:
1077:
1073:
1069:
1066:
1062:
1056:
1053:
1047:
1043:
1039:
1033:
1030:
1024:
1019:
1014:
1010:
1007:
1004:
990:
989:
978:
974:
969:
963:
960:
954:
950:
947:
944:
941:
938:
935:
931:
927:
924:
900:
894:
891:
885:
869:
868:
851:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
763:
758:
755:
753:
751:
746:
742:
738:
735:
732:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
684:
682:
677:
673:
669:
666:
663:
662:
639:
599:
596:
585:if and only if
581:
580:
569:
565:
560:
556:
553:
550:
547:
543:
536:
533:
527:
523:
519:
515:
511:
508:
505:
502:
499:
496:
493:
490:
487:
481:
471:
467:
463:
456:
452:
449:
445:
437:
433:
430:
427:
424:
421:
418:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
335:
334:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
278:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
154:
151:
126:card shuffling
109:Cheeger number
95:
94:
49:
47:
40:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1720:
1709:
1706:
1704:
1701:
1700:
1698:
1686:
1682:
1678:
1674:
1670:
1666:
1662:
1658:
1653:
1648:
1644:
1640:
1635:
1631:
1627:
1623:
1619:
1615:
1611:
1607:
1603:
1598:
1593:
1589:
1585:
1580:
1576:
1572:
1568:
1564:
1560:
1556:
1551:
1546:
1541:
1537:
1533:
1529:
1525:
1521:
1520:
1515:
1507:
1502:
1499:
1495:
1490:
1487:
1480:
1476:
1473:
1471:
1468:
1466:
1463:
1461:
1460:Cheeger bound
1458:
1456:
1453:
1451:
1448:
1447:
1443:
1441:
1439:
1435:
1431:
1415:
1395:
1372:
1337:
1328:
1320:
1312:
1308:
1301:
1298:
1295:
1289:
1283:
1280:
1273:
1272:
1271:
1269:
1265:
1257:
1255:
1247:
1240:
1233:
1213:
1204:
1194:
1185:
1179:
1176:
1170:
1166:
1161:
1150:
1135:
1117:
1116:
1115:
1098:
1094:
1087:
1084:
1081:
1075:
1071:
1067:
1064:
1060:
1054:
1051:
1045:
1041:
1037:
1031:
1028:
1022:
1017:
1012:
1008:
1005:
995:
994:
993:
976:
972:
967:
961:
958:
952:
948:
945:
942:
939:
936:
933:
929:
925:
922:
915:
914:
913:
898:
892:
889:
883:
841:
838:
835:
829:
823:
820:
817:
814:
811:
805:
802:
799:
793:
790:
787:
781:
775:
772:
769:
756:
754:
744:
740:
733:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
687:
685:
675:
671:
664:
653:
652:
651:
648:
633:
628:
623:
619:
615:
604:
597:
595:
593:
586:
567:
563:
551:
545:
534:
531:
525:
517:
509:
506:
503:
497:
491:
488:
485:
479:
465:
450:
435:
428:
422:
416:
409:
408:
407:
403:
399:
390:
371:
368:
365:
359:
353:
350:
347:
321:
315:
306:
300:
297:
294:
291:
288:
285:
282:
276:
267:
261:
258:
252:
249:
246:
237:
234:
224:
223:
222:
216:
215:edge boundary
203:
195:
191:
187:
180:
176:
172:and edge set
169:
165:
152:
150:
148:
145:
144:mathematician
140:
138:
135:
131:
127:
123:
118:
114:
110:
106:
102:
91:
88:
80:
77:February 2013
70:
66:
60:
59:
53:
48:
39:
38:
33:
19:
1652:math/0205327
1642:
1638:
1587:
1583:
1558:
1554:
1535:
1531:
1524:Mohar, Bojan
1501:
1489:
1470:Connectivity
1430:spectral gap
1358:
1261:
1245:
1235:
1231:
1228:
1113:
991:
870:
646:
631:
627:ring network
624:
617:
613:
609:
582:
401:
397:
388:
336:
214:
201:
193:
189:
185:
178:
174:
167:
163:
156:
147:Jeff Cheeger
141:
112:
108:
104:
98:
83:
74:
55:
1465:Conductance
645:1, 2, ...,
101:mathematics
69:introducing
1697:Categories
1516:References
1494:Mohar 1989
395:, denoted
153:Definition
52:references
1677:0020-9910
1622:1742-5468
1575:1551-305X
1416:λ
1367:Δ
1359:in which
1332:Δ
1302:≥
1299:λ
1296:≥
1211:∞
1208:→
1192:→
1133:∂
1003:∂
946:⋯
815:−
803:⋯
715:−
706:⋯
526:≤
489:⊆
448:∂
313:∖
298:∈
286:∈
259:∈
232:∂
1685:12847770
1630:16192273
1526:(1989).
1444:See also
1186:⌋
1171:⌊
1061:⌋
1046:⌊
1038:⌋
1023:⌊
968:⌋
953:⌊
899:⌋
884:⌊
1657:Bibcode
1602:Bibcode
1432:of the
1428:is the
134:compact
115:) of a
65:improve
1683:
1675:
1628:
1620:
1573:
483:
477:
387:. The
280:
274:
198:, let
107:(also
103:, the
54:, but
1681:S2CID
1647:arXiv
1626:S2CID
1592:arXiv
1481:Notes
871:Take
590:is a
132:of a
117:graph
1673:ISSN
1618:ISSN
1588:2006
1571:ISSN
1408:and
1114:and
992:So,
510:<
157:Let
1665:doi
1643:164
1610:doi
1563:doi
1540:doi
1248:→ ∞
634:≥ 3
629:of
432:min
391:of
221:):
217:of
111:or
99:In
1699::
1679:.
1671:.
1663:.
1655:.
1641:.
1624:.
1616:.
1608:.
1600:.
1586:.
1569:.
1557:.
1536:47
1534:.
1530:.
1440:.
620:)|
429::=
238::=
188:⊆
149:.
139:.
124:,
1687:.
1667::
1659::
1649::
1632:.
1612::
1604::
1594::
1577:.
1565::
1559:1
1548:.
1542::
1396:G
1376:)
1373:G
1370:(
1341:)
1338:G
1335:(
1329:2
1324:)
1321:G
1318:(
1313:2
1309:h
1293:)
1290:G
1287:(
1284:h
1281:2
1252:N
1246:N
1241:)
1238:N
1236:G
1234:(
1232:h
1214:.
1205:N
1195:0
1180:2
1177:N
1167:2
1162:=
1155:|
1151:A
1147:|
1140:|
1136:A
1129:|
1099:,
1095:}
1091:}
1088:1
1085:,
1082:N
1079:{
1076:,
1072:}
1068:1
1065:+
1055:2
1052:N
1042:,
1032:2
1029:N
1018:{
1013:{
1009:=
1006:A
977:.
973:}
962:2
959:N
949:,
943:,
940:2
937:,
934:1
930:{
926:=
923:A
893:2
890:N
873:A
850:}
845:}
842:1
839:,
836:N
833:{
830:,
827:}
824:N
821:,
818:1
812:N
809:{
806:,
800:,
797:}
794:3
791:,
788:2
785:{
782:,
779:}
776:2
773:,
770:1
767:{
762:{
757:=
750:)
745:N
741:G
737:(
734:E
727:}
724:N
721:,
718:1
712:N
709:,
703:,
700:2
697:,
694:1
691:{
688:=
681:)
676:N
672:G
668:(
665:V
647:N
640:N
638:G
632:N
618:G
616:(
614:V
612:|
588:G
568:.
564:}
559:|
555:)
552:G
549:(
546:V
542:|
535:2
532:1
522:|
518:A
514:|
507:0
504:,
501:)
498:G
495:(
492:V
486:A
480::
470:|
466:A
462:|
455:|
451:A
444:|
436:{
426:)
423:G
420:(
417:h
404:)
402:G
400:(
398:h
393:G
375:}
372:x
369:,
366:y
363:{
360:=
357:}
354:y
351:,
348:x
345:{
322:.
319:}
316:A
310:)
307:G
304:(
301:V
295:y
292:,
289:A
283:x
277::
271:)
268:G
265:(
262:E
256:}
253:y
250:,
247:x
244:{
241:{
235:A
219:A
211:A
207:A
202:A
200:∂
196:)
194:G
192:(
190:V
186:A
181:)
179:G
177:(
175:E
170:)
168:G
166:(
164:V
159:G
90:)
84:(
79:)
75:(
61:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
