1391:. The result that graphs of uncountable chromatic number contain an infinite half graph is credited in this paper to Hajnal and cited to a 1973 paper of the same authors with Shelah, but that paper states the result only in the weaker form that graphs of uncountable chromatic number contain complete bipartite graphs where one side is any finite number and the other side is infinite.
20:
1111:
1185:. Intuitively, the existence of these half graphs allows one to construct infinite ordered sets within the model. The unstable formula theorem states that a complete theory is stable if and only if it does not have the order property.
536:. Half-graphs are a special case of the bipartite chain graphs (bipartite graphs in which, on each side of the bipartition, the vertices can be ordered by neighborhood inclusion), which are in turn a special case of the bipartite
255:
The same concept can also be defined in the same way for infinite graphs over two copies of any ordered set of vertices. The half graph over the natural numbers (with their usual ordering) has the property that each vertex
647:, which states that the vertices of any graph can be partitioned into a constant number of subsets of equal size, such that most pairs of subsets are regular (the edges connecting the pair behave in certain ways like a
1542:
Agrawal, Akanksha; Allumalla, Ravi Kiran; Dhanekula, Varun Teja (2021), "Refuting FPT algorithms for some parameterized problems under Gap-ETH", in
Golovach, Petr A.; Zehavi, Meirav (eds.),
979:
844:
170:
127:
1201:
algorithm for finding a half-graph of a given size in a larger bipartite graph, either as a subgraph or an induced subgraph, when parameterized by the size of the half-graph.
1183:
1147:
974:
938:
691:. Therefore, it is not possible to strengthen the regularity lemma to show the existence of a partition for which all pairs are regular. On the other hand, for any integer
1463:
902:
873:
250:
608:
581:
534:
507:
480:
453:
426:
399:
372:
345:
281:
224:
197:
732:
84:
791:
709:
689:
669:
305:
610:, and the remaining vertices form another half graph. More strongly, every bipartite graph with a unique perfect matching is a subgraph of a half graph.
482:. If two vertices on opposite sides of the bipartition are not adjacent (at distance one), then they are at distance three via a path through both
1571:
1514:, Studies in Logic and the Foundations of Mathematics, vol. 92 (2nd ed.), Amsterdam: North-Holland Publishing Co., pp. 30–31,
1519:
1410:
1249:
626:, then the graph necessarily contains as a subgraph a half graph on the natural numbers. This half graph, in turn, contains every
1225:(1984), "Some combinatorial, geometric and set theoretic problems in measure theory", in Kölzow, D.; Maharam-Stone, D. (eds.),
1364:
644:
1544:
16th
International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8–10, 2021, Lisbon, Portugal
1194:
1106:{\displaystyle {\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i})\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}}
796:
1198:
537:
627:
44:
1240:
769:) by the nonexistence of countably infinite half graphs. Shelah defines a complete theory as having the
284:
132:
89:
1152:
1116:
943:
907:
1454:
766:
1472:
1419:
1258:
43:. These graphs are called the half graphs because they have approximately half of the edges of a
878:
849:
1546:, LIPIcs, vol. 214, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 2:1–2:12,
1515:
229:
1547:
1482:
1429:
1373:
1352:
1330:
1268:
735:
619:
553:
541:
52:
1529:
1494:
1441:
1387:
1280:
586:
559:
512:
485:
458:
431:
404:
377:
350:
323:
259:
202:
175:
1525:
1490:
1437:
1383:
1276:
762:
40:
630:
in which one side of the bipartition is finite and the other side is countably infinite.
320:
In a half graph, every two vertices are at distance one, two, or three. Any two vertices
714:
66:
1507:
1458:
1244:
776:
746:
694:
674:
654:
290:
1272:
1565:
1378:
1348:
1321:
1222:
758:
48:
1486:
1293:
1401:
1316:
754:
648:
28:
623:
32:
1552:
651:
of some particular density). If the half graph is partitioned in this way into
1433:
1356:
1405:
19:
307:. The vertices on the other side of the bipartition have infinite degree.
738:
obey a stronger version of the regularity lemma with no irregular pairs.
544:
of a half-graph, the distances are the same as in the half-graph itself.
540:. Thus, half-graphs are distance-hereditary. That is, in every connected
671:
subsets, the number of irregular pairs will be at least proportional to
1334:
1263:
1477:
1424:
18:
1357:"Chromatic number of finite and infinite graphs and hypergraphs"
1512:
Classification theory and the number of nonisomorphic models
47:
on the same vertices. The name was given to these graphs by
1408:(2012), "Bounds for graph regularity and removal lemmas",
1298:
Information System on Graph
Classes and their Inclusions
1229:, Lecture Notes in Mathematics, vol. 1089, Springer
1155:
1119:
1113:
form the edges of a countable half graph on vertices
982:
946:
910:
881:
852:
799:
779:
717:
697:
677:
657:
589:
562:
515:
488:
461:
434:
407:
380:
353:
326:
293:
262:
232:
205:
178:
135:
92:
69:
1177:
1141:
1105:
968:
932:
896:
867:
838:
785:
726:
703:
683:
663:
602:
575:
528:
501:
474:
447:
420:
393:
366:
339:
299:
275:
244:
218:
191:
164:
121:
78:
1464:Transactions of the American Mathematical Society
643:One application for the half graph occurs in the
1461:(2014), "Regularity lemmas for stable graphs",
556:. This is straightforward to see by induction:
1098:
985:
8:
1247:(2003), "On the order of countable graphs",
839:{\displaystyle \phi ({\bar {x}},{\bar {y}})}
1551:
1476:
1423:
1377:
1262:
1169:
1158:
1157:
1154:
1133:
1122:
1121:
1118:
1097:
1096:
1087:
1076:
1075:
1065:
1054:
1053:
1028:
1017:
1016:
1006:
995:
994:
984:
983:
981:
960:
949:
948:
945:
924:
913:
912:
909:
883:
882:
880:
854:
853:
851:
822:
821:
807:
806:
798:
778:
716:
696:
676:
656:
614:In graphs of uncountable chromatic number
594:
588:
567:
561:
520:
514:
493:
487:
466:
460:
439:
433:
412:
406:
385:
379:
358:
352:
331:
325:
292:
267:
261:
231:
210:
204:
183:
177:
156:
140:
134:
113:
97:
91:
68:
976:for these variables such that the pairs
904:, and a system of countably many values
1209:
846:on two finite tuples of free variables
455:are at distance two via a path through
374:are at distance two via a path through
583:must be matched to its only neighbor,
7:
1217:
1215:
1213:
14:
1411:Geometric and Functional Analysis
1250:European Journal of Combinatorics
165:{\displaystyle v_{1},\dots v_{n}}
122:{\displaystyle u_{1},\dots u_{n}}
711:, the graphs that do not have a
1487:10.1090/S0002-9947-2013-05820-5
1227:Measure Theory Oberwolfach 1983
1338:. See in particular Lemma 2.1.
1178:{\displaystyle {\bar {y}}_{i}}
1163:
1142:{\displaystyle {\bar {x}}_{i}}
1127:
1093:
1081:
1059:
1049:
1034:
1022:
1000:
990:
969:{\displaystyle {\bar {y}}_{i}}
954:
933:{\displaystyle {\bar {x}}_{i}}
918:
888:
859:
833:
827:
812:
803:
1:
1572:Parametric families of graphs
1319:(1985), "Inverses of trees",
1273:10.1016/S0195-6698(03)00064-7
1379:10.1016/0012-365X(85)90148-7
552:The half graph has a unique
63:To define the half graph on
16:Type of graph in mathematics
1195:exponential time hypothesis
1588:
1553:10.4230/LIPIcs.IPEC.2021.2
897:{\displaystyle {\bar {y}}}
868:{\displaystyle {\bar {x}}}
645:Szemerédi regularity lemma
538:distance-hereditary graphs
1434:10.1007/s00039-012-0171-x
1199:fixed-parameter tractable
793:of the theory, a formula
734:-vertex half graph as an
1189:Computational complexity
751:unstable formula theorem
628:complete bipartite graph
45:complete bipartite graph
773:if there exist a model
401:, and any two vertices
245:{\displaystyle i\leq j}
1179:
1143:
1107:
970:
934:
898:
869:
840:
787:
728:
705:
685:
665:
604:
577:
530:
503:
476:
449:
422:
395:
368:
341:
301:
277:
246:
220:
193:
166:
123:
80:
24:
23:A 14-vertex half graph
1180:
1144:
1108:
971:
935:
899:
870:
841:
788:
729:
706:
686:
666:
605:
603:{\displaystyle v_{n}}
578:
576:{\displaystyle u_{n}}
531:
529:{\displaystyle v_{n}}
504:
502:{\displaystyle u_{1}}
477:
475:{\displaystyle u_{1}}
450:
448:{\displaystyle v_{j}}
423:
421:{\displaystyle v_{i}}
396:
394:{\displaystyle v_{n}}
369:
367:{\displaystyle u_{j}}
342:
340:{\displaystyle u_{i}}
302:
278:
276:{\displaystyle v_{j}}
247:
221:
219:{\displaystyle v_{j}}
194:
192:{\displaystyle u_{i}}
167:
124:
81:
39:is a special type of
22:
1365:Discrete Mathematics
1193:Under a form of the
1153:
1117:
980:
944:
908:
879:
850:
797:
777:
715:
695:
675:
655:
587:
560:
513:
486:
459:
432:
405:
378:
351:
324:
291:
260:
230:
226:by an edge whenever
203:
176:
133:
90:
67:
1335:10.1007/bf02579440
1241:Nešetřil, Jaroslav
1175:
1139:
1103:
966:
930:
894:
865:
836:
783:
757:characterizes the
727:{\displaystyle 2k}
724:
701:
681:
661:
600:
573:
526:
499:
472:
445:
418:
391:
364:
337:
297:
273:
242:
216:
189:
162:
119:
79:{\displaystyle 2n}
76:
25:
1166:
1130:
1084:
1062:
1025:
1003:
957:
921:
891:
862:
830:
815:
786:{\displaystyle M}
763:complete theories
704:{\displaystyle k}
684:{\displaystyle k}
664:{\displaystyle k}
300:{\displaystyle j}
1579:
1557:
1556:
1555:
1539:
1533:
1532:
1504:
1498:
1497:
1480:
1471:(3): 1551–1585,
1451:
1445:
1444:
1427:
1418:(5): 1191–1256,
1398:
1392:
1390:
1381:
1361:
1345:
1339:
1337:
1313:
1307:
1306:
1305:
1304:
1290:
1284:
1283:
1266:
1237:
1231:
1230:
1219:
1184:
1182:
1181:
1176:
1174:
1173:
1168:
1167:
1159:
1148:
1146:
1145:
1140:
1138:
1137:
1132:
1131:
1123:
1112:
1110:
1109:
1104:
1102:
1101:
1092:
1091:
1086:
1085:
1077:
1070:
1069:
1064:
1063:
1055:
1033:
1032:
1027:
1026:
1018:
1011:
1010:
1005:
1004:
996:
989:
988:
975:
973:
972:
967:
965:
964:
959:
958:
950:
939:
937:
936:
931:
929:
928:
923:
922:
914:
903:
901:
900:
895:
893:
892:
884:
874:
872:
871:
866:
864:
863:
855:
845:
843:
842:
837:
832:
831:
823:
817:
816:
808:
792:
790:
789:
784:
736:induced subgraph
733:
731:
730:
725:
710:
708:
707:
702:
690:
688:
687:
682:
670:
668:
667:
662:
620:chromatic number
609:
607:
606:
601:
599:
598:
582:
580:
579:
574:
572:
571:
554:perfect matching
542:induced subgraph
535:
533:
532:
527:
525:
524:
508:
506:
505:
500:
498:
497:
481:
479:
478:
473:
471:
470:
454:
452:
451:
446:
444:
443:
427:
425:
424:
419:
417:
416:
400:
398:
397:
392:
390:
389:
373:
371:
370:
365:
363:
362:
346:
344:
343:
338:
336:
335:
306:
304:
303:
298:
282:
280:
279:
274:
272:
271:
251:
249:
248:
243:
225:
223:
222:
217:
215:
214:
198:
196:
195:
190:
188:
187:
171:
169:
168:
163:
161:
160:
145:
144:
128:
126:
125:
120:
118:
117:
102:
101:
85:
83:
82:
77:
1587:
1586:
1582:
1581:
1580:
1578:
1577:
1576:
1562:
1561:
1560:
1541:
1540:
1536:
1522:
1506:
1505:
1501:
1453:
1452:
1448:
1400:
1399:
1395:
1359:
1347:
1346:
1342:
1315:
1314:
1310:
1302:
1300:
1292:
1291:
1287:
1245:Shelah, Saharon
1239:
1238:
1234:
1221:
1220:
1211:
1207:
1191:
1156:
1151:
1150:
1120:
1115:
1114:
1074:
1052:
1015:
993:
978:
977:
947:
942:
941:
911:
906:
905:
877:
876:
848:
847:
795:
794:
775:
774:
759:stable theories
744:
713:
712:
693:
692:
673:
672:
653:
652:
641:
636:
616:
590:
585:
584:
563:
558:
557:
550:
516:
511:
510:
489:
484:
483:
462:
457:
456:
435:
430:
429:
408:
403:
402:
381:
376:
375:
354:
349:
348:
327:
322:
321:
318:
313:
289:
288:
263:
258:
257:
228:
227:
206:
201:
200:
179:
174:
173:
152:
136:
131:
130:
109:
93:
88:
87:
65:
64:
61:
41:bipartite graph
17:
12:
11:
5:
1585:
1583:
1575:
1574:
1564:
1563:
1559:
1558:
1534:
1520:
1499:
1446:
1393:
1353:Hajnal, András
1340:
1308:
1285:
1257:(6): 649–663,
1232:
1208:
1206:
1203:
1197:, there is no
1190:
1187:
1172:
1165:
1162:
1136:
1129:
1126:
1100:
1095:
1090:
1083:
1080:
1073:
1068:
1061:
1058:
1051:
1048:
1045:
1042:
1039:
1036:
1031:
1024:
1021:
1014:
1009:
1002:
999:
992:
987:
963:
956:
953:
927:
920:
917:
890:
887:
861:
858:
835:
829:
826:
820:
814:
811:
805:
802:
782:
771:order property
765:that have few
747:Saharon Shelah
743:
740:
723:
720:
700:
680:
660:
640:
637:
635:
632:
622:of a graph is
615:
612:
597:
593:
570:
566:
549:
546:
523:
519:
496:
492:
469:
465:
442:
438:
415:
411:
388:
384:
361:
357:
334:
330:
317:
314:
312:
309:
296:
270:
266:
241:
238:
235:
213:
209:
186:
182:
159:
155:
151:
148:
143:
139:
116:
112:
108:
105:
100:
96:
75:
72:
60:
57:
31:, a branch of
15:
13:
10:
9:
6:
4:
3:
2:
1584:
1573:
1570:
1569:
1567:
1554:
1549:
1545:
1538:
1535:
1531:
1527:
1523:
1521:0-444-70260-1
1517:
1513:
1509:
1503:
1500:
1496:
1492:
1488:
1484:
1479:
1474:
1470:
1466:
1465:
1460:
1456:
1455:Malliaris, M.
1450:
1447:
1443:
1439:
1435:
1431:
1426:
1421:
1417:
1413:
1412:
1407:
1403:
1402:Conlon, David
1397:
1394:
1389:
1385:
1380:
1375:
1371:
1367:
1366:
1358:
1354:
1350:
1344:
1341:
1336:
1332:
1328:
1324:
1323:
1322:Combinatorica
1318:
1317:Godsil, C. D.
1312:
1309:
1299:
1295:
1294:"Half graphs"
1289:
1286:
1282:
1278:
1274:
1270:
1265:
1260:
1256:
1252:
1251:
1246:
1242:
1236:
1233:
1228:
1224:
1218:
1216:
1214:
1210:
1204:
1202:
1200:
1196:
1188:
1186:
1170:
1160:
1134:
1124:
1088:
1078:
1071:
1066:
1056:
1046:
1043:
1040:
1037:
1029:
1019:
1012:
1007:
997:
961:
951:
925:
915:
885:
856:
824:
818:
809:
800:
780:
772:
768:
764:
760:
756:
752:
748:
741:
739:
737:
721:
718:
698:
678:
658:
650:
646:
638:
633:
631:
629:
625:
621:
613:
611:
595:
591:
568:
564:
555:
547:
545:
543:
539:
521:
517:
494:
490:
467:
463:
440:
436:
413:
409:
386:
382:
359:
355:
332:
328:
315:
310:
308:
294:
286:
268:
264:
253:
239:
236:
233:
211:
207:
184:
180:
157:
153:
149:
146:
141:
137:
114:
110:
106:
103:
98:
94:
73:
70:
58:
56:
54:
53:András Hajnal
50:
46:
42:
38:
34:
30:
21:
1543:
1537:
1511:
1502:
1468:
1462:
1449:
1415:
1409:
1396:
1369:
1363:
1343:
1329:(1): 33–39,
1326:
1320:
1311:
1301:, retrieved
1297:
1288:
1264:math/0404319
1254:
1248:
1235:
1226:
1192:
770:
755:model theory
750:
745:
649:random graph
642:
634:Applications
617:
551:
319:
254:
62:
36:
29:graph theory
26:
1372:: 281–285,
1349:Erdős, Paul
1223:Erdős, Paul
624:uncountable
283:has finite
33:mathematics
1508:Shelah, S.
1459:Shelah, S.
1406:Fox, Jacob
1303:2023-04-15
1205:References
639:Regularity
311:Properties
287:, at most
172:, connect
59:Definition
49:Paul Erdős
37:half graph
1478:1102.3904
1425:1107.4829
1164:¯
1128:¯
1082:¯
1060:¯
1047:ϕ
1044:⊨
1038:∣
1023:¯
1001:¯
955:¯
919:¯
889:¯
860:¯
828:¯
813:¯
801:ϕ
742:Stability
316:Distances
237:≤
150:…
107:…
86:vertices
1566:Category
1510:(1990),
1355:(1985),
548:Matching
1530:1083551
1495:3145742
1442:2989432
1388:0786496
1281:1995579
618:If the
1528:
1518:
1493:
1440:
1386:
1279:
285:degree
1473:arXiv
1420:arXiv
1360:(PDF)
1259:arXiv
767:types
1516:ISBN
1149:and
940:and
875:and
509:and
428:and
347:and
129:and
51:and
35:, a
1548:doi
1483:doi
1469:366
1430:doi
1374:doi
1331:doi
1269:doi
753:in
749:'s
199:to
27:In
1568::
1526:MR
1524:,
1491:MR
1489:,
1481:,
1467:,
1457:;
1438:MR
1436:,
1428:,
1416:22
1414:,
1404:;
1384:MR
1382:,
1370:53
1368:,
1362:,
1351:;
1325:,
1296:,
1277:MR
1275:,
1267:,
1255:24
1253:,
1243:;
1212:^
252:.
55:.
1550::
1485::
1475::
1432::
1422::
1376::
1333::
1327:5
1271::
1261::
1171:i
1161:y
1135:i
1125:x
1099:}
1094:)
1089:j
1079:y
1072:,
1067:i
1057:x
1050:(
1041:M
1035:)
1030:i
1020:y
1013:,
1008:i
998:x
991:(
986:{
962:i
952:y
926:i
916:x
886:y
857:x
834:)
825:y
819:,
810:x
804:(
781:M
761:(
722:k
719:2
699:k
679:k
659:k
596:n
592:v
569:n
565:u
522:n
518:v
495:1
491:u
468:1
464:u
441:j
437:v
414:i
410:v
387:n
383:v
360:j
356:u
333:i
329:u
295:j
269:j
265:v
240:j
234:i
212:j
208:v
185:i
181:u
158:n
154:v
147:,
142:1
138:v
115:n
111:u
104:,
99:1
95:u
74:n
71:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
