Multi‐to One‐Dimensional Optimal Transport

We consider the Monge‐Kantorovich problem of transporting a probability density on to another on the line, so as to optimize a given cost function. We introduce a nestedness criterion relating the cost to the densities, under which it becomes possible to solve this problem uniquely by constructing an optimal map one level set at a time. This map is continuous if the target density has connected support. We use level‐set dynamics to develop and quantify a local regularity theory for this map and the Kantorovich potentials solving the dual linear program. We identify obstructions to global regularity through examples. More specifically, fix probability densities f and g on open sets and with . Consider transporting f onto g so as to minimize the cost . We give a nondegeneracy condition on that ensures the set of x paired with [g‐a.e.] y ∈ Y lie in a codimension‐n submanifold of X. Specializing to the case m > n = 1, we discover a nestedness criterion relating s to (f,g) that allows us to construct a unique optimal solution in the form of a map . When and g and f are bounded, the Kantorovich dual potentials (u,υ) satisfy , and the normal velocity V of with respect to changes in y is given by . Positivity of V locally implies a Lipschitz bound on f; moreover, if intersects transversally. On subsets where this nondegeneracy, positivity, and transversality can be quantified, for each integer the norms of and are controlled by these bounds, , and the smallness of . We give examples showing regularity extends from $X to part of , but not from Y to . We also show that when s remains nested for all (f,g), the problem in reduces to a supermodular problem in . © 2017 Wiley Periodicals, Inc.     

What Is Variable Bandwidth?

We propose a new notion of variable bandwidth that is based on the spectral subspaces of an elliptic operator where p > 0 is a strictly positive function. Denote by the orthogonal projection of A_p corresponding to the spectrum of A_p in ; the range of this projection is the space of functions of variable bandwidth with spectral set in Λ. We will develop the basic theory of these function spaces. First, we derive (nonuniform) sampling theorems; second, we prove necessary density conditions in the style of Landau. Roughly, for a spectrum the main results say that, in a neighborhood of , a function of variable bandwidth behaves like a band‐limited function with local bandwidth . Although the formulation of the results is deceptively similar to the corresponding results for classical band‐limited functions, the methods of proof are much more involved. On the one hand, we use the oscillation method from sampling theory and frame‐theoretic methods; on the other hand, we need the precise spectral theory of Sturm‐Liouville operators and the scattering theory of one‐dimensional Schrödinger operators. © 2017 Wiley Periodicals, Inc.     

Global Existence of Weak Solutions of the Nematic Liquid Crystal Flow in Dimension Three

For any bounded smooth domain , we establish the global existence of a weak solution of the initial boundary value (or the Cauchy) problem of the simplified Ericksen‐Leslie system LLF modeling the hydrodynamic flow of nematic liquid crystals for any initial and boundary (or Cauchy) data , with (the upper hemisphere). Furthermore, (u,d) satisfies the global energy inequality.© 2016 Wiley Periodicals, Inc.     

Entanglement Thresholds for Random Induced States

For a random quantum state on obtained by partial tracing a random pure state on , we consider the question whether it is typically separable or typically entangled. For this problem, we show the existence of a sharp threshold of order roughly . More precisely, for any and for d large enough, such a random state is entangled with very large probability when , and separable with very large probability when . One consequence of this result is as follows: for a system of N identical particles in a random pure state, there is a threshold such that two subsystems of k particles each typically share entanglement if k > k₀, and typically do not share entanglement if k < k₀. Our methods also work for multipartite systems and for “unbalanced” systems such as , . The arguments rely on random matrices, classical convexity, high‐dimensional probability, and geometry of Banach spaces; some of the auxiliary results may be of reference value. © 2013 Wiley Periodicals, Inc.     

Upper Bounds for Erdös–Hajnal Coefficients of Tournaments

A celebrated unresolved conjecture of Erdös and Hajnal (see Discrete Appl Math 25 (1989), 37–52) states that for every undirected graph H, there exists , such that every graph on n vertices which does not contain H as an induced subgraph contains either a clique or an independent set of size at least . In (Combinatorica (2001), 155–170), Alon et al. proved that this conjecture was equivalent to a similar conjecture about tournaments. In the directed version of the conjecture cliques and stable sets are replaced by transitive subtournaments. For a fixed undirected graph H, define to be the supremum of all ε for which the following holds: for some n₀ and every every undirected graph with vertices not containing H as an induced subgraph has a clique or independent set of size at least . The analogous definition holds if H is a tournament. We call the Erdös–Hajnal coefficient of H. The Erdös–Hajnal conjecture is true if and only if for every H. We prove in this article that:

• the Erdös–Hajnal coefficient of every graph H is at most ,
• there exists such that the Erdös–Hajnal coefficient of almost every tournament T on k vertices is at most , i.e. the proportion of tournaments on k vertices with the coefficient exceeding goes to 0 as k goes to infinity.

     

Hierarchical Construction of Bounded Solutions in Critical Regularity Spaces

We construct uniformly bounded solutions for the equations div U = f and U = f in the critical cases and , respectively. Criticality in this context manifests itself by the lack of a linear solution operator mapping . Thus, the intriguing aspect here is that although the problems are linear, construction of their solutions is not. Our constructions are special cases of a general framework for solving linear equations of the form , where is a linear operator densely defined in Banach space with a closed range in a (proper subspace) of Lebesgue space , and with an injective dual . The solutions are realized in terms of a multiscale hierarchical representation, , interesting for its own sake. Here, u _j's are constructed recursively as minimizers of where the residuals are resolved in terms of a dyadic sequence of scales with large enough . The nonlinear aspect of this construction is a counterpart of the fact that one cannot linearly solve in critical regularity spaces.© 2016 Wiley Periodicals, Inc.     

On the Existence of

Let there is an . For or , has been determined by Hanani, and for or , has been determined by the first author. In this paper, we investigate the case . A necessary condition for is . It is known that , and that there is an for all with a possible exception . We need to consider the case . It is proved that there is an for all with an exception and a possible exception , thereby, .     

On the Hamilton–Waterloo Problem with Odd Orders

Given nonnegative integers , the Hamilton–Waterloo problem asks for a factorization of the complete graph into α ‐factors and β ‐factors. Without loss of generality, we may assume that . Clearly, v odd, , , and are necessary conditions. To date results have only been found for specific values of m and n. In this paper, we show that for any integers , these necessary conditions are sufficient when v is a multiple of and , except possibly when or 3. For the case where we show sufficiency when with some possible exceptions. We also show that when are odd integers, the lexicographic product of with the empty graph of order n has a factorization into α ‐factors and β ‐factors for every , , with some possible exceptions.     

Petersen Cores and the Oddness of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. We study lists by three 1‐factors, and call with a ‐core of G. If G is not 3‐edge‐colorable, then . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if , then is an upper bound for the girth of G. We show that bounds the oddness of G as well. We prove that . If , then every ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with . On the other hand, the difference between and can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer , there exists a bridgeless cubic graph G such that .     

The Game Saturation Number of a Graph

Given a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts). Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P₄‐saturation game on .     

A Hypercube Variant with Small Diameter

This article introduces a new variant of hypercubes . The n‐dimensional twisted hypercube is obtained from two copies of the ‐dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the n‐dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.     

Block‐Transitive and Point‐Primitive 2‐ Designs with Sporadic Socle

The purpose of this paper is to classify all pairs , where is a nontrivial 2‐ design, and acts transitively on the set of blocks of and primitively on the set of points of with sporadic socle. We prove that there exists only one such pair : is the unique 2‐(176,8,2) design and , the Higman–Sims simple group.     

Saturation Numbers in Tripartite Graphs

Given graphs H and F, a subgraph is an F‐saturated subgraph of H if , but for all . The saturation number of F in H, denoted , is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For and n₁, n₂, and n₃ sufficiently large, we determine and exactly and within an additive constant. We also include general constructions of ‐saturated subgraphs of with few edges for .     

A Note on the Order of Iterated Line Digraphs

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices of the k‐iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of G.     

Subcubic Edge‐Chromatic Critical Graphs Have Many Edges

We consider graphs G with such that and for every edge e, so‐called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, , is such a graph and has average degree only . He showed that every critical graph has average degree at least , and asked if is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if G is a subcubic critical graph other than , then G has average degree at least . This bound is best possible, as shown by the Hajós join of two copies of .     

Cayley Graphs of Diameter Two from Difference Sets

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree d and diameter k. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large d and if , and m is odd.     

Characterization of Digraphic Sequences with Strongly Connected Realizations

Let be a sequence of of nonnegative integers pairs. If a digraph D with satisfies and for each i with , then d is called a degree sequence of D. If D is a strict digraph, then d is called a strict digraphic sequence. Let be the collection of digraphs with degree sequence d . We characterize strict digraphic sequences d for which there exists a strict strong digraph .     

The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and , which has the most complete subgraphs of size t, for . The conjectured extremal graph is , where with . Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when , and also reduced the general conjecture to the case . We prove the conjecture for and also establish a weaker form of the conjecture for all r.     

A Complete Solution to the Existence of ‐Cycle Frames of Type

The existence problem of a ‐cycle frame of type is now solved for any quadruple .