Mantel's theorem for random graphs

For a graph G, denote by t(G) (resp. b(G)) the maximum size of a triangle‐free (resp. bipartite) subgraph of G. Of course for any G, and a classic result of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e., for what p = p(n)) is the “Erd?s‐Rényi” random graph G = G(n,p) likely to satisfy t(G) = b(G)? We show that this is true if for a suitable constant C, which is best possible up to the value of C. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 59–72, 2015     

Global optimization for first order Markov Random Fields with submodular priors

This paper copes with the global optimization of Markovian energies. Energies are defined on an arbitrary graph and pairwise interactions are considered. The label set is assumed to be linearly ordered and of finite cardinality, while each interaction term (prior) shall be a submodular function. We propose an algorithm that computes a global optimizer under these assumptions. The approach consists of mapping the original problem into a combinatorial one that is shown to be globally solvable using a maximum-flow/s-t minimum-cut algorithm. This restatement relies on considering the level sets of the labels (seen as binary variables) instead of the label values themselves. The submodularity assumption of the priors is shown to be a necessary and sufficient condition for the applicability of the proposed approach. Finally, some numerical results are presented.     

Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0–1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to n = 100, independent of the density. For some problems of special structure we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so. Supported in part by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438.     

On the complexity of cutting-plane proofs using split cuts

We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997) [20], implies that cutting-plane proofs which use split cuts (or, equivalently, mixed-integer rounding cuts or Gomory mixed-integer cuts) have exponential length in the worst case.     

Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts

An Euler tour in a hypergraph is a closed walk that traverses each edge of the hypergraph exactly once, while an Euler family, first defined by Bahmanian and ?ajna, is a family of closed walks that jointly traverse each edge exactly once and cannot be concatenated. In this paper, we study the notions of a spanning Euler tour and a spanning Euler family, that is, an Euler tour (family) that also traverses each vertex of the hypergraph at least once. We examine necessary and sufficient conditions for a hypergraph to admit a spanning Euler family, most notably when the hypergraph possesses a vertex cut consisting of vertices of degree two. Moreover, we characterise hypergraphs with a vertex cut of cardinality at most two that admit a spanning Euler tour (family). This result enables us to reduce the problem of existence of a spanning Euler tour (which is NP-complete), as well as the problem of a spanning Euler family, to smaller hypergraphs.     

Balloons,cut‐edges,matchings, and total domination in regular graphs of odd degree

A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}$ be the family of connected (2r+1)‐regular graphs with n vertices, and let ${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$. For ${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$, we prove the sharp inequalities c(G)?[r(n?2)?2]/(2r²+2r?1)?1 and α′(G)?n/2?rb/(2r+1). Using b?[(2r?1)n+2]/(4r²+4r?2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number γ_t(G) of a cubic graph, we prove γ_t(G)?n/2?b(G)/2 (except that γ_t(G) may be n/2?1 when b(G)=3 and the balloons cover all but one vertex). With α′(G)?n/2?b(G)/3 for cubic graphs, this improves the known inequality γ_t(G)?α′(G). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 116–131, 2010     

Gas-hydrate formation, agglomeration and inhibition in oil-based drilling fluids for deep-water drilling

One of the main challenges in deep-water drilling is gas-hydrate plugs, which make the drilling unsafe. Some oil-based drilling fluids (OBDF) that would be used for deep-water drilling in the South China Sea were tested to investigate the characteristics of gas-hydrate formation, agglomeration and inhibition by an experimental system under the temperature of 4 ℃ and pressure of 20 MPa, which would be similar to the case of 2000 m water depth. The results validate the hydrate shell formation model and show that the water cut can greatly influence hydrate formation and agglomeration behaviors in the OBDF. The oleophobic effect enhanced by hydrate shell formation which weakens or destroys the interfacial films effect and the hydrophilic effect are the dominant agglomeration mechanism of hydrate particles. The formation of gas hydrates in OBDF is easier and quicker than in water-based drilling fluids in deep-water conditions of low temperature and high pressure because the former is a W/O dispersive emulsion which means much more gas-water interfaces and nucleation sites than the later. Higher ethylene glycol concentrations can inhibit the formation of gas hydrates and to some extent also act as an anti-agglomerant to inhibit hydrates agglomeration in the OBDF.     

Statistical fluctuations in hot rotating nuclei

Thermal fluctuations in angular momentum due to excitation is investigated. Shape changes or structural rearrangement are observed as a consequence of fluctuation in second moment of spin. The uncertainty in angular momentum is considerably enhanced due to thermal fluctuation and is strongly dependent on spin and structural changes.     

Generation of three-dimensional block-structured grids based on rotation of two-dimensional multiply connected cross sections

An algorithm for generating curvilinear block-structured grids in axisymmetric three-dimensional domains of any connectivity is developed. The organization of the connection between the blocks is automated. The grids constructed are used to compute ideal gas steady flows past axisymmetric bodies at a nonzero angle of attack.     

Cone Adaptation Strategies for a Finite and Exact Cutting Plane Algorithm for Concave Minimization

In this paper we are concerned with pure cutting plane algorithms for concave minimization. One of the most common types of cutting planes for performing the cutting operation in such algorithm is the concavity cut. However, it is still unknown whether the finite convergence of a cutting plane algorithm can be enforced by the concavity cut itself or not. Furthermore, computational experiments have shown that concavity cuts tend to become shallower with increasing iteration. To overcome these problems we recently proposed a procedure, called cone adaptation, which deepens concavity cuts in such a way that the resulting cuts have at least a certain depth with 0, where is independent of the respective iteration, which enforces the finite convergence of the cutting plane algorithm. However, a crucial element of our proof that these cuts have a depth of at least was that we had to confine ourselves to -global optimal solutions, where is a prescribed strictly positive constant. In this paper we examine possible ways to ensure the finite convergence of a pure cutting plane algorithm for the case where = 0.