1,213 results
Search Results
2. A Note on a Paper of Aivazidis, Safonova and Skiba
- Author
-
M. M. Al-Shomrani, Adolfo Ballester-Bolinches, and A. A. Heliel
- Subjects
Subnormal subgroup ,Combinatorics ,Mathematics::Group Theory ,Finite group ,General Mathematics ,Mathematics - Abstract
The main result of this paper states that if $${\mathcal {F}}$$ is a subgroup-closed saturated formation of full characteristic, then the $${\mathcal {F}}$$ -residual of a K- $${\mathcal {F}}$$ -subnormal subgroup S of a finite group G is a large subgroup of G provided that the $${\mathcal {F}}$$ -hypercentre of every subgroup X of G containing S is contained in the $${\mathcal {F}}$$ -residual of X. This extends a recent result of Aivazidis, Safonova and Skiba.
- Published
- 2021
3. Constructive Combinatorics in Elementary School Mathematics.
- Author
-
Posicelskaya, M. A.
- Subjects
COMBINATORICS ,ELEMENTARY schools ,COMPUTATIONAL mathematics ,MATHEMATICS ,SEARCH theory - Abstract
The paper describes in detail a class of educational problems from an elementary school course of mathematics and computer science. This course has been implemented over the past decades by a team led by Academician of the RAS A.L. Semenov. In the problems, it is necessary to find, build, or list all objects that satisfy a certain system of conditions. The student conducts these activities in a visual world of basic objects of discrete mathematics and computer science: strings (finite sequences of symbols), bags (multisets), tables, trees, and statements containing quantifiers. The connections of these problems with problems in computational combinatorics (counting the number of options), with search problems in the theory of computational complexity, with "big ideas," and general cognitive strategies for their formation in education are considered. The content of education in our approach is more adequate to the context of the modern world. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. On the Difference between Laplacian and Signless Laplacian Coefficients of a Graph and its Applications on the Fullerene Graphs.
- Author
-
Arabzadeh, Mahsa, Fath-Tabar, Gholam Hossein, Rasouli, Hamid, and Tehranian, Abolfazl
- Subjects
GRAPH theory ,LAPLACIAN matrices ,POLYNOMIALS ,MATHEMATICS ,COMBINATORICS - Abstract
Let ∑
n i=0 (-1)i li xn-i and ∑n i=0 (-1)i qi xn-i be the characteristic polynomials of the Laplacian matrix and signless Laplacian matrix of an n-vertex graph, respectively. Let αi = |qi - li |, 0 ≤ i ≤ n. In this paper, we find formulas for some of αi 's. In particular, we compute αi 's for some fullerene graphs. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
5. APPLICATION OF MATHEMATICS IN DESIGN OF GROUP KEY MANAGEMENT METHOD.
- Author
-
MURTHY, A. V. V. S. and VASUDEVA REDDY, P.
- Subjects
GROUP theory ,MATHEMATICS ,COMBINATORICS ,INTERNET of things ,CRYPTOGRAPHIC equipment - Abstract
Group theory and Combinatorics play important role in design security protocols, algorithms and techniques for various security applications. Secure group-oriented communication is crucial to a wide range of applications in Internet of Things (IoT). Key management is the mechanism which is used to work out the problem of creation, establishment, to distribute, periodic refresh and the maintenance of the cryptographic keys. It is not enough to care only about primitives that satisfy a stated security objective in the domain of the IoT. The design of group key establishment techniques for securing group communications between resource-constrained IoT devices is presented in this work. Furthermore, the paper assesses possible ways for tailoring current security protocols to the peculiarities of IoT devices and networks. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
6. Divine mathematics: Leibniz's combinatorial theory of compossibility.
- Author
-
Kim, Jun Young
- Subjects
- *
COMBINATORICS , *MATHEMATICS , *GOD , *PUZZLES , *GOOD & evil - Abstract
Leibniz's famous proposition that God has created the best of all possible worlds holds a significant place in his philosophical system. However, the precise manner in which God determines which world is the best remains somewhat ambiguous. Leibniz suggests that a form of "Divine mathematics" is employed to construct and evaluate possible worlds. In this paper, I uncover the underlying mechanics of Divine mathematics by formally reconstructing it. I argue that Divine mathematics is a one-player combinatorial game, in which God's goal is to find the best combination among many possibilities. Drawing on the combinatorial theory, I provide new solutions to some puzzles of compossibility. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
7. THE FAITHFUL REPRESENTATIONS OF RIGID MOTIONS OF A REGULAR POLYGON.
- Author
-
MAHTO, DILCHAND and TANTI, JAGMOHAN
- Subjects
POLYGONS ,NATURAL numbers ,LINEAR algebra ,COMBINATORICS ,MATHEMATICS - Abstract
Let n be a natural number. In this paper we characterize all degree n faithful representations of a dihedral group G of order 2m, m ≥ 3, over the field of complex numbers C. The results are important due to their applications in the study of physical sciences. [ABSTRACT FROM AUTHOR]
- Published
- 2022
8. An Algorithm for the Free Generators of a Free Subgroup.
- Author
-
Li, Aaron J.
- Subjects
GROUP theory ,CRYPTOGRAPHY ,COMPUTER graphics ,GRAPH theory ,COMBINATORICS - Abstract
Group Theory has diverse applications in mathematics and has been used to solve real-world problems, such as in cryptography, computer graphics, molecular systems biology, and crystal studies. In this article, we delve into a detailed analysis of subgroups of the free group of rank 2. The primary focus of this study is to develop an intuitive visualization for constructing a free set of generators for a free subgroup, using a graph-theoretic approach based on Stallings Foldings to provide a topological interpretation and solution to the problem. This algorithm leverages the connection between algebraic structures and geometric constructs, allowing for an intuitive understanding of the structure of a free group. An implementation of this algorithm is included in Python, making it immediately useful for computational applications. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
9. Simultaneously vanishing higher derived limits without large cardinals.
- Author
-
Bergfalk, Jeffrey, Hrušák, Michael, and Lambie-Hanson, Chris
- Subjects
COMBINATORICS ,AXIOMS ,MATHEMATICS ,MATHEMATICAL continuum - Abstract
A question dating to Mardešić and Prasolov's 1988 work [S. Mardešić and A. V. Prasolov, Strong homology is not additive, Trans. Amer. Math. Soc. 307(2) (1988) 725–744], and motivating a considerable amount of set theoretic work in the years since, is that of whether it is consistent with the ZFC axioms for the higher derived limits lim n (n > 0) of a certain inverse system A indexed by ω ω to simultaneously vanish. An equivalent formulation of this question is that of whether it is consistent for all n -coherent families of functions indexed by ω ω to be trivial. In this paper, we prove that, in any forcing extension given by adjoining ℶ ω -many Cohen reals, lim n A vanishes for all n > 0. Our proof involves a detailed combinatorial analysis of the forcing extension and repeated applications of higher-dimensional Δ -system lemmas. This work removes all large cardinal hypotheses from the main result of [J. Bergfalk and C. Lambie-Hanson, Simultaneously vanishing higher derived limits, Forum Math. Pi 9 (2021) e4] and substantially reduces the least value of the continuum known to be compatible with the simultaneous vanishing of lim n A for all n > 0. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
10. 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
11. COMBINATORICS: THE MATHEMATICS OF FAIR THIEVES AND SOPHISTICATED FORGETTERS.
- Author
-
Alon, Noga
- Subjects
COMBINATORICS ,COMPUTER storage devices ,MATHEMATICAL analysis ,MATHEMATICS ,SATISFACTION - Abstract
Mathematics is the most logical and unbiased scientific field there is. What is true in mathematics today will forever stay true, and mathematical arguments will always clearly indicate which side "wins". These are some of the characteristics of mathematics that I have liked very much since I was young. In this article, I will try to demonstrate the beauty of mathematics and show you that it appears in many situations in our daily lives--including places we might not expect. Then, I will give you a taste of two studies I conducted in a mathematical field called combinatorics, and I will explain how they are related to everyday problems. One of these problems is how to perform accurate mathematical analyses of large streams of data that we cannot save in a computer's memory. Finally, I will try to give you an idea of my life as a mathematician--the challenges and difficulties, alongside the immense enjoyment and satisfaction I derive from them. Join me to an extended dive into my work on the wonders of combinatorics. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
12. Biological Models for Finite Mathematics.
- Author
-
Jungck, John R.
- Subjects
BIOLOGICAL models ,GRAPH theory ,MATHEMATICS ,INFORMATION theory ,FINITE differences ,LOTKA-Volterra equations - Abstract
Finite Mathematics has become an enormously rich and productive area of contemporary mathematical biology. Fortunately, educators have developed educational modules based upon many of the models that have used Finite Mathematics in mathematical biology research. A sufficient variety of computer modules that employ graph theory (phylogenetic trees, food webs, networks), cellular automata (pattern formation, diffusion limited aggregation), fractals (both measurement and generation of self-similar structures), finite difference equations and deterministic chaos (logistic growth, predator–prey, SIR epidemiology), combinatorics and probability (genetics and evolution), information theory (biodiversity, sequence logos), and Boolean logic (operons) are available to adopt, adapt, and implement. An emphasis has been placed on modules that are freely available, that have been educationally vetted, and that run on a variety of operating systems. Most modules are easy to use, graphically visual, and amenable to modification. In this paper, two different approaches are stressed: (1) "glass box models" that allow students to see equations associated with each cell in a spreadsheet and to modify/extend those models with minimal effort; and (2) agent-based models that emphasize "bottom-up" modeling and that instantiate the power of massively parallel simulation and address the misconceptions of a "centralized mind-set." [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
13. Researcher from Department of Mathematics Describes Findings in Mathematics (Adjoint Separating Systems).
- Subjects
RESEARCH personnel ,MATHEMATICS ,COMBINATORICS ,REPORTERS & reporting - Abstract
A recent study from the Department of Mathematics explores the use of combinatorial group testing as a method for efficiently testing individuals for diseases like COVID-19. The researchers propose the use of separating systems, which are subsets of a finite set that allow for the separation of individual elements. The study presents a method for constructing small separating systems on large sets, which can save time and money. This research provides valuable insights into the potential application of combinatorial group testing in disease testing. [Extracted from the article]
- Published
- 2024
14. CONVEX CHARACTERS, ALGORITHMS, AND MATCHINGS.
- Author
-
KELK, STEVEN, MEUWESE, RUBEN, and WAGNER, STEPHAN
- Subjects
GOLDEN ratio ,ALGORITHMS ,PHYLOGENY ,TREE graphs ,PARSIMONIOUS models ,MATHEMATICS ,GRAPH labelings - Abstract
Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species ("taxa""), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [Adv. Appl. Math., 84 (2017), pp. 34--46] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity g
2 (T), defined as the number of convex characters on T in which each state appears on at least 2 taxa. We use this to give an algorithm with running time Oφn poly(n)), where 1.6181 is the golden ratio and n is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by g2(T) we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to O(1.5895n poly(n)) and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
15. Seating Groups and 'What a Coincidence!': Mathematics in the Making and How It Gets Presented.
- Author
-
Rowlett, Peter J.
- Subjects
MATHEMATICS ,COINCIDENCE ,COMBINATORICS ,COINCIDENCE theory - Abstract
Mathematics is often presented as a neatly polished finished product, yet its development is messy and often full of mis-steps that could have been avoided with hindsight. An experience with a puzzle illustrates this conflict. The puzzle asks for the probability that a group of four and a group of two are seated adjacently within a hundred seats, and is solved using combinatorics techniques. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
16. New self-dual codes from $ 2 \times 2 $ block circulant matrices, group rings and neighbours of neighbours
- Author
-
Abidin Kaya, Rhian Taylor, Adam Roberts, Joe Gildea, and Alexander Tylyshchak
- Subjects
Quadratic residue ,Combinatorics ,Algebra and Number Theory ,Computer Networks and Communications ,Applied Mathematics ,Block (permutation group theory) ,Discrete Mathematics and Combinatorics ,Microbiology ,Circulant matrix ,Mathematics ,Group ring - Abstract
In this paper, we construct new self-dual codes from a construction that involves a unique combination; \begin{document}$ 2 \times 2 $\end{document} block circulant matrices, group rings and a reverse circulant matrix. There are certain conditions, specified in this paper, where this new construction yields self-dual codes. The theory is supported by the construction of self-dual codes over the rings \begin{document}$ \mathbb{F}_2 $\end{document} , \begin{document}$ \mathbb{F}_2+u \mathbb{F}_2 $\end{document} and \begin{document}$ \mathbb{F}_4+u \mathbb{F}_4 $\end{document} . Using extensions and neighbours of codes, we construct \begin{document}$ 32 $\end{document} new self-dual codes of length \begin{document}$ 68 $\end{document} . We construct 48 new best known singly-even self-dual codes of length 96.
- Published
- 2023
17. The weight recursions for the 2-rotation symmetric quartic Boolean functions
- Author
-
Thomas W. Cusick and Younhwan Cheon
- Subjects
Sequence ,Monomial ,Algebra and Number Theory ,Computer Networks and Communications ,Applied Mathematics ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,01 natural sciences ,Microbiology ,Combinatorics ,010201 computation theory & mathematics ,Quartic function ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Invariant (mathematics) ,Boolean function ,Hamming weight ,Rotation (mathematics) ,Mathematics - Abstract
A Boolean function in \begin{document}$ n $\end{document} variables is 2-rotation symmetric if it is invariant under even powers of \begin{document}$ \rho(x_1, \ldots, x_n) = (x_2, \ldots, x_n, x_1) $\end{document} , but not under the first power (ordinary rotation symmetry); we call such a function a 2-function. A 2-function is called monomial rotation symmetric (MRS) if it is generated by applying powers of \begin{document}$ \rho^2 $\end{document} to a single monomial. If the quartic MRS 2-function in \begin{document}$ 2n $\end{document} variables has a monomial \begin{document}$ x_1 x_q x_r x_s $\end{document} , then we use the notation \begin{document}$ {2-}(1,q,r,s)_{2n} $\end{document} for the function. A detailed theory of equivalence of quartic MRS 2-functions in \begin{document}$ 2n $\end{document} variables was given in a \begin{document}$ 2020 $\end{document} paper by Cusick, Cheon and Dougan. This theory divides naturally into two classes, called \begin{document}$ mf1 $\end{document} and \begin{document}$ mf2 $\end{document} in the paper. After describing the equivalence classes, the second major problem is giving details of the linear recursions that the Hamming weights for any sequence of functions \begin{document}$ {2-}(1,q,r,s)_{2n} $\end{document} (with \begin{document}$ q say), \begin{document}$ n = s, s+1, \ldots $\end{document} can be shown to satisfy. This problem was solved for the \begin{document}$ mf1 $\end{document} case only in the \begin{document}$ 2020 $\end{document} paper. Using new ideas about "short" functions, Cusick and Cheon found formulas for the \begin{document}$ mf2 $\end{document} weights in a \begin{document}$ 2021 $\end{document} sequel to the \begin{document}$ 2020 $\end{document} paper. In this paper the actual recursions for the weights in the \begin{document}$ mf2 $\end{document} case are determined.
- Published
- 2023
18. Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed
- Author
-
László Babai
- Subjects
Algebra and Number Theory ,Conjecture ,Degree (graph theory) ,20B05 (primary) 20E18, 05E18, 05C63 (secondary) ,Structure (category theory) ,Motion (geometry) ,Group Theory (math.GR) ,Disjoint sets ,Permutation group ,Automorphism ,Combinatorics ,FOS: Mathematics ,Inverse limit ,Mathematics - Group Theory ,Mathematics - Abstract
An asymmetric coloring of a graph is a coloring of its vertices that is not preserved by any non-identity automorphism of the graph. The motion of a graph is the minimal degree of its automorphism group, i.e., the minimum number of elements displaced by any non-identity automorphism. In this paper we confirm Tom Tucker's "Infinite Motion Conjecture" that connected locally finite graphs with infinite motion admit an asymmetric 2-coloring. We infer this from the more general result that the inverse limit of a sequence of finite permutation groups with disjoint domains, viewed as a permutation group on the union of those domains, admits an asymmetric 2-coloring. The proof is based on the study of the interaction between epimorphisms of finite permutation groups and the structure of the setwise stabilizers of subsets of their domains., Comment: V.2 updates: Choi 1972 ref. added, Sec. 8.3 (Mathieu groups) updated, question about $M_{24}$ deleted from "Open questions." New material: New Sec. 14 added, incl. two conjectures. Minor changes made for improved clarity throughout the paper. None of the updates affects the main results or their proofs
- Published
- 2022
19. Vertex partitioning problems on graphs with bounded tree width
- Author
-
Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare, and N. R. Aravind
- Subjects
Matching (graph theory) ,Applied Mathematics ,0211 other engineering and technologies ,Induced subgraph ,Parameterized complexity ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Vertex (geometry) ,Combinatorics ,Treewidth ,010201 computation theory & mathematics ,Bounded function ,Discrete Mathematics and Combinatorics ,Partition (number theory) ,Time complexity ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H - Free Coloring if none of the color classes contain H as an induced subgraph. The H - Free Chromatic Number of G is the minimum number of colors required for an H - Free Coloring of G . Both The Matching Cut problem and the H - Free Coloring problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f ( | | φ | | , t ) n O ( 1 ) , where | | φ | | is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f ( | | φ | | , t ) on | | φ | | can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for Matching Cut problem and H - Free Coloring problem, parameterized by the tree-width of G . The single exponential FPT algorithm for the Matching Cut problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H -free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G .
- Published
- 2022
20. Oriented diameter of star graphs
- Author
-
K. S. Ajish Kumar, K. S. Sudeep, and Deepak Rajendraprasad
- Subjects
FOS: Computer and information sciences ,Star network ,Discrete Mathematics (cs.DM) ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Orientation (graph theory) ,Star (graph theory) ,05C20, 05C12 ,Network topology ,01 natural sciences ,Upper and lower bounds ,Prime (order theory) ,Combinatorics ,Permutation ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Mathematics ,Applied Mathematics ,021107 urban & regional planning ,Computer Science - Distributed, Parallel, and Cluster Computing ,010201 computation theory & mathematics ,Distributed, Parallel, and Cluster Computing (cs.DC) ,Combinatorics (math.CO) ,Hypercube ,Computer Science - Discrete Mathematics - Abstract
An {\em orientation} of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The $n$-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The $n$-star graph $S_n$ consists of $n!$ vertices, each labelled with a distinct permutation of $[n]$. Two vertices are adjacent if their labels differ exactly in the first and one other position. $S_n$ is an $(n-1)$-regular, vertex-transitive graph with diameter $\lfloor 3(n-1)/2 \rfloor$. Orientations of $S_n$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $\overrightarrow{S_n}$ is at most $\lceil{5n/2}\rceil + 2$. In this paper, we propose a new distributed routing algorithm for the same $\overrightarrow{S_n}$ analysed by Fujita, which routes a packet from any node $s$ to any node $t$ at an undirected distance $d$ from $s$ using at most $\min\{4d+4, 2n+4\}$ hops. This shows that the (directed) diameter of $\overrightarrow{S_n}$ is at most $2n+4$. We also show that the diameter of $\overrightarrow{S_n}$ is at least $2n$ when $n \geq 7$, thereby showing that our upper bound is tight up to an additive factor., Full version of the paper to be presented in CALDAM 2020
- Published
- 2022
21. On a conjecture of Erdős and Lewin
- Author
-
Wang-Xing Yu and Yong-Gao Chen
- Subjects
Combinatorics ,Set (abstract data type) ,Algebra and Number Theory ,Conjecture ,Integer ,Mathematics - Abstract
Text A set A of positive integers is called d-complete if every sufficiently large integer is the sum of distinct terms taken from A such that no one divides the other. In this paper we answer two questions of Erdős and Lewin partially and settle a conjecture of Erdős and Lewin on d-complete sequences affirmatively. We also pose two conjectures for further research. Video For a video summary of this paper, please visit https://www.youtube.com/watch?v=I0AoLpvj4QQ .
- Published
- 2022
22. On the distance spectrum of minimal cages and associated distance biregular graphs
- Author
-
Aditi Howlader and Pratima Panigrahi
- Subjects
Numerical Analysis ,Algebra and Number Theory ,Degree (graph theory) ,Spectral radius ,Girth (graph theory) ,Combinatorics ,FOS: Mathematics ,Bipartite graph ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Adjacency list ,Regular graph ,Combinatorics (math.CO) ,Geometry and Topology ,Cage ,05C12, 05C50 ,Connectivity ,Mathematics - Abstract
A $(k,g)$-cage is a $k$-regular simple graph of girth $g$ with minimum possible number of vertices. In this paper, $(k,g)$-cages which are Moore graphs are referred as minimal $(k,g)$-cages. A simple connected graph is called distance regular(DR) if all its vertices have the same intersection array. A bipartite graph is called distance biregular(DBR) if all the vertices of the same partite set admit the same intersection array. It is known that minimal $(k,g)$-cages are DR graphs and their subdivisions are DBR graphs. In this paper, for minimal $(k,g)$-cages we give a formula for distance spectral radius in terms of $k$ and $g$, and also determine polynomials of degree $[\frac{g}{2}]$, which is the diameter of the graph. This polynomial gives all distance eigenvalues when the variable is substituted by adjacency eigenvalues. We show that a minimal $(k,g)$-cage of diameter $d$ has $d+1$ distinct distance eigenvalues, and this partially answers a problem posed in [5]. We prove that every DBR graph is a $2$-partitioned transmission regular graph and then give a formula for its distance spectral radius. By this formula we obtain the distance spectral radius of subdivision of minimal $(k,g)$-cages. Finally we determine the full distance spectrum of subdivision of some minimal $(k,g)$-cages., 22 pages
- Published
- 2022
23. A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
- Author
-
Fred Glover, Zhipeng Lü, and Xinyun Wu
- Subjects
Set (abstract data type) ,Combinatorics ,Minimum dominating set ,General Engineering ,Undirected graph ,Metaheuristic ,Connected dominating set ,Local search (constraint satisfaction) ,Vertex (geometry) ,Mathematics ,Weighting - Abstract
The minimum connected dominating set (MCDS) problem consists of selecting a minimum set of vertices from an undirected graph, such that each vertex not in this set is adjacent to at least one of the vertices in it, and the subgraph induced by this vertex set is connected. This paper presents a fast vertex weighting (FVW) algorithm for solving the MCDS problem, which integrates several distinguishing features, such as a vertex weighting-based local search with tabu and perturbation strategies to help the search to jump out of the local optima, as well as a search space reduction strategy to improve the search efficiency. Computational experiments on four sets of 112 commonly used public benchmark instances, as well as 15 newly introduced sparse instances, show that FVW is highly competitive compared with the state-of-the-art algorithms in the literature despite its simplicity. FVW improves the previous best-known results for 20 large public benchmark instances while matching the best-known results for all but 2 of the remaining ones. Several ingredients of FVW are investigated to demonstrate the importance of the proposed ideas and techniques. Summary of Contribution: As a challenging classical NP-hard problem, the minimum connected dominating set (MCDS) problem has been studied for decades in the areas of both operations research and computer science, although there does not exist an exact polynomial algorithm for solving it. Thus, the new breakthrough on this classical NP-hard problem in terms of the computational results on classical benchmark instances is significant. This paper presents a new fast vertex weighting local search for solving the MCDS problem. Computational experiments on four sets of 112 commonly used public benchmark instances show that fast vertex weighting (FVW) is able to improve the previous best-known results for 20 large instances while matching the best-known results for all but 2 of the remaining instances. Several ingredients of FVW are also investigated to demonstrate the importance of the proposed ideas and techniques.
- Published
- 2022
24. Hill representations for ∗-linear matrix maps
- Author
-
A. van der Merwe and S. ter Horst
- Subjects
Combinatorics ,Linear map ,Matrix (mathematics) ,General Mathematics ,Nonnegative matrix ,Linear matrix ,Hermitian matrix ,Mathematics - Abstract
In the paper (Hill, 1973) from 1973 R.D. Hill studied linear matrix maps L : ℂ q × q → ℂ n × n which map Hermitian matrices to Hermitian matrices, or equivalently, preserve adjoints, i.e., L ( V ∗ ) = L ( V ) ∗ , via representations of the form L ( V ) = ∑ k , l = 1 m H k l A l V A k ∗ , V ∈ ℂ q × q , for matrices A 1 , … , A m ∈ ℂ n × q and continued his study of such representations in later work, sometimes with co-authors, to completely positive matrix maps and associated matrix reorderings. In this paper we expand the study of such representations, referred to as Hill representations here, in various directions. In particular, we describe which matrices A 1 , … , A m can appear in Hill representations (provided the number m is minimal) and determine the associated Hill matrix H = H k l explicitly. Also, we describe how different Hill representations of L (again with m minimal) are related and investigate further the implication of ∗ -linearity on the linear map L .
- Published
- 2022
25. A Note on Horadam Hybrinomials
- Author
-
Can Kızılateş
- Subjects
Combinatorics ,Matematik ,Dual number ,Horadam number,Horadam polynomial,Hybrid number ,General Medicine ,Complex number ,algebra_number_theory ,Mathematics - Abstract
This paper ensures an extensive survey of the generalization of the various hybrid numbers and hybrid polynomials especially as part of its enhancing importance in the disciplines of mathematics and physics. In this paper, by using the Horadam polynomials, we define the Horadam hybrid polynomials called Horadam hybrinomials. We obtain some special cases and algebraic properties of the Horadam hybrinomials such as recurrence relation, generating function, exponential generating function, Binet formula, summation formulas, Catalan's identity, Cassini's identity and d'Ocagne's identity, respectively. Moreover, we give some applications related to the Horadam hybrinomials in matrices.
- Published
- 2022
26. Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
- Author
-
Stefano Coniglio and Stefano Gualandi
- Subjects
Settore INF/01 - Informatica ,Branch and bound ,cutting plane generation ,bilevel programming ,General Engineering ,Integer programming ,Context (language use) ,Bilevel optimization ,maximum stable set problem ,rank inequalities ,branch-and-cut ,branch-and-bound ,Set (abstract data type) ,Combinatorics ,Cardinality ,Closure (mathematics) ,Independent set ,Rank (graph theory) ,Settore MAT/09 - Ricerca Operativa ,Mathematics - Abstract
In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is [Formula: see text]-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub.
- Published
- 2022
27. Vertices of the unit ball of subspaces in L(H) and strong unicity of best approximation in L(l22)
- Author
-
Paweł Wójcik
- Subjects
Unit sphere ,Numerical Analysis ,Algebra and Number Theory ,Linear operators ,Hilbert space ,Space (mathematics) ,Linear subspace ,Projection (linear algebra) ,Combinatorics ,symbols.namesake ,symbols ,Discrete Mathematics and Combinatorics ,Effective method ,Geometry and Topology ,Mathematics - Abstract
Let L ( H ) be the space of linear operators acting from the finite-dimensional real Hilbert space into itself. The purpose of this paper is to present results concerning the geometric properties of some subspaces of L ( H ) . In particular, vertices of the closed unit ball of those subspaces are discussed. The problem of best approximation in the space L ( l 2 2 ) is investigated. Moreover, in this paper we show an example of an effective method seeking a unique minimal projection which is strongly unique.
- Published
- 2022
28. The maximum $k$-colorable subgraph problem and related problems
- Author
-
Juan C. Vera, Olga Kuryatnikova, Renata Sotirov, Econometrics and Operations Research, and Research Group: Operations Research
- Subjects
Semidefinite programming ,General Engineering ,Johnsons graphs ,chromatic number of a graph ,semidefinite programming ,Combinatorics ,Hamming graph ,Optimization and Control (math.OC) ,Independent set ,FOS: Mathematics ,generalized theta number ,Graph (abstract data type) ,Cardinality (SQL statements) ,Mathematics - Optimization and Control ,stable set ,k-colorable subgraph problem ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Hamming graphs - Abstract
The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. To simplify these relaxations, we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the MkCS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Summary of Contribution: The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. The MkCS problem has a number of applications, such as channel assignment in spectrum sharing networks (e.g., Wi-Fi or cellular), very-large-scale integration design, human genetic research, and so on. The MkCS problem is also related to several other optimization problems, including the graph partition problem and the max-k-cut problem. The two mentioned problems have applications in parallel computing, network partitioning, floor planning, and so on. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. Further, our analysis relates the MkCS results with the stable set and the chromatic number problems. We provide extended numerical results that verify that the proposed bounding approaches provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Moreover, our lower bounds on the chromatic number of a graph are competitive with existing bounds in the literature.
- Published
- 2022
29. Post-quantum Simpson's type inequalities for coordinated convex functions
- Author
-
Xuexiao You, Saowaluck Chasreechai, Muhammad Ali, Ghulam Murtaza, Thanin Sitthiwirattham, and Sotiris K. Ntouyas
- Subjects
Inequality ,General Mathematics ,media_common.quotation_subject ,simpson's inequalities ,co-ordinated convexity ,Combinatorics ,(p ,QA1-939 ,Convex function ,Quantum ,post quantum calculus ,q)-integrals ,Mathematics ,media_common - Abstract
In this paper, we prove some new Simpson's type inequalities for partial $ (p, q) $-differentiable convex functions of two variables in the context of $ (p, q) $-calculus. We also show that the findings in this paper are generalizations of comparable findings in the literature.
- Published
- 2022
30. On the Cayleyness of Praeger-Xu graphs
- Author
-
Robert Jajcay, Primo Potočnik, and Steve Wilson
- Subjects
Combinatorics ,Arbitrarily large ,Computational Theory and Mathematics ,Group (mathematics) ,Homogeneous space ,Discrete Mathematics and Combinatorics ,Symmetry group ,Graph ,Theoretical Computer Science ,Mathematics ,Connection (mathematics) - Abstract
This paper discusses a family of graphs, called Praeger-Xu graphs and denoted PX ( n , k ) here, introduced by C.E. Praeger and M.-Y. Xu in 1989. These tetravalent graphs are distinguished by having large symmetry groups ; their vertex-stabilizers can be arbitrarily larger than the number of vertices in the graph. This paper does the following: (1) exhibits a connection between vertex-transitive groups of symmetries in a Praeger-Xu graph and certain linear codes, (2) characterizes those linear codes, (3) characterizes Praeger-Xu graphs PX ( n , k ) which are Cayley, (4) shows that every PX ( n , k ) is quasi-Cayley, and (5) constructs an infinite family of Praeger-Xu graphs in which a smallest vertex-transitive group of symmetries has arbitrarily large vertex-stabiliser.
- Published
- 2022
31. A class of bivariate independence copula transformations
- Author
-
Martynas Manstavičius and Gediminas Bagdonas
- Subjects
0209 industrial biotechnology ,Logic ,Copula (linguistics) ,02 engineering and technology ,Bivariate analysis ,Function (mathematics) ,Characterization (mathematics) ,Lebesgue integration ,Combinatorics ,symbols.namesake ,020901 industrial engineering & automation ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,symbols ,Order (group theory) ,020201 artificial intelligence & image processing ,Almost everywhere ,Differentiable function ,Mathematics - Abstract
This paper deals with the problem of characterizing all functions f : [ 0 , 1 ] → R + such that C f ( x , y ) = x y f ( ( 1 − x ) ( 1 − y ) ) , x , y ∈ [ 0 , 1 ] is a bivariate copula. We provide a complete characterization for the two cases: (i) when C f is, in addition, totally positive of order 2 (TP2) and (ii) when f is twice continuously differentiable. In general, the function f need only be twice differentiable Lebesgue almost everywhere as shown by investigating necessary conditions for C f to be a copula. The paper also contains numerous examples illustrating obtained results and connections to known facts from the literature. Moreover, several properties of such copulas are described.
- Published
- 2022
32. K3 surfaces with maximal finite automorphism groups containing M 20
- Author
-
Alessandra Sarti, Cédric Bonnafé, Institut Montpelliérain Alexander Grothendieck (IMAG), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques et Applications (LMA-Poitiers), Université de Poitiers-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0010,GeRepMod,Méthodes géométriques en théorie des représentations modulaires des groupes réductifs finis(2016), and ANR-18-CE40-0024,CATORE,CATEGORIFICATIONS EN TOPOLOGIE ET EN THEORIE DES REPRESENTATIONS(2018)
- Subjects
Finite group ,Algebra and Number Theory ,Group (mathematics) ,010102 general mathematics ,Group Theory (math.GR) ,Kummer surface ,Automorphism ,01 natural sciences ,[MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] ,K3 surface ,Combinatorics ,Mathematics - Algebraic Geometry ,0103 physical sciences ,FOS: Mathematics ,Order (group theory) ,Mathieu group ,[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] ,010307 mathematical physics ,Geometry and Topology ,0101 mathematics ,Algebraic Geometry (math.AG) ,Mathematics - Group Theory ,Symplectic geometry ,Mathematics - Abstract
It was shown by Mukai that the maximum order of a finite group acting faithfully and symplectically on a K3 surface is $960$ and that the group is isomorphic to the group $M\_{20}$. Then Kondo showed that the maximum order of a finite group acting faithfully on a K3 surface is $3\,840$ and this group contains the Mathieu group $M\_{20}$ with index four. Kondo also showed that there is a unique K3 surface on which this group acts faithfully, which is the Kummer surface $\Km(E\_i\times E\_i)$. In this paper we describe two more K3 surfaces admitting a big finite automorphism group of order $1\,920$, both groups contains $M\_{20}$ as a subgroup of index 2. We show moreover that these two groups and the two K3 surfaces are unique. This result was shown independently by S. Brandhorst and K. Hashimoto in a forthcoming paper, with the aim of classifying all the finite groups acting faithfully on K3 surfaces with maximal symplectic part., 15 pages
- Published
- 2021
33. Generalized Polynomial Complementarity Problems over a Polyhedral Cone
- Author
-
Guo-ji Tang, Tong-tong Shang, and Jing Yang
- Subjects
Polynomial (hyperelastic model) ,Combinatorics ,Control and Optimization ,Compact space ,Cone (topology) ,Applied Mathematics ,Complementarity (molecular biology) ,Theory of computation ,Solution set ,Tensor ,Extension (predicate logic) ,Management Science and Operations Research ,Mathematics - Abstract
The goal of this paper is to investigate a new model, called generalized polynomial complementarity problems over a polyhedral cone and denoted by GPCPs, which is a natural extension of the polynomial complementarity problems and generalized tensor complementarity problems. Firstly, the properties of the set of all $$R^{K}_{{\varvec{0}}}$$ -tensors are investigated. Then, the nonemptiness and compactness of the solution set of GPCPs are proved, when the involved tensor in the leading term of the polynomial is an $$ER^{K}$$ -tensor. Subsequently, under fairly mild assumptions, lower bounds of solution set via an equivalent form are obtained. Finally, a local error bound of the considered problem is derived. The results presented in this paper generalize and improve the corresponding those in the recent literature.
- Published
- 2021
34. Adaptive learning of compressible strings
- Author
-
Rossano Venturini, Gabriele Fici, Nicola Prezza, Fici G., Prezza N., and Venturini R.
- Subjects
FOS: Computer and information sciences ,Centroid decomposition ,General Computer Science ,String compression ,Adaptive learning ,Kolmogorov complexity ,Context (language use) ,Data_CODINGANDINFORMATIONTHEORY ,String reconstruction ,Theoretical Computer Science ,Combinatorics ,String learning ,Lempel-Ziv ,Suffix tree ,Integer ,Computer Science - Data Structures and Algorithms ,Order (group theory) ,Data Structures and Algorithms (cs.DS) ,Time complexity ,Computer Science::Databases ,Mathematics ,Settore INF/01 - Informatica ,Linear space ,String (computer science) ,Substring ,Bounded function - Abstract
Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $\sigma n/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $\sigma$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(\sigma-1)n+O(\sigma \sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to $\tau$ bits, performs $q=O(\tau)$ substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length $n$ over an integer alphabet of size $\sigma$ with $rle$ runs can be reconstructed with $q=O(rle (\sigma + \log \frac{n}{rle}))$ substring queries in linear time and space. We then present an algorithm that spends $q \in O(\sigma g\log n)$ substring queries and runs in $O(n(\log n + \log \sigma)+ q)$ time using linear space, where $g$ is the size of a smallest straight-line program generating the string., Comment: Accepted for publication in Theoretical Computer Science
- Published
- 2021
35. An Algebraic Approach to Projective Uniqueness with an Application to Order Polytopes
- Author
-
João Gouveia, Juan Camilo Torres, and Tristram Bogart
- Subjects
Property (philosophy) ,Order (ring theory) ,Polytope ,Theoretical Computer Science ,Combinatorics ,Computational Theory and Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Mathematics::Metric Geometry ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,Geometry and Topology ,Uniqueness ,Projective test ,Algebraic number ,Realization (systems) ,Mathematics ,Merge (linguistics) - Abstract
A combinatorial polytope $P$ is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling property but is difficult to verify. In this paper, we merge two approaches to projective uniqueness in the literature. One is primarily geometric and is due to McMullen, who showed that certain natural operations on polytopes preserve projective uniqueness. The other is more algebraic and is due to Gouveia, Macchia, Thomas, and Wiebe. They use certain ideals associated to a polytope to verify a property called graphicality that implies projective uniqueness. In this paper, we show that that McMullen's operations preserve not only projective uniquness but also graphicality. As an application, we show that large families of order polytopes are graphic and thus projectively unique.
- Published
- 2021
36. A parity theorem about trees with specified degrees
- Author
-
Kathie Cameron
- Subjects
Spanning tree ,Degree (graph theory) ,Generalization ,Applied Mathematics ,010102 general mathematics ,Eulerian path ,0102 computer and information sciences ,Extension (predicate logic) ,01 natural sciences ,Tree (graph theory) ,Vertex (geometry) ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,symbols ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Parity (mathematics) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Carsten Thomassen and I proved that in any graph G , the number of cycles containing a specified edge as well as all the vertices of odd degree is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Shunichi Toida and where all vertices have odd degree it is Andrew Thomason’s extension of Smith’s Theorem. Our proof was not algorithmic. In this paper, I extend Thomason’s algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices. Kenneth Berman extended Thomason’s Theorem to spanning trees: he proved that if T is a spanning tree such that the degree of every vertex in G − E ( T ) is odd, then there is an even number of spanning trees of G with the same degree as T at each vertex. In this paper, I give a common generalization of all of these theorems to a parity theorem about “good” trees in general graphs. My proof provides an algorithm for finding a second “good” tree.
- Published
- 2021
37. Fundamental Limits of Distributed Linear Encoding
- Author
-
Nastaran Abadi Khooshemehr and Mohammad Ali Maddah-Ali
- Subjects
Order (ring theory) ,Field (mathematics) ,Data_CODINGANDINFORMATIONTHEORY ,Coding theory ,Function (mathematics) ,Library and Information Sciences ,Computer Science Applications ,Combinatorics ,Cardinality ,Finite field ,Production (computer science) ,Decoding methods ,Information Systems ,Mathematics - Abstract
In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of $K \in \mathbb {N}$ isolated source nodes and $N \in \mathbb {N}$ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by $\beta \in \mathbb {N}$ , and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb {N}$ , the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb {N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is $t^{*} \in \mathbb {N}$ , the minimum of such $t$ , which is a function of $K$ , $N$ , $\beta $ , and $v$ . In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that $t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$ , if $N\ge K+2\beta (v-1)$ , and $t^{*}_{\textrm {Linear}}=N$ , if $N\le K+2\beta (v-1)$ . In order to achieve $t^{*}_{\textrm {Linear}}$ , we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node.
- Published
- 2021
38. Density estimation of a mixture distribution with unknown point-mass and normal error
- Author
-
Nguyen Nhu Lan, Nguyen Hoang Thanh, Nguyen Dang Minh, and Dang Duc Trong
- Subjects
Statistics and Probability ,Applied Mathematics ,05 social sciences ,Estimator ,Observable ,Density estimation ,01 natural sciences ,Noise (electronics) ,Upper and lower bounds ,Combinatorics ,010104 statistics & probability ,Rate of convergence ,0502 economics and business ,Mixture distribution ,0101 mathematics ,Statistics, Probability and Uncertainty ,Random variable ,050205 econometrics ,Mathematics - Abstract
We consider the model Y = X + ξ where Y is observable, ξ is a noise random variable with density f ξ , X has an unknown mixed density such that P ( X = X c ) = 1 − p , P ( X = a ) = p with X c being continuous and p ∈ ( 0 , 1 ) , a ∈ R . Typically, in the last decade, the model has been widely considered in a number of papers for the case of fully known quantities a , f ξ . In this paper, we relax the assumptions and consider the parametric error ξ ∼ σ N ( 0 , 1 ) with an unknown σ > 0 . From i.i.d. copies Y 1 , … , Y m of Y we will estimate ( σ , p , a , f X c ) where f X c is the density of X c . We also find the lower bound of convergence rate and verify the minimax property of established estimators.
- Published
- 2021
39. New comments on 'A Hamilton sufficient condition for completely independent spanning tree'
- Author
-
Guanbang Song, Junjiang Li, and Guifu Su
- Subjects
Combinatorics ,Spanning tree ,Applied Mathematics ,Discrete Mathematics and Combinatorics ,Graph (abstract data type) ,Always true ,Disjoint sets ,Independent spanning trees ,Hamiltonian graphs ,Mathematics - Abstract
For k ≥ 2 , spanning trees T 1 , T 2 , … , T k in a graph G are called to be completely independent if for any two distinct vertices x and y , the paths connecting them in T 1 , T 2 , … , T k are pairwise openly disjoint. We call such spanning trees T 1 , T 2 , … , T k the completely independent spanning trees (CIST for short). Recently, Hong and Zhang (2020) found that a sufficient condition for Hamiltonian graphs also suffices the existence of two CISTs. That is, if G is a graph with n vertices, | N ( x ) ∪ N ( y ) | ≥ n 2 and | N ( x ) ∩ N ( y ) | ≥ 3 for every two non-adjacent vertices x , y of G and n ≥ 5 , then G has two CISTs. More recently, Qin et al. (2020) proposed that the restriction on the number of vertices in the statement should be n ≥ 8 , and then pointed out that the Claim 1 in Hong’s paper is not always true for general case, which was corrected by presenting an amendment. However, there still exists a flaw in the corresponding revised proof (see details from the second part of our paper). Accordingly, we give a new amendment to correct the proof.
- Published
- 2021
40. Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
- Author
-
Min Ye
- Subjects
FOS: Computer and information sciences ,Random graph ,Stochastic process ,Information Theory (cs.IT) ,Computer Science - Information Theory ,Probability (math.PR) ,Structure (category theory) ,Machine Learning (stat.ML) ,Library and Information Sciences ,Composition (combinatorics) ,Computer Science Applications ,Combinatorics ,Statistics - Machine Learning ,Stochastic block model ,FOS: Mathematics ,Cluster (physics) ,Graph (abstract data type) ,Ising model ,Mathematics - Probability ,Information Systems ,Mathematics - Abstract
The stochastic block model (SBM) is a random graph model in which the edges are generated according to the underlying cluster structure on the vertices. The (ferromagnetic) Ising model, on the other hand, assigns $\pm 1$ labels to vertices according to an underlying graph structure in a way that if two vertices are connected in the graph then they are more likely to be assigned the same label. In SBM, one aims to recover the underlying clusters from the graph structure while in Ising model, an extensively-studied problem is to recover the underlying graph structure based on i.i.d. samples (labelings of the vertices). In this paper, we propose a natural composition of SBM and the Ising model, which we call the Stochastic Ising Block Model (SIBM). In SIBM, we take SBM in its simplest form, where $n$ vertices are divided into two equal-sized clusters and the edges are connected independently with probability $p$ within clusters and $q$ across clusters. Then we use the graph $G$ generated by the SBM as the underlying graph of the Ising model and draw $m$ i.i.d. samples from it. The objective is to exactly recover the two clusters in SBM from the samples generated by the Ising model, without observing the graph $G$. As the main result of this paper, we establish a sharp threshold $m^\ast$ on the sample complexity of this exact recovery problem in a properly chosen regime, where $m^\ast$ can be calculated from the parameters of SIBM. We show that when $m\ge m^\ast$, one can recover the clusters from $m$ samples in $O(n)$ time as the number of vertices $n$ goes to infinity. When $m, Comment: Fixed a gap in the original proof of Theorem 5. The new proof of Theorem 5 relies on Lemma 5, which is the main new element in this version
- Published
- 2021
41. Gallai–Ramsey numbers for graphs with chromatic number three
- Author
-
Qinghong Zhao and Bing Wei
- Subjects
Combinatorics ,Edge coloring ,Conjecture ,Integer ,Applied Mathematics ,Complete graph ,Discrete Mathematics and Combinatorics ,Value (computer science) ,Join (topology) ,Ramsey's theorem ,Upper and lower bounds ,Mathematics - Abstract
Given a graph H and an integer k ≥ 1 , the Gallai–Ramsey number G R k ( H ) is defined to be the minimum integer n such that every k -edge coloring of the complete graph K n contains either a rainbow (all different colored) triangle or a monochromatic copy of H . In this paper, we study Gallai–Ramsey numbers for graphs with chromatic number three such as K m for m ≥ 2 , where K m is a kipas with m + 1 vertices obtained from the join of K 1 and P m , and a class of graphs with five vertices, denoted by ℋ . We first study the general lower bound of such graphs and propose a conjecture for the exact value of G R k ( K m ) . Then we give a unified proof to determine the Gallai–Ramsey numbers for many graphs in ℋ and obtain the exact value of G R k ( K 4 ) for k ≥ 1 . Our outcomes not only indicate that the conjecture on G R k ( K m ) is true for m ≤ 4 , but also imply several results on G R k ( H ) for some H ∈ ℋ which are proved individually in different papers.
- Published
- 2021
42. Tight Bounds for Online Weighted Tree Augmentation
- Author
-
David P. Williamson, Joseph (Seffi) Naor, and Seeun William Umboh
- Subjects
Combinatorics ,Tree (data structure) ,000 Computer science, knowledge, general works ,General Computer Science ,Applied Mathematics ,Computer Science ,Computer Science Applications ,Mathematics - Abstract
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex spanning tree T and an additional set L of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T cup F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log^2 n)-competitive algorithm and showed an Omega(log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O(log n)-competitive algorithm for online WTAP, which is tight up to constant factors.
- Published
- 2021
43. A parameterized family of quadratic class groups with 3-Sylow subgroups of rank at least three
- Author
-
Duncan A. Buell
- Subjects
Combinatorics ,Algebra and Number Theory ,Number theory ,Discriminant ,Group (mathematics) ,Sylow theorems ,Structure (category theory) ,Order (ring theory) ,Rank (graph theory) ,Algebraic number ,Mathematics - Abstract
In a recent paper, Kishi and Komatsu have shown that the complex quadratic fields of discriminant $$\begin{aligned} \Delta _{18} = 4 - 3^{18n+3} \end{aligned}$$ have a class group whose 3-Sylow subgroup is of rank at least three for all integers n. The Kishi and Komatsu paper proves this by looking at the structure of the algebraic fields involved. Our purpose in this paper is to show that the class groups for the order whose discriminant is $$\Delta _{18}$$ have a 3-SSG of rank at least three, to show this using elementary means that would have been available to Gauss, and to elucidate further the group structure of the subgroup of classes of order 3. More generally, we shall show that $$\Delta _{18}$$ is actually a special case of a more general sequence of discriminants, all of which can be shown parametrically to have a class group whose 3-Sylow subgroup has rank at least three.
- Published
- 2021
44. Real subset sums and posets with an involution
- Author
-
Cinzia Bisi, Tommaso Gentile, and Giampiero Chiaselotti
- Subjects
Computer Science::Information Retrieval ,General Mathematics ,Carry (arithmetic) ,Astrophysics::Instrumentation and Methods for Astrophysics ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Context (language use) ,Combinatorics ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,ComputingMethodologies_DOCUMENTANDTEXTPROCESSING ,Computer Science::General Literature ,Order (group theory) ,Involution (philosophy) ,Partially ordered set ,ComputingMilieux_MISCELLANEOUS ,Mathematics - Abstract
In this paper, we carry out in an abstract order context some real subset combinatorial problems. Specifically, let [Formula: see text] be a finite poset, where [Formula: see text] is an order-reversing and involutive map such that [Formula: see text] for each [Formula: see text]. Let [Formula: see text] be the Boolean lattice with two elements and [Formula: see text] the family of all the order-preserving 2-valued maps [Formula: see text] such that [Formula: see text] if [Formula: see text] for all [Formula: see text]. In this paper, we build a family [Formula: see text] of particular subsets of [Formula: see text], that we call [Formula: see text]-bases on [Formula: see text], and we determine a bijection between the family [Formula: see text] and the family [Formula: see text]. In such a bijection, a [Formula: see text]-basis [Formula: see text] on [Formula: see text] corresponds to a map [Formula: see text] whose restriction of [Formula: see text] to [Formula: see text] is the smallest 2-valued partial map on [Formula: see text] which has [Formula: see text] as its unique extension in [Formula: see text]. Next we show how each [Formula: see text]-basis on [Formula: see text] becomes, in a particular context, a sub-system of a larger system of linear inequalities, whose compatibility implies the compatibility of the whole system.
- Published
- 2021
45. Lattice equable quadrilaterals I: Parallelograms
- Author
-
Grant Cairns and Christian Aebi
- Subjects
Combinatorics ,Quadrilateral ,Degree (graph theory) ,Lattice (music) ,Pythagorean theorem ,Integer lattice ,Tree (set theory) ,Rectangle ,Parallelogram ,Mathematics - Abstract
This paper studies equable parallelograms whose vertices lie on the integer lattice. Using Rosenberger's Theorem on generalised Markov equations, we show that the g.c.d. of the side lengths of such parallelograms can only be 3, 4 or 5, and in each of these cases the set of parallelograms naturally forms an infinite tree all of whose vertices have degree 4, bar the root. The paper then focuses on what we call Pythagorean equable parallelograms. These are lattice equable parallelograms whose complement in a circumscribing rectangle consists of two Pythagorean triangles. We prove that for these parallelograms the shortest side can only be 3, 4, 5, 6 or 10, and there are five infinite families of such parallelograms, given by solutions to corresponding Pell-like equations.
- Published
- 2021
46. Metric properties of Cayley graphs of alternating groups
- Author
-
M.S. Olshevskyi
- Subjects
Combinatorics ,Cayley graph ,General Mathematics ,Metric (mathematics) ,Mathematics - Abstract
A well known diameter search problem for finite groups with respect to its systems of generators is considered. The problem can be formulated as follows: find the diameter of a group over its system of generators. The diameter of a group over a specific system of generators is the diameter of the corresponding Cayley graph. It is considered alternating groups with classic irreducible system of generators consisting of cycles with length three of the form $(1,2,k)$. The main part of the paper concentrates on analysis how even permutations decompose with respect to this system of generators. The rules for moving generators from permutation's decomposition from left to right and from right to left are introduced. These rules give rise for transformations of decompositions, that do not increase their lengths. They are applied for removing fixed points of a permutation, that were included in its decomposition. Based on this rule the stability of system of generators is proved. The strict growing property of the system of generators is also proved, as the corollary of transformation rules and the stability property. It is considered homogeneous theory, that was introduced in the previous author's paper. For the series of alternating groups with systems of generators mentioned above it is shown that this series is uniform and homogeneous. It makes possible to apply the homogeneous down search algorithm to compute the diameter. This algorithm is applied and exact values of diameters for alternating groups of degree up to 43 are computed.
- Published
- 2021
47. The Optimal Graph Whose Least Eigenvalue is Minimal among All Graphs via 1-2 Adjacency Matrix
- Author
-
Nudrat Aamir, Lubna Gul, Gohar Ali, and Usama Waheed
- Subjects
Combinatorics ,Article Subject ,General Mathematics ,QA1-939 ,Adjacency matrix ,Mathematics ,Graph ,Eigenvalues and eigenvectors - Abstract
All graphs under consideration are finite, simple, connected, and undirected. Adjacency matrix of a graph G is 0,1 matrix A = a i j = 0 , i f v i = v j o r d v i , v j ≥ 2 1 , i f d v i , v j = 1. . Here in this paper, we discussed new type of adjacency matrix known by 1-2 adjacency matrix defined as A 1,2 G = a i j = 0 , i f v i = v j o r d v i , v j ≥ 3 1 , i f d v i , v j = 2 , from eigenvalues of the graph, we mean eigenvalues of the 1-2 adjacency matrix. Let T n c be the set of the complement of trees of order n . In this paper, we characterized a unique graph whose least eigenvalue is minimal among all the graphs in T n c .
- Published
- 2021
48. Covering by homothets and illuminating convex bodies
- Author
-
Alexey Glazyrin
- Subjects
Conjecture ,Applied Mathematics ,General Mathematics ,Discrete geometry ,Boundary (topology) ,Metric Geometry (math.MG) ,Upper and lower bounds ,Infimum and supremum ,Homothetic transformation ,Combinatorics ,Mathematics - Metric Geometry ,Hausdorff dimension ,FOS: Mathematics ,Mathematics::Metric Geometry ,Convex body ,Mathematics - Abstract
The paper is devoted to coverings by translative homothets and illuminations of convex bodies. For a given positive number $\alpha$ and a convex body $B$, $g_{\alpha}(B)$ is the infimum of $\alpha$-powers of finitely many homothety coefficients less than 1 such that there is a covering of $B$ by translative homothets with these coefficients. $h_{\alpha}(B)$ is the minimal number of directions such that the boundary of $B$ can be illuminated by this number of directions except for a subset whose Hausdorff dimension is less than $\alpha$. In this paper, we prove that $g_{\alpha}(B)\leq h_{\alpha}(B)$, find upper and lower bounds for both numbers, and discuss several general conjectures. In particular, we show that $h_{\alpha} (B) > 2^{d-\alpha}$ for almost all $\alpha$ and $d$ when $B$ is the $d$-dimensional cube, thus disproving the conjecture from Research Problems in Discrete Geometry by Brass, Moser, and Pach.
- Published
- 2021
49. On Rainbow Vertex Antimagic Coloring of Graphs: A New Notion
- Author
-
Marsidi Marsidi, Dafik Dafik, Ika Hesti Agustin, and E. Y. Kurniawati
- Subjects
Combinatorics ,Mathematics::Combinatorics ,Computer Science::Discrete Mathematics ,Simple (abstract algebra) ,Path (graph theory) ,Rainbow ,Connection number ,General Medicine ,Function (mathematics) ,Graph ,Vertex (geometry) ,Connection (mathematics) ,Mathematics - Abstract
All graph in this paper are simple, finite, and connected. Let be a labeling of a graph . The function is called antimagic rainbow edge labeling if for any two vertices and , all internal vertices in path have different weight, where the weight of vertex is the sum of its incident edges label. The vertex weight denoted by for every . If G has a antimagic rainbow edge labeling, then is a antimagic rainbow vertex connection, where the every vertex is assigned with the color . The antimagic rainbow vertex connection number of , denoted by , is the minimum colors taken over all rainbow vertex connection induced by antimagic rainbow edge labeling of . In this paper, we determined the exact value of the antimagic rainbow vertex connection number of path ( ), wheel ( ), friendship ( ), and fan ( ).
- Published
- 2021
50. On Connected Partial Domination in Graphs
- Author
-
Jessa Mae Carpentero Cabulao and Rowena T. Isla
- Subjects
Statistics and Probability ,Numerical Analysis ,Algebra and Number Theory ,Cartesian product of graphs ,Domination analysis ,Applied Mathematics ,Lexicographic product of graphs ,Join (topology) ,Cartesian product ,Theoretical Computer Science ,Combinatorics ,symbols.namesake ,Cardinality ,Dominating set ,Binary operation ,symbols ,Geometry and Topology ,Mathematics - Abstract
This paper introduces and investigates a variant of partial domination called the connected α-partial domination. For any graph G = (V (G), E(G)) and α ∈ (0, 1], a set S ⊆ V (G) is an α-partial dominating set in G if |N[S]| ≥ α |V (G)|. An α-partial dominating set S ⊆ V (G) is a connected α-partial dominating set in G if ⟨S⟩, the subgraph induced by S, is connected. The connected α-partial domination number of G, denoted by ∂Cα(G), is the smallest cardinality of a connected α-partial dominating set in G. In this paper, we characterize the connected α-partial dominating sets in the join and lexicographic product of graphs for any α ∈ (0, 1] and determine the corresponding connected α-partial domination numbers of graphs resulting from the said binary operations. Moreover, we establish sharp bounds for the connected α-partial domination numbers of the corona and Cartesian product of graphs. Furthermore, we determine ∂Cα(G) of some special graphs when α =1/2. Several realization problems are also generated in this paper.
- Published
- 2021
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.