Search

Using a mixed methods approach, we explore a relationship between students' graph reasoning and graph selection via a fully online assessment. Our population includes 673 students enrolled in college algebra, an introductory undergraduate mathematics course, across four U.S. postsecondary institutions. The assessment is accessible on computers, tablets, and mobile phones. There are six items; for each, students are to view a video animation of a dynamic situation (e.g., a toy car moving along a square track), declare their understanding of the situation, select a Cartesian graph to represent a relationship between given attributes in the situation, and enter text to explain their graph choice. To theorize students' graph reasoning, we draw on Thompson's theory of quantitative reasoning, which explains students' conceptions of attributes as being possible to measure. To code students' written responses, we appeal to Johnson and colleagues' graph reasoning framework, which distinguishes students' quantitative reasoning about one or more attributes capable of varying (Covariation, Variation) from students' reasoning about observable elements in a situation (Motion, Iconic). Quantitizing those qualitative codes, we examine connections between the latent variables of students' graph reasoning and graph selection. Using structural equation modeling, we report a significant finding: Students' graph reasoning explains 40% of the variance in their graph selection (standardized regression weight is 0.64, p < 0.001). Furthermore, our results demonstrate that students' quantitative forms of graph reasoning (i.e., variational and covariational reasoning) influence the accuracy of their graph selection. [ABSTRACT FROM AUTHOR]

The article discusses tectonic stresses determined in the West Sakhalin terrain using different tectonophysical methods. The reconstruction of the stress field in coal fields in Sakhalin is implemented using the graphical method of orientation finding of stress axes in fractures and faults (at 16 observation points). The supplementary on-site tectonophysical studies made it possible to estimate the preferred orientation of the main slickensides of different kinematics and to reconstruct on this basis the local stress tensors at 53 observation points. The typical stress state of the West Sakhalin terrain is horizontal tension. [ABSTRACT FROM AUTHOR]

This study aimed to investigate direct relationships of work addiction symptoms with dimensions of work engagement. We used three samples in which work addiction was measured with the Bergen Work Addiction Scale and work engagement was measured with the Utrecht Work Engagement Scale. One sample comprised responses from working Norwegians (n1 = 776), and two samples comprised responses from working Poles (n2 = 719; n3 = 715). We jointly estimated three networks using the fused graphic lasso method. Additionally, we estimated the stability of each network, node centrality, and node predictability and quantitatively compared all networks. The results showed that absorption and mood modification could constitute a bridge between work addiction and work engagement. It suggests that further investigation of properties of absorption and mood modification might be crucial for answering the question of how engaged workers become addicted to work. [ABSTRACT FROM AUTHOR]

Affect (e.g., beliefs, attitudes, emotions) plays a crucial role in mathematics learning, but reliance on verbal and written responses (from surveys, interviews, etc.) limits students' expression of their affective states. As a complement to existing methods that rely on verbal reports, we explore how graphing can be used to study affect during mathematical experiences. We analyze three studies that used graphing to represent, stimulate recall, and reflect on affect. In each, students were asked to draw their perception of an affective construct, such as confidence or intensity of emotion, against time. The studies differed in participant populations, target affect, timescales of participant experience, and structural features of the graphs. The affordances of graphing include reduced dependence on verbal data, temporal ordering of participants' recollections, explicit representation of change over time, and the creation of objects (the graph) for discussion. These studies as examples show that well-structured graphing can productively supplement existing methods for studying affect in mathematics education, as a different medium through which students can communicate their experience. [ABSTRACT FROM AUTHOR]

We examine a publication by Euler, De novo genere oscillationum, written in 1739 and published in 1750, in which he derived for the first time, the differential equation of the (undamped) simple harmonic oscillator under harmonic excitation, namely the motion of an object acted on by two forces, one proportional to the distance traveled, the other varying sinusoidally with time. He then developed a general solution, using two different methods of integration, making extensive use of direct and inverse sine and cosine functions. After much manipulation of the resulting equations, he proceeded to an analysis of the periodicity of the solutions by varying the relation between two parameters, a and b , eventually identifying the phenomenon of resonance in the case where 2 b = a . This is shown to be nothing more than the equality between the driving frequency and the natural frequency of the oscillator, which, indeed, characterizes the phenomenon of resonance. Graphical representations of the behavior of the oscillator for different relations between these parameters are given. Despite having been a brilliant discovery, Euler's publication was not influential and has been neglected by scholars and by specialized publications alike. [ABSTRACT FROM AUTHOR]

The automation of document processing has recently gained attention owing to its great potential to reduce manual work. Any improvement in information extraction systems or reduction in their error rates aids companies working with business documents because lowering reliance on cost-heavy and error-prone human work significantly improves the revenue. Neural networks have been applied to this area before, but they have been trained only on relatively small datasets with hundreds of documents so far. To successfully explore deep learning techniques and improve information extraction, we compiled a dataset with more than 25,000 documents. We expand on our previous work in which we proved that convolutions, graph convolutions, and self-attention can work together and exploit all the information within a structured document. Taking the fully trainable method one step further, we now design and examine various approaches to using Siamese networks, concepts of similarity, one-shot learning, and context/memory awareness. The aim is to improve micro F 1 of per-word classification in the huge real-world document dataset. The results verify that trainable access to a similar (yet still different) page, together with its already known target information, improves the information extraction. The experiments confirm that all proposed architecture parts (Siamese networks, employing class information, query-answer attention module and skip connections to a similar page) are all required to beat the previous results. The best model yields an 8.25% gain in the F 1 score over the previous state-of-the-art results. Qualitative analysis verifies that the new model performs better for all target classes. Additionally, multiple structural observations about the causes of the underperformance of some architectures are revealed, since all the techniques used in this work are not problem-specific and can be generalized for other tasks and contexts. [ABSTRACT FROM AUTHOR]

This paper proposes a process for locating civic action, in its varied forms, wherever it may appear. First, develop a clear, a priori definition of the qualities of action you consider "civic." Simultaneously, observe actors' varied "typifications (Schutz 1962, 1970; Cicourel 1991, 1993; Cefaï 1994)" that include action that you would call "civic." We illustrate how to use this approach, using the case of "empowerment projects (Eliasoph Journal of Civil Society, 12(3), 247–265, 2016):" Observe the typifications that actors themselves experience in empowerment projects, by observing the dilemmas they experience. You will see that actors' typical patterns of navigating those typical dilemmas often have typical unintended consequences, both for their own emotions, and for the researcher's aspirations for civic action. In empowerment projects, typical patterns of navigating typical dilemmas tend to make important kinds of politically oriented civic action difficult to conduct. This kind of back-and-forth examination reveals the "civic landscape (Grubb and Henriksen 2018)" in the making. [ABSTRACT FROM AUTHOR]

Deep learning has brought a dramatic development in molecular property prediction that is crucial in the field of drug discovery using various representations such as fingerprints, SMILES, and graphs. In particular, SMILES is used in various deep learning models via character-based approaches. However, SMILES has a limitation in that it is hard to reflect chemical properties. In this paper, we propose a new self-supervised method to learn SMILES and chemical contexts of molecules simultaneously in pre-training the Transformer. The key of our model is learning structures with adjacency matrix embedding and learning logics that can infer descriptors via Quantitative Estimation of Drug-likeness prediction in pre-training. As a result, our method improves the generalization of the data and achieves the best average performance by benchmarking downstream tasks. Moreover, we develop a web-based fine-tuning service to utilize our model on various tasks. [ABSTRACT FROM AUTHOR]

Key issues related to determining the limit of quantification (LOQ) in practice are considered. Requirements to the value of LOQ and its precision and accuracy are formulated. It is shown that the use of a calibration curve for LOQ determination may result in erroneous conclusions for impurity determination methods. Answers to a number of questions relevant to practice are given. The precision of the LOQ value should always be checked if the LOQ is determined from a calibration curve. A typical requirement for LOQ precision is RSD ≤ 5.0%. An RSD ≤ 10% is acceptable in exceptional cases of a very low LOQ concentration. For this, the validation documentation should visually confirm the acceptability of the LOQ value by a chromatogram of a solution of the determined substance with the LOQ concentration. [ABSTRACT FROM AUTHOR]

Reliability assessment is the key to the reliability design of a complex system. This paper takes the lithium battery pole slice separators (LBPSS) as the research object and selects the superposition Weibull model as the initial model. Based on the graphic method, a pivot quantity is introduced to estimate the range of scale parameters. A genetic algorithm is used to optimize parameters in a given parameter interval. Compared with other models and techniques, using the superposition Weibull model, pivot quantity, and graphic method to evaluate the reliability of LBPSS is more reasonable, provides a reference for improving the reliability and maintainability of LBPSS, and lays a theoretical foundation for analyzing the failure mode and failure mechanism of a complex system. [ABSTRACT FROM AUTHOR]

We identify and investigate isoscattering strings of concatenating quantum graphs possessing n units and 2n infinite external leads. We give an insight into the principles of designing large graphs and networks for which the isoscattering properties are preserved for n → ∞ . The theoretical predictions are confirmed experimentally using n = 2 units, four-leads microwave networks. In an experimental and mathematical approach our work goes beyond prior results by demonstrating that using a trace function one can address the unsettled until now problem of whether scattering properties of open complex graphs and networks with many external leads are uniquely connected to their shapes. The application of the trace function reduces the number of required entries to the 2 n × 2 n scattering matrices S ^ of the systems to 2n diagonal elements, while the old measures of isoscattering require all (2 n) 2 entries. The studied problem generalizes a famous question of Mark Kac "Can one hear the shape of a drum?", originally posed in the case of isospectral dissipationless systems, to the case of infinite strings of open graphs and networks. [ABSTRACT FROM AUTHOR]

A paper reviews existing and future seismohydroacoustic technologies, equipment, and novel scientific approaches to studying the Arctic Ocean. Particular attention is paid to the state of scientific and practical groundwork in the possibilities of developing passive geohydroacoustic methods for monitoring the ice-covered shelf of Russia's northern seas. New knowledge on the structure and conditions of the formation and propagation of wave fields in the layered lithosphere–hydrosphere–ice–cover-atmosphere system generated by induced geodynamic processes has been obtained in the course of solving a separate class of problems within the fundamental scientific problem of seeking ways to build innovative, environmentally friendly geophysical technologies for delineating local heterogeneities, including hydrocarbon deposits, in ice-covered water areas. [ABSTRACT FROM AUTHOR]

In Earth science, original data elaboration is often very complex and the results are generally provided in the form of (computer-made) maps, a qualitative representation. The aim of this paper is to illustrate a graphic method of analysis that allows the reverse: tracing back, on scientific bases, quantitative data from computer-mapped information, by using widely-available graphic tools, including an estimate of the precision of the numerical outcomes. That may be needed, e.g., for independent evaluation of published data or, for comparison with new elaborations. A NASA video was used as an example, reconstructing the maps of the Earth surface yearly from 1998 to 2017. Static frames were extracted from it and used to obtain numerical data on the evolution of the min/max snow/ice-covered land/sea surfaces, separately for the two hemispheres. The use of the proposed method allows concerned scientists to obtain the quantitative values of the relevant data, including an uncertainty estimate, e.g., in order to compare them with those found in the literature and on websites. The paper focuses on the map-analysis method, and on the metrological evaluation of the uncertainty of the retrieved data. Finally, some quantitative results are commented and found consistent with literature data on the same subject matter. [ABSTRACT FROM AUTHOR]

This article discusses the mathematizing of the chemical periodic system as a grid, which leads to a quadratic function or "binódica function" formed by pairs of periods or binodos (dyads). We describe the periodic law as an increasing function of the principal quantum number (n). It works subject to the dialectical laws that generate; first: gradual quantitative changes: (2n2), with "duplication" of periods: (2n2, 2n2). Second: radical quantitative changes: (4n2), with the emergence of new quantum transitions, growth and a change in the format of the binodos (qualitative change). We use analytical and graphic methods to mathematize Mendeleev's law, making the size of the binodos (Y) and the continuous series (Z) depend on the number of the binode (B), which is the same quantum number (n). Likewise, we show a graphic representation, in 2D, of a continuous and self-similar spiral function of the elements, in a geometric growth pattern. [ABSTRACT FROM AUTHOR]

Network science has become a powerful tool to describe the structure and dynamics of real-world complex physical, biological, social, and technological systems. Largely built on empirical observations to tackle heterogeneous, temporal, and adaptive patterns of interactions, its intuitive and flexible nature has contributed to the popularity of the field. With pioneering work on the evolution of random graphs, graph theory is often cited as the mathematical foundation of network science. Despite this narrative, the two research communities are still largely disconnected. In this commentary, we discuss the need for further cross-pollination between fields – bridging the gap between graphs and networks – and how network science can benefit from such influence. A more mathematical network science may clarify the role of randomness in modeling, hint at underlying laws of behavior, and predict yet unobserved complex networked phenomena in nature. What is the path towards a physical theory of complex networked systems? With an eye to the historical maths-physics duality, and an outlook towards the future, this commentary discusses promises and challenges accompanying the convergence of formal graph theory and data-inspired network science. [ABSTRACT FROM AUTHOR]

We develop graphlet analysis for multiplex networks and discuss how this analysis can be extended to multilayer and multilevel networks as well as to graphs with node and/or link categorical attributes. The analysis has been adapted for two typical examples of multiplexes: economic trade data represented as a 957-plex network and 75 social networks each represented as a 12-plex network. We show that wedges (open triads) occur more often in economic trade networks than in social networks, indicating the tendency of a country to produce/trade of a product in local structure of triads which are not closed. Moreover, our analysis provides evidence that the countries with small diversity tend to form correlated triangles. Wedges also appear in the social networks, however the dominant graphlets in social networks are triangles (closed triads). If a multiplex structure indicates a strong tie, the graphlet analysis provides another evidence for the concepts of strong/weak ties and structural holes. In contrast to Granovetter's seminal work on the strength of weak ties, in which it has been documented that the wedges with only strong ties are absent, here we show that for the analyzed 75 social networks, the wedges with only strong ties are not only present but also significantly correlated. [ABSTRACT FROM AUTHOR]

Cyber-physical system (CPS) is an orchestration of cyber and physical system, in which enormous events are generated. The emerging technology of complex event processing (CEP) could be utilized to generate composite events which are combined with atomic events through composition operation. In this paper, an algebra of interaction events (AI(E)) is proposed to describe various kinds of interaction events. AI(E) has two binary operators of union "+" and synchronization "·". Further, the algebra structure (AI(E), + , · , 0, 1) is strictly proved to be a commutative semiring in theory. Additionally, a graphic description method of partial-order tree is introduced to specify the construction of interaction events. Meanwhile, this paper discusses how to detect the significant events from numerous primitive events on the basis of partial-order tree. Finally, a simulation of smart home is executed to verify out method. Simulation result shows that the numbers of events will be decreased in each cycle of CEP by using AI(E). [ABSTRACT FROM AUTHOR]

This paper presents a novel subject-dependent deep aging path (SDAP), which inherits the merits of both generative probabilistic modeling and inverse reinforcement learning to model the facial structures and the longitudinal face aging process of a given subject. The proposed SDAP is optimized using tractable log-likelihood objective functions with convolutional neural networks (CNNs) based deep feature extraction. Instead of applying a fixed aging development path for all input faces and subjects, SDAP is able to provide the most appropriate aging development path for individual subject that optimizes the reward aging formulation. Unlike previous methods that can take only one image as the input, SDAP further allows multiple images as inputs, i.e. all information of a subject at either the same or different ages, to produce the optimal aging path for the given subject. Finally, SDAP allows efficiently synthesizing in-the-wild aging faces. The proposed model is experimented in both tasks of face aging synthesis and cross-age face verification. The experimental results consistently show SDAP achieves the state-of-the-art performance on numerous face aging databases, i.e. FG-NET, MORPH, aging faces in the wild (AGFW), and cross-age celebrity dataset (CACD). Furthermore, we also evaluate the performance of SDAP on large-scale Megaface challenge to demonstrate the advantages of the proposed solution. [ABSTRACT FROM AUTHOR]

In sufficiently large schools, courses are given to classes in sections of various sizes. Consequently, classes have to be split into various given numbers of sections. We focus on how to dispatch the students into sections of equal size, so as to minimize the number of edges in the resulting conflict graph. As a main result, we show that subdividing the students set in a regular way is optimal. We then discuss our solution uniqueness and feasibility, as well as practical issues concerning teacher assignments to sections and the case of an additional course with unequal section sizes requirements. [ABSTRACT FROM AUTHOR]

Network representation learning (NRL) enables the application of machine learning tasks such as classification, prediction and recommendation to networks. Apart from their graph structure, networks are often associated with diverse information in the form of attributes. Most NRL methods have focused just on structural information, and separately apply a traditional representation learning on attributes. When multiple sources of information are available, using a combination of them may be beneficial as they complement each other in generating accurate contexts; moreover, their combined use may be fundamental when the information sources are sparse. The learning methods should thus preserve both the structural and attribute aspects. In this paper, we investigate how attributes can be modeled, and subsequently used along with structural information in learning the representation. We introduce the GAT2VEC framework that uses structural information to generate structural contexts, attributes to generate attribute contexts, and employs a shallow neural network model to learn a joint representation from them. We evaluate our proposed method against state-of-the-art baselines, using real-world datasets on vertex classification (multi-class and multi-label), link-prediction, and visualization tasks. The experiments show that GAT2VEC is effective in exploiting multiple sources of information, thus learning accurate representations and outperforming the state-of-the-art in the aforementioned tasks. Finally, we perform query tasks on learned representation and show how the qualitative analysis of results has better performance as well. [ABSTRACT FROM AUTHOR]

The minimum number of observations such that the maximum likelihood estimator in a Gaussian graphical model exists with probability one is called the maximum likelihood threshold of the underlying graph G. The natural algebraic relaxation is the generic completion rank introduced by Uhler. We show that the maximum likelihood threshold and the generic completion rank behave in the same way under clique sums, which gives us large families of graphs on which these invariants coincide. On the other hand, we determine both invariants for complete bipartite graphs Km,n and show that for some choices of m and n the two parameters may be quite far apart. In particular, this gives the first examples of graphs on which the maximum likelihood threshold and the generic completion rank do not agree. [ABSTRACT FROM AUTHOR]

This paper investigates the vertex coloring problem in an uncertain graph in which all vertices are deterministic, while all edges are not deterministic and exist with some degree of belief in uncertain measures. The concept of the maximal uncertain independent vertex set of an uncertain graph is first introduced. We then present a degree of belief rule to obtain the family of maximal uncertain independent vertex sets. Based on the maximal uncertain independent vertex set, some properties of the separation degree of an uncertain graph are discussed. Following that, the concept of an uncertain chromatic set is introduced. Then, a maximum separation degree algorithm is derived to obtain the uncertain chromatic set. Finally, numerical examples are presented to demonstrate the application of the vertex coloring problem in uncertain graphs and the effectiveness of the maximum separation degree algorithm. [ABSTRACT FROM AUTHOR]

The mantle is the intersection of all ground models of V. We show that if there exists an extendible cardinal then the mantle is the smallest ground model of V. [ABSTRACT FROM AUTHOR]

A graph-controlled insertion-deletion system is a regulated extension of an insertion-deletion system. It has several components and each component contains some insertion-deletion rules. These components are the vertices of a directed control graph. A transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. This also describes the arcs of the control graph. Starting from an axiom in the initial component, strings thus move through the control graph. The language of the system is the set of all terminal strings collected in the final component. In this paper, we investigate a variant of the main question in this area: which combinations of size parameters (the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; plus three similar restrictions with respect to deletion) are sufficient to maintain computational completeness of such restricted systems under the additional restriction that the (undirected) control graph is a path? Notice that these results also bear consequences for the domain of insertion-deletion P systems, improving on a number of previous results from the literature, concerning in particular the number of components (membranes) that are necessary for computational completeness results. [ABSTRACT FROM AUTHOR]

In a seminal paper Montanari and Meseguer have shown that an algebraic interpretation of Petri nets in terms of commutative monoids can be used to provide an elegant characterisation of the deterministic computations of a net, accounting for their sequential and parallel composition. A smoother and more complete theory for deterministic computations has been later developed by relying on the concept of pre-net, a variation of Petri nets with a non-commutative flavor. This paper shows that, along the same lines, by adding an (idempotent) operation and thus considering dioids (idempotent semirings) rather than just monoids, one can faithfully characterise the non-deterministic computations of a net. [ABSTRACT FROM AUTHOR]

Dimension reduction techniques are very important, as high-dimensional data are ubiquitous in many real-world applications, especially in this era of big data. In this paper, we propose a novel supervised dimensionality reduction method, called appropriate points choosing based DAG-DNE (Apps-DAG-DNE). In Apps-DAG-DNE, we choose appropriate points to construct adjacency graphs, for example, it chooses nearest neighbors to construct inter-class graph, which can build a margin between samples if they belong to the different classes, and chooses farthest points to construct intra-class graph, which can establish relationships between remote samples if and only if they belong to the same class. Thus, Apps-DAG-DNE could find a good representation for original data. To investigate the performance of Apps-DAG-DNE, we compare it with the state-of-the-art dimensionality reduction methods on Caltech-Leaves and Yale datasets. Extensive experimental demonstrates that the proposed Apps-DAG-DNE outperforms other dimensionality reduction methods and achieves state-of-the-art performance for image classification. [ABSTRACT FROM AUTHOR]

The Apriori algorithm is one of the most well-known and widely accepted methods for the association rule mining. In Apriori, it uses a prefix tree to represent k-itemsets, generates k-itemset candidates based on the frequent (k-1)-itemsets, and determines the frequent k-itemsets by traversing the prefix tree iteratively based on the transaction records. When k is small, the execution of Apriori is very efficient. However, the execution of Apriori could be very slow when k becomes large because of the deeper recursion depth to determine the frequent k-itemsets. From the perspective of graph computing, the transaction records can be converted to a graph G(V,E), where V is the set of vertices of G that represents the transaction records and E is the set of edges of G that represents the relations among transaction records. Each k-itemset in the transaction records will have a corresponding connected component in G. The number of vertices in the corresponding connected component is the support of the k-itemset. Since the time to find the corresponding connected component of a k-itemset in G is constant for any k, the graph computing method will be very efficient if the number of k-itemsets is relatively small. Based on Apriori and graph computing techniques, a hybrid method, called Apriori and Graph Computing (ANG), is proposed to compute the frequent itemsets. Initially, ANG uses Apriori to compute the frequent k-itemsets and then switches to the graph computing method when k becomes large (where the number of k-itemset candidates is relatively small). The experimental results show that ANG outperforms both Apriori and the graph computing method for all test cases. [ABSTRACT FROM AUTHOR]

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets Vi, i∈{1,…,k}, where each Vi is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs ST3n is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs SGn with respect to all connected graphs G of order 4. [ABSTRACT FROM AUTHOR]

Let S1 and S2 be two (k − 1)-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S1 ∩ e ≠ ∅ and S2 ∩ e ≠ ∅ or e ⊆ S1 ∪ S2 or e ⊇ S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k2 − k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k − 1)-sets equal to 2n−4(k−1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k−2)k. If the degree sum of any two middle independent (k−1)-subsets is larger than 2(d−1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k − 1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n. [ABSTRACT FROM AUTHOR]

The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (As and Ad) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix AsTAs is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of As and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm. [ABSTRACT FROM AUTHOR]

Despite the influences on one’s thoughts and actions, the attitude has usually been overlooked in conflict analysis. The purpose of this paper is to develop a new systematic methodology for the graph model for conflict resolution that can be employed to study real-world conflict situations and gain enhanced insights. More specifically, the proposed method starts with the development of an expanded option-oriented preference structure that is derived from decision makers’ attitudes toward others. Then based on this attitude-driven preference structure, the general concepts of stabilities are extended to contain the definitions of different degrees of stabilities under attitude. In addition, the proposed method is embedded in a decision support system, called NUAAGMCR, to facilitate the analytical process. Through a detailed case study of the two-stage environmental conflict of post-Fukushima controversy in Japan, the predicted resolutions are demonstrated to be more accurate and stable than those derived by the general stability analysis. [ABSTRACT FROM AUTHOR]

Let X be a bounded subset of Rd and write Cu(X) for the set of uniformly continuous functions on X equipped with the uniform norm. The lower and upper box dimensions, denoted by dim̲B(graph(f)) and dim¯B(graph(f)), of the graph graph(f) of a function f∈Cu(X) are defined by dim̲B(graph(f))=limδ↘0inflogNδ(graph(f))-logδ,dim¯B(graph(f))=limδ↘0suplogNδ(graph(f))-logδ,where Nδ(graph(f)) denotes the number of δ-mesh cubes that intersect graph(f).Hyde et al. have recently proved that the box counting function (∗)logNδ(graph(f))-logδof the graph of a typical function f∈Cu(X) diverges in the worst possible way as δ↘0. More precisely, Hyde et al. showed that for a typical function f∈Cu(X), the lower box dimension of the graph of f is as small as possible and if X has only finitely many isolated points, then the upper box dimension of the graph of f is as big as possible.In this paper we will prove that the box counting function (*) of the graph of a typical function f∈Cu(X) is spectacularly more irregular than suggested by the result due to Hyde et al. Namely, we show the following surprising result: not only is the box counting function in (*) divergent as δ↘0, but it is so irregular that it remains spectacularly divergent as δ↘0 even after being “averaged" or “smoothened out" using exceptionally powerful averaging methods including all higher order Hölder and Cesàro averages and all higher order Riesz-Hardy logarithmic averages. For example, if the box dimension of X exists, then we show that for a typical function f∈Cu(X), all the higher order lower Hölder and Cesàro averages of the box counting function (*) are as small as possible, namely, equal to the box dimension of X, and if, in addition, X has only finitely many isolated points, then all the higher order upper Hölder and Cesàro averages of the box counting function (*) are as big as possible, namely, equal to the box dimension of X plus 1. [ABSTRACT FROM AUTHOR]

We study generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise naturally from the shortest-path distances on directed graphs. Perhaps surprisingly, very little is known about low-distortion embeddings for quasimetric spaces.Random embeddings into ultrametric spaces are arguably one of the most successful geometric tools in the context of algorithm design. We extend this to the quasimetric case as follows. We show that any n-point quasimetric space supported on a graph of treewidth t admits a random embedding into quasiultrametric spaces with distortion O(tlog2n), where quasiultrametrics are a natural generalization of ultrametrics. This result allows us to obtain tlogO(1)n-approximation algorithms for the Directed Non-Bipartite Sparsest Cut and the Directed Multicut problems on n-vertex graphs of treewidth t, with running time polynomial in both n and t. The above results are obtained by considering a generalization of random partitions to the quasimetric case, which we refer to as random quasipartitions. Using this definition and a construction of Chuzhoy and Khanna (JACM 56(2):6, 2009) we derive a polynomial lower bound on the distortion of random embeddings of general quasimetric spaces into quasiultrametric spaces. Finally, we establish a lower bound for embedding the shortest-path quasimetric of a graph G into graphs that exclude G as a minor. This lower bound is used to show that several embedding results from the metric case do not have natural analogues in the quasimetric setting. [ABSTRACT FROM AUTHOR]

A Not-All-Equal decomposition of a graph G is a decomposition of the vertices of G into two parts such that each vertex in G has at least one neighbor in each part. Also, a 1-in-Degree decomposition of a graph G is a decomposition of the vertices of G into two parts A and B such that each vertex in the graph G has exactly one neighbor in part A. Among our results, we show that for a given graph G, if G does not have any cycle of length congruent to 2 mod 4, then there is a polynomial time algorithm to decide whether G has a 1-in-Degree decomposition. In sharp contrast, we prove that for every r, r≥3, for a given r-regular bipartite graph G determining whether G has a 1-in-Degree decomposition is NP-complete. These complexity results have been especially useful in proving NP-completeness of various graph related problems for restricted classes of graphs. In consequence of these results we show that for a given bipartite 3-regular graph G determining whether there is a vector in the null-space of the 0,1-adjacency matrix of G such that its entries belong to {±1,±2} is NP-complete. Among other results, we introduce a new version of Planar 1-in-3 SAT and we prove that this version is also NP-complete. In consequence of this result, we show that for a given planar (3, 4)-semiregular graph G determining whether there is a vector in the null-space of the 0,1-incidence matrix of G such that its entries belong to {±1,±2} is NP-complete. [ABSTRACT FROM AUTHOR]

We propose a multi-fidelity system reduction technique that uses weighted graphs paired with three-dimensional discrete fracture network (DFN) modelling for efficient simulation of subsurface flow and transport in fractured media. DFN models are used to simulate flow and transport in subsurface fractured rock with low-permeability. One method to alleviate the heavy computational overhead associated with these simulations is to reduce the size of the DFN using a graph representation of it to identify the primary flow sub-network and only simulate flow and transport thereon. The first of these methods used unweighted graphs constructed solely on DFN topology and could be used for accurate predictions of first-passage times. However, these techniques perform poorly when predicting later stages of the mass breakthrough. We utilize a weighted-graph representation of the DFN where edge weights are based on hydrological parameters in the DFN that allows us to exploit the kinematic quantities derivable a posteriori from the flow solution obtained on the graph representation of the DFN to perform system reduction and predict the later stages of the breakthrough curve with high fidelity. We also propose and demonstrate the use of an adaptive pruning algorithm with error control that produces a pruned DFN sub-network whose predicted mass breakthrough agrees with the original DFN within a user-specified tolerance. The method allows for the level of accuracy to be a user-controlled parameter. [ABSTRACT FROM AUTHOR]

The paper gives an overview of a number of mathematical models and problems on planning anti-terrorist and special actions. These are problems of monitoring a territory, protecting critical infrastructure (described by optimization models), interdicting transport and information networks. It is shown that many territory control problems can be reduced to well-known optimization problems on graphs, shortest paths search, and minimal covering on graphs. The problems of protecting critical infrastructure and interdicting networks are reduced to stochastic minimax game problems. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G=(A∪B,E) with strict preference lists and given an edge e∗∈E, we ask if there exists a popular matching in G that contains e∗. We call this the popular edge problem. A matching M is popular if there is no matching M′ such that the vertices that prefer M′ to M outnumber those that prefer M to M′. It is known that every stable matching is popular; however G may have no stable matching with the edge e∗. In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge e∗, then there is either a stable matching that contains e∗ or a dominant matching that contains e∗. This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an O(n3) algorithm to find a popular matching containing a given set of edges or report that none exists, where n=|A|+|B|. [ABSTRACT FROM AUTHOR]

We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our main result is an O(klogn)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth O(logn), we obtain an O(log2n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem, matching the best known approximation ratio for UFP on trees with a linear objective function. Our main technical contribution is a new geometric relaxation for UFP on trees that builds on the recent work of Bonsma et al. (2014, FOCS), Anagnostopoulos et al. (Amazing 2+ϵ approximation for unsplittable flow on a path, SIAM, pp 26-41, 2014) for UFP on paths with a linear objective. Our relaxation is very structured, so it can be combined with the contention resolution framework of Chekuri et al. (2009, STOC). Our approach is robust and extends to several related problems, such as UFP with bag constraints and the Storage Allocation Problem. Additionally, we study the special case of UFP on trees with a linear objective and upward instances where, for each task, the source node is a descendant of the sink node. Such instances generalize UFP on paths. We build on the work of Bansal et al. (A quasi-PTAS for unsplittable flow on line graphs, ACM, pp 721-729, 2006) for UFP on paths and obtain a QPTAS for upward instances when the input data is quasi-polynomially bounded. We complement this result by showing that, unlike the path setting, upward instances are APX-hard if the input data is arbitrary. [ABSTRACT FROM AUTHOR]

We give a very short and simple proof of Zykov’s generalization of Turán’s theorem, which implies that the number of maximum independent sets of a graph of order n and independence number α with αn, and we also characterize the extremal graphs. Finally, we show that the number of maximum independent sets of a subcubic tree of order n and independence number α is at most 1+522n-3α+1, and we provide more precise results for extremal values of α. [ABSTRACT FROM AUTHOR]

An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd subgraphs. In this paper we give a necessary and sufficient condition for thedecomposability of a multigraph into two odd subgraphs. We also present a polynomial time algorithm for finding such a decomposition or showing its non-existence. We also deal with the case of the decomposability into an even subgraph and an odd subgraph. [ABSTRACT FROM AUTHOR]

The neighborhood complex of a graph is the family of subsets of open neighborhoods of its vertices. The neighborhood polynomial is the ordinary generating function for the number of sets of the neighborhood complex with respect to their cardinality. This paper provides a new representation of the neighborhood polynomial as a sum over complete bipartite subgraphs of a graph. Using the close relation between the domination polynomial and the neighborhood polynomial of a graph, we can also give a new presentation of the domination polynomial. Finally we show that finding the number of certain double cliques of a graph is sufficient to determine the number of dominating sets of a graph. [ABSTRACT FROM AUTHOR]

Given graphs G and H, G is H-saturated if G does not contain a copy of H but the addition of any edge e∉E(G) creates at least one copy of H within G. The edge spectrum of H is the set of all possible sizes of an H-saturated graph on n vertices. Let K4- be the graph obtained from K4 by deleting an edge. In this note, we show that (a) if G is a K4--saturated graph with |V(G)|=n and |E(G)|>⌊n-12⌋⌈n-12⌉+2, then G must be a bipartite graph; (b) there exists a K4--saturated non-bipartite graph on n≥8 vertices with size being in the interval 3n-11,n-12n-12+2. Together with a result of Fuller and Gould (Graphs Combin 34:85-95, 2018), we determine the edge spectrum of K4- completely, and a conjecture proposed by Fuller and Gould in the same paper also has been resolved. [ABSTRACT FROM AUTHOR]

Gallai-Ramsey numbers often consider edge-colorings of complete graphs in which there are no rainbow triangles. Within such colored complete graphs, the goal is to look for specified monochromatic subgraphs. We consider an “off diagonal” case of this concept by looking for either a monochromatic K3 in one of some set of colors or a monochromatic C4 in one of some other set of colors. [ABSTRACT FROM AUTHOR]

In this paper we introduce the 3-way intersection problem for G-designs, and we consider this problem for kite systems. Let bv=v(v-1)/8 and I3(v)={0,1,…,bv}\{bv-1}. Let J3(v)={s: there exist three kite systems of order v intersecting in s blocks}. We show that for any positive integer v≡0,1(mod8) and v≥8, J3(v)=I3(v). [ABSTRACT FROM AUTHOR]

The chromatic edge stability number esχ(G) of a graph G is the minimum number of edges whose removal results in a graph H⊆G with chromatic number χ(H)=χ(G)-1. The chromatic bondage number ρ(G) of G is the minimum number of edges between any two color classes in a χ(G)-coloring of G, where the minimum is taken over all χ(G)-colorings of G. In this paper, we characterize graphs for which these two parameters coincide. Moreover, we give general bounds and we determine these parameters for several classes of graphs. [ABSTRACT FROM AUTHOR]

We derive a simple bijection between geometric plane perfect matchings on 2n points in convex position and triangulations on n+2 points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodically k-colored vertices and (k+2)-gonal tilings of convex point sets. These structures are related to a generalization of Temperley-Lieb algebras and our bijections provide explicit one-to-one relations between matchings and tilings. Moreover, for a given element of one class, the corresponding element of the other class can be computed in linear time. [ABSTRACT FROM AUTHOR]

In 2000, Enomoto and Ota conjectured that if a graph G satisfies σ2(G)≥|G|+k-1, then for any set of k vertices v1,…,vk and for any positive integers n1,…,nk with ∑ni=|G|, there exists a partition of V(G) into k paths P1,…,Pk such that vi is an end of Pi and |Pi|=ni for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. [ABSTRACT FROM AUTHOR]

Let G be a graph embedded in a surface of nonnegative characteristic with maximum degree Δ. The entire chromatic number χvef of G is the least number of colors such that any two adjacent or incident elements in V(G)∪E(G)∪F(G) have different colors. In this paper, we prove that χvef(G)≤Δ+4 if Δ≥6, and χvef(G)≤Δ+5 if Δ≤5. [ABSTRACT FROM AUTHOR]

An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. A graph G is equitably k-colorable if there exists an equitable coloring of G which uses k colors, each one appearing on either ⌊|V(G)|/k⌋ or ⌈|V(G)|/k⌉ vertices of G. In 1994, Fu conjectured that for any simple graph G, the total graph of G, T(G), is equitably k-colorable whenever k≥max{χ(T(G)),Δ(G)+2} where χ(T(G)) is the chromatic number of the total graph of G and Δ(G) is the maximum degree of G. We investigate the list coloring analogue. List coloring requires each vertex v to be colored from a specified list L(v) of colors. A graph is k-choosable if it has a proper list coloring whenever vertices have lists of size k. A graph is equitably k-choosable if it has a proper list coloring whenever vertices have lists of size k, where each color is used on at most ⌈|V(G)|/k⌉ vertices. In the spirit of Fu’s conjecture, we conjecture that for any simple graph G, T(G) is equitably k-choosable whenever k≥max{χl(T(G)),Δ(G)+2} where χl(T(G)) is the list chromatic number of T(G). We prove this conjecture for all graphs satisfying Δ(G)≤2 while also studying the related question of the equitable choosability of powers of paths and cycles. [ABSTRACT FROM AUTHOR]

In this paper we consider one of the most extensively studied graph search parameters, namely the zero-forcing number of a graph. We relate the zero-forcing number to the brushing number, which as a graph parameter gained recent attention due to certain industrial applications where a network system needs to be cleaned efficiently. In particular, we prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Eroh, Kang and Yi conjectured that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph, which we settle in the affirmative. Moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight. [ABSTRACT FROM AUTHOR]