Reductions on equivalence relations generated by universal sets

Let X, Y be Polish spaces, , . We say A is universal for Γ provided that each x‐section of A is in Γ and each element of Γ occurs as an x‐section of A. An equivalence relation generated by a set is denoted by , where . The following results are shown:

• (1) If A is a set universal for all nonempty closed subsets of Y, then is a equivalence relation and .
• (2) If A is a set universal for all countable subsets of Y, then is a equivalence relation, and
  • (i) and ;
  • (ii) if , then ;
  • (iii) if every set is Lebesgue measurable or has the Baire property, then .
  • (iv) for , if every set has the Baire property, and E is any equivalence relation, then .

     

Factorials and the finite sequences of sets

We write for the cardinality of the set of finite sequences of a set which is of cardinality . With the Axiom of Choice (), for every infinite cardinal where is the cardinality of the permutations on a set which is of cardinality . In this paper, we show that “ for every cardinal ”  is provable in and this is the best possible result in the absence of . Similar results are also obtained for : the cardinality of the set of finite sequences without repetition of a set which is of cardinality .     

Jump inversions of algebraic structures and Σ‐definability

It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump . We also show that this result does not hold for the limit ordinal . Moreover, we prove that there is no countable structure with the degree spectrum for .     

On the relative strengths of fragments of collection

Let be the basic set theory that consists of the axioms of extensionality, emptyset, pair, union, powerset, infinity, transitive containment, Δ₀‐separation and set foundation. This paper studies the relative strength of set theories obtained by adding fragments of the set‐theoretic collection scheme to . We focus on two common parameterisations of the collection: ‐collection, which is the usual collection scheme restricted to ‐formulae, and strong ‐collection, which is equivalent to ‐collection plus ‐separation. The main result of this paper shows that for all ,

1. proves that there exists a transitive model of Zermelo Set Theory plus ‐collection,
2. the theory is ‐conservative over the theory .

It is also shown that (2) holds for when the Axiom of Choice is included in the base theory. The final section indicates how the proofs of (1) and (2) can be modified to obtain analogues of these results for theories obtained by adding fragments of collection to a base theory (Kripke‐Platek Set Theory with Infinity plus ) that does not include the powerset axiom.     

The first omitting cardinal for Magidority

An infinite cardinal λ is Magidor if and only if . It is known that if λ is Magidor then for some , and the first such α is denoted by . In this paper we try to understand some of the properties of . We prove that can be the successor of a supercompact cardinal, when λ is a Magidor cardinal. From this result we obtain the consistency of being a successor of a singular cardinal with uncountable cofinality.     

The cofinality of the least Berkeley cardinal and the extent of dependent choice

This paper is concerned with the possible values of the cofinality of the least Berkeley cardinal. Berkeley cardinals are very large cardinal axioms incompatible with the Axiom of Choice, and the interest in the cofinality of the least Berkeley arises from a result in [1], showing it is connected with the failure of . In fact, by a theorem of Bagaria, Koellner and Woodin, if γ is the cofinality of the least Berkeley cardinal then γ‐ fails. We shall prove that this result is optimal for or . In particular, it will follow that the cofinality of the least Berkeley is independent of .     

A variant of Shelah's characterization of Strong Chang's Conjecture

Shelah considered a certain version of Strong Chang's Conjecture which we denote , and proved that it is equivalent to several statements, including the assertion that Namba forcing is semiproper. We introduce an apparently weaker version, denoted , and prove an analogous characterization of it. In particular, is equivalent to the assertion that the the Friedman‐Krueger poset is semiproper. This strengthens and sharpens results by Cox and sheds some light on problems posed by Usuba, Torres‐Perez and Wu.     

Many symmetrically indivisible structures

A structure in a first‐order language is indivisible if for every colouring of its universe M in two colours, there is a monochromatic such that . Additionally, we say that is symmetrically indivisible if can be chosen to be symmetrically embedded in (that is, every automorphism of can be extended to an automorphism of ). In the following paper we give a general method for constructing new symmetrically indivisible structures out of existing ones. Using this method, we construct many non‐isomorphic symmetrically indivisible countable structures in given (elementary) classes and answer negatively the following question from 6 : Let be a symmetrically indivisible structure in a language . Let . Is symmetrically indivisible?     

Neutrally expandable models of arithmetic

A subset of a model of is called neutral if it does not change the relation. A model with undefinable neutral classes is called neutrally expandable. We study the existence and non‐existence of neutral sets in various models of . We show that cofinal extensions of prime models are neutrally expandable, and ω₁‐like neutrally expandable models exist, while no recursively saturated model is neutrally expandable. We also show that neutrality is not a first‐order property. In the last section, we study a local version of neutral expandability.     

Algebraic numbers with elements of small height

In this paper, we study the field of algebraic numbers with a set of elements of small height treated as a predicate. We prove that such structures are not simple and have the independence property. A real algebraic integer is called a Salem number if α and are Galois conjugate and all other Galois conjugates of α lie on the unit circle. It is not known whether 1 is a limit point of Salem numbers. We relate the simplicity of a certain pair with Lehmer's conjecture and obtain a model‐theoretic characterization of Lehmer's conjecture for Salem numbers.     

Phase transitions in graphs on orientable surfaces

Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

Reconstruction from the deck of -vertex induced subgraphs

The - deck of a graph is its multiset of subgraphs induced by vertices; we study what can be deduced about a graph from its -deck. We strengthen a result of Manvel by proving for that when is large enough ( suffices), the -deck determines whether an -vertex graph is connected ( suffices when , and cannot suffice). The reconstructibility of a graph with vertices is the largest such that is determined by its -deck. We generalize a result of Bollobás by showing for almost all graphs. As an upper bound on , we have . More generally, we compute whenever , which involves extending a result of Stanley. Finally, we show that a complete -partite graph is reconstructible from its -deck.     

On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

Strong chromatic index of unit distance graphs

The strong chromatic index of a graph , denoted by , is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges and have the same color, then both vertices of are not adjacent to any vertex of ). A graph is a unit distance graph in if vertices of can be uniquely identified with points in , so that is an edge of if and only if the Euclidean distance between the points identified with and is 1. We would like to find the largest possible value of , where is a unit distance graph (in and ) of maximum degree . We show that , where is a unit distance graph in of maximum degree . We also show that the maximum possible size of a strong clique in unit distance graph in is linear in and give a tighter result for unit distance graphs in the plane.     

The tree property and the continuum function below

We say that a regular cardinal κ, , has the tree property if there are no κ‐Aronszajn trees; we say that κ has the weak tree property if there are no special κ‐Aronszajn trees. Starting with infinitely many weakly compact cardinals, we show that the tree property at every even cardinal , , is consistent with an arbitrary continuum function below which satisfies , . Next, starting with infinitely many Mahlo cardinals, we show that the weak tree property at every cardinal , , is consistent with an arbitrary continuum function below which satisfies , . Thus the tree property has no provable effect on the continuum function below except for the trivial requirement that the tree property at implies for every infinite κ.     

Filling the complexity gaps for colouring planar and bounded degree graphs

A colouring of a graph is a function such that for every . A -regular list assignment of is a function with domain such that for every , is a subset of of size . A colouring of respects a -regular list assignment of if for every . A graph is -choosable if for every -regular list assignment of , there exists a colouring of that respects . We may also ask if for a given -regular list assignment of a given graph , there exists a colouring of that respects . This yields the -Regular List Colouring problem. For , we determine a family of classes of planar graphs, such that either -Regular List Colouring is -complete for instances with , or every is -choosable. By using known examples of non--choosable and non--choosable graphs, this enables us to classify the complexity of -Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs, and planar graphs with no -cycles and no -cycles. We also classify the complexity of -Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.     

Arc index of spatial graphs

Bae and Park found an upper bound on the arc index of prime links in terms of the minimal crossing number. In this paper, we extend the definition of the arc presentation to spatial graphs and find an upper bound on the arc index of any spatial graph as where is the minimal crossing number of , is the number of edges, and is the number of bouquet cut-components. This upper bound is lowest possible.