Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Set Systems, Designs and Hypergraphs
abel_2024_improvements_lower_bounds_mutually_orthogonal_latin/: Shows there are at least 8, 10 and 9 mutually orthogonal Latin squares of orders 54, 96 and 108 respectively.
achlioptas_iliopoulos_sinclair_2020_point_set_correlations/: Point-to-set correlation criteria for resampling, backtracking, and hybrid local-lemma algorithms, with a quantified convergence theorem.
aharoni_berger_briggs_guo_zerbib_2023_looms/: Defines orthogonal hypergraph pairs whose members are minimum covers of one another, proving fractional matching and rainbow consequences and structural loom constructions.
aharoni_berger_meshulam_2003_flag_complexes_vector_representations/: Bounds the reduced Laplacian eigenvalues of a graph's flag complex, deduces that a spectral gap above kn/(k+1) makes its k-th reduced cohomology vanish, and derives a vector-domination bound for independence complexes and a Hall-type theorem in terms of fractional width for systems of disjoint representatives.
ahlswede_1997_complete_intersection_theorem_systems_finite_sets/: Determines the maximum size of a t-intersecting family of k-subsets of an n-set for all n, k and t, proving Frankl's general conjecture and, as the case n equal to 4m, k equal to 2m, t equal to 2, the 4m-conjecture of Erdős, Ko and Rado.
alon_2013_sunflowers_matrix_multiplication/: Relates variants of the Erdos-Rado sunflower conjecture to each other and shows they obstruct known approaches to fast matrix multiplication.
alweiss_2020_improved_bounds_sunflower_lemma/: Improves the Erdos-Rado sunflower bound from roughly w^w to (log w)^w sets, and proves a sharp version for robust sunflowers.
barat_2021_intersecting_hypergraphs_maximal_covering_number/: Determines the minimum number of edges in intersecting r-uniform hypergraphs of covering number r for small r, showing q(5) = 13.
bell_2021_note_sunflowers/: Improves the sunflower bound to Sun(p,k) at most (Cp log k)^k, removing the log p factor from Rao's bound.
bohman_2019_large_girth_approximate_steiner_triple_systems/: Shows that for every fixed girth bound there are partial Steiner triple systems on n vertices with (1/6-o(1))n^2 triples and girth exceeding that bound.
bollobas_1976_sets_independent_edges_hypergraph/: Gives edge-count and minimum-degree conditions forcing many pairwise disjoint edges in an r-uniform hypergraph, with the extremal example identified.
bose_1960_further_results_construction_mutually_orthogonal_latin/: Disproves Euler's conjecture by constructing a pair of orthogonal Latin squares of every order 4t+2 greater than 6, and improves lower bounds on N(v).
bruck_1949_nonexistence_certain_finite_projective_planes/: Proves no finite projective plane of order N exists when N is 1 or 2 mod 4 and the squarefree part of N has a prime factor congruent to 3 mod 4.
bruijn_1948_combinatorial_problem/: Proves that more than one block covering every pair of n points exactly once means at least n blocks, with n only for the near-pencil or a uniform regular system on k(k-1)+1 points.
bucic_et_al_2019_covering_graphs_by_monochromatic_trees_helly_type_results_hypergraphs/: Bounds the global cover number of a uniform hypergraph whose every q edges have a small cover, a Helly-type parameter whose two-point case is the Problem 644 quantity f(k,q).
chowla_1960_maximum_number_pairwise_orthogonal_latin_squares/: Proves the maximum number of pairwise orthogonal Latin squares of order n tends to infinity, and exceeds (1/3) n^{1/91} for all sufficiently large n.
chvatal_1974_intersecting_families_edges_hypergraphs_hereditary_property/: Proves that in a family of subsets of {1, ..., n} closed under the left-shift order no intersecting subfamily is larger than the star at 1, and states the conjecture that for every family closed under taking subsets some element's star is at least as large as every intersecting subfamily.
conlon_2016_short_proofs_extremal_results_ii/: Collects short proofs of several extremal and Ramsey results, including a construction settling the Erdos-Hajnal set-mapping problem when each k-set is mapped to a set of (k-1)! points.
conlon_2023_new_bound_brown_erdos_sos_problem/: Gives the first asymptotic improvement on the Brown-Erdos-Sos problem, replacing the log e error term by one of order log e over log log e.
cunningham_marsh_1978_primal_algorithm_optimum_matching/: Presents a primal algorithm for maximum-weight perfect matching, retaining Edmonds's odd-set constraints and dual certificates while maintaining a perfect matching throughout.
edmonds_1965_transversals_matroid_partition/: Compiles both finite transversal and matroid-partition routes, all prescribed variants, and the relative matching representation.
ellis_2010_irredundant_families_subcubes/: Bounds the size of irredundant families of k-subcubes in the Boolean cube, gives a new proof of Meshulam's estimate, and records principal-family results and near-tight lower constructions.
erdos_1946_asymptotic_number_latin_rectangles/: Proves the conjectured asymptotic count (n!)^k exp(-binom(k,2)) of n by k Latin rectangles (k rows on n symbols) for k < (log n)^{3/2-eps}.
erdos_1960_intersection_theorems_systems_sets/: Proves the sunflower lemma: any family of more than about b! a^{b+1} sets of at most b elements contains a sunflower with more than a petals.
erdos_1961_intersection_theorems_systems_finite_sets/: Bounds the size of a family of l-element subsets of an m-set in which every two sets meet in at least k elements, giving the sharp binomial estimate.
erdos_1963_combinatorial_problem/: Proves lower bounds on the least number m(p) of p-element sets without property B: m(p) > 2^{p-1} for p >= 2 and m(p) > (1-epsilon) 2^p log 2 for large p.
erdos_1964_combinatorial_problem/: Proves that at most about n^2 2^n sets of size n are needed to form a family without property B, by a non-constructive argument.
erdos_1965_problem_independent_tuples/: Determines the largest number of edges in an r-uniform hypergraph with no k disjoint edges, once the vertex count is large relative to k.
erdos_1968_egy_kombinatorikus_problemarol/: Proves that the least size H(n) forcing a set mapping on n points to cover everything satisfies log n/log 2 < H(n) < log n/log 2 + (3+epsilon)log log n/log 2 for n > n_0(epsilon).
erdos_1981_combinatorial_problems_which_i_would_most/: Erdos collects his favorite open combinatorial problems on set systems, number theory, extremal and Ramsey theory, many with cash prizes.
erdos_1982_pairwise_balanced_block_designs_sizes_blocks/: Constructs pairwise balanced designs on n points whose block sizes all equal the square root of n up to an error of a smaller power of n.
erdos_1983_intersection_properties_families_containing_sets_nearly/: Proves probabilistically that for every c > 2e every projective plane of large order n has property B(c log n), plus a weaker constructive property B(n+2-j) with j of order sqrt(n/2).
erdos_1985_2_designs/: Studies which numbers of lines a 2-design (linear space) on v points can have: every count from v + v^{1/2+c} to binom(v,2) - 4 for large v and any c > 11/40, and none strictly between v and v + p when v is p squared plus p plus one.
falikman_1981_proof_van_der_waerden_conjecture_permanent/: Proves van der Waerden's conjecture that every doubly stochastic n by n matrix has permanent at least n factorial over n to the n.
fici_2023_abelian_combinatorics_words_survey/: Surveys abelian combinatorics on words, collecting results on abelian complexity, abelian repetitions, avoidability of abelian powers, and abelian periods.
fon_der_flaass_et_al_1999_transversals_uniform_hypergraphs_property_7_2/: Proves the largest transversal number of a k-uniform family in which every seven sets are pierced by two points is at least 3k/4+1 when k is a multiple of 4 with k >= 40, and at most the ceiling of 7k/8 for k >= 8.
ford_1958_network_flow_systems_representatives/: Ford–Fulkerson (1958): flow criteria for single and common representatives with occurrence bounds.
frankl_1977_families_finite_sets_intersect_singleton/: Proves the Erdos-Sos conjecture that for k>=4 and n>n_0(k) a k-uniform family on n points with more than binom(n-2,k-2) sets has two members meeting in exactly one point.
frankl_1984_hypergraphs_without_two_edges_intersecting_given/: Determines the largest family of subsets of an n-set in which no two members meet in exactly t elements, for all large n.
frankl_1987_forbidden_intersections/: Frankl and Rödl (1987), exponential forbidden-intersection bounds and full joint-pattern counts for dense partition families, with source corrections and explicit numerical and metric limitations.
frankl_2012_matchings_hypergraphs/: Proves that for k at least 3 and n greater than 2k^2 s / log k the k-uniform hypergraphs on n vertices with matching number s and the most edges are exactly the covers of an s-set.
frankl_2023_perfect_matchings_down_sets/: Proves that between two down-sets there is a disjointness matching covering the smaller one, and deduces Chvátal's conjecture for intersecting families of covering number at most two.
frankston_2019_thresholds_versus_fractional_expectation_thresholds/: Proves Talagrand's fractional expectation-threshold conjecture, showing a threshold is within a log factor of its fractional lower bound.
furedi_1984_hypergraphs_which_all_disjoint_pairs_have/: Shows a disjoint-union-free family of r-sets on n points, r >= 3, has fewer than 3.5 binom(n,r-1) members, settling the order of magnitude.
furedi_gyarfas_kiraly_2023_one_cross_intersecting_set_pair_systems/: Studies 1-cross-intersecting set-pair systems, proving a sharp bound in the (2,n)-bounded case, linear-hypergraph bounds, and equivalent clique and biclique partition formulations.
gao_2025_cliques_hypergraphs/: Proves that for k at least 3 and n large every k-uniform hypergraph on n vertices has at most n minus any fixed constant distinct clique sizes, answering a question of Erdős.
ghorbani_et_al_2007_inclusion_matrices_chains/: Builds, from a rank-chain decomposition of the Boolean lattice, a modification of the t-subset versus k-subset inclusion matrix with Smith form (I | O) for t <= k <= v - t, and from it rederives Wilson's diagonal form and Wilson's integrality criterion for W_{tk} x = b.
glock_2020_conjecture_erdos_locally_sparse_steiner_triple/: Proves Erdős's conjecture on locally sparse (high-girth) Steiner triple systems approximately: for every fixed k there are k-sparse partial systems on n vertices with (1/6-o(1))n^2 triples.
gyarfas_lehel_tuza_1982_tau_critical_hypergraphs/: Bounds the order of finite r-uniform τ-critical hypergraphs, giving an estimate of the right order of magnitude for fixed uniformity and graph and 3-uniform consequences.
hall_1935_representatives_subsets/: Reconstructs Hall's finite distinct-representative theorem by exchange reachability, with the partition and equal finite block consequences.
harris_2016_lopsidependency_moser_tardos/: Harris's lopsided-dependency extension of the Moser–Tardos framework, including its orderability criterion and resampling bounds.
he_2026_erdos_trotter_problem_antichains_multiplicity_each/: Determines the Erdos-Trotter threshold exactly for r=2,3 and bounds it between 2r+2 and 2r + 2 log_2 r + O(log log r) for every r >= 4.
he_li_liu_wang_xia_2017_variable_lovasz_local_lemma/: Variable-version Lovász local lemma results beyond Shearer's bound, including exclusive event systems and gapless event-variable bigraphs.
huang_2012_size_hypergraph_matching_number/: Verifies Erdos's conjectured maximum edge count for k-uniform hypergraphs with no t disjoint edges whenever t is less than n/(3k^2).
johansson_2008_factors_random_graphs/: Determines the threshold for an H-factor in G(n,p) for every strictly balanced H up to a constant factor, and the perfect-matching threshold in random k-uniform hypergraphs, which it presents as resolving Shamir's problem.
kaced_romashchenko_vereshchagin_2017_conditional_information_inequality/: Proves an entropy inequality under an explicit support condition and applies it to proper rich bipartite edge colorings, biclique covers, and a conditional Ingleton inequality.
kahn_1994_problem_erdos_lovasz_ii/: Proves that the least size n(r) of an intersecting family of r-sets such that every set of size r minus 1 misses some member is O(r), settling the Erdős-Lovász problem, with an explicit but unevaluated constant of about 5K for a fixed prime power K.
kahn_2023_asymptotics_shamir_s_problem/: Determines the asymptotic threshold for a perfect matching in a random r-uniform hypergraph, confirming the natural (n/r)log n guess.
keevash_2014_existence_designs/: Proves the existence conjecture for combinatorial designs, so for fixed q, r divisibility conditions suffice for Steiner systems (n,q,r) with n large.
koishichan_2025_counterexample_erdos_1022/: Gives a direct two-level hypergraph construction that refutes Problem 1022 and was accepted in the site's discussion.
kolupaev_2023_erdos_matching_conjecture_almost_perfect_matchings/: Proves the Erdős matching conjecture's bound by the clique of all k-subsets of [(s+1)k-1] for s > k >= 5, s > 101k^3 and (s+1)k <= n < (s+1)(k + 1/(100k)), widening Frankl's almost-perfect-matching range.
komorech_2025_non_jumping_densities_3_uniform_hypergraphs/: Gives a pattern-based method producing new non-jumping Turan densities for 3-uniform hypergraphs, including the density 64/81.
koperberg_2022_couplings_matchings_strassen/: Gives finite coupling criteria, an equivalent weighted edge-flow statement, Hall-type deficiency bounds, and combinatorial derivations through a subforest lemma.
kostochka_1999_properties_descartes_construction_triangle_free_graphs/: Refines Descartes' construction to produce 3-chromatic uniform hypergraphs of arbitrary girth with density arbitrarily close to 1, and sparse k-critical uniform hypergraphs of arbitrary girth.
kostochka_1999_systems_small_sets_no_large_subsystems/: Shows that for each fixed r the least number of r-sets forcing a Δ-system of k sets is k^r + o(k^r) as k grows, and bounds the error term from above.
kullmann_2011_constraint_satisfaction_clausal_form/: Kullmann's report on clausal constraint satisfaction with non-boolean variables: matching lean kernels, autarkies and satisfiability in polynomial time at bounded maximal deficiency, minimally unsatisfiable clause-sets of deficiency 1, and the hermitian-defect bound.
kunen_2013_impact_paul_erdos_set_theory/: Survey of Erdos's influence on set theory: large cardinals, forcing chain conditions, set-theoretic topology, order types, geometry and free sets.
kwan_2022_high_girth_steiner_triple_systems/: Proves Erdős's 1973 conjecture that Steiner triple systems of arbitrarily high girth exist for all large admissible orders.
lam_1997_search_finite_projective_plane_order_10/: Expository account, by one of the authors of the computer search, of the history of the finite projective plane of order 10 and of the searches that showed no such plane exists. The copy read for this card is the author's 2005 TeX revision of the 1991 Monthly article.
lawler_martel_1980_polymatroidal_network_flows/: Generalizes augmenting paths, max-flow min-cut, and integral-flow results to network capacities given by polymatroid rank functions.
li_2025_erdos_lovasz_problem_3_critical/: Resolves both documented meanings of three-criticality: a sharp degree-six obstruction for transversal criticality and a degree-seven construction for chromatic criticality.
liu_2026_number_4_9_is_non_jump/: Proves that 4/9 is a non-jump for 3-uniform hypergraphs, breaking the barrier of the finite-pattern Frankl-Rodl method.
lovasz_1968_graphs_set_systems/: Extends forests and circuits from graphs to finite set systems, proves that every forest in the paper's counting sense is two-colorable, and constructs uniform set systems with long circuits and large chromatic number.
lovasz_1973_coverings_colorings_hypergraphs/: Surveys two-colorability of hypergraphs: its hardness, the union-of-edges criterion with its pointer to the 1968 proof, a pair-degree obstruction, and announced bounds for intersecting 3-chromatic hypergraphs.
lovitz_petrov_2021_generalization_kruskals_theorem_tensor_decomposition/: A theorem-indexed source review with a complete local Markdown reading copy.
luczak_2014_erdos_extremal_problem_matchings_hypergraphs/: Proves Erdos's matching conjecture for 3-uniform hypergraphs on sufficiently many vertices, and identifies the extremal hypergraphs.
moser_tardos_2009_constructive_proof_general_lovasz_local_lemma/: A theorem-indexed source review read from the complete arXiv preprint.
nagy_pach_tomon_2026_hyperplane_covers_finite_spaces/: Establishes logarithmic lower bounds for irredundant hyperplane covers of finite vector spaces and applies them to non-vanishing linear maps, additive bases, and abelian coset covers.
naslund_2017_upper_bounds_sunflower_free_sets/: Bounds the Erdos-Szemeredi sunflower-free capacity for k=3 by 3/2^{2/3}, using the polynomial method directly.
pikhurko_2009_maximum_size_hypergraphs_without_generalized_4/: Improves the upper bound on limsup f_r(n)/binom(n,r-1) for r-uniform hypergraphs without generalized 4-cycles to min(1+2/sqrt r, 7/4), and to 13/9 when r=3.
pittman_2021_constructive_bollobas_varopoulos_theorem/: Gives a constructive finite-measure criterion for choosing disjoint prescribed-mass subsets, together with finite Hall-type corollaries.
pluhar_2009_greedy_colorings_uniform_hypergraphs/: Gives a short random-greedy proof that a non-2-colorable n-uniform hypergraph has more than 0.5268 n^{1/4} 2^n edges for n >= 3.
rado_1949_axiomatic_treatment_rank_infinite_sets/: Compiles the original selection principle and infinite-rank chain, including the countability counterexample and exact choice boundaries.
rao_2020_coding_sunflowers/: Gives a short coding-theoretic proof that any family of more than (alpha p log(pk))^k sets of size k contains a p-sunflower.
solymosi_2017_small_cores_3_uniform_hypergraphs/: Proves that for every c > 0 and large n, any 3-uniform hypergraph on n vertices with at least cn^2 edges contains a core, a subgraph of minimum degree two, on at most 15 vertices.
steele_1995_variations_monotone_subsequence_theme_erdos_szekeres/: Steele's 1995 survey of the Erdős-Szekeres monotone subsequence theorem and its variations, with new results on monotone subsequences of windows of an infinite sequence and a list of open problems, among them Erdős's weighted question and his question on the largest sum of a monotone subsequence.
tamir_1983_balanced_matrices_location_problems/: Proves balancedness for intersection matrices of neighborhood subtrees, distinguishes an equality-polyhedron theorem from fractional covering examples, and gives two restricted polynomial location cases.
tidor_2016_1_color_avoiding_paths_special_tournaments/: Studies Loh's question on 1-color-avoiding paths in 3-colored transitive tournaments and derives a weighted Erdos-Szekeres bound.
tripathi_2014_note_uniform_intersecting_families_maximum_transversal/: Determines the Erdos-Lovasz value q(4) = 9 through an explicit intersecting family M_k of length k+1, and builds 3-regular intersecting k-families of length 2k+1 for k = 2^m - 1.
tuza_1985_critical_hypergraphs_intersecting_set_pair_systems/: Bounds the number of vertices of matching-critical and transversal-critical hypergraphs by the intersecting set-pair method, giving Problem 644 a finite critical-core framework but no linear bound.
van_wee_1991_covering_codes_perfect_codes_algebraic_curves/: Digests van Wee's dissertation of eight papers on covering codes, perfect and perfect multiple codes, normal codes, and algebraic-geometric codes, with result pages for the main results of each chapter.
wagner_2017_large_subgraphs_rainbow_triangle_free_colorings/: Shows that for s at most r every Gallai r-coloring of a complete graph on n vertices has an s-colored subgraph of chromatic number at least n to the power s over r.
wdowinski_2025_bounded_degree_no_full_rainbow_matchings/: Constructs bounded-degree graphs and hypergraphs without full rainbow matchings, including sharp general classes, proper-coloring counterexamples and a bipartite list edge-coloring counterexample.
welsh_1969_transversal_theory_matroids/: Reconstructs Welsh's finite matroid criteria for transversals with prescribed and bounded multiplicities, with two false printed theorems separated from corrected compilation results.
wilson_1974_number_mutually_orthogonal_latin_squares/: Proves that the maximum number N(n) of mutually orthogonal Latin squares of order n is at least n to the power 1/17, minus 2, for all large n, improving the sieve bounds of Chowla, Erdős and Straus and of Rogers by a new transversal-design construction. Also shows N(n) at least 2 for n other than 2 and 6, and N(n) at least 6 for n above 90.
wood_2013_hypergraph_colouring_degeneracy/: Constructs triangle-free d-degenerate r-uniform hypergraphs with chromatic number exactly d+1 for all r at least 2 and d at least 1.
yamamoto_1951_asymptotic_number_latin_rectangles/: Extends the Erdos-Kaplansky asymptotic formula for the number of n by k Latin rectangles to k below n^{1/3-delta}.
This folder holds sources whose primary subject is Set Systems, Designs and Hypergraphs.
Sources with other primary subjects
Explicit links to this subject's problems support these cross-references.
- erdos_1957_unsolved_problems
- erdos_1975_problems_results_combinatorial_number_theory
- frankl_furedi_1986_non_trivial_intersecting_families
- erdos_1982_my_favourite_problems_which_recently_have
- furedi_1991_maximal_independent_subsets_steiner_systems_planar_sets
- kahn_kalai_1993_borsuk_counterexample
- erdos_1975_problems_elementary_combinatorial_geometry
- erdos_1970_extremal_problems_combinatorial_number_theory
- alon_2006_extremal_hypergraph_problem_brown_erdos_sos
- alon_2026_problems_results_extremal_combinatorics_v
- brown_1973_extremal_problems_graphs
- erdos_1959_maximal_paths_circuits_graphs
- erdos_1964_extremal_problems_graphs_generalized_graphs
- erdos_1966_representation_graph_set_intersections
- erdos_1971_unsolved_problems_graph_theory_combinatorial_analysis
- erdos_1974_extremal_problems_graphs_hypergraphs
- erdos_1976_problems_results_combinatorial_analysis
- erdos_1976_problems_results_graph_theory_combinatorial_analysis
- erdos_1986_asymptotic_number_graphs_not_containing_fixed
- erdos_1997_some_unsolved_problems
- janzer_2025_power_saving_brown_erdos_sos_problem
- moon_moser_1965_cliques_graphs
- spencer_1971_cliques_graphs
- erdos_1975_problems_results_3_chromatic_hypergraphs_related
- erdos_1979_problems_results_graph_theory_combinatorial_analysis
- radhakrishnan_2000_improved_bounds_algorithms_hypergraph_coloring
- tang_2025_harmonic_lcm_patterns_sunflower_free_capacity
- erdos_1961_unsolved_problems
- erdos_1965_recent_advances_current_problems_number_theory
- guy_1991_western_number_theory_problems
- burr_1989_maximal_anti_ramsey_graphs_strong_chromatic
- erdos_1997_some_recent_problems_results_graph_theory
- erdos_1958_structure_set_mappings
- erdos_1966_chromatic_number_graphs_set_systems
- komjath_2025_erdos_hajnal_problem_list