×

Menger’s theorem for infinite graphs. (English) Zbl 1216.05092

Summary: We prove that Menger’s theorem is valid for infinite graphs, in the following strong version: let \(A\) and \(B\) be two sets of vertices in a possibly infinite digraph. Then there exist a set \(\mathcal{P}\) of disjoint \(A-B\) paths, and a set \(S\) of vertices separating \(A\) from \(B\), such that \(S\) consists of a choice of precisely one vertex from each path in \(\mathcal{P}\). This settles an old conjecture of Erdős.

MSC:

05C63 Infinite graphs
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni, R.: Menger’s theorem for graphs containing no infinite paths. Eur. J. Comb. 4, 201–204 (1983) · Zbl 0525.05043
[2] Aharoni, R.: König’s duality theorem for infinite bipartite graphs. J. Lond. Math. Soc. 29, 1–12 (1984) · Zbl 0528.05047 · doi:10.1112/jlms/s2-29.1.1
[3] Aharoni, R.: Menger’s theorem for countable graphs. J. Comb. Theory, Ser. B 43, 303–313 (1987) · Zbl 0631.05032 · doi:10.1016/0095-8956(87)90006-2
[4] Aharoni, R.: Matchings in graphs of size 1. J. Comb. Theory, Ser. B 36, 113–117 (1984) · Zbl 0522.05054 · doi:10.1016/0095-8956(84)90017-0
[5] Aharoni, R.: Matchings in infinite graphs. J. Comb. Theory, Ser. B 44, 87–125 (1988) · Zbl 0642.05048 · doi:10.1016/0095-8956(88)90098-6
[6] Aharoni, R.: Linkability in countable-like webs. In: Hahn, G., Sabidussi, G., Woodrow, R.E. (eds.) Cycles and Rays: Proceedings of the NATO Advanced Research Workshop on ”Cycles and Rays: Basic Structures in Finite and Infinite Graphs”, held in Montreal, Canada, May 3–9, 1987, pp. 1–8. Springer (1987)
[7] Aharoni, R.: Infinite matching theory. Discrete Math. 95, 5–22 (1991) · Zbl 0763.05074 · doi:10.1016/0012-365X(91)90327-X
[8] Aharoni, R.: A few remarks on a conjecture of Erdos on the infinite version of Menger’s theorem. In: Graham, R.L., Nesteril, J. (eds.) The Mathematics of Paul Erdos, pp. 394–408. Springer, Berlin Heidelberg (1997) · Zbl 0870.05043
[9] Aharoni, R., Diestel, R.: Menger’s theorem for countable source sets. Comb. Probab. Comput. 3, 145–156 (1994) · Zbl 0817.05037 · doi:10.1017/S0963548300001073
[10] Aharoni, R., Korman, V.: Greene–Kleitman’s theorem for infinite posets. Order 9, 245–253 (1992) · Zbl 0766.06004 · doi:10.1007/BF00383948
[11] Aharoni, R., Nash-Williams, C.S.J., Shelah, S.: A general criterion for the existence of transversals. Proc. Lond. Math. Soc. 47, 43–68 (1983) · Zbl 0522.05002 · doi:10.1112/plms/s3-47.1.43
[12] Ahlswede, R., Khachatrian, L.H.: A counterexample to Aharoni’s strongly maximal matching conjecture. Discrete Math. 149, 289 (1996) · Zbl 0842.05094 · doi:10.1016/0012-365X(95)00243-P
[13] Damerell, M.R., Milner, E.C.: Necessary and sufficient conditions for transversals of countable set systems. J. Comb. Theory, Ser. A 17, 350–374 (1974) · Zbl 0303.05004 · doi:10.1016/0097-3165(74)90100-9
[14] Diestel, R.: Graph Theory, 1st edn. Springer (1997) · Zbl 0873.05001
[15] Fodor, G.: Eine Bemerkung zur Theorie der regressive Funktionen. Acta Sci. Math. 17, 139–142 (1956) · Zbl 0072.04302
[16] Gallai, T.: Ein neuer Beweis eines Mengerschen Satzes. J. Lond. Math. Soc. 13, 188–192 (1938) · Zbl 0019.23701 · doi:10.1112/jlms/s1-13.3.188
[17] Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10, 26–30 (1935) · Zbl 0010.34503 · doi:10.1112/jlms/s1-10.37.26
[18] König, D.: Graphs and matrices. Mat. Fiz. Lapok 38, 116–119 (1931) (Hungarian) · JFM 57.1340.04
[19] König, D.: Theorie der endlichen und unendlichen Graphen. Akademischen Verlagsgesellschaft, Leipzig (1936) (Reprinted: Chelsea, New York, 1950) · JFM 62.0654.05
[20] Lovász, L., Plummer, M.D.: Matching Theory. Ann. Math., vol. 29. North Holland (1991) · Zbl 0618.05001
[21] McDiarmid, C.: On separated separating sets and Menger’s theorem. Congr. Numerantium 15, 455–459 (1976) · Zbl 0326.05111
[22] Menger, K.: Zur allgemeinen Kurventhoerie. Fundam. Math. 10, 96–115 (1927) · JFM 53.0561.01
[23] Nash-Williams, C.S.J.A.: Infinite graphs – a survey. J. Comb. Theory 3, 286–301 (1967) · Zbl 0153.25801 · doi:10.1016/S0021-9800(67)80077-2
[24] Nash-Williams, C.S.J.A.: Which infinite set-systems have transversals? – A possible approach. In: Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 237–253. Inst. Math. Appl., Southend-on-Sea (1972)
[25] Nash-Williams, C.S.J.A.: Marriage in denumerable societies. J. Comb. Theory, Ser. A 19, 335–366 (1975) · Zbl 0311.05003 · doi:10.1016/0097-3165(75)90057-6
[26] Nash-Williams, C.S.J.A.: Another criterion for marriage in denumerable societies. In: Bollobás, B. (ed.) Advances in Graph Theory. Ann. Discrete Math., vol. 3, pp. 165–179. North-Holland, Amsterdam (1978) · Zbl 0393.05003
[27] Oellrich, H., Steffens, K.: On Dilworth’s decomposition theorem. Discrete Math. 15, 301–304 (1976) · Zbl 0339.06001 · doi:10.1016/0012-365X(76)90032-7
[28] Podewski, K.-P., Steffens, K.: Injective choice functions for countable families. J. Comb. Theory, Ser. B 21, 40–46 (1976) · Zbl 0357.04017 · doi:10.1016/0095-8956(76)90025-3
[29] Podewski, K.-P., Steffens, K.: Über Translationen und der Satz von Menger in unendlichen Graphen. Acta Math. Hung. 30, 69–84 (1977) · Zbl 0382.05038 · doi:10.1007/BF01895650
[30] Fiedler, M.: Theory of graphs and its applications. In: Proceedings of the Symposium held in Smolenice, June 1963. Czechoslovak Academy of Sciences, Prague (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.