Abstract Extending the notion of geometric bijections for regular matroids, introduced by the first and third author with Matthew Baker, we describe a family of bijections between bases of an oriented matroid and special reorientations of it. These bijections are specified by a pair of circuit and cocircuit signatures coming respectively from a generic single-element lifting and extension. We then characterize generic single-element liftings and extensions using these bijections. We also explain the relation of our work with works of Gioan–Las Vergnas and Ding. Some implications in oriented matroid programming and oriented matroid triangulations are also discussed.

Abstract Let $$\Delta _{k}(n)$$ Δ k ( n ) denote the simplicial complex of $$(k+1)$$ ( k + 1 ) -crossing-free subsets of edges in $${\left( {\begin{array}{c}[n]\\ 2\end{array}}\right) }$$ [ n ] 2 . Here $$k,n\in \mathbb {N}$$ k , n ∈ N and $$n\ge 2k+1$$ n ≥ 2 k + 1 . Jonsson (2003) proved that [neglecting the short edges that cannot be part of any $$(k+1)$$ ( k + 1 ) -crossing], $$\Delta _{k}(n)$$ Δ k ( n ) is a shellable sphere of dimension $$k(n-2k-1)-1$$ k ( n - 2 k - 1 ) - 1 , and conjectured it to be polytopal. The same result and question arose in the work of Knutson and Miller (Adv Math 184(1):161-176, 2004) on subword complexes. Despite considerable effort, the only values of (k, n) for which the conjecture is known to hold are $$n\le 2k+3$$ n ≤ 2 k + 3 (Pilaud and Santos, Eur J Comb. 33(4):632–662, 2012. https://doi.org/10.1016/j.ejc.2011.12.003 ) and (2, 8) (Bokowski and Pilaud, On symmetric realizations of the simplicial complex of 3-crossing-free sets of diagonals of the octagon. In: Proceedings of the 21st annual Canadian conference on computational geometry, 2009). Using ideas from rigidity theory and choosing points along the moment curve we realize $$\Delta _{k}(n)$$ Δ k ( n ) as a polytope for $$(k,n)\in \{(2,9), (2,10) , (3,10)\}$$ ( k , n ) ∈ { ( 2 , 9 ) , ( 2 , 10 ) , ( 3 , 10 ) } . We also realize it as a simplicial fan for all $$n\le 13$$ n ≤ 13 and arbitrary k, except the pairs (3, 12) and (3, 13). Finally, we also show that for

Knowledge graphs represent relationships between entities. These graphs can take dynamic forms to trace changes along time through text models and further used by reasoning systems with the intent to answer queries. In this research we explore their applicability for extracting temporal patterns of knowledge in the form of communities. To this end, we propose a method for generating knowledge relationships over unconnected components of a knowledge graph, allowing for a targeted exploration of emerging contents in corpora. This analysis is applied to the corpora of the Conference on Knowledge Discovery and Data Mining (KDD) publications over the last decade. We find the key knowledge communities over time and rank the underlying concepts. Results show that the publication efforts increasingly focus on graph research and the creation of relationships instead of new concepts. The acquired results confirm the validity of the proposed knowledge discovery methodology for community-centered analysis of emerging changes in dynamic knowledge graphs.

Diabetic Foot Ulcers (DFU) are lesions in the foot region caused by diabetes mellitus. It is essential to define the appropriate treatment in the early stages of the disease once late treatment may result in amputation. This article proposes an ensemble approach composed of five modified convolutional neural networks (CNNs) - VGG-16, VGG-19, Resnet-50, InceptionV3, and Densenet-201 - to classify DFU images. To define the parameters, we fine-tuned the CNNs, evaluated different configurations of fully connected layers, and used batch normalization and dropout operations. The modified CNNs were well suited to the problem; however, we observed that the union of the five CNNs significantly increased the success rates. We performed tests using 8,250 images with different resolution, contrast, color, and texture characteristics and included data augmentation operations to expand the training dataset. 5-fold cross-validation led to an average accuracy of 95.04%, resulting in a Kappa index greater than 91.85%, considered “Excellent”.

Network sampling is the task of selecting a subset of nodes and links from a network in a way that preserves its topological properties and other user requirements. This paper investigates the problem of generating an unbiased network sample that contains balanced proportion of nodes from different groups. Creating such a representative sample would require handling the trade-off between ensuring structural preservability and group representativity of the selected nodes. We present a novel max-min subgraph fairness measure that can be used as a unifying framework to combine both criteria. A greedy algorithm is then proposed to generate a fair and representative sample from an initial set of target nodes. A theoretical approximation guarantee for the output of the proposed greedy algorithm based on submodularity and curvature ratios is also presented. Experimental results on real-world datasets show that the proposed method will generate more fair and representative samples compared to other existing network sampling methods.

Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph data due to their ability to learn a concise representation of the data by integrating the node attributes and link information in a principled fashion. However, despite their promise, there are several practical challenges that must be overcome to effectively use them for node classification problems. In particular, current approaches are vulnerable to different kinds of biases inherent in the graph data. First, if the class distribution is imbalanced, then the GNNs' loss function is biased towards classifying the majority class correctly rather than the minority class, which hurts the performance of the latter class. Second, due to homophily effect, the learned representation and subsequent downstream tasks may favor certain demographic groups over others when applied to social network data. To mitigate such biases, we propose a novel framework called Fairness-Aware Cost Sensitive Graph Convolutional Network (FACS-GCN) for classifying nodes in networks with skewed class distributions. Our approach combines a cost-sensitive exponential loss with an adversarial learning component to alleviate the ill-effects of both biases. The framework employs a stagewise additive modeling approach to ensure there is no significant loss in accuracy when imparting fairness into the GNN. Experimental results on 6 benchmark graph data demonstrate the effectiveness of FACS-GCN against comparable baseline methods in terms of promoting fairness while maintaining a high model accuracy on the majority of the datasets.

Abstract We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of d/2 in dimension d, achieved by the “standard terminal simplices” and direct sums of them. We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino and Schymura (Discrete Comput. Geom. 58(3), 663–685 (2017)) that the d-th covering minimum of the standard terminal n-simplex equals d/2, for every $$n\ge d$$ n ≥ d . We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger’s formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume. To this end, we introduce a new notion of discrete surface area of non-hollow simplices. We prove our discrete analog in dimension two and give strong evidence for its validity in arbitrary dimension.

We extend White's classification of empty tetrahedra to the complete classification of lattice 3-polytopes with five lattice points, showing that, apart from infinitely many of width one, there are exactly nine equivalence classes of them with width two and none of larger width. We also prove that, for each $n\in\mathbb{N}$, there is only a finite number of (classes of) lattice 3-polytopes with $n$ lattice points and of width larger than one. This implies that extending the present classification to larger sizes makes sense, which is the topic of subsequent papers of ours.

We completely classify lattice 3-polytopes with six lattice points, modulo unimodular equivalence. We give explicit coordinates for representatives of each, together with other invariants, such as their oriented matroid (or order type) and volume vector. There are infinitely many of width one, 74 of width two, two of width three, and none of larger width. Those of width one lie, in terms of their oriented matroid, in eight infinite classes and 12 individual polytopes.

No abstract available.

We consider whether any two triangulations of a polygon or a point set on a nonplanar surface with a given metric can be transformed into each other by a sequence of edge flips. The answer is negative in general with some remarkable exceptions, such as polygons on the cylinder, and on the flat torus, and certain configurations of points on the cylinder.

For any finite set A of n points in general position in R2, we define a (3n-3)-dimensional simple polyhedron whose face poset is isomorphic to the poset of "non-crossing marked graphs" with vertex set A, where a marked graph is defined as a geometric graph together with a subset of its pointed vertices. The poset of non-crossing graphs on A appears as the complement of the star of a face in that polyhedron.The polyhedron has a unique maximal bounded face, of dimension 3n-3-2n;b; where n;b; is the number of convex hull points of A. The vertices of this polytope are all the pseudo triangulations of A, and the edges are flips of two types: the traditional diagonal flips (in pseudo-triangulations) and the removal or insertion of a single edge.

The interaction between polyhedral combinatorics and algebraic geometry is a classical theme. Two examples from the 70's, in which each discipline has benefited from the other, are the Bernstein-Kouchnirenko-Khovanski Theorem on the number of roots of a generic sparse system via mixed volumes and the algebraic proofs by Stanley of the Upper Bound Theorem for simplicial spheres and the g-theorem for simplicial polytopes.

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than p). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide---to the best of our knowledge---the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces.

This paper presents an approach to the automatic classification of microorganisms based on image-processing techniques. A computer application that processes and classifies the images has been developed. The classification is carried out using a competitive neural network. Its input pattern is evaluated from a frequency analysis of images taken through a microscope. This paper focuses on the application of this technique to the classification of living diatoms.

This paper presents an approach to the automatic supervision of the sugar crystallization process based on image-processing techniques. The detection of the different phases of the process is carried out by generating patterns from a wavelet decomposition of the microscopic images taken from the process.

A dissection of a convex d-polytope is a partition of the polytope into d-simplices whose vertices are among the vertices of the polytope. Triangulations are dissections that have the additional property that the set of all its simplices forms a simplicial complex. The size of a dissection is the number of d-simplices it contains. This paper compares triangulations of maximal size with dissections of maximal size. We also exhibit lower and upper bounds for the size of dissections of a 3-polytope and analyze extremal size triangulations for specific nonsimplicial polytopes: prisms, antiprisms, Archimedean solids, and combinatorial d-cubes.

Voronoi diagrams in the plane for strictly convex distances have been studied in [3], [5] and [7]. These distances induce the usual topology in the plane and, moreover, the Voronoi diagrams they produce enjoy many of the good properties of Euclidean Voronoi diagrams. Nevertheless, we show (Th.1) that it is not possible to transform, by means of a bijection from the plane into itself, the computation of such Voronoi diagrams to the computation of Euclidean Voronoi diagrams (except in the trivial case of the distance being affinely equivalent to the Euclidean distance). The same applies if we want to compute just the topological shape of a Voronoi diagram of at least four points (Th.2).