Facets of the Graph Coloring Polytope

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.     

Critical Facets of the Stable Set Polytope

Dedicated to the memory of Paul Erdős A facet of the stable set polytope of a graph G can be viewed as a generalization of the notion of an -critical graph. We extend several results from the theory of -critical graphs to facets. The defect of a nontrivial, full-dimensional facet of the stable set polytope of a graph G is defined by . We prove the upper bound for the degree of any node u in a critical facet-graph, and show that can occur only when . We also give a simple proof of the characterization of critical facet-graphs with defect 2 proved by Sewell [11]. As an application of these techniques we sharpen a result of Surányi [13] by showing that if an -critical graph has defect and contains nodes of degree , then the graph is an odd subdivision of . Received October 23, 1998     

A Lower Bound for the Rectilinear Crossing Number

We give a new lower bound for the rectilinear crossing number of the complete geometric graph K_n. We prove that and we extend the proof of the result to pseudolinear drawings of K_n. Dedicated to the memory of our good friend and mentor Víctor Neumann-Lara. Received: April, 2003 Final version received: March 18, 2005     

A Lower Bound on Unknotting Number

In this paper the authors use a modified Wirtinger presentation to give a lower bound on the unknotting number of a knot in S3.     

Partitions of a Polytope and Mappings of a Point Set to Facets

Three theorems of this paper generalize previous results of the author on conjectures of A. Bezdek and V.V. Proizvolov. They show the existence of mappings from a given point set to the set of facets of a given polytope that satistfy some special conditions. Developing the same technique, some results on convex polytope partitions are presented, two of them dealing with partitions with prescribed measures of parts. Then we prove a corollary on the existence of a possibly nonconvex polytope with a given set of vertices, containing given points in its interior. We also consider problems of the following type: find an assignment of vectors from a given set to the parts of a given convex partition of ℝⁿ so that the shifts of the parts by their corresponding vectors either do not intersect by interior points or cover ℝⁿ     

A Lower Bound for the Crossing Number of Links in Thickened Surfaces

We introduce the notion of homological multiplicity for an oriented link in a thickened orientable closed surface. Using the notion, we establish some lower bounds for the crossing number of a link in thickened surfaces.     

关于Ramsey数下界的部分结果

本文得到 Ramsey数下界的一个计算公式 :R( l,s+ t-2 )≥ R( l,s) + R( l,t) -1 ,(式中 l、s、t≥ 3) .用此公式算得的 Ramsey数的下界比用其它公式算得的下界好 .     

A Lower Bound for the Algebraic Connectivity of a Graph in Terms of the Domination Number

We investigate how the algebraic connectivity of a graph changes by relocating a connected branch from one vertex to another vertex, and then minimize the algebraic connectivity among all connected graphs of order n with fixed domination number \(\gamma\leq\frac{n+2}{3}\), and finally present a lower bound for the algebraic connectivity in terms of the domination number. We also characterize the minimum algebraic connectivity of graphs with domination number half their order.     

A New Lower Bound on the Potential-Ramsey Number of Two Graphs

A nonincreasing sequence π=(d₁,…,d_n) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices.In this case,G is referred to as a realization of π.Given a graph H,a graphic sequence π is potentially H-graphic if π has a realization containing H as a subgraph.For graphs G₁ and G₂,the potential-Ramsey number r_pot(G₁,G₂) is the smallest integer k such that for every k-term graphic ...     

On a Finite Branch and Bound Algorithm for the Global Minimization of a Concave Power Law Over a Polytope

In this paper, a finite branch-and-bound algorithm is developed for the minimization of a concave power law over a polytope. Linear terms are also included in the objective function. Using the first order necessary conditions of optimality, the optimization problem is transformed into an equivalent problem consisting of a linear objective function, a set of linear constraints, a set of convex constraints, and a set of bilinear complementary constraints. The transformed problem is then solved using a finite branch-and-bound algorithm that solves two convex problems at each of its nodes. The method is illustrated by means of an example from the literature.     

A Lower Bound for the Determinantal Complexity of a Hypersurface

We prove that the determinantal complexity of a hypersurface of degree \(d > 2\) is bounded below by one more than the codimension of the singular locus, provided that this codimension is at least 5. As a result, we obtain that the determinantal complexity of the \(3 \times 3\) permanent is 7. We also prove that for \(n> 3\), there is no nonsingular hypersurface in \({\mathbb {P}}^n\) of degree d that has an expression as a determinant of a \(d \times d\) matrix of linear forms, while on the other hand for \(n \le 3\), a general determinantal expression is nonsingular. Finally, we answer a question of Ressayre by showing that the determinantal complexity of the unique (singular) cubic surface containing a single line is 5.     

A New Lower Bound on the Number of Odd Values of the Ordinary Partition Function

The parity of p(n), the ordinary partition function, has been studied for at least a century, yet it still remains something of a mystery. Although much work has been done, the known lower bounds for the number of even and odd values of p(n) for n ≤ N still appear to have a great deal of room for improvement. In this paper, we use classical methods to give a new lower bound for the number of odd values of p(n).     

图的距离无符号拉普拉斯谱半径的关于色数的下界

Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.     

A Bound for the Number of Preimages of a Polynomial Mapping

Mathematical Notes - An upper bound for the number of field elements that can be taken to roots of unity of fixed multiplicity by means of several given polynomials is obtained. This bound...     

A Lower Bound for the Height of a Rational Function at S-unit Points

Let a,b be given, multiplicatively independent positive integers and let >0. In a recent paper jointly with Y. Bugeaud we proved the upper bound exp(n) for g.c.d.(aⁿ–1, bⁿ–1); shortly afterwards we generalized this to the estimate g.c.d.(u–1,v–1)<>u,v) for multiplicatively independent S-units u,vZ. In a subsequent analysis of those results it turned out that a perhaps better formulation of them may be obtained in terms of the language of heights of algebraic numbers. In fact, the purposes of the present paper are: to generalize the upper bound for the g.c.d. to pairs of rational functions other than {u–1,v–1} and to extend the results to the realm of algebraic numbers, giving at the same time a new formulation of the bounds in terms of height functions and algebraic subgroups of G_m².     

Truncated Transversal Designs: A New Lower Bound on the Number of Idempotent MOLS of Side n

A truncated transversal design TTD of type g^km¹ is a {k, k+1}-GDD of type g^km¹ in which each point on the group of size m lies only in blocks of size k+1. Thus a TTD of type g^km¹ is equivalent to a transversal design TD (k, g) having m disjoint parallel classes of blocks. We employ a new construction developed by the author (1993, J. Combin. Des.1, 15–26) to show that if g₁<g₂ and if there exists a TD (k, g₁) and a TD (k+1, g₂), then there exists a TTD of type (g₁g₂)^km¹ for any 0m(g₂ div g₁) g²₁. As a corollary, we obtain a new lower bound on the number of mutually orthogonal idempotent latin squares of side g: if g₁<g₂ and there exist r MOLS of side g₁ and r+1 MOLS of side g₂ , then N(1 ^g₁g₂)r.     

关于《关于Ramsey数下界的部分结果》的注

本文用反例 ,说明了 [1 ]中 R( l,s+ t-2 ) R( l,s) + R( l,t) -1是错的     

Lower bounds for the Chvátal-Gomory rank in the 0/1 cube

We revisit the method of Chvátal, Cook, and Hartmann to establish lower bounds on the Chvátal-Gomory rank, and develop a simpler method. We provide new families of polytopes in the 0/1 cube with high rank, and we describe a deterministic family achieving a rank of at least (1+1/e)n−1>n. Finally, we show how integrality gaps lead to lower bounds.     

A Lower Bound for Congruence Representations

G. Grätzer, H. Lakser, and E. T. Schmidt proved that every finite distributive lattice D with n join-irreducible elements can be represented as the congruence lattice of a lattice L with O(n2) elements. G. Grätzer, I. Rival, and N. Zaguia gave kn, < 2, as a lower bound for the size of such a lattice L; a sharper form, 1/64(n/log2n)2, of this result was given by Y. Zhang.In this note, we apply a recent result of R. Freese, to obtain 1/16 n2/log2n as a lower bound. We also give a direct proof of Freese's result.     

A Sharp Bound for the Marginal Appendage Number

For a connected graph G, the distance d(u, v) between two vertices u and v is the length of a shortest u − v path in G and the distance d(v) of a vertex v is the sum of the distances between v and all vertices of G. The margin, μ (G), is the subgraph induced by vertices of G having the maximum distance. It is known that every graph is isomorphic to the margin of some graph H. For a graph G, the marginal appendage number is defined as min{p(H) − p(G) ∣ μ(H) = G}. In this paper it is shown that Δ (G) + 2 is a sharp bound for the marginal appendage number.