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.     

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.     

A Rigidity Result for Overdetermined Elliptic Problems in the Plane

Let be a (locally) Lipschitz function and a domain whose boundary is unbounded and connected. If there exists a positive bounded solution to the overdetermined elliptic problem we prove that Ω is a half‐plane. In particular, we obtain a partial answer to a question raised by H. Berestycki, L. Caffarelli, and L. Nirenberg in 1997.© 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.     

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 .     

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 .     

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.     

On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring

A proper k‐coloring of a graph is a function such that , for every . The chromatic number is the minimum k such that there exists a proper k‐coloring of G. Given a spanning subgraph H of G, a q‐backbone k‐coloring of is a proper k‐coloring c of such that , for every edge . The q‐backbone chromatic number is the smallest k for which there exists a q‐backbone k‐coloring of . In this work, we show that every connected graph G has a spanning tree T such that , and that this value is the best possible. As a direct consequence, we get that every connected graph G has a spanning tree T for which , if , or , otherwise. Thus, by applying the Four Color Theorem, we have that every connected nonbipartite planar graph G has a spanning tree T such that . This settles a question by Wang, Bu, Montassier, and Raspaud (J Combin Optim 23(1) (2012), 79–93), and generalizes a number of previous partial results to their question.     

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 .     

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 .     

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.     

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 .     

Optimal 1—Spontaneous Emission Error Designs*

A t‐spontaneous emission error design, denoted by t‐ SEED or t‐SEED in short, is a system of k‐subsets of a v‐set V with a partition of satisfying for any and , , where is a constant depending only on E. The design of t‐SEED was introduced by Beth et al. in 2003 (T. Beth, C. Charnes, M. Grassl, G. Alber, A. Delgado, M. Mussinger, Des Codes Cryptogr 29 (2003), 51–70) to construct quantum jump codes. The number m of designs in a t‐ SEED is called dimension, which corresponds to the number of orthogonal basis states in a quantum jump code. A t‐SEED is nondegenerate if every point appears in each of its member design. A nondegenerate t‐SEED is called optimal when it achieves the largest possible dimension. This paper investigates the dimension of optimal 1‐SEEDs, in which Baranyai's Lemma plays a significant role and the hypergraph distribution is closely related as well. Several classes of optimal 1‐SEEDs are shown to exist. In particular, we determine the exact dimensions of optimal 1‐ SEEDs for all orders v and block sizes k with .     

Asymptotic Size of Covering Arrays: An Application of Entropy Compression

A covering array is an array A such that each cell of A takes a value from a v‐set V, which is called the alphabet. Moreover, the set is contained in the set of rows of every subarray of A. The parameter N is called the size of an array and denotes the smallest N for which a exists. It is well known that  [10]. In this paper, we derive two upper bounds on using an algorithmic approach to the Lovász local lemma also known as entropy compression.     

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, .     

Matching Extension Missing Vertices and Edges in Triangulations of Surfaces

Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let be the Euler characteristic of Σ. Suppose that with even and M and N are two matchings in of sizes m and n respectively such that . It is shown that if the pairwise distance between any two elements of is at least five and the face‐width of the embedding of G in Σ is at least , then there is a perfect matching M₀ in containing M such that .     

On the Rigidity of Sparse Random Graphs

A graph with a trivial automorphism group is said to be rigid. Wright proved (Acta Math 126(1) (1971), 1–9) that for a random graph is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for with positive probability is nontrivial. We show that in the sparser case , it holds whp that G's 2‐core is rigid. We conclude that for all p, a graph in is reconstructible whp. In addition this yields for a canonical labeling algorithm that almost surely runs in polynomial time with o(1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92).     

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.     

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.     

Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

For any graph G, let be the number of spanning trees of G, be the line graph of G, and for any nonnegative integer r, be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e. In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on for such a graph G.