Connections between semidefinite relaxations of the max-cut and stable set problems

We describe links between a recently introduced semidefinite relaxation for the max-cut problem and the well known semidefinite relaxation for the stable set problem underlying the Lovász’s theta function. It turns out that the connection between the convex bodies defining the semidefinite relaxations mimics the connection existing between the corresponding polyhedra. We also show how the semidefinite relaxations can be combined with the classical linear relaxations in order to obtain tighter relaxations. This work was done while the author visited CWI, Amsterdam, The Netherlands. Svata Poljak untimely deceased in April 1995. We shall both miss Svata very much. Svata was an excellent colleague, from whom we learned a lot of mathematics and with whom working was always a very enjoyable experience; above all, Svata was a very nice person and a close friend of us. The research was partly done while the author visited CWI, Amsterdam, in October 1994 with a grant fom the Stieltjes Institute, whose support is gratefully acknowledged. Partially supported also by GACR 0519. Research support by Christian Doppler Laboratorium für Diskrete Optimierung.     

On set systems determined by intersections

The set systems determined by intersections are studied and a sufficient condotion for this property is given. For case of graphs a necessary and sufficient condition is established. Some connections to other results are discussed.     

On a product dimension of bipartite graphs

A product dimension of bipartite graphs bid G analogous to the Dushnik-Miller dimension of posets and to the dimension of general symmetric graphs is studied. It is shown that bidG ≦ 1/2|V(G)| + 1 and almost all bipartite graphs G have bidG close to 1/2|V(G)|. On the other hand it is shown to be considerably less for everyday graphs like trees, cycles, cubes, etc.     

A spectral approach to bandwidth and separator problems in graphs

Lower bounds on the bandwidth, the size of a vertex separator of general undirected graphs, and the largest common subgraph of two undirected (weighted) graphs are obtained. The bounds are based on a projection technique developed for the quadratic assignment problem, and once more demonstrate the importance of the extreme eigenvalues of the Laplacian. They will be shown to be strict for certain classes of graphs and compare favourably to bounds already known in literature. further improvement is gained by applying nonlinear optimization methods.     

The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤ 2 andx _ij -x _ik -x _jk ≤ 0 for 1 ≤i,j, k ≤n. Hence, the metric polytope M_n, defined as the solution set of the triangle inequalities, is a relaxation ofP _n . We consider several properties of geometric type for P_n, in particular, concerning its position withinM _n . Strengthening the known fact ([3]) thatP _n has diameter 1, we show that any set ofk cuts,k ≤ log₂ n, satisfying some additional assumption, determines a simplicial face ofM _n and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum of P_n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.     

On periodical behaviour in societies with symmetric influences

We propose a simple model of society with a symmetric functionw(u, v) measuring the influence of the opinion of memberv on that of memberu. The opinions are chosen from a finite set. At each step everyone accepts the majority opinion (with respect tow) of the other members. The behaviour of such a society is clearly periodic after some initial time. We prove that the length of the period is either one or two.     

Energy Properties and Biomass Yield of Miscanthus x Giganteus Fertilized by Municipal Sewage Sludge

The application of municipal sewage sludge as fertilizer in the production of non-food energy crops is an environmentally and economically sustainable approach to sewage sludge management. In addition, the application of municipal sewage sludge to energy crops such as Miscanthus x giganteus is an alternative form of recycling nutrients and organic material from waste. Municipal sewage sludge is a potential source of heavy metals in the soil, some of which can be removed by growing energy crops that are also remediation agents. Therefore, the objective of the research was to investigate the effect of municipal sewage sludge applied at three different rates of 1.66, 3.22 and 6.44 t/ha on the production of Miscanthus. Based on the analyses conducted on the biomass of Miscanthus fertilized with sludge from the wastewater treatment plant in three fertilization treatments, it can be concluded that the biomass of Miscanthus is a good feedstock for the process of direct combustion. Moreover, the application of the largest amount of municipal sewage sludge during cultivation had no negative effect on the properties of Miscanthus biomass. Moreover, the cellulose and hemicellulose content of Miscanthus is ideal for the production of second-generation liquid biofuels. Fertilizer treatments had no effect on the content of cellulose and lignin, while a significant statistical difference was found for hemicellulose.     

Stochastic analysis of the electromagnetic induction effect on a neuron’s action potential dynamics

Nonlinear Dynamics - The presence of time-varying electromagnetic fields across a neuron cell may cause changes in its electrical characteristics, most notably, in the action potential dynamics....     

Laplacian eigenvalues and the maximum cut problem

We introduce and study an eigenvalue upper bound(G) on the maximum cut mc (G) of a weighted graph. The function(G) has several interesting properties that resemble the behaviour of mc (G). The following results are presented.We show that is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. We prove that(G) is never worse that 1.131 mc(G) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. We give a dual characterization of(G), and show that(G) is computable in polynomial time with an arbitrary precision.The research has been partially done when the second author visited LRI in September 1989.