The isoperimetric constant of the random graph process

The isoperimetric constant of a graph G on n vertices, i(G), is the minimum of , taken over all nonempty subsets S ⊂ V (G) of size at most n/2, where ∂S denotes the set of edges with precisely one end in S. A random graph process on n vertices, , is a sequence of graphs, where is the edgeless graph on n vertices, and is the result of adding an edge to , uniformly distributed over all the missing edges. The authors show that in almost every graph process equals the minimal degree of as long as the minimal degree is o(log n). Furthermore, it is shown that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically Θ(log n), the ratio between the isoperimetric constant and the minimum degree falls from 1 to , its final value. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

A periodic isoperimetric problem related to the unique games conjecture

We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Let n ≥ 2. Suppose a subset Ω of n‐dimensional Euclidean space satisfies ?Ω = Ω^c and Ω + v = Ω^c (up to measure zero sets) for every standard basis vector . For any and for any q ≥ 1, let and let . For any x ∈ ?Ω, let N(x) denote the exterior normal vector at x such that ‖N(x)‖₂ = 1. Let . Our main result shows that B has the smallest Gaussian surface area among all such subsets Ω, less a small error: In particular, Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10^?9 would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.     

Discrete versions of continuous isoperimetric problems

Discrete isoperimetric variational problems which model single and double integral isoperimetric problems are formulated and some multiplier rules are derived. For quardratic functionals, the Euler-Lagrange equation is linear and can be analyzed bydeterminant methods. difference equations methods. or numerically bythealgebraic eigenvalue problem. A specific example is given wherethe eigenfuntions and eigenvalue of this discrete problem converge. as the step size goes to zero, to the eigenfunctionsand eigenvalues of the corresponding, continuous problem Recent developments in algebraic geometry offer the hopeof using Groebner (=Gröbner or Grobner) basis methods to numerically solve some systems of equationsgenerated by Lagrange multiplier methods. These methods mayapply to nonlinear systems of equations whenever they can be reduced to systems of polynomial equations. The Groebner basis algorithm of Buchberger is an extension of Gaussian elimination to polynomial systems.     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

Adaptable chromatic number of graph products

A colouring of the vertices of a graph (or hypergraph) G is adapted to a given colouring of the edges of G if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of G is the smallest integer k such that each edge-colouring of G by colours 1,2,…,k admits an adapted vertex-colouring of G by the same colours 1,2,…,k. (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph G is smaller than or equal to the ordinary chromatic number of G. While the ordinary chromatic number of all (categorical) powers G^k of G remains the same as that of G, the adaptable chromatic number of G^k may increase with k. We conjecture that for all sufficiently large k the adaptable chromatic number of G^k equals the chromatic number of G. When G is complete, we prove this conjecture with k≥4, and offer additional evidence suggesting it may hold with k≥2. We also discuss other products and propose several open problems.     

The isoperimetric problem on surfaces of revolution of decreasing Gauss curvature

We prove that the least-perimeter way to enclose prescribed area in the plane with smooth, rotationally symmetric, complete metric of nonincreasing Gauss curvature consists of one or two circles, bounding a disc, the complement of a disc, or an annulus. We also provide a new isoperimetric inequality in general surfaces with boundary.

     

R3中卯形闭曲面的等周亏格的上界的注记

利用R^3中卵形结果的高斯曲率不等式以及著名的等周不等式,将R^3中卵形闭曲面的高斯曲率K应用到空间曲面的等周亏格的上界估计中,得到了R^3中卵形闭曲面的等周亏格的一个新的上界,并给出其简单证明．     

多重调和映射的等周型和Fejer-Riesz型不等式

本文讨论多重调和映射的等周型和Fejer-Riesz型不等式.首先,本文改进Kalaj和Meˇstrovi′c的相应结果,并将其结果推广到多重调和映射.其次,本文证明Pavlovi′c和Dostani′c的相应结果对于多重调和映射也是成立的.最后,本文建立关于多重调和映射的Fejer-Riesz型不等式.     

The Bonnesen isoperimetric inequality in a surface of constant curvature

We first estimate the containment measure of a convex domain to contain in another in a surface X of constant curvature.Then we obtain the analogue of the known Bonnesen isoperimetric inequality for convex domain in X.Finally we strengthen the known Bonnesen isoperimetric inequality.     

An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.     

Existence of three weak solutions for a perturbed anisotropic discrete Dirichlet problem

In this paper, we study the existence of at least three distinct solutions for a perturbed anisotropic discrete Dirichlet problem. Our approach is based on recent variational methods for smooth functionals defined on reflexive Banach spaces. Some examples are presented to demonstrate the application of our main results.     

Dirichlet problem on locally finite graphs

In this paper, we study the existence and uniqueness of solutions to the vertex-weighted Dirichlet problem on locally finite graphs. Let B be a subset of the vertices of a graph G. The Dirichlet problem is to find a function whose discrete Laplacian on G?B and its values on B are given. Each infinite connected component of G?B is called an end of G relative to B. If there are no ends, then there is a unique solution to the Dirichlet problem. Such a solution can be obtained as a limit of an averaging process or as a minimizer of a certain functional or as a limit-solution of the heat equation on the graph. On the other hand, we show that if G is a locally finite graph with l ends, then the set of solutions of any Dirichlet problem, if non-empty, is at least l-dimensional.     

The carvingwidth of hypercubes

The notion of the carvingwidth of a graph was introduced by Seymour and Thomas [Call routing and the ratcatcher, Combinatorica 14 (1994) 217-241]. In this note, we show that the carvingwidth of a d-dimensional hypercube equals 2^d-1.     

Exceptional sets in Waring-Goldbach problem for fifth powers

We consider exceptional sets in the Waring-Goldbach problem for fifth powers.For example,we prove that all but O(N^131/132)integers satisfying the necessary local conditions can be represented as the sum of 11 fifth powers of primes,which improves the previous results due to A.V.Kumchev[Canad.J.Math.,2005,57:298–327]and Z.X.Liu[Int.J.Number Theory,2012,8:1247–1256].     

On the isoperimetric problem in Euclidean space with density

We study the isoperimetric problem for Euclidean space endowed with a continuous density. In dimension one, we characterize isoperimetric regions for a unimodal density. In higher dimensions, we prove existence results and we derive stability conditions, which lead to the conjecture that for a radial log-convex density, balls about the origin are isoperimetric regions. Finally, we prove this conjecture and the uniqueness of minimizers for the density exp by using symmetrization techniques. First and second authors are partially supported by MCyT-Feder research project MTM2004-01387, fourth author by the National Science Foundation.     

The Cauchy problem for the dissipative Boussinesq equation

This work is devoted to the solvability and finite time blow-up of solutions of the Cauchy problem for the dissipative Boussinesq equation in all space dimension. We prove the existence and uniqueness of local mild solutions in the phase space by means of the contraction mapping principle. By establishing the time-space estimates of the corresponding Green operators, we obtain the continuation principle. Under some restriction on the initial data, we further study the results on existence and uniqueness of global solutions and finite time blow-up of solutions with the initial energy at three different level. Moreover, the sufficient and necessary conditions of finite time blow-up of solutions are given.