Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

On qualitatively independent partitions and related problems

The paper is concerned with several related combinatorial problems one of which is that of estimating the numbers of qualitatively independent p-partitions. Besides nonconstructive basic estimates, a constructive procedure yielding not much worse ones is presented. In conclusion, some applications are shown.     

Long induced paths and cycles in Kneser graphs

We present some lower and upper bounds on the length of the maximum induced paths and cycles in Kneser graphs.     

Graphs with the balas—uhry property

We characterize graphs H with the following property: Let G be a graph and F be a subgraph of G such that (i) each component of F is isomorphic to H or K₂, (ii) the order of F is maximum, and (iii) the number of H-components in F is minimum subject to (ii). Then a maximum matching of F is also a maximum matching of G. This result is motivated by an analogous property of fractional matchings discovered independently by J. P. Uhry and E. Balas.     

On the dimension of trees

It is proved that for trees (and forests) G one has dimG?3 log⁺₂∣G∣(where dim G, the dimension of G, is the minimum k such that G is embeddable into a product of k complete graphs; ∣G∣ is the size of G). Moreover, if m(G) is the quotient of G obtained by identifying the points with coinciding neighbour sets, one has, for forests G, log⁺₂ ∣m(G)∣ ? 1 ? dimG ? 3 log⁺₂m(G>) + 1. Also, for the bipartite dimension bid G (arising from embeddings into P^k₃) one has bid G ? 8 log⁺₂ ∣G ∣.     

Optimization of Two Eco-Friendly Extractions of Black Medick (Medicago lupulina L.) Phenols and Their Antioxidant,Cosmeceutical, α-Glucosidase and α-Amylase Inhibitory Properties

Medicago lupulina is an ancient edible plant from the Fabaceae family. In this work, two eco-friendly methods for extraction of bioactive phenolics from M. lupulina were developed using mixtures of water with two non-toxic, skin- and environmentally-friendly polyol solvents: glycerol and polypropylene glycol. Ultrasound-assisted extractions were optimized using a Box–Behnken design. The independent variables were the concentration of organic solvent in water (X₁), extraction temperature (X₂) and time (X₃), while the response was phenolic content. The optimum conditions for extraction of polyphenols were (X₁, X₂, X₃): (45%, 70 °C, 60 min) and (10%, 80 °C, 60 min) for glycerol and polypropylene glycol extraction, respectively. The extracts prepared at optimum conditions were rich in phenolic compounds, mainly derivatives of apigenin, kaempferol, luteolin, quercetin, caffeic and ferulic acid, as well as coumestrol. Their cosmeceutical and antidiabetic activity was tested. Both extracts demonstrated notable antioxidant, anti-lipoxygenase and anti-α-amylase activity. In addition to those activities, the glycerol extract efficiently inhibited protein coagulation, elastase and α-glucosidase activity. Glycerol present in the extract displayed enzyme-inhibiting activity in several assays and supported the action of the bioactive constituents. Thus, the optimized glycerol extract is a desirable candidate for direct incorporation in antidiabetic food supplements and cosmeceutical products.     

One-third-integrality in the max-cut problem

Given a graphG = (V, E), the metric polytopeS (G) is defined by the inequalitiesx(F) – x(CF) |F| – 1 for , |F| odd,C cycle ofG, and 0 x _e 1 fore E. Optimization overS (G) provides an approximation for the max-cut problem. The graphG is called 1/d-integral if all the vertices ofS(G) have their coordinates in{i/d 0 i d}. We prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for 1/3-integrality. In particular, we characterize the 1/3-integral graphs on seven nodes. We study several operations preserving 1/d-integrality, in particular, thek-sum operation for 0 k 3. We prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytopeS (G) {x x u} are 1/3-integral for every choice of 1/3-integral bounds, u on the edges ofG. Research by this author was partially done at CWI in Amsterdam.Research by this author was done at the Institut für Diskrete Mathematik of Bonn, supported by the A. von Humboldt Foundation.Deceased on April 2nd, 1995.     

Nonlinear programming methods in the presence of noise

The problem of minimizing a nonlinear function with nonlinear constraints when the values of the objective, the constraints and their gradients have errors, is studied. This noise may be due to the stochastic nature of the problem or to numerical error.Various previously proposed methods are reviewed. Generally, the minimization algorithms involve methods of subgradient optimization, with the constraints introduced through penalty, Lagrange, or extended Lagrange functions. Probabilistic convergence theorems are obtained. Finally, an algorithm to solve the general convex (nondifferentiable) programming problem with noise is proposed.Originally written for presentation at the 1976 Budapest Symposium on Mathematical Programming.     

Maximum bipartite subgraphs of Kneser graphs

We investigate the maximum number of edges in a bipartite subgraph of the Kneser graphK(n, r). The exact solution is given for eitherr arbitrary andn (4.3 + o(1))r, orr = 2 andn arbitrary. The problem is in connection with the study of the bipartite subgraph polytope of a graph.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences