Search

We study the existence of nontrivial unbounded surfaces S ⊂ ℝ³ with the property that the constant charge distribution on S is an electrostatic equilibrium, i.e., the resulting electrostatic force is normal to the surface at each point on S . Among bounded regular surfaces S, only the round sphere has this property by a result of Reichel [Arch. Ration. Mech. Anal., 137 (1997), pp. 381--394] (see also Mendez and Reichel [Forum Math., 12 (2000), pp. 223--245]) confirming a conjecture of Gruber. In the present paper, we show the existence of nontrivial exceptional domains Ω ⊂ ℝ³ whose boundaries S=∂Ω enjoy the above property. [ABSTRACT FROM AUTHOR]

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

Let r \geq k \geq 2 and K(k) r,n denote the complete n-balanced r-partite k-uniform hypergraph, whose vertex set consists of r parts, each has n vertices, and whose edge set contains all the k-element subsets with no two vertices from one part. A decomposition of K(k) r,n is a partition of E(K(k) r,n). A perfect matching (resp., Hamilton tight cycle) decomposition of K(k) r,n is a decomposition of K(k) r,n into perfect matchings (resp., Hamilton tight cycles). In this paper, we prove that if k | n (resp., 2 - k and k | n), then K(k) k+1,n (resp., K(k) k+2,n) has a perfect matching decomposition. We also prove that for any integer k \geq 2, K(k) k+1,n has a Hamilton tight cycle decomposition. In all cases, we use constructive methods involving number theory. In fact, we confirm two conjectures proposed by Zhang, Lu, and Liu [Appl. Math. Comput., 386 (2020), 125492]. [ABSTRACT FROM AUTHOR]

Given a graph H, the Tur'an number ex(n,H) is the largest number of edges in an Hfree graph on n vertices. We make progress on a recent conjecture of Conlon, Janzer, and Lee [More on the Extremal Number of Subdivisions, arXiv:1903.10631v1, 2019] on the Tur'an numbers of bipartite graphs, which in turn yields further progress on a conjecture of Erdos and Simonovits [Combinatorica, 1 (1981), pp. 25-42]. Let s, t, k = 2 be integers. Let Kk s,t denote the graph obtained from the complete bipartite graph Ks,t by replacing each edge uv in it with a path of length k between u and v such that the st replacing paths are internally disjoint. It follows from a general theorem of Bukh and Conlon [J. Eur. Math. Soc. (JEMS), 20 (2018), pp. 1747-1757] that ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Conlon, Janzer, and Lee recently conjectured that for any integers s, t, k = 2, ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Among many other things, they settled the k = 2 case of their conjecture. As the main result of this paper, we prove their conjecture for k = 3, 4. Our main results also yield infinitely many new so-called Tur'an exponents: rationals r ? (1, 2) for which there exists a bipartite graph H with ex(n,H) = T(nr), adding to the lists recently obtained by Jiang, Ma, and Yepremyan [On Tur'an Exponents of Bipartite Graphs, arXiv:1806.02838, 2018], by Kang, Kim, and Liu [On the Rational Tur'an Exponent Conjecture, arXiv:1811.06916, 2018], and by Conlon, Janzer, and Lee. Our method builds on an extension of the Conlon-Janzer-Lee method. We also note that the extended method also gives a weaker version of the Conlon-Janzer-Lee conjecture for all k = 2. [ABSTRACT FROM AUTHOR]

Tuza [Finite and Infinite Sets, Proc. Colloq. Math. Soc. János Bolyai 37, North Holland, 1981, p. 888] conjectured that τ(G) ≤ 2v(G) for all graphs G, where τ(G) is the minimum size of an edge set whose removal makes G triangle-free and v(G) is the maximum size of a collection of pairwise edge-disjoint triangles. Here, we generalize Tuza's conjecture to simple binary matroids that do not contain the Fano plane as a restriction and prove that the geometric version of the conjecture holds for cographic matroids. [ABSTRACT FROM AUTHOR]

M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687{694] that a bipartite digraph of minimum out-degree at least 3 contains two vertex disjoint directed cycles of different lengths. In this paper, we disprove this conjecture. Further, we classify strong tournaments and strong bipartite tournaments of minimum out-degree 3 without two vertex disjoint directed cycles of different lengths. [ABSTRACT FROM AUTHOR]

A queue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its queue-number. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in $\mathbb{Z}^3$ and the edges by noncrossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph G is closely related to the queue-number of G. In particular, if G is an n-vertex member of a proper minor-closed family of graphs (such as a planar graph), then G has a $\mathcal{O}(1) \times \mathcal{O}(1) \times \mathcal{O}(n)$ drawing if and only if G has a $\mathcal{O}(1)$ queue-number. (2) It is proved that the queue-number is bounded by the tree-width, thus resolving an open problem due to Ganley and Heath [Discrete Appl. Math., 109 (2001), pp. 215--221] and disproving a conjecture of Pemmaraju [Exploring the Powers of Stacks and Queues via Graph Layouts, Ph. D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1992]. This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with $\mathcal{O}(n)$ volume. This is the most general family of graphs known to admit three-dimensional drawings with $\mathcal{O}(n)$ volume. The proofs depend upon our results regarding track layouts and tree-partitions of graphs, which may be of independent interest. [ABSTRACT FROM AUTHOR]

This paper presents some known results on the approximate and null controllability of the Navier­Stokes equations. All of them can be viewed as partial answers to a conjecture of J.-L. Lions. [ABSTRACT FROM AUTHOR]

Consider a semialgebraic function f: Rn → R, which is continuous around a point x ∈ Rn. Using the so-called tangency variety of f at x, we first provide necessary and sufficient conditions for x to be a local minimizer of, and then in the case where x is an isolated local minimizer of, we define a "tangency exponent" α* > 0 so that for any α &#8712 R the following four conditions are always equivalent: (i) the inequality a≤a* holds, (ii) the point x is an ceth order sharp local minimizer of, (iii) the limiting subdifferential df of f is (α -- l)th order strongly metrically subregular at x for 0, and (iv) the function f satisfies the Łojaseiwcz gradient inequality at x with the exponent 1-- 1/α. Besides, we also present a counterexample to a conjecture posed by Drusvyatskiy and Ioffe [Math. Program. Ser. A, 153 (2015), pp. 635-653]. [ABSTRACT FROM AUTHOR]

Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented a proof of a theorem of Reed and Wakabayashi that a brick G is nonsolid if and only if there exist two vertex-disjoint odd cycles C1 and C2 such that G V (C1 ∪ C2) has a perfect matching. Consequently, every brick with no two vertex-disjoint odd cycles is solid. Recently, Lucchesi et al. [SIAM J. Discrete Math., 32 (2018), pp. 1478--1501] constructed infinite families of solid bricks containing two vertex-disjoint odd cycles. Noticing that none of these graphs is cubic, they conjectured that no cubic solid brick contains two vertex-disjoint odd cycles. In this note, we present an infinite family of graphs showing that this conjecture fails. We further show that the minimum counterexample is unique, which has 12 vertices. [ABSTRACT FROM AUTHOR]

King, Lu, and Peng recently proved that for Δ ≥ 4, any KΔ-free graph with maximum degree Δ has fractional chromatic number at most Δ - 2/67 unless it is isomorphic to C5 ... K2 or C8². Using a different approach we give improved bounds for Δ ≥ 6 and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's ω, Δ, χ conjecture. [ABSTRACT FROM AUTHOR]

An L(p, 1)-labeling of a graph is a function f from the vertex set to the positive integers such that |f(x)-f(y)|≥p if dist(x, y)=1 and |f(x)-f(y)|≥1 if dist (x, y)=2 ,w h e r e dist(x, y) is the distance between the two vertices x and y in the graph. The span of an L(p, 1)- labeling f is the di?erence between the largest and the smallest labels used by f. In 1992, Griggs and Yeh conjectured that every graph with maximum degree Δ≥2 has an L(2, 1)-labeling with span at most Δ². We settle this conjecture for Δ sufficiently large. More generally, we show that for any positive integer p there exists a constant Δp such that every graph with maximum degree Δ ≥ Δp has an L(p, 1)-labeling with span at most Δ². This yields that for each positive integer p, there is an integer Cp such that every graph with maximum degree Δ has an L(p, 1)-labeling with span at most Δ² + Cp. [ABSTRACT FROM AUTHOR]

The smoothed analysis of algorithms is concerned with the expected running time of an algorithm under slight random perturbations of arbitrary inputs. Spielman and Teng proved that the shadow vertex simplex method has polynomial smoothed complexity. On a slight random perturbation of an arbitrary linear program, the simplex method finds the solution after a walk on polytope(s) with expected length polynomial in the number of constraints n, the number of variables d, and the inverse standard deviation of the perturbation 1/σ. We show that the length of walk in the simplex method is actually polylogarithmic in the number of constraints n. Spielman-Teng's bound on the walk was O*(n86d55σ-30), up to logarithmic factors. We improve this to O(log7 n(d9 +d3σ-4)). This shows that the tight Hirsch conjecture n-d on the length of walk on polytopes is not a limitation for the smoothed linear programming. Random perturbations create short paths between vertices. We propose a randomized Phase-I for solving arbitrary linear programs, which is of independent interest. Instead of finding a vertex of a feasible set, we add a vertex at random to the feasible set. This does not affect the solution of the linear program with constant probability. So, in expectation it takes a constant number of independent trials until a correct solution is found. This overcomes one of the major difficulties of smoothed analysis of the simplex method-one can now statistically decouple the walk from the smoothed linear program. This yields a much better reduction of the smoothed complexity to a geometric quantity-the size of planar sections of random polytopes. We also improve upon the known estimates for that size, showing that it is polylogarithmic in the number of vertices. [ABSTRACT FROM AUTHOR]

We describe a new method of computing functions of highly nonnormal matrices by using the concept of approximate diagonalization. We formulate a conjecture about its efficiency and provide both theoretical and numerical evidence in support of the conjecture. We apply the method to compute arbitrary real powers of highly nonnormal matrices. [ABSTRACT FROM AUTHOR]