Sum-Free Sets and Related Sets

A   of integers is sum-free if . Cameron conjectured that the number of sum-free sets is . As a step towards this conjecture, we prove that the number of sets satisfying

Efficient generation of accurate mobility maps using machine learning algorithms

U.S Army’s mission is to develop, integrate, and sustain the right technology solutions for all manned and unmanned ground vehicles, and mobility is a key requirement for all ground vehicles. Mobility focuses on ground vehicles’ capabilities that enable them to be deployable worldwide, operationally mobile in all environments, and protected from symmetrical and asymmetrical threats. In order for military ground vehicles to operate in any combat zone, the planners require a mobility map that gives the maximum predicted speeds on these off-road terrains. In the past, empirical and semi-empirical techniques (Ahlvin and Haley, 1992; Haley et al., 1979) were used to predict vehicle mobility on off-road terrains such as the NATO Reference Mobility Model (NRMM). Because of its empirical nature, the NRMM method cannot be extrapolated to new vehicle designs containing advanced technologies, nor can it be applied to lightweight robotic vehicles.The mobility map is a function of different parameters such as terrain topology and profile, soil type (mud, snow, sand, etc.), vegetation, obstacles, weather conditions, and vehicle type and characteristics.A physics-based method such as the discrete element method (DEM) (Dasch et al., 2016) was identified by the NATO Next Generation NRMM Team as a potential high fidelity method to model the soil. This method allows the capture of the soil deformation as well as its non-linear behavior. Hence it allows the simulation of the vehicle on any off-road terrain and have an accurate mobility map generated. The drawback of the DEM method is the required simulation time. It takes several weeks to generate the mobility map because of the large number of soil particles (millions) even while utilizing high performance computing.One approach to reduce the computational time is to use machine learning algorithms to predict the mobility map. Machine learning (Boutell et al., 2004; Burges, 1998; Barber et al., 1997) can lead to very accurate mobility predictions over a wide range of terrains. Machine learning is divided into two categories: the supervised and the unsupervised learning. Supervised learning requires the training data to be labeled into predetermined classes, while the unsupervised learning does not require the training data to be labeled. Machine learning can help generate mobility maps using trained models created from a minimum number of simulation runs. In this study different supervised machine learning algorithms such as the support vector machine (SVM), the nearest neighbor classifier (k-NN), decision trees, and boosting methods were used to create trained models labeled as 2 classes for the ‘go/no-go’ map, 5 classes for the 5-speed map, and 7 classes for the 7-speed map. The trained models were created from the physics-based simulation runs of a nominal wheeled vehicle traversing on a cohesive soil.     

Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three

. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs. Received: November 21, 1996/Revised: Revised February 19, 1998     

Note – Edge-Coloring Cliques with Three Colors on All 4-Cliques

is constructed such that every copy of has at least three colors on its edges. As , the number of colors used is . This improves upon the previous probabilistic bound of due to Erdős and Gyárfás. Received: March 12, 1998     

Algorithms for Measuring Perturbability in Matroid Optimization

perturbability function of a matroid measures the maximum increase in the weight of its minimum weight bases that can be produced by increases of a given total cost on the weights of its elements. We present an algorithm for computing this function that runs in strongly polynomial time for matroids in which independence can be tested in strongly polynomial time. Furthermore, for the case of transversal matroids we are able to take advantage of their special structure to design a faster algorithm for computing the perturbability function. Received: June 13, 1997     

A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations

be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset . In the minimum 0-extension problem (*), one is asked for finding a (semi)metric m on V such that m coincides with μ within T, each is at zero distance from some , and the value is as small as possible. This is the classical minimum (undirected) cut problem when and , and the minimum (2, r)-metric problem when μ is the path metric of the complete bipartite graph . It is known that the latter problem can be solved in strongly polynomial time by use of the ellipsoid method. We develop a polynomial time algorithm for the minimum (2, r)-metric problem, using only ``purely combinatorial' means. The algorithm simultaneously solves a certain associated integer multiflow problem. We then apply this algorithm to solve (*) for a wider class of metrics μ, present other results and raise open questions. Received: June 11, 1998     

An Extremal Problem For Random Graphs And The Number Of Graphs With Large Even-Girth

C _{2 k} -free subgraph of a random graph may have, obtaining best possible results for a range of p=p(n). Our estimates strengthen previous bounds of Füredi [12] and Haxell, Kohayakawa, and Łuczak [13]. Two main tools are used here: the first one is an upper bound for the number of graphs with large even-girth, i.e., graphs without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom condition; the second tool is the powerful result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [1] on uncrowded hypergraphs as given by Duke, Lefmann, and R?dl [7]. Received: February 17, 1995     

Invariant distributions supported on the nilpotent cone of a semisimple Lie algebra

Let be a semisimple complex Lie algebra with adjoint group and be the algebra of differential operators with polynomial coefficients on . If is a real form of , we give the decomposition of the semisimple -module of invariant distributions on supported on the nilpotent cone.

     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

Linear k-blocking Sets

We point out the relationship between normal spreads and the linear k-blocking sets introduced in [9]. We give a characterisation of linear k-blocking sets proving that the projections and the embeddings of a PG(kt,q) in are linear k-blocking sets of . Finally, we construct some new examples. Received December 19, 1997/Revised September 19, 2000 RID="*" ID="*" Partially supported by Italian M.U.R.S.T.