Set Theory and Infinite Combinatorics

../

E0070/: Asks whether the order type of the real line arrows a countable ordinal and a finite number for two-colorings of triples.

E0111/: Asks how many edge deletions make an n-vertex subgraph bipartite, and whether that number grows faster than n for graphs of uncountable chromatic number.

E0118/: Asks whether an order type whose two-colorings always give a red copy of itself or a blue triangle must likewise force a blue complete graph on n vertices.

E0474/: Which set theoretic assumptions allow a three-coloring of the plane in which every uncountable set contains a pair of points of each color.

E0501/: Asks whether bounded sets of outer measure below one assigned to the reals leave an infinite set no member of which lies in another's set (independent of ZFC), and whether closed sets of measure below one leave three (proved).

E0590/: Asks whether every red-blue coloring of the pairs from the ordinal omega to the omega yields a red complete subgraph of that order type or a blue triangle.

E0591/: Asks whether every red-blue coloring of pairs from the ordinal omega to the omega squared gives a red complete subgraph of that order type or a blue triangle.

E0592/: Determines which countable ordinals force every red-blue coloring of pairs from omega to that ordinal to give a red clique of that type or a blue triangle.

E0593/: Characterizes the finite three-uniform hypergraphs that must appear in every three-uniform hypergraph with uncountable chromatic number.

E0594/: Asks whether every graph with chromatic number at least the first uncountable cardinal contains all sufficiently large odd cycles.

E0595/: Asks whether there is an infinite graph with no complete subgraph on four vertices that is not a union of countably many triangle-free graphs.

E0596/: Characterizes pairs of graphs for which finite colorings of a host avoiding the first force a monochromatic second, while countably many colors do not; Erdős and Hajnal first guessed that no pair exists, which C_4 and C_6 refute.

E0597/: Asks whether a partition relation holds for graphs on at most aleph_1 vertices with no K_4 and no K_{aleph_0,aleph_0}; Erdős first asked it for every K_4-free graph, which a relation of Baumgartner refutes.

E0598/: Asks whether the countable subsets of an infinite cardinal can be colored with successor-of-continuum many colors so every set of that size gets all colors.

E0599/: Asks whether every graph with two disjoint independent sets has a family of disjoint paths between them plus a blocking set meeting each path once.

E0601/: Asks for which limit ordinals every graph on that many vertices has an infinite path or an independent set whose vertices have that same order type.

E0602/: Asks whether a family of countably infinite sets meeting pairwise in a finite set of size other than one can always be two-colored with no set monochromatic.

E0603/: The least number of colors always enough to color the union of countably infinite sets meeting pairwise in a set of size other than two with none one color.

E0623/: Asks whether a function on the finite subsets of a set of size aleph_omega that never picks a member of its input (a set mapping) must have an infinite independent set.

E1067/: Asks whether every graph of chromatic number aleph one contains an infinitely connected subgraph of chromatic number aleph one.

E1068/: Asks whether every graph of chromatic number aleph one contains a countable subgraph that is infinitely vertex-connected.

E1119/: Asks whether a family of entire functions taking at most m distinct values at each point has cardinality at most m, for m between countable and continuum.

E1123/: Compares the Boolean algebra of sets of integers modulo density zero with the Boolean algebra of sets modulo logarithmic density zero.

E1127/: Asks whether real n-dimensional space splits into countably many sets in each of which all pairwise distances are distinct.

E1128/: Asks whether every two-coloring of a product of three sets of size aleph one contains a monochromatic product of three countably infinite subsets.

E1167/: Asks about a partition problem for infinite cardinals, coloring r-element sets when the parts are given by a sequence of prescribed cardinals; open under the Erdős–Hajnal list's conditions gamma at least 2 and every kappa_alpha above r, which exclude the failures of the site's wording.

E1168/: Asks for a proof of a negative partition relation for pairs at the successor of the omega-th infinite cardinal, without the generalized continuum hypothesis.

E1169/: Asks whether the square of the first uncountable ordinal fails a partition relation for pairs into itself and a triangle.

E1170/: Asks whether it is consistent that the second uncountable ordinal has the two-color partition property for pairs for every smaller ordinal.

E1171/: Asks whether the square of the first uncountable ordinal has a partition property for pairs giving a large ordinal or a triangle, for each finite color count.

E1172/: Asks whether several partition relations for pairs of small uncountable ordinals hold, or are consistent, under the generalized continuum hypothesis.

E1173/: Asks whether, under the generalized continuum hypothesis, a set mapping on omega_{omega+1} with values of size at most aleph_omega and pairwise intersections below aleph_omega must have a free set of size aleph_{omega+1}.

E1174/: Asks whether some K_4-free graph forces a monochromatic triangle, and whether some K_{aleph_1}-free graph forces a monochromatic K_{aleph_0}, in every edge coloring with countably many colors.

E1175/: Asks whether, for each uncountable cardinal kappa, some cardinal lambda makes every graph of chromatic number lambda contain a triangle-free subgraph of chromatic number kappa.

E1176/: Asks whether every graph of chromatic number aleph_1 has an edge coloring with aleph_1 colors such that every countable vertex coloring has a class containing edges of all colors.

E1177/: Concerns the families of three-uniform hypergraphs of a given chromatic number that avoid a fixed finite three-uniform hypergraph.

E1218/: Asks whether, under GCH, the successor of aleph_{omega_{omega+1}} fails the partition relation for triples whose first target is that cardinal and whose other countably many targets are 4.

E1219/: Asks whether a sum of strictly increasing powers two to the aleph n_k, the first above aleph omega, satisfies the partition relation to aleph omega for pairs.

E1220/: Asks whether a singular cardinal that is aleph-zero-inaccessible, as is its cofinality, satisfies the partition relation to itself and aleph one for pairs.

---

Infinite graphs and hypergraphs, partition calculus and infinite Ramsey theory, cardinal arithmetic, and problems whose answers are independent of the usual axioms of set theory.

Site tags routed here: algebra, analysis, chromatic number, combinatorics, distances, geometry, graph theory, hypergraphs, ramsey theory, set theory.