32,664 results
Search Results
202. A Systematic Literature Review of Combinatorial Testing.
- Author
-
Abdullah, Ariffin, Hassan, Rohayanti, and Shah, Zuraini Ali
- Subjects
COMBINATORICS ,PARAMETER estimation ,CONSTRAINT satisfaction ,COMPUTER algorithms ,PRIMARY research ,STRATEGIC planning - Abstract
As a context of this research, combinatorial testing (CT) in simplifications of the parameter interactions strategy is to grade or rank the best algorithm in order to eliminated the parameter interaction on various crucial issue. These will become the most interesting research finding so as to enhance the efficiency of the test cases generations. The objective of this research is to identify and analyze existing combinatorial testing technique in the context of the formulated research questions. Search terms with relevant keywords were used to identify primary research that was related to combinatorial testing technique classified under journal articles, conference papers, workshops, symposiums, book chapters and IEEE bulletins. In the end of this research, we provided a primarily result of comparison on efficiency of the simplifications strategy in order to enhance the combinatorial testing technique. [ABSTRACT FROM AUTHOR]
- Published
- 2017
203. A Broadcast-enhanced Key Predistribution Scheme Using Combinatorial KPSs Based on Orthogonal Arrays for the Temporal Layer.
- Author
-
QIANG GAO and WENPING MA
- Subjects
COMBINATORIAL designs & configurations ,COMBINATORICS ,POLYOMINOES ,ORTHOGONAL arrays ,WIRELESS sensor networks - Abstract
Broadcast-enhanced key predistribution schemes (BEKPSs) proposed by Kendall et al. have advantages over key predistribution schemes. In this paper, we present a broadcast-enhanced key predistribution scheme based on orthogonal arrays for a wireless sensor network (WSN) which uses a trusted base station and an authenticated broadcast channel to periodically distribute and update temporal keys encrypted with underlying keys. In this scheme, we still use logical key hierarchy (LKH) schemes for the underlying layer to revoke nodes more efficiently, but for the temporal layer, we use key predistribution schemes based on orthogonal arrays. The connectivity, resilience and broadcast load of the resulting sensor networks are analyzed. It is found that the scheme in this paper has better connectivity and resilience than the existing one when the number of nodes per LKH tree is low. [ABSTRACT FROM AUTHOR]
- Published
- 2017
204. Biomolecular network motif counting and discovery by color coding
- Author
-
S. Cenk Sahinalp, Fereydoun Hormozdiari, Iman Hajirasouliha, Noga Alon, and Phuong Dao
- Subjects
Statistics and Probability ,Proteome ,Color-coding ,Color ,Protein Interactions and Molecular Networks ,Biology ,Network topology ,Preferential attachment ,Biochemistry ,Models, Biological ,Combinatorics ,Network motif ,Betweenness centrality ,Reachability ,Ismb 2008 Conference Proceedings 19–23 July 2008, Toronto ,Protein Interaction Mapping ,Computer Simulation ,Molecular Biology ,Degree distribution ,Original Papers ,Computer Science Applications ,Treewidth ,Computational Mathematics ,Computational Theory and Mathematics ,Algorithms ,Signal Transduction - Abstract
Protein–protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks. Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k≤ 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k≥ 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. In this article, we show how to apply the ‘color coding’ technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G′ with k vertices in a network G with n vertices in time polynomial with n, provided k=O(log n). We use our algorithm to obtain ‘treelet’ distributions for k≤ 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the ‘duplication model’ but are quite different from that of the ‘preferential attachment model’. The treelet distribution is robust w.r.t. sparsification with bait/edge coverage of 70% but differences can be observed when bait/edge coverage drops to 50%. Contact: cenk@cs.sfu.ca
- Published
- 2008
205. Contributions by Aart Blokhuis to finite geometry, discrete mathematics, and combinatorics.
- Author
-
Ball, Simeon, Lavrauw, Michel, and Szőnyi, Tamás
- Subjects
FINITE geometries ,COMBINATORICS ,GRAPH theory ,CODING theory ,SPECTRAL geometry - Abstract
The present Special Issue of Designs, Codes and Cryptography is dedicated to Aart Blokhuis, one of the leading mathematicians in finite geometry and combinatorics. References 1 Ball S, Blokhuis A, Mazzocca F. Maximal arcs in Desarguesian planes of odd order do not exist. The third editor of this special issue, Michel Lavrauw, was a PhD student of Aart between 1997 and 2001. Another challenging problem at the time was to prove the non-existence of maximal arcs in Galois planes of odd order; this was achieved by Aart and his coauthors Simeon Ball and Francesco Mazzocca in [[1]]. [Extracted from the article]
- Published
- 2022
- Full Text
- View/download PDF
206. Shellings from Relative Shellings, with an Application to NP-Completeness.
- Author
-
Santamaría-Galvis, Andrés and Woodroofe, Russ
- Subjects
NP-complete problems ,STATISTICAL decision making ,EVIDENCE ,COMBINATORICS - Abstract
Shellings of simplicial complexes have long been a useful tool in topological and algebraic combinatorics. Shellings of a complex expose a large amount of information in a helpful way, but are not easy to construct, often requiring deep information about the structure of the complex. It is natural to ask whether shellings may be efficiently found computationally. In a recent paper, Goaoc, Paták, Patáková, Tancer, and Wagner gave a negative answer to this question (assuming P ≠ NP ), showing that the problem of deciding whether a simplicial complex is shellable is NP -complete. In this paper, we give simplified constructions of various gadgets used in the NP -completeness proof of these authors. Using these gadgets combined with relative shellability and other ideas, we also exhibit a simpler proof of the NP -completeness of the shellability decision problem. Our method systematically uses relative shellings to build up large shellable complexes with desired properties. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
207. The Efficacy and Superiority of the Expert Systems in Reservoir Engineering Decision Making Processes.
- Author
-
Ertekin, Turgay
- Subjects
DECISION making ,SYSTEMS engineering ,ENGINEERING systems ,ARTIFICIAL intelligence ,EXPERT systems ,COMBINATORICS ,RESERVOIRS - Abstract
In the process of making a critical decision in reservoir engineering, most of the time we find ourselves in a quandary. Like in any other scientific or technical field, when we find ourselves having to make a critical decision at a juncture, we cannot go ahead with our gut feelings, but rather must figure out what knowledge and information is lacking. In generating the missing knowledge and understanding, the depth and the rapid nature of the search will surface as two critical parameters. In other words, most of the time, a shallow search that can be conducted in a short period of time will not produce the missing information and the knowledge and more often, possibly, it will provide misguidance. When a large volume of sources of information is reviewed and the missing knowledge is generated using unbiased deductive methodologies, then, one can make an informed decision based on facts rather than intuition. In achieving such a desired result, it will be necessary to use fast algorithmic protocols to not sacrifice the wide nature of the search domain, to ensure that it is possible to generate the desired solution. In this paper, it is shown how in reservoir engineering desirable decisions can be reached in a timely manner choosing the most appealing course of action. It is true that in reservoir engineering applications, the decision-making process may involve a blend of intuition and scientific and rational thinking, critical factors such as blind spots, and the use of conventional methodologies that make decision-making hard to fully operationalize or to get a handle on. Luckily, there are mathematical and computational tools to ensure that scientists/engineers consistently make correct decisions, which include gathering as much information as possible and considering all possible alternatives (like combinatorial analysis protocols). The tool (model) proposed in this paper for making critical reservoir engineering decisions is a new computational platform/protocol that exploits the advantages of mathematically developed formulations and of the models that are based on the data/information collected. It is furthermore shown that the analyses conducted, and critical decisions reached, represent more thorough and far-reaching solutions that are structured using less computational overhead, thereby increasing the quality of the decision even further. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
208. Combinatorics and Algorithms for Quasi-Chain Graphs.
- Author
-
Alecu, Bogdan, Atminas, Aistis, Lozin, Vadim, and Malyshev, Dmitriy
- Subjects
GRAPH algorithms ,COMBINATORICS ,REPRESENTATIONS of graphs ,NP-complete problems ,ISOMORPHISM (Mathematics) ,QUASI-Newton methods - Abstract
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
209. Sequence knitting.
- Author
-
Jensen, Sara
- Abstract
Sequence knitting comes from a straightforward directive; determine a short basic sequence of stitches and create a piece by continuous repetition of that sequence. This paper determines the number of sequence knitting patterns. We restrict our attention to sequences containing only knit and purl stitches and to flat knitting. We further assume that a sequence is restarted at the beginning of each row of knitting, but we do not assume that the number of stitches cast on is a multiple of the sequence length. We consider the case that a pattern and its left/right mirror image are the same, and the case that a pattern and its left/right mirror image are not necessarily the same. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
210. Linear Trees, Lattice Walks, and RNA Arrays.
- Author
-
Evans, Jasmine Renee and Nkwanta, Asamoah
- Subjects
MOLECULAR biology ,COMBINATORICS ,GENERALIZATION ,BIJECTIONS ,GENETIC mutation - Abstract
The leftmost column entries of RNA arrays I and II count the RNA numbers that are related to RNA secondary structures from molecular biology. RNA secondary structures sometimes have mutations and wobble pairs. Mutations are random changes that occur in a structure, and wobble pairs are known as non-Watson–Crick base pairs. We used topics from RNA combinatorics and Riordan array theory to establish connections among combinatorial objects related to linear trees, lattice walks, and RNA arrays. In this paper, we establish interesting new explicit bijections (one-to-one correspondences) involving certain subclasses of linear trees, lattice walks, and RNA secondary structures. We provide an interesting generalized lattice walk interpretation of RNA array I. In addition, we provide a combinatorial interpretation of RNA array II as RNA secondary structures with n bases and k base-point mutations where ω of the structures contain wobble base pairs. We also establish an explicit bijection between RNA structures with mutations and wobble bases and a certain subclass of lattice walks. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
211. Efficient Isomorphism for Sd-Graphs and T-Graphs.
- Author
-
Ağaoğlu Çağırıcı, Deniz and Hliněný, Petr
- Subjects
ISOMORPHISM (Mathematics) ,GRAPH theory ,COMPUTATIONAL mathematics ,GRAPH connectivity ,COMBINATORICS ,AUTOMORPHISM groups ,INTERSECTION graph theory - Abstract
An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for S d -graphs and T-graphs, where S d is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of S d -graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of S d -graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper S d - and T-graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
212. Optimal Scheduling of Photovoltaic Generators in Asymmetric Bipolar DC Grids Using a Robust Recursive Quadratic Convex Approximation.
- Author
-
Montoya, Oscar Danilo, Gil-González, Walter, and Hernández, Jesus C.
- Subjects
TAYLOR'S series ,COMBINATORIAL optimization ,COMBINATORICS ,PHOTOVOLTAIC power systems ,TEST systems ,GRIDS (Cartography) ,PHOTOVOLTAIC power generation - Abstract
This paper presents a robust quadratic convex model for the optimal scheduling of photovoltaic generators in unbalanced bipolar DC grids. The proposed model is based on Taylor's series expansion which relaxes the hyperbolic relation between constant power terminals and voltage profiles. Furthermore, the proposed model is solved in the recursive form to reduce the error generated by relaxations assumed. Additionally, uncertainties in PV generators are considered to assess the effectiveness of the proposed recursive convex. Several proposed scenarios for the numerical validations in a modified 21-bus test system were tested to validate the robust convex model's performance. All the simulations were carried out in the MATLAB programming environment using Yalmip and Gurobi solver. Initially, a comparative analysis with three combinatorial optimization methods under three PV generation scenarios was performed. These scenarios consider levels of 0, 50, and 100% capacity of the PV systems. The results demonstrate the effectiveness of the proposed recursively solved convex model, which always achieves the global optimum for three levels of capacity of the PV generators, with solutions of 95.423 kW, 31.525 kW, and 22.985 kW for 0%, 50%, and 100% of the capacity PV rating, respectively. In contrast, the combinatorial optimization methods do not always reach these solutions. Furthermore, the power loss for the robust model is comparable to the deterministic model, increasing by 1.65% compared to the deterministic model. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
213. The Valabrega–Valla module of monomial ideals.
- Author
-
Nasrollah Nejad, Abbas and Yazdan Pour, Ali Akbar
- Subjects
POLYNOMIAL rings ,IDEALS (Algebra) ,GROBNER bases ,COMBINATORICS - Abstract
In this paper, we focus on the initial degree and the vanishing of the Valabrega–Valla module of a pair of monomial ideals J ⊆ I in a polynomial ring over a field . We prove that the initial degree of this module is bounded above by the maximum degree of a minimal generators of J. For edge ideal of graphs, a complete characterization of the vanishing of the Valabrega–Valla module is given. For higher degree ideals, we find classes, where the Valabrega–Valla module vanishes. For the case that J is the facet ideal of a clutter and I is the defining ideal of singular subscheme of J, the non-vanishing of this module is investigated in terms of the combinatorics of . Finally, we describe the defining ideal of the Rees algebra of I/J provided that the Valabrega–Valla module is zero. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
214. A study on some combinatorial sets in partial semigroups.
- Author
-
Ghosh, Arpita
- Subjects
COMBINATORICS ,HOMOMORPHISMS - Abstract
In this paper, we investigate the image and preimage of the important combinatorial sets such as central sets, C -sets, and J δ -sets which play an important role in the study of combinatorics under certain partial semigroup homomorphism. Using that we prove certain results that deal with the existence of C -set which are not central in partial semigroup framework. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
215. Small toric resolutions of toric varieties of string polytopes with small indices.
- Author
-
Cho, Yunhyung, Kim, Yoosik, Lee, Eunjeong, and Park, Kyeong-Dong
- Subjects
TORIC varieties ,POLYTOPES ,WEYL groups ,COMBINATORICS ,TOPOLOGY ,TORUS - Abstract
Let G be a semisimple algebraic group over ℂ. For a reduced word i of the longest element in the Weyl group of G and a dominant integral weight λ , one can construct the string polytope Δ i (λ) , whose lattice points encode the character of the irreducible representation V λ . The string polytope Δ i (λ) is singular in general and combinatorics of string polytopes heavily depends on the choice of i. In this paper, we study combinatorics of string polytopes when G = S L n + 1 (ℂ) , and present a sufficient condition on i such that the toric variety X Δ i (λ) of the string polytope Δ i (λ) has a small toric resolution. Indeed, when i has small indices and λ is regular, we explicitly construct a small toric resolution of the toric variety X Δ i (λ) using a Bott manifold. Our main theorem implies that a toric variety of any string polytope admits a small toric resolution when n < 4. As a byproduct, we show that if i has small indices then Δ i (λ) is integral for any dominant integral weight λ , which in particular implies that the anticanonical limit toric variety X Δ i (λ P) of a partial flag variety G / P is Gorenstein Fano. Furthermore, we apply our result to symplectic topology of the full flag manifold G / B and obtain a formula of the disk potential of the Lagrangian torus fibration on G / B obtained from a flat toric degeneration of G / B to the toric variety X Δ i (λ) . [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
216. Implementations and the independent set polynomial below the Shearer threshold.
- Author
-
Galanis, Andreas, Goldberg, Leslie Ann, and Štefankovič, Daniel
- Subjects
- *
POLYNOMIALS , *PARTITION functions , *REAL numbers , *STATISTICAL physics , *COMBINATORICS , *INDEPENDENT sets - Abstract
The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2 , the Shearer threshold is the value λ ⁎ (Δ) = (Δ − 1) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ (Δ) , there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ , is at most 0. Also, there are no such graphs for any λ > − λ ⁎ (Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ (Δ). The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ , simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ (Δ) , it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ (Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ (Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness). [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
217. Lifted Reasoning for Combinatorial Counting.
- Author
-
Totis, Pietro, Davis, Jesse, De Raedt, Luc, and Kimmig, Angelika
- Subjects
COMBINATORICS ,NATURAL languages ,ARTIFICIAL intelligence ,CONSTRAINT programming ,DECLARATIVE programming languages - Abstract
Combinatorics math problems are often used as a benchmark to test human cognitive and logical problem-solving skills. These problems are concerned with counting the number of solutions that exist in a specific scenario that is sketched in natural language. Humans are adept at solving such problems as they can identify commonly occurring structures in the questions for which a closed-form formula exists for computing the answer. These formulas exploit the exchangeability of objects and symmetries to avoid a brute-force enumeration of all possible solutions. Unfortunately, current AI approaches are still unable to solve combinatorial problems in this way. This paper aims to fill this gap by developing novel AI techniques for representing and solving such problems. It makes the following five contributions. First, we identify a class of combinatorics math problems which traditional lifted counting techniques fail to model or solve efficiently. Second, we propose a novel declarative language for this class of problems. Third, we propose novel lifted solving algorithms bridging probabilistic inference techniques and constraint programming. Fourth, we implement them in a lifted solver that solves efficiently the class of problems under investigation. Finally, we evaluate our contributions on a real-world combinatorics math problems dataset and synthetic benchmarks. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
218. Monotonicity result for the simple exclusion process on finite connected graphs.
- Author
-
Biswal, Shiba and Lanchier, Nicolas
- Subjects
GEOMETRIC vertices ,ROBOTICS ,MATHEMATICS ,GRAPHIC methods ,COMBINATORICS - Abstract
The simple exclusion process studied in this paper consists of a system of K particles moving on the vertex set of a finite undirected connected graph. If there is one, the particle at x chooses one of the deg(x) neighbors of its current location uniformly at random at rate ρx > 0, and jumps to that vertex if and only if it is empty. Though this model is a natural mathematical object, it is also motivated by applications in the control of robotic swarms. After expressing the stationary distribution and the limiting occupation times of the process, we study how the total number of particles affects the occupation times ratios at different vertices. Using a novel qualitative argument based on combinatorial techniques, we prove that, while the occupation time at x increases with both D(x) = deg(x)=ρx and the total number of particles, the limiting occupation time increases faster with the total number of particles at vertices with a low D(x). [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
219. Coxeter factorizations with generalized Jucys–Murphy weights and Matrix‐Tree theorems for reflection groups.
- Author
-
Chapuy, Guillaume and Douvropoulos, Theo
- Subjects
COXETER groups ,FACTORIZATION ,WEYL groups ,FINITE groups ,COMBINATORICS ,LAPLACIAN matrices ,LAPLACIAN operator - Abstract
We prove universal (case‐free) formulas for the weighted enumeration of factorizations of Coxeter elements into products of reflections valid in any well‐generated reflection group W$W$, in terms of the spectrum of an associated operator, the W$W$‐Laplacian. This covers in particular all finite Coxeter groups. The results of this paper include generalizations of the Matrix‐Tree and Matrix Forest theorems to reflection groups, and cover reduced (shortest length) as well as arbitrary length factorizations. Our formulas are relative to a choice of weighting system that consists of n$n$ free scalar parameters and is defined in terms of a tower of parabolic subgroups. To study such systems we introduce (a class of) variants of the Jucys–Murphy elements for every group, from which we define a new notion of "tower equivalence" of virtual characters. A main technical point is to prove the tower equivalence between virtual characters naturally appearing in the problem, and exterior products of the reflection representation of W$W$. Finally we study how this W$W$‐Laplacian matrix we introduce can be used in other problems in Coxeter combinatorics; for instance, we explain how it defines analogs of trees for W$W$ and how it relates them to Coxeter factorizations. Moreover, we build a parabolic recursion for the W$W$‐Laplacian that proves, without relying on the classification, new numerological identities between the Coxeter number of W$W$ and those of its parabolic subgroups, and, when W$W$ is a Weyl group, a new, explicit formula for the volume of the corresponding root zonotope. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
220. Railway operations modelling and analysis: an introduction to the special issue.
- Author
-
Hansen, Ingo Arne
- Subjects
RAILROADS ,MATHEMATICAL analysis ,SIMULATION methods & models ,SEMINARS ,RAILROAD research ,COMBINATORICS - Abstract
This special issue is based on a selection of the four best papers from the Third International Seminar on Railway Operations Modelling and Analysis held in Zurich from 11 to 13 February 2009. The papers have been selected and reviewed by Board and other senior members of the International Association of Railway Operations Research (IAROR) and subsequently revised by their authors. The authors and their papers come from universities in Sweden, The Netherlands, Italy, Switzerland and Portugal. They represent valuable contributions to the current state of scientific and professional knowledge in the area of railway operations that can stimulate the broader application and further development of advanced analytical, combinatorial and simulation models. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
221. On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing.
- Author
-
Inan, Huseyin A., Kairouz, Peter, Wootters, Mary, and Ozgur, Ayfer
- Subjects
COMBINATORICS ,ERROR probability ,RANDOM sets ,CONSTRUCTION ,NOISE measurement ,TWO-dimensional bar codes - Abstract
We consider the probabilistic group testing problem where $d$ random defective items in a large population of $N$ items are identified with high probability by applying binary tests. It is known that the $\Theta (d \log N)$ tests are necessary and sufficient to recover the defective set with vanishing probability of error when $d = O(N^{\alpha })$ for some $\alpha \in (0, 1)$. However, to the best of our knowledge, there is no explicit (deterministic) construction achieving $\Theta (d \log N)$ tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of $d$) achieves the order optimal $\Theta (d \log N)$ tests in the probabilistic group testing problem when $d = \Omega (\log ^{2}\,\,N)$. This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of $d$. To prove the order-optimality of Kautz and Singleton’s construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
222. Combinatorics of the Gauss Digitization Under Translation in 2D.
- Author
-
Baudrier, Étienne and Mazo, Loïc
- Abstract
The action of a translation on a continuous object before its digitization generates several digital objects. This paper focuses on the combinatorics of the generated digital objects up to integer translations. In the general case, a worst-case upper bound is exhibited and proved to be reached on an example. Another upper bound is also proposed by making a link between the number of the digital objects and the boundary curve, through its self-intersections on the torus. An upper bound, quadratic in digital perimeter, is then derived in the convex case and eventually an asymptotic upper bound, quadratic in the grid resolution, is exhibited in the polygonal case. A few significant examples finish the paper. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
223. Cash transfers and HIV/HSV-2 prevalence: A replication of a cluster randomized trial in Malawi.
- Author
-
Smith, Lynette M., Hein, Nicholas A., and Bagenda, Danstan
- Subjects
HIV infection epidemiology ,HERPES simplex virus ,DISEASE prevalence ,CONFIDENCE intervals ,SCHOOL dropouts - Abstract
Introduction: In this paper we perform a replication analysis of “Effect of a cash transfer programme for schooling on prevalence of HIV and herpes simplex type 2 in Malawi: a cluster randomised trial” by Sarah Baird and others published in “The Lancet” in 2012. The original study was a two-year cluster randomized intervention trial of never married girls aged 13–22 in Malawi. Enumeration areas were randomized to either an intervention involving cash transfer (conditional or unconditional of school enrollment) or control. The study included 1708 Malawian girls, who were enrolled at baseline and had biological testing for HIV and herpes simplex virus type 2 (HSV-2) at 18 months. The original findings showed that in the cohort of girls enrolled in school at baseline, the intervention had an effect on school enrollment, sexual outcomes, and HIV and HSV-2 prevalence. However, in the baseline school dropout cohort, the original study showed no intervention effect on HIV and HSV-2 prevalence. Methods: We performed a replication of the study to investigate the consistency and robustness of key results reported. A pre-specified replication plan was approved and published online. Cleaned data was obtained from the original authors. A pure replication was conducted by reading the methods section and reproducing the results and tables found in the original paper. Robustness of the results were examined with alternative analysis methods in a measurement and estimation analysis (MEA) approach. A theory of change analysis was performed testing a causal pathway, the effect of intervention on HIV awareness, and whether the intervention effect depended on the wealth of the individual. Results: The pure replication found that other than a few minor discrepancies, the original study was well replicated. However, the randomization and sampling weights could not be verified due to the lack of access to raw data and a detailed sample selection plan. Therefore, we are unable to determine how sampling influenced the results, which could be highly dependent on the sample. In MEA it was found that the intervention effect on HIV prevalence in the baseline schoolgirls cohort was somewhat sensitive to model choice, with a non-significant intervention effect for HIV depending on the statistical model used. The intervention effect on HSV-2 prevalence was more robust in terms of statistical significance, however, the odds ratios and confidence intervals differed from the original result by more than 10%. A theory of change analysis showed no effect of intervention on HIV awareness. In a causal pathway analysis, several variables were partial mediators, or potential mediators, indicating that the intervention could be working through its effect on school enrollment or selected sexual behaviors. Conclusions: The effect of intervention on HIV prevalence in the baseline schoolgirls was sensitive to the model choice; however, HSV-2 prevalence results were confirmed. We recommend that the results from the original published analysis indicating the impact of cash transfers on HIV prevalence be treated with caution. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
224. Preface.
- Author
-
Charlier, Émilie, Leroy, Julien, and Rigo, Michel
- Subjects
PROGRAMMING languages ,COMBINATORICS ,STATISTICAL decision making ,COMPUTER algorithms - Published
- 2019
- Full Text
- View/download PDF
225. Mitigating combinatorial attacks in node to node communication using high level security measures based on analysis of efficiency factor through regression and deviation.
- Author
-
Gayathri, V. M. and Nedunchelian, R.
- Subjects
FACTOR analysis ,SECURITY systems ,COMPUTER network security ,TRAFFIC engineering ,NETWORK performance ,COMBINATORICS ,AD hoc computer networks - Abstract
In this contemporary world, mobile ad-hoc networks emerges as an imperative field in computer science. An application of MANET is vehicular networks (VANET) which gives its maximum coverage towards real time actions like vehicular traffic control etc. A mobile ad-hoc network is a network where nodes are movable in state, infrastructure-less, self-configuring and self-repairing from the disconnected links between the nodes. The network topology changes according to the nodes' factors. Due to lack of monitoring, any node can join the network topology based on RF level or distance coverage. Any unauthorised node enters the network and involves in communication without any legalized acceptance from the network. In case of any unusual entry of the node will results in degrade in the network efficiency factors. Anyhow it will ruin the entire network performance and makes to split the topology which causes overhead to start from the initial process. In this paper, we combined one or more attacks by deploying one or more suspicious nodes into the network. By analysing the results from simulation various performance factors are compared based on several test cases. An authorised agent node is placed in the network and issues secret key value to the mobile nodes. Analysis form the results are calculated using regression and deviation method. This paper also gives the analysis of various combinatorial ways of deployed attacks in the network. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
226. HADAMARD DIFFERENCE SETS AND RELATED COMBINATORIAL OBJECTS IN GROUPS OF ORDER 144.
- Author
-
VUČIČIĆ, TANJA
- Subjects
DIFFERENCE sets ,COMBINATORICS ,EXISTENCE theorems ,REGULAR graphs ,AUTOMORPHISM groups - Abstract
Copyright of Rad HAZU: Matematicke Znanosti is the property of Croatian Academy of Sciences & Arts (HAZU) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2019
- Full Text
- View/download PDF
227. Combinatorics of Second Derivative: Graphical Proof of Glaisher-Crofton Identity.
- Author
-
Blasiak, Pawel, Duchamp, Gérard H. E., and Penson, Karol A.
- Subjects
COMBINATORICS ,DERIVATIVES (Mathematics) ,GENERATING functions ,CALCULUS ,COMPUTATIONAL complexity - Abstract
We give a purely combinatorial proof of the Glaisher-Crofton identity which is derived from the analysis of discrete structures generated by the iterated action of the second derivative. The argument illustrates the utility of symbolic and generating function methodology of modern enumerative combinatorics. The paper is meant for nonspecialists as a gentle introduction to the field of graphical calculus and its applications in computational problems. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
228. Minimal Binary Linear Codes.
- Author
-
Ding, Cunsheng, Heng, Ziling, and Zhou, Zhengchun
- Subjects
BOOLEAN functions ,LINEAR codes ,BINARY codes ,COMBINATORICS ,CRYPTOGRAPHY ,DATA transmission systems - Abstract
In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
229. On the history of the Euclidean Steiner tree problem.
- Author
-
Brazil, Marcus, Graham, Ronald, Thomas, Doreen, and Zachariasen, Martin
- Subjects
GEOMETRY problems & exercises ,COMBINATORICS ,HISTORY - Abstract
The history of the Euclidean Steiner tree problem, which is the problem of constructing a shortest possible network interconnecting a set of given points in the Euclidean plane, goes back to Gergonne in the early nineteenth century. We present a detailed account of the mathematical contributions of some of the earliest papers on the Euclidean Steiner tree problem. Furthermore, we link these initial contributions with results from the recent literature on the problem. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
230. Hop-Level Flow Formulation for the Hop Constrained Survivable Network Design Problem
- Author
-
Eduardo Uchoa, Luidi Simonetti, Ridha Mahjoub, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
021103 operations research ,Flow ,Short paper ,0211 other engineering and technologies ,02 engineering and technology ,Steiner tree problem ,Hop (networking) ,Combinatorics ,Network planning and design ,symbols.namesake ,Survivable Network ,Demand set ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,020201 artificial intelligence & image processing ,[INFO]Computer Science [cs] ,Mathematics ,Hop-constraint - Abstract
International audience; The HSNDP consists in finding a minimum cost subgraph containing K edge-disjoint paths with length at most H joining each pair of vertices in a given demand set. The only formulation found in the literature that is valid for any K and any H is based on multi-commodity flows over suitable layered graphs (Hop-MCF) and has typical integrality gaps in the range of 5% to 25%. We propose a new formulation called Hop-Level-MCF (in this short paper only for the rooted demands case), having about H times more variables and constraints than Hop-MCF, but being significantly stronger. Typical gaps for rooted instances are between 0% and 6%. Some instances from the literature are solved for the first time.
- Published
- 2011
231. Combinatorics of criniferous entire maps with escaping critical values.
- Author
-
Pardo-Simón, Leticia
- Subjects
COMBINATORICS ,TOPOLOGICAL dynamics ,POINT set theory ,INFINITY (Mathematics) ,INTEGRAL functions ,TRANSCENDENTAL functions - Abstract
A transcendental entire function is called criniferous if every point in its escaping set can eventually be connected to infinity by a curve of escaping points. Many transcendental entire functions with bounded singular set have this property, and this class has recently attracted much attention in complex dynamics. In the presence of escaping critical values, these curves break or split at critical points. In this paper, we develop combinatorial tools that allow us to provide a complete description of the escaping set of any criniferous function without asymptotic values on its Julia set. In particular, our description precisely reflects the splitting phenomenon. This combinatorial structure provides the foundation for further study of this class of functions. For example, we use these results in another paper to give the first full description of the topological dynamics of a class of transcendental entire maps with unbounded postsingular set. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
232. Enhancing young children's understanding of a combinatorial task by using a duo of digital and physical artefacts.
- Author
-
van Bommel, Jorryt and Palmér, Hanna
- Subjects
EARLY childhood education ,COMBINATORICS ,EDUCATION research ,PROBLEM solving ,CHILD development - Abstract
In mathematics education, digital tools have been used to enhance young children's understanding of specific subject matter. In such implementations, the digital tool can replace, amplify or transform 'ordinary' mathematics teaching. In an initial study, systematization and duplication were identified as critical when young children were to solve a combinatorial task. Therefore, a digital version of the task was developed and combined with a non-digital version, to introduce the use of dual artefacts. The digital version of the task enabled the children to visually explore systematization as well as the principle of completion. After using this digital version of the task, the children's written records became more systematic and included fewer duplications. We conclude that the digital version of the task reinforced young children's understanding of the combinatorial task and that the use of dual artefacts enhanced children's understanding of what a combinatorial problem encompasses. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
233. Opportunities for language enhancement in a learning environment designed on the basis of the theory of didactical situations.
- Author
-
Rønning, Frode
- Subjects
CLASSROOM environment ,FOREIGN language education ,SCIENTIFIC language ,LEARNING goals ,DEAF children ,PRIMARY schools - Abstract
This paper is based on data from two teaching sequences in primary school that are designed using principles from the theory of didactical situations (TDS). The following research question is addressed: "What opportunities can a teaching design based on TDS give a teacher to gain insight into pupils' language use, and to use this insight to establish shared, and mathematically acceptable, knowledge in a group of primary school pupils?" Empirical data from one teaching sequence on geometrical shapes and another teaching sequence on combinatorial problems are used to answer this question. The research shows that a sharp focus on well-defined learning goals does not limit the pupils' possibilities in expressing their thoughts and ideas in their own language. The research also shows that despite clear learning goals, the teacher has rich opportunities to build on pupils' language to connect everyday and scientific language for the purpose of developing a mathematically accepted discourse. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
234. Bourgain's work in Fourier restriction.
- Author
-
Demeter, Ciprian
- Subjects
PARTIAL differential equations ,NUMBER theory ,COMBINATORICS - Abstract
This note will show how Bourgain's work in Fourier restriction theory has built bridges to number theory, partial differential equations, and additive combinatorics. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
235. Using known zeta-series to derive the Dancs-He series for $\,\ln{2}\,$ and $\,\zeta{(2\,n+1)}$
- Author
-
Fabio M. S. Lima
- Subjects
Combinatorics ,symbols.namesake ,Integer ,Series (mathematics) ,Mathematics - History and Overview ,Short paper ,Euler's formula ,symbols ,11M06, 11Y35, 41A30, 65D15 ,Mathematics - Abstract
In a recent work, Dancs and He found new `Euler-type' formulas for $\,\ln{2}\,$ and $\,\zeta{(2\,n+1)}$, $\,n\,$ being a positive integer, each containing a series that apparently can not be evaluated in closed form, distinctly from $\,\zeta{(2\,n)}$, for which the Euler's formula allows us to write it as a rational multiple of $\,\pi^{2n}$. There in that work, however, the formulas are derived through certain series manipulations, by following Tsumura's strategy, which makes it \emph{curious} --- in the words of those authors themselves --- the appearance of the numbers $\,\ln{2}\,$ and $\,\zeta{(2\,n+1)}$. In this short paper, I show how some known zeta-series can be used to derive the Dancs-He series in an alternative manner., Comment: 7 pages, no figures. Second revision completed. Only small corrections. Submitted to J. T. N. Bordeaux (04/07/2011)
- Published
- 2009
236. Multigraphs (only) satisfy a weak triangle removal lemma
- Author
-
Raphael Yuster and Asaf Shapira
- Subjects
Discrete mathematics ,Lemma (mathematics) ,Simple graph ,Applied Mathematics ,Short paper ,Computer Science::Computational Geometry ,Omega ,Theoretical Computer Science ,Combinatorics ,Computational Theory and Mathematics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Geometry and Topology ,05D99 ,ComputingMethodologies_COMPUTERGRAPHICS ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can be extended to multi-graphs (or equivalently, weighted graphs). In this short paper we rule out the possibility of such an extension by showing that there are multi-graphs with only n^{2+o(1)} triangles that are still far from being triangle-free. On the other hand, we show that for some g(n)=\omega(1), if a multi-graph (or weighted graph) has only g(n)n^2 triangles then it must be close to being triangle-free. The proof relies on variants of the Ruzsa-Szemer\'edi theorem.
- Published
- 2009
237. Log-concavity of infinite product and infinite sum generating functions.
- Author
-
Heim, Bernhard and Neuhauser, Markus
- Subjects
- *
GENERATING functions , *COMBINATORICS - Abstract
In this paper, we expand on the remark by Andrews on the importance of infinite sums and products in combinatorics. Let { g d (n) } d ≥ 0 , n ≥ 1 be the double sequences σ d (n) = ∑ ℓ | n ℓ d or ψ d (n) = n d . We associate double sequences { p g d (n) } and { q g d (n) } , defined as the coefficients of ∑ n = 0 ∞ p g d (n) t n : = ∏ n = 1 ∞ (1 − t n) − ∑ ℓ | n μ (ℓ) g d (n / ℓ) n , ∑ n = 0 ∞ q g d (n) t n : = 1 1 − ∑ n = 1 ∞ g d (n) t n . These coefficients are related to the number of partitions p (n) = p σ 1 (n) , plane partitions pp (n) = p σ 2 (n) of n , and Fibonacci numbers F 2 n = q ψ 1 (n). Let n ≥ 3 and let n ≡ 0 (mod 3). Then the coefficients are log-concave at n for almost all d in the exponential (involving p g d ) and geometric cases (involving q g d ). The coefficients are not log-concave for almost all d in both cases, if n ≡ 2 (mod 3). Let n ≡ 1 (mod 3). Then the log-concave property flips for almost all d. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
238. The saṃyoga-meru: A combinatorial tool in the Saṅgīta-ratnākara.
- Author
-
Sreeram, G and Kolachana, Aditya
- Abstract
The Saṅgīta-ratnākara (Ocean of Music) of Śārṅgadeva (c. 1225 CE) is a 13th century text on musicology in Sanskrit. The fifth chapter of the Saṅgīta-ratnākara deals with a general analysis of all possible rhythms (tāla s) which can be obtained by combining a set of basic rhythmic components known as tālāṅga s. Here, Śārṅgadeva describes the construction of the saṃyoga-meru (Table of Combinations), a tool that tabulates the total number of possible tāla s of a given duration which are obtained by combining elements of different subsets of tālāṅga s. In this paper, we discuss the mathematical rationale employed by Śārṅgadeva in the construction of the saṃyoga-meru. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
239. Combinatorics of Euclidean Spaces over Finite Fields.
- Author
-
Yoo, Semin
- Subjects
- *
FINITE fields , *COMBINATORICS , *VECTOR spaces , *ORTHONORMAL basis , *QUADRATIC forms - Abstract
The q-binomial coefficients are q-analogues of the binomial coefficients, counting the number of k-dimensional subspaces in the n-dimensional vector space F q n over F q. In this paper, we define a Euclidean analogue of q-binomial coefficients as the number of k-dimensional subspaces which have an orthonormal basis in the quadratic space (F q n , x 1 2 + x 2 2 + ⋯ + x n 2). We prove its various combinatorial properties compared with those of q-binomial coefficients. In addition, we formulate the number of subspaces of other quadratic types and study some related properties. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
240. Mathematical Combinatorics: - My Philosophy Promoted on Science Internationally.
- Author
-
Linfan MAO
- Subjects
- *
PHILOSOPHY of science , *COMBINATORICS , *SUBDIVISION surfaces (Geometry) , *MATHEMATICAL physics , *BANACH spaces , *PARTICLES (Nuclear physics) - Abstract
Mathematical science is the human recognition on the evolution laws of things that we can understand with the principle of logical consistency by mathematics, i.e., math-ematical reality. So, is the mathematical reality equal to the reality of thing? The answer is not because there always exists contradiction between things in the eyes of human, which is only a local or conditional conclusion. Such a situation enables us to extend the mathe-matics further by combinatorics for the reality of thing from the local reality and then, to get a combinatorial reality of thing. This is the combinatorial conjecture for mathematical science, i.e., CC conjecture that I put forward in my postdoctoral report for Chinese Acade-my of Sciences in 2005, namely any mathematical science can be reconstructed from or made by combinatorialization. After discovering its relation with Smarandache multi-spaces, it is then be applied to generalize mathematics over 1-dimensional topological graphs, namely the mathematical combinatorics that I promoted on science internationally for more than 20 years. This paper surveys how I proposed this conjecture from combinatorial topology, how to use it for characterizing the non-uniform groups or contradictory systems and furthermore, why I introduce the continuity ow GL as a mathematical element, i.e., vectors in Banach space over topological graphs with operations and then, how to apply it to generalize a few of important conclusions in functional analysis for providing the human recognition on the reality of things, including the subdivision of substance into elementary particles or quarks in theoretical physics with a mathematical supporting. [ABSTRACT FROM AUTHOR]
- Published
- 2024
241. On the existence of products of primes in arithmetic progressions.
- Author
-
Szabó, Barnabás
- Subjects
ARITHMETIC series ,COMBINATORICS ,SIEVES - Abstract
We study the existence of products of primes in arithmetic progressions, building on the work of Ramaré and Walker. One of our main results is that if q$q$ is a large modulus, then any invertible residue class mod q$q$ contains a product of three primes where each prime is at most q6/5+ε$q^{6/5+\epsilon }$. Our arguments use results from a wide range of areas, such as sieve theory or additive combinatorics, and one of our key ingredients, which has not been used in this setting before, is a result by Heath‐Brown on character sums over primes from his paper on Linnik's theorem. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
242. On Iiro Honkala's Contributions to Identifying Codes.
- Author
-
Hudry, Olivier, Ville, Junnila, and Lobstein, Antoine
- Subjects
- *
DOMINATING set , *COMBINATORICS , *GRAPH theory - Abstract
A set C of vertices in a graph G = (V, E) is an identifying code if it is dominating and any two vertices of V are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala's contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
243. Uniqueness on Difference Operators of Meromorphic Functions of Infinite Order.
- Author
-
Li, Hui, Fang, Ming Liang, and Yao, Xiao
- Subjects
- *
MEROMORPHIC functions , *DIFFERENCE operators , *OPERATOR functions , *COMBINATORICS , *LINEAR algebra , *VECTOR valued functions - Abstract
We investigate the uniqueness problems of meromorphic functions and their difference operators by using a new method. It is proved that if a non-constant meromorphic function f shares a non-zero constant and ∞ counting multiplicities with its difference operators Δcf(z) and Δ c 2 f (z) , then Δ c f (z) ≡ Δ c 2 f (z) . In particular, we give a difference analogue of a result of Jank–Mues–Volkmann. Our method has two distinct features: (i) It converts the relations between functions into the corresponding vectors. This makes it possible to deal with the uniqueness problem by linear algebra and combinatorics. (ii) It circumvents the obstacle of the difference logarithmic derivative lemma for meromorphic functions of infinite order, since this method does not depend on the growth of the functions. Furthermore, the idea in this paper can also be applied to the case for several variables. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
244. Rational Singularities of Nested Hilbert Schemes.
- Author
-
Ramkumar, Ritvik and Sammartano, Alessio
- Subjects
- *
ALGEBRAIC geometry , *COMMUTATIVE algebra , *GROBNER bases , *REPRESENTATION theory , *COMBINATORICS - Abstract
The Hilbert scheme of points |$\textrm {Hilb}^{n}(S)$| of a smooth surface |$S$| is a well-studied parameter space, lying at the interface of algebraic geometry, commutative algebra, representation theory, combinatorics, and mathematical physics. The foundational result is a classical theorem of Fogarty, stating that |$\textrm {Hilb}^{n}(S)$| is a smooth variety of dimension |$2n$|. In recent years there has been growing interest in a natural generalization of |$\textrm {Hilb}^{n}(S)$| , the nested Hilbert scheme |$\textrm {Hilb}^{(n_{1}, n_{2})}(S)$| , which parametrizes nested pairs of zero-dimensional subschemes |$Z_{1} \supseteq Z_{2}$| of |$S$| with |$\deg Z_{i}=n_{i}$|. In contrast to Fogarty's theorem, |$\textrm {Hilb}^{(n_{1}, n_{2})}(S)$| is almost always singular, and very little is known about its singularities. In this paper, we aim to advance the knowledge of the geometry of these nested Hilbert schemes. Work by Fogarty in the 70's shows that |$\textrm {Hilb}^{(n,1)}(S)$| is a normal Cohen–Macaulay variety, and Song more recently proved that it has rational singularities. In our main result, we prove that the nested Hilbert scheme |$\textrm {Hilb}^{(n,2)}(S)$| has rational singularities. We employ an array of tools from commutative algebra to prove this theorem. Using Gröbner bases, we establish a connection between |$\textrm {Hilb}^{(n,2)}(S)$| and a certain variety of matrices with an action of the general linear group. This variety of matrices plays a central role in our work, and we analyze it by various algebraic techniques, including the Kempf–Lascoux–Weyman technique of calculating syzygies, square-free Gröbner degenerations, and the Stanley–Reisner correspondence. Along the way, we also obtain results on classes of irreducible and reducible nested Hilbert schemes, dimension of singular loci, and |$F$| -singularities in positive characteristic. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
245. ON IDEAL CONVERGENCE OF SEQUENCES VIA CATALAN MATRIX OPERATOR.
- Author
-
KHAN, VAKEEL AHMAD, ET, MIKAIL, and TUBA, UMME
- Subjects
- *
CATALAN numbers , *NUMBER theory , *PROBABILITY theory , *COMBINATORICS , *MATHEMATICAL formulas - Abstract
Catalan sequence initially introduced by Euler but named after Eugene Catalan has found abundant applications in the fields of probability theory, number theory, analysis, combinatorics etc. Recently ˙Ilkhan formulated the matrix associated with Catalan numbers and studied its domain in c0(C~) and c(C~). In this paper, by employing Catalan matrix defined by Catalan sequence and convergence via ideal, we establish Catalan sequence spaces c I 0 (C~), c I (C~) and ℓ I ∞(C~), study the properties of these corresponding spaces and establish inclusion relations. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
246. Bounds on Sombor Index for Corona Products on R-Graphs.
- Author
-
Sarkar, Ishita, Nanjappa, Manjunath, and Gutman, Ivan
- Subjects
- *
MATHEMATICAL bounds , *GRAPH theory , *DIMENSION theory (Algebra) , *MOLECULAR structure , *COMBINATORICS - Abstract
Operations in the theory of graphs has a substantial inuence in the analytical and factual dimensions of the domain. In the realm of chemical graph theory, topological descriptor serves as a comprehensive graph invariant linked with a specific molecular structure. The study on the Sombor index is initiated recently by Ivan Gutman. The triangle parallel graph comprises of the edges of subdivision graph along with the edges of the original graph. In this paper, we make use of combinatorial inequalities related with the vertices, edges and the neighborhood concepts as well as the other topological descriptors in the computations for the determination of bounds of Sombor index for certain corona products involving the triangle parallel graph. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
247. Graft Analogue of general Kotzig–Lovász decomposition.
- Author
-
Kita, Nanao
- Subjects
- *
BIPARTITE graphs , *POLYTOPES , *MATCHING theory , *GENERALIZATION , *COMBINATORICS - Abstract
Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
248. Degröbnerization: a political manifesto.
- Author
-
Ceria, Michela, Lundqvist, Samuel, and Mora, Teo
- Subjects
POLITICAL manifestoes ,GROBNER bases ,ALGEBRA ,COMBINATORICS - Abstract
Computer Algebra relies heavily on the computation of Gröbner bases, and these computations are primarily performed by means of Buchberger's algorithm. In this overview paper, we focus on methods avoiding the computational intensity associated to Buchberger's algorithm and, in most cases, even avoiding the concept of Gröbner bases, in favour of methods relying on linear algebra and combinatorics. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
249. Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems.
- Author
-
Turkensteen, Marcel and Jäger, Gerold
- Subjects
- *
COMBINATORICS , *SENSITIVITY analysis , *ASSIGNMENT problems (Programming) , *COMBINATORIAL optimization , *SPANNING trees - Abstract
This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem. • We study sensitivity of combinatorial problems with bottleneck objective (CBPs). • We investigate the range of element costs that keep current solutions optimal. • We derive algorithms for two CBPs in particular. • We determine the elements belonging to optimal solutions of CBPs efficiently. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
250. Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term.
- Author
-
Coronado, Tomás M., Mir, Arnau, and Rosselló, Francesc
- Subjects
POLYNOMIALS ,COMPUTER science ,MATHEMATICAL optimization ,COMBINATORICS ,PHYLOGENY - Abstract
Divide-and-conquer dividing by a half recurrences, of the form x n = a · x ⌈ n / 2 ⌉ + a · x ⌊ n / 2 ⌋ + p (n) , n ⩾ 2 , appear in many areas of applied mathematics, from the analysis of algorithms to the optimization of phylogenetic balance indices. These equations are usually "solved" by means of a Master Theorem that provides a bound for the growing order of x
n , but not the solution's explicit expression. In this paper we give a finite explicit expression for this solution, in terms of the binary decomposition of n, when the independent term p(n) is a polynomial in ⌈n/2⌉ and ⌊n/2⌋. As an application, we obtain explicit formulas for several sequences of interest in phylogenetics, combinatorics, and computer science, for which no such formulas were known so far: for instance, for the Total Cophenetic index and the rooted Quartet index of the maximally balanced bifurcating phylogenetic trees with n leaves, and the sum of the bitwise AND operator applied to pairs of complementary numbers up to n. [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.