‐subgroups in the space Cremona group

We prove that if X is a rationally connected threefold and G is a p‐subgroup in the group of birational selfmaps of X, then G is an abelian group generated by at most 3 elements provided that . We also prove a similar result for under an assumption that G acts on a (Gorenstein) G‐Fano threefold, and show that the same holds for under an assumption that G acts on a G‐Mori fiber space.     

Finding Minors in Graphs with a Given Path Structure

Given graphs G and H with , suppose that we have a ‐path in G for each edge in H. There are obvious additional conditions that ensure that G contains H as a rooted subgraph, subdivision, or immersion; we seek conditions that ensure that G contains H as a rooted minor or minor. This naturally leads to studying sets of paths that form an H‐immersion, with the additional property that paths that contain the same vertex must have a common endpoint. We say that H is contractible if, whenever G contains such an H‐immersion, G must also contain a rooted H‐minor. We show, for example, that forests, cycles, K₄, and K_{1, 1, 3} are contractible, but that graphs that are not 6‐colorable and graphs that contain certain subdivisions of K_{2, 3} are not contractible.     

Flows and Bisections in Cubic Graphs

A k‐weak bisection of a cubic graph G is a partition of the vertex‐set of G into two parts V₁ and V₂ of equal size, such that each connected component of the subgraph of G induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere‐zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere‐zero r‐flow has a ‐weak bisection. In this article, we study problems related to the existence of k‐weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4‐weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5‐weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5‐flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.     

Degree sum and vertex dominating paths

A vertex dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. In 1988 H. Broersma [5] stated a result implying that every n‐vertex k‐connected graph G such that contains a vertex dominating path. We provide a short, self‐contained proof of this result and further show that every n‐vertex k‐connected graph such that contains a vertex dominating path of length at most , where T is a minimum dominating set of vertices. An immediate corollary of this result is that every such graph contains a vertex dominating path with length bounded above by a logarithmic function of the order of the graph. To derive this result, we prove that every n‐vertex k‐connected graph with contains a path of length at most , through any set of T vertices where .     

Long cycles through prescribed vertices have the Erdős‐Pósa property

We prove that for every graph, any vertex subset S, and given integers : there are k disjoint cycles of length at least ℓ that each contain at least one vertex from S, or a vertex set of size that meets all such cycles. This generalizes previous results of Fiorini and Herinckx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in time, where s denotes the cardinality of S.     

Proper‐walk connection number of graphs

This paper studies the problem of proper‐walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph, that is, a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$.     

Excluding pairs of tournaments

The Erdős–Hajnal conjecture states that for every given undirected graph H there exists a constant such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least . The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant such that every H‐free tournament T contains a transitive subtournament of order at least . In this article, we prove that for several pairs of tournaments, H₁ and H₂, there exists a constant such that every ‐free tournament T contains a transitive subtournament of size at least . In particular, we prove that for several tournaments H, there exists a constant such that every ‐free tournament T, where stands for the complement of H, has a transitive subtournament of size at least . To the best of our knowledge these are first nontrivial results of this type.     

Anti‐Pasch optimal packings with triples

It is shown that for , there exists an optimal packing with triples on points that contains no Pasch configurations. Furthermore, for all (mod 6), there exists a pairwise balanced design of order , whose blocks are all triples apart from a single quintuple, and that has no Pasch configurations amongst its triples.     

Grünbaum colorings of even triangulations on surfaces

A Grünbaum coloring of a triangulation G is a map c : such that for each face f of G, the three edges of the boundary walk of f are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grünbaum coloring. So, in this article, we investigate the question whether each even (i.e., Eulerian) triangulation on a surface with representativity at least r has a Grünbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface has a Grünbaum coloring as long as is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grünbaum coloring and representativity , and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least 3.     

Graph minors and linkages

Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005     

Decomposing a graph into expanding subgraphs

A paradigm that was successfully applied in the study of both pure and algorithmic problems in graph theory can be colloquially summarized as stating that any graph is close to being the disjoint union of expanders. Our goal in this paper is to show that in several of the instantiations of the above approach, the quantitative bounds that were obtained are essentially best possible. Three examples of our results are the following:

• A classical result of Lipton, Rose and Tarjan from 1979 states that if is a hereditary family of graphs and every graph in has a vertex separator of size , then every graph in has O(n) edges. We construct a hereditary family of graphs with vertex separators of size such that not all graphs in the family have O(n) edges.
• Trevisan and Arora‐Barak‐Steurer have recently shown that given a graph G, one can remove only 1% of its edges to obtain a graph in which each connected component has good expansion properties. We show that in both of these decomposition results, the expansion properties they guarantee are essentially best possible, even when one is allowed to remove 99% of G's edges.
• Sudakov and the second author have recently shown that every graph with average degree d contains an n‐vertex subgraph with average degree at least and vertex expansion . We show that one cannot guarantee a better vertex expansion even if allowing the average degree to be O(1).

The above results are obtained as corollaries of a new family of graphs which we construct in this paper. These graphs have a super‐linear number of edges and nearly logarithmic girth, yet each of their subgraphs has (optimally) poor expansion properties.     

Quantitative Bessaga–Pełczyński property and quantitative Rosenthal property

We prove that c₀ and , where K is a dispersed compact Hausdorff space, enjoy a quantitative version of the Bessaga–Pe?czyński property. We also prove that l₁ possesses a quantitative version of the Pe?czyński property. Finally, we show that has a quantitative version of the Rosenthal property for any finite measure μ.     

Sequencing partial Steiner triple systems

A partial Steiner triple system of order $n$ is sequenceable if there is a sequence of length $n$ of its distinct points such that no proper segment of the sequence is a union of point‐disjoint blocks. We prove that if a partial Steiner triple system has at most three point‐disjoint blocks, then it is sequenceable.     

Holonomy group scheme of an integral curve

Let Y be a projective variety over a field k (of arbitrary characteristic). Assume that the normalization X of Y is such that is normal, being the algebraic closure of k. We define a notion of strong semistability for vector bundles on Y. We show that a vector bundle on Y is strongly semistable if and only if its pull back to X is strongly semistable and hence it is a tensor category. In case , we show that strongly semistable vector bundles on Y form a neutral Tannakian category. We define the holonomy group scheme of Y to be the Tannakian group scheme for this category. For a strongly semistable principal G‐bundle , we construct a holonomy group scheme. We show that if Y is an integral complex nodal curve, then the holonomy group of a strongly semistable vector bundle on Y is the Zariski closure of the (topological) fundamental group of Y.     

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.     

Asymptotics beyond All Orders in a Model of Crystal Growth

In its simplest form, the geometric model of crystal growth is a third-order, nonlinear, ordinary differential equation for θ(s, ε): A needle crystal is a solution that satisfies boundary conditions The geometric model admits a needle-crystal solution for ε = 0; for small ε, it admits an asymptotic expansion that is valid to all orders for such a solution. Even so, we prove that the geometric model in this form admits no needle crystal for any small, nonzero ε, a fact that lies beyond all orders of the asymptotic expansion. A more complicated version of the geometric model is where α represents crystalline anisitropy. We show that for 0 < α < 1, the geometric model admits needle crystals for a discrete set of values of α. The number of such values of α increases like ε^?1 as ε → 0.     

On Airy Solutions of the Second Painlevé Equation

In this paper, we discuss Airy solutions of the second Painlevé equation (P_II) and two related equations, the Painlevé XXXIV equation () and the Jimbo–Miwa–Okamoto σ form of P_II (S_II), are discussed. It is shown that solutions that depend only on the Airy function have a completely different structure to those that involve a linear combination of the Airy functions and . For all three equations, the special solutions that depend only on are tronquée solutions, i.e., they have no poles in a sector of the complex plane. Further, for both and S_II, it is shown that among these tronquée solutions there is a family of solutions that have no poles on the real axis.     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

On quasi‐infinitely divisible distributions with a point mass

An infinitely divisible distribution on is a probability measure μ such that the characteristic function has a Lévy–Khintchine representation with characteristic triplet , where ν is a Lévy measure, and . A natural extension of such distributions are quasi‐infinitely distributions. Instead of a Lévy measure, we assume that ν is a “signed Lévy measure”, for further information on the definition see [10]. We show that a distribution with and , where is the absolutely continuous part, is quasi‐infinitely divisible if and only if for every . We apply this to show that certain variance mixtures of mean zero normal distributions are quasi‐infinitely divisible distributions, and we give an example of a quasi‐infinitely divisible distribution that is not continuous but has infinite quasi‐Lévy measure. Furthermore, it is shown that replacing the signed Lévy measure by a seemingly more general complex Lévy measure does not lead to new distributions. Last but not least it is proven that the class of quasi‐infinitely divisible distributions is not open, but path‐connected in the space of probability measures with the Prokhorov metric.     

On the Smith normal form of a skew‐symmetric d‐optimal design of order

We show that the Smith normal form of a skew‐symmetric D ‐optimal design of order is determined by its order. Furthermore, we show that the Smith normal form of such a design can be written explicitly in terms of the order , thereby proving a recent conjecture of Armario. We apply our result to show that certain D ‐optimal designs of order are not equivalent to any skew‐symmetric D ‐optimal design. We also provide a correction to a result in the literature on the Smith normal form of D ‐optimal designs.