Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Set Theory and Infinite Combinatorics
abraham_1985_consistency_partition_theorems_continuous_colorings_structure/: Develops c.c.c. forcing techniques and proves consistency results for sets of reals of power aleph_1: MA with the open coloring axiom OCA, Baumgartner's axiom BA with 2^aleph_0 > aleph_2, and finite distributive lattices as the embeddability order of homogeneous aleph_1-dense order types, with a ZFC proof that MA + OCA implies 2^aleph_0 = aleph_2.
aharoni_2009_menger_s_theorem_infinite_graphs/: Proves the Erdos-Menger conjecture: in any digraph there is a family of disjoint A-B paths and a separating set picking one vertex from each path.
baumgartner_1987_remark_partition_relations_infinite_ordinals/: Proves in ZFC that (kappa^+)^2 -> (kappa^+ kappa, 3, 3)^2 for regular kappa with kappa^{<kappa} = kappa, and that 2^kappa = kappa^+ gives (kappa^+)^2 does not arrow (kappa^+ kappa, 4)^2, so omega_1^2 -> (omega_1 omega, 3, 3)^2 holds and CH forbids a four-clique target, the ZFC cases k <= 2 of Problem 1171; the paper is not held and its statements are taken from its zbMATH review.
baumgartner_1989_remarks_partition_ordinals/: Shows, under Martin's axiom for aleph_1 dense sets, that omega_1 omega and omega_1 omega^2 are partition ordinals, alpha -> (alpha, n)^2 for every finite n, the consistency input behind the not-disprovable status of Problem 1171; the chapter is not held and its statements are taken from its zbMATH review.
bowler_2024_note_uncountably_chromatic_graphs/: Gives a short elementary construction of a graph of chromatic number aleph one with no uncountable, infinitely connected subgraph.
chang_1972_partition_theorem_complete_graph_omega_omega/: Chang's 1972 proof of the partition relation ω^ω → (ω^ω, 3)^2: every red-blue coloring of the pairs from the ordinal ω^ω has a red triangle or a blue set of order type ω^ω, Problem 7 of the Erdős–Hajnal list; with the two problems it poses, ω^ω → (ω^ω, 4)^2 and ω^{ω^α} → (ω^{ω^α}, 3)^2 for countable α, and its note of Milner's and Larson's later results.
chen_2018_cardinal_characteristics_continuum_partitions/: Shows that small values of cardinal characteristics and the stick principle force many ordinary and polarized partition relations to fail.
erdos_1943_non_denumerable_graphs/: Shows the continuum hypothesis is equivalent to splitting the reals into countably many rationally independent sets.
erdos_1956_partition_calculus_set_theory/: Builds a systematic calculus of partition relations for cardinals and order types, generalizing Ramsey's theorem far beyond its original setting.
erdos_1958_structure_set_mappings/: Generalizes free-set theorems from point set-mappings to mappings defined on subsets, proving both positive and negative partition-type results.
erdos_1960_remarks_set_theory/: Proves independent pairs exist when each assigned picture set is null and not everywhere dense, and independent k-sets when the pictures are bounded with outer measure at most 1.
erdos_1964_interpolation_problem_associated_continuum_hypothesis/: Shows Wetzel's question, whether analytic functions taking countably many values at each point form a countable family, hinges on the continuum hypothesis.
erdos_1966_chromatic_number_graphs_set_systems/: Studies chromatic and coloring numbers of infinite graphs and set systems, forcing large even cycles and complete bipartite subgraphs.
erdos_1967_decomposition_graphs/: Develops the theory of vertex- and edge-decompositions of graphs into members with no large complete subgraph, no quadrilateral, or forests.
erdos_1970_set_mappings_polarized_partition_relations/: Proves that set mappings on certain ordered sets of power aleph_1 have free subsets of full order type, bounds these results by polarized partition relations, and derives an independent-set theorem for graphs without infinite paths.
erdos_1974_unsolved_solved_problems_set_theory/: Surveys progress on the authors' 1967 set-theory problem list and states many new partition, set-mapping and free-set problems.
erdos_1975_set_systems_having_large_chromatic_number/: Long study of which finite subsystems must occur in set systems of large chromatic number, with many constructions avoiding prescribed subsystems.
erdos_1987_problems_finite_infinite_graphs/: A problem list on infinite and finite graphs, covering partition relations, chromatic number, Folkman-type coloring questions and extremal problems.
folkman_1970_graphs_monochromatic_complete_subgraphs_every_edge/: Constructs graphs whose largest clique has size max(k1,k2) yet every two-coloring of their edges yields a red k1-clique or a blue k2-clique.
galvin_nd_pinning_countable_ordinals/: Characterizes exactly which countable ordinals can be pinned to omega cubed, answering a question of Specker on pinning maps.
gao_2026_finite_color_partition_relation_omega_1_squared/: Unrefereed, AI-assisted Zenodo deposit proving that Martin's axiom for aleph_1 dense sets implies the exact relation of Problem 1171 for every finite k, by a color-reduction lemma applied to Baumgartner's relation omega_1 omega -> (omega_1 omega, 3)^2; the site's partial proof claim, since withdrawn, that prompted its not-disprovable label.
garti_2019_first_omitting_cardinal_magidority/: Shows the first omitting cardinal for Magidority can be the successor of a supercompact cardinal, with related consistency results for singular cardinals.
garti_2025_problem_erdos_hajnal/: Proves the negative partition relation for successors of singular strong limit cardinals is consistent without GCH, addressing an Erdos-Hajnal question.
glazer_2026_erdos_problem_501_after_adding_random_reals/: Proves that adding omega_2 random reals to any model of ZFC plus CH gives a model in which every family of sets of outer measure below one has an infinite independent set, so the first question of Problem 501 is independent of ZFC; a self-published draft with a public Lean development.
koepke_1984_consistency_strength_free_subset_property_omega/: Shows the free-subset property for omega_omega is equiconsistent with the existence of a measurable cardinal.
komjath_1988_forcing_constructions_uncountably_chromatic_graphs/: Builds forcing models refuting the Erdos-Hajnal conjecture that every uncountably chromatic graph has a triangle-free subgraph of the same chromatic number.
komjath_2002_finite_subgraphs_uncountably_chromatic_graphs/: Consistency results: finite subgraphs of an uncountably chromatic graph can have arbitrarily slowly growing chromatic numbers, and Taylor's conjecture can fail.
komjath_2025_erdos_hajnal_problem_list/: Surveys fifty years of progress on the 82 set-theory problems of the 1967 Erdos-Hajnal problem list, recording which remain open.
kumar_2017_question_about_families_entire_functions/: Shows that Erdos's question on a continuum-sized family of entire functions taking fewer than continuum many values at each point is undecidable in ZFC plus the negation of CH.
lee_2026_erdos_problem_623_free_subset_property/: Proves in ZFC that Erdős Problem 623 has a positive answer exactly when Koepke's property Fr_omega(aleph_omega, omega) holds, so a positive answer has the consistency strength of a measurable cardinal.
lee_2026_relative_independence_erdos_problem_501/: Proves, assuming Lebesgue measure extends to a countably additive measure on all subsets of the reals, that every family of sets of outer measure below one has an infinite independent set, making the first question of Problem 501 independent of ZFC relative to a measurable cardinal.
li_2026_resolution_erdos_problems_593_1177_obligatory/: Claims a full characterization of the finite triple systems forced in every uncountably chromatic triple system, plus an exact chromatic spectrum dichotomy.
newelski_1987_infinite_free_set_small_measure_set_mappings/: Proves by a Fubini-type lemma that a set mapping on the reals with closed values of measure less than one has an infinite free set, answering Problem 38(B) of Erdős and Hajnal, with finite free-set bounds under an integral condition.
schilhan_2024_wetzel_families_continuum/: Shows a family of entire functions taking few values at each point is consistent with any value of the continuum of uncountable cofinality.
schipperus_2010_countable_partition_ordinals/: Schipperus's 2010 paper on the countable partition ordinals, the countable α with α → (α,3)^2: Theorem 28, ω^{ω^β} → (ω^{ω^β},3)^2 when β < ω_1 is the sum of one or two indecomposable ordinals, and Theorem 29, the failures ω^{ω^β} ↛ (ω^{ω^β},6)^2 for two indecomposables, ↛ (·,4)^2 for three and ↛ (·,3)^2 for four or more; together, at β = 2, the example that α → (α,3)^2 need not give α → (α,n)^2 for all finite n.
shelah_1975_notes_partition_calculus/: Shelah's 1975 notes proving the last open case of λ → (μ)^2_2 for infinite cardinals, Problem 3 of the 1971 Erdős–Hajnal list, that Σ_{n<ω} 2^{ℵ_n} → (ℵ_ω, ℵ_ω)^2 when ℵ_ω < 2^{ℵ_{n(0)}} < 2^{ℵ_{n(1)}} < ⋯, by a canonization lemma, and recording Hajnal's conjecture Σ_{n<ω} 2^{ℵ_n} → (ℵ_ω, 4)^3, with further sections on Problems 32, 42, 48 and 50 of the list.
shelah_1988_was_sierpinski_right_i/: Establishes consistency and ZFC results on square-bracket partition relations, settling an old Erdős-Hajnal problem about colorings of pairs of reals.
shelah_1989_consistency_positive_partition_theorems_graphs_models/: Proves the consistency with ZFC of strong positive partition relations for graphs and models, including a K4-free graph G with G -> (K3)^2_{aleph_0}.
soukup_2015_open_problems_around_uncountable_graphs/: A workshop problem list collecting open questions on uncountable graphs, mainly about chromatic number, with their known consistency status.
soukup_2015_trees_ladders_graphs/: Builds in ZFC an uncountably chromatic graph with no uncountable omega-connected subgraph, answering a 1985 Erdos-Hajnal question.
This folder holds sources whose primary subject is Set Theory and Infinite Combinatorics.
Sources with other primary subjects
Explicit links to this subject's problems support these cross-references.
- erdos_1978_set_theoretic
- erdos_1982_my_favourite_problems_which_recently_have
- feng_2026_semi_autonomous_mathematics_discovery_gemini_case
- adamczewski_2026_erdos74
- erdos_1974_general_properties_chromatic_numbers
- erdos_1979_problems_results_graph_theory_combinatorial_analysis
- erdos_1982_almost_bipartite_large_chromatic_graphs
- erdos_1995_problems_combinatorial_set_theory
- various_1999_some_pauls_favorite_problems
- erdos_1965_partition_relations_cardinal_numbers
- erdos_1975_problems_results_finite_infinite_graphs
- ramsey_1930_problem_formal_logic
- erdos_1981_combinatorial_problems_which_i_would_most
- kunen_2013_impact_paul_erdos_set_theory