136,742 results
Search Results
2. Stirling Numbers via Combinatorial Sums
- Author
-
Bhattacharya, Anwesh, Bhattacharya, Bivas, Filipe, Joaquim, Editorial Board Member, Ghosh, Ashish, Editorial Board Member, Prates, Raquel Oliveira, Editorial Board Member, Zhou, Lizhu, Editorial Board Member, Saha, Snehanshu, editor, Nagaraj, Nithin, editor, and Tripathi, Shikha, editor
- Published
- 2020
- Full Text
- View/download PDF
3. Evaluation of Efficiency of Using Simple Transformations When Searching for Orthogonal Diagonal Latin Squares of Order 10
- Author
-
Vatutin, Eduard, Belyshev, Alexey, Nikitina, Natalia, Manzuk, Maxim, Filipe, Joaquim, Editorial Board Member, Ghosh, Ashish, Editorial Board Member, Prates, Raquel Oliveira, Editorial Board Member, Zhou, Lizhu, Editorial Board Member, Jordan, Vladimir, editor, Filimonov, Nikolay, editor, Tarasov, Ilya, editor, and Faerman, Vladimir, editor
- Published
- 2020
- Full Text
- View/download PDF
4. Enumerating the Orthogonal Diagonal Latin Squares of Small Order for Different Types of Orthogonality
- Author
-
Vatutin, Eduard, Belyshev, Alexey, Filipe, Joaquim, Editorial Board Member, Ghosh, Ashish, Editorial Board Member, Prates, Raquel Oliveira, Editorial Board Member, Zhou, Lizhu, Editorial Board Member, Voevodin, Vladimir, editor, and Sobolev, Sergey, editor
- Published
- 2020
- Full Text
- View/download PDF
5. Enumeration of Isotopy Classes of Diagonal Latin Squares of Small Order Using Volunteer Computing
- Author
-
Vatutin, Eduard, Belyshev, Alexey, Kochemazov, Stepan, Zaikin, Oleg, Nikitina, Natalia, Barbosa, Simone Diniz Junqueira, Series Editor, Filipe, Joaquim, Series Editor, Kotenko, Igor, Series Editor, Sivalingam, Krishna M., Series Editor, Washio, Takashi, Series Editor, Yuan, Junsong, Series Editor, Zhou, Lizhu, Series Editor, Ghosh, Ashish, Series Editor, Voevodin, Vladimir, editor, and Sobolev, Sergey, editor
- Published
- 2019
- Full Text
- View/download PDF
6. Applying Volunteer and Parallel Computing for Enumerating Diagonal Latin Squares of Order 9
- Author
-
Vatutin, Eduard I., Kochemazov, Stepan E., Zaikin, Oleg S., Barbosa, Simone Diniz Junqueira, Series editor, Chen, Phoebe, Series editor, Filipe, Joaquim, Series editor, Kotenko, Igor, Series editor, Sivalingam, Krishna M., Series editor, Washio, Takashi, Series editor, Yuan, Junsong, Series editor, Zhou, Lizhu, Series editor, Sokolinsky, Leonid, editor, and Zymbler, Mikhail, editor
- Published
- 2017
- Full Text
- View/download PDF
7. Discussion of Paper by T. Tjur
- Author
-
Bailey, R. A.
- Published
- 1984
- Full Text
- View/download PDF
8. Torn-Paper Coding
- Author
-
Ilan Shomorony and Alireza Vahid
- Subjects
Combinatorics ,Computer science ,Block (permutation group theory) ,Binary number ,Library and Information Sciences ,Dna storage ,Computer Science Applications ,Information Systems - Abstract
We consider the problem of communicating over a channel that randomly “tears” the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\mathrm{ Geometric}}(p_{n})$ , we characterize the capacity as $C = e^{-\alpha }$ , where $\alpha = \lim _{n\to \infty } p_{n} \log n$ . Our results show that the case of ${\mathrm{ Geometric}}(p_{n})$ -length fragments and the case of deterministic length- $(1/p_{n})$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.
- Published
- 2021
9. An improved bound on the optimal paper Moebius band
- Author
-
Richard Evan Schwartz
- Subjects
Combinatorics ,Aspect ratio ,Differential geometry ,Hyperbolic geometry ,Geometry and Topology ,Algebraic geometry ,Lambda ,Topology (chemistry) ,Projective geometry ,Mathematics - Abstract
We show that a smooth embedded paper Moebius band must have aspect ratio at least $$\begin{aligned}\lambda _1= \frac{2 \sqrt{4-2 \sqrt{3}}+4}{\root 4 \of {3} \sqrt{2}+2 \sqrt{2 \sqrt{3}-3}} =1.69497\ldots \end{aligned}$$ This bound comes more than 3/4 of the way from the old known bound of $$\pi /2=1.5708\ldots $$ to the conjectured bound of $$\sqrt{3} = 1.732\ldots $$
- Published
- 2021
10. Simultaneously Flippable Edges in Triangulations
- Author
-
Souvaine, Diane L., Tóth, Csaba D., Winslow, Andrew, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Márquez, Alberto, editor, Ramos, Pedro, editor, and Urrutia, Jorge, editor
- Published
- 2012
- Full Text
- View/download PDF
11. A note on the paper 'Best proximity point results for $$p$$-proximal contractions'
- Author
-
M. Gabeleh and J. Markin
- Subjects
Combinatorics ,Metric space ,Class (set theory) ,General Mathematics ,Fixed-point theorem ,Point (geometry) ,Mathematics - Abstract
Very recently, I. Altun, M. Aslantas and H. Sahin [1] introduced the notion of $$p$$ -proximal contractions and surveyed the existence of best proximity points for such class of non-self mappings in metric spaces. In this note we show that this existence result is a straightforward consequence of the same conclusion in fixed point theory.
- Published
- 2021
12. Sendov’s Conjecture: A Note on a Paper of Dégot
- Author
-
T. P. Chalebgwa
- Subjects
Combinatorics ,Conjecture ,General Mathematics ,Sendov's conjecture ,Complex polynomial ,Unit distance ,Unit disk ,Critical point (mathematics) ,Mathematics - Abstract
Sendov’s conjecture states that if all the zeroes of a complex polynomial P(z) of degree at least two lie in the unit disk, then within a unit distance of each zero lies a critical point of P(z). In a paper that appeared in 2014, Degot proved that, for each a ∈ (0, 1), there exists an integer N such that for any polynomial P(z) with degree greater than N, if P(a) = 0 and all zeroes lie inside the unit disk, the disk |z − a| ≤ 1 contains a critical point of P(z). Based on this result, we derive an explicit formula N(a) for each a ∈ (0, 1) and, consequently obtain a uniform bound N for all a ∈ [α, β] where 0 < α < β < 1. This (partially) addresses the questions posed in Degot’s paper.
- Published
- 2020
13. Disruptive papers published in Scientometrics: meaningful results by using an improved variant of the disruption index originally proposed by Wu, Wang, and Evans (2019)
- Author
-
George Chacko, Alexander Tekles, Lutz Bornmann, and Sitaram Devarakonda
- Subjects
Combinatorics ,05 social sciences ,General Social Sciences ,Field (mathematics) ,0509 other social sciences ,Library and Information Sciences ,Scientometrics ,050905 science studies ,050904 information & library sciences ,Measure (mathematics) ,Computer Science Applications ,Mathematics - Abstract
Wu et al. (Nature 566:378–382, 2019) introduced a new indicator measuring disruption ($${DI}_{1}$$DI1). Bornmann et al. (Do disruption index indicators measure what they propose to measure? The comparison of several indicator variants with assessments by peers, 2019. https://arxiv.org/abs/1911.08775) compared variants of the disruption index and pointed to $${DI}_{5}$$DI5 as an interesting variant. The calculation of a field-specific version of $${DI}_{5}$$DI5 (focusing on disruptiveness within the same field) for Scientometrics papers in the current study reveals that the variant is possibly able to identify landmark papers in scientometrics. This result is in contrast to the Scientometrics analysis previously published by Bornmann and Tekles (Scientometrics 120(1):331–336, 2019) based on the original disruption index ($${DI}_{1}$$DI1).
- Published
- 2020
14. Partner choice correlates with fine scale kin structuring in the paper wasp Polistes dominula
- Author
-
Paul J. Parsons, Jeremy Field, and Lena Grinsted
- Subjects
0106 biological sciences ,0301 basic medicine ,Topography ,Heredity ,Wasps ,NERC ,Social Sciences ,01 natural sciences ,Nesting Behavior ,Habits ,Nest ,Psychology ,Inbreeding ,Islands ,education.field_of_study ,Multidisciplinary ,Behavior, Animal ,biology ,Agricultural and Biological Sciences(all) ,Eusociality ,Spring ,Databases as Topic ,Physical Sciences ,NE/M003191/1 ,Medicine ,Female ,Seasons ,Research Article ,Statistical Distributions ,Kin recognition ,Permutation ,Science ,Population ,Cuticular Hydrocarbons ,Insect Physiology ,Polistes dominula ,NE/K00655X/1 ,010603 evolutionary biology ,Nesting Habits ,03 medical and health sciences ,Genetics ,Animal Physiology ,Animals ,Social Behavior ,education ,General ,Invertebrate Physiology ,Paper wasp ,Evolutionary Biology ,Behavior ,Landforms ,Population Biology ,Discrete Mathematics ,Biochemistry, Genetics and Molecular Biology(all) ,Biology and Life Sciences ,RCUK ,Geomorphology ,Probability Theory ,biology.organism_classification ,Statistical Dispersion ,030104 developmental biology ,Natal homing ,Combinatorics ,Evolutionary biology ,Earth Sciences ,Philopatry ,Zoology ,Entomology ,Population Genetics ,Mathematics - Abstract
Cooperation among kin is common in animal societies. Kin groups may form by individuals directly discriminating relatives based on kin recognition cues, or form passively through natal philopatry and limited dispersal. We describe the genetic landscape for a primitively eusocial wasp, Polistes dominula, and ask whether individuals choose cooperative partners that are nearby and/or that are genetic relatives. Firstly, we genotyped an entire sub-population of 1361 wasps and found genetic structuring on an extremely fine scale: the probability of finding genetic relatives decreases exponentially within just a few meters of an individual’s nest. At the same time, however, we found a lack of genetic structuring between natural nest aggregations within the population. Secondly, in a separate dataset where ~2000 wasps were genotyped, we show that wasps forced experimentally to make a new nest choice tended to choose new nests near to their original nests, and that these nests tended to contain some full sisters. However, a significant fraction of wasps chose nests that did not contain sisters, despite sisters being present in nearby nests. Although we cannot rule out a role for direct kin recognition or natal nest-mate recognition, our data suggest that kin groups may form via a philopatric rule-of-thumb, whereby wasps simply select groups and nesting sites that are nearby. The result is that most subordinate helpers obtain indirect fitness benefits by breeding cooperatively.
- Published
- 2019
15. Addendum to the paper 'High‐order symmetric cubature rules for tetrahedra and pyramids'
- Author
-
Jan Jaśkowiec and N. Sukumar
- Subjects
Combinatorics ,Numerical Analysis ,Applied Mathematics ,General Engineering ,Tetrahedron ,Addendum ,High order ,Mathematics - Published
- 2021
16. Ramsey, Paper, Scissors
- Author
-
Jacob Fox, Xiaoyu He, and Yuval Wigderson
- Subjects
Computer Science::Computer Science and Game Theory ,Applied Mathematics ,General Mathematics ,Combinatorial game theory ,0102 computer and information sciences ,01 natural sciences ,Computer Graphics and Computer-Aided Design ,Upper and lower bounds ,Combinatorics ,010201 computation theory & mathematics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,FOS: Mathematics ,Mathematics - Combinatorics ,Graph (abstract data type) ,Combinatorics (math.CO) ,Ramsey's theorem ,Null graph ,Software ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,Independence number - Abstract
We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.
- Published
- 2020
17. Correcting mistakes in the paper 'A mass formula for negacyclic codes of length 2k and some good negacyclic codes over $\mathbb {Z}_{4}+u\mathbb {Z}_{4}$' [Cryptogr. Commun. (2017) 9: 241–272]
- Author
-
Rama Krishna Bandi, Yuan Cao, Yonglin Cao, and Fang-Wei Fu
- Subjects
Mass formula ,Combinatorics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Computer Networks and Communications ,Applied Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020206 networking & telecommunications ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Mathematics - Abstract
We correct some mistakes in the paper “A mass formula for negacyclic codes of length 2k and some good negacyclic codes over $\mathbb {Z}_{4}+u\mathbb {Z}_{4}$ ” (Bandi et al. Cryptogr. Commun. 9, 241–272, 2017).
- Published
- 2020
18. On a paper of Dressler and Van de Lune
- Author
-
Pablo Andres Panzone
- Subjects
Combinatorics ,Lune ,General Mathematics ,Arithmetic function ,Natural number ,Prime (order theory) ,Mathematics - Abstract
If $$z\in {\mathbb {C}}$$ and $$1\le n$$ is a natural number then $$\begin{aligned} \sum _{d_1 d_2 =n} (1-z^{p_1})\cdots (1-z^{p_m}) z^{q_1 e_{1}+\cdots +q_i e_{i} }=1, \end{aligned}$$ where $$d_1=p_1^{r_1}\dots p_m^{r_m }$$ , $$d_2=q_1^{e_1}\dots q_i^{e_i }$$ are the prime decompositions of $$d_1, d_2$$ . This is one of the identities involving arithmetic functions that we prove using ideas from the paper of Dressler and van de Lune [3].
- Published
- 2020
19. Abelian powers in paper-folding words
- Author
-
Holub, Štěpán
- Subjects
- *
ABELIAN groups , *PAPER arts , *VOCABULARY , *ARBITRARY constants , *ALGEBRA , *COMBINATORICS - Abstract
Abstract: We show that paper-folding words contain arbitrarily large abelian powers. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
20. Redistribution of Mechanical Secret Shares
- Author
-
Desmedt, Yvo, Safavi-Naini, Rei, Wang, Huaxiong, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, and Blaze, Matt, editor
- Published
- 2003
- Full Text
- View/download PDF
21. Stochastic Local Search Algorithms for DNA Word Design
- Author
-
Tulpan, Dan C., Hoos, Holger H., Condon, Anne E., Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Hagiya, Masami, editor, and Ohuchi, Azuma, editor
- Published
- 2003
- Full Text
- View/download PDF
22. 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
23. Capacity of the Torn Paper Channel with Lost Pieces
- Author
-
Aditya Narayan Ravi, Alireza Vahid, and Ilan Shomorony
- Subjects
Combinatorics ,Capacity planning ,Fragment (logic) ,Channel (programming) ,Binary number ,Length distribution ,Nuclear Experiment ,Information theory ,Computer Science::Information Theory ,Block (data storage) ,Mathematics - Abstract
We study the problem of transmitting a message over a channel that randomly breaks the message block into small fragments, deletes a subset of them, and shuffles the remaining fragments. We characterize the capacity of the binary torn-paper channel under arbitrary fragment length distribution and fragment deletion probabilities. We show that, for a message with block length $n$ , discarding fragments shorter than $\log(n)$ does not affect the achievable rates, and that the capacity is given by a simple closed-form expression that can be understood as “coverage minus reordering-cost”.
- Published
- 2021
24. Note on a paper by Bordellès, Dai, Heyman, Pan and Shparlinski
- Author
-
Jie Wu
- Subjects
Combinatorics ,General Mathematics ,010102 general mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,02 engineering and technology ,0101 mathematics ,01 natural sciences ,Mathematics - Abstract
Very recently Bordelles, Dai, Heyman, Pan and Shparlinski studied asymptotic behaviour of the quantity $$\begin{aligned} S_f(x) := \sum _{n\leqslant x} f\left( \left[ \frac{x}{n}\right] \right) , \end{aligned}$$and established some asymptotic formulas for $$S_f(x)$$ under three different types of assumptions on f. In this short note we improve some of their results.
- Published
- 2019
25. On the Dispersions of the Gel’fand–Pinsker Channel and Dirty Paper Coding
- Author
-
Jonathan Scarlett
- Subjects
Independent and identically distributed random variables ,Gaussian ,Variable-length code ,Data_CODINGANDINFORMATIONTHEORY ,Library and Information Sciences ,Computer Science Applications ,Gel’fand-Pinsker channel ,Combinatorics ,symbols.namesake ,Second-order coding rate ,Shannon–Fano coding ,Dirty paper coding ,symbols ,Channel dispersion ,Channels with state ,Algorithm ,Encoder ,Decoding methods ,Information Systems ,Mathematics ,Coding (social sciences) - Abstract
This paper studies the second-order coding rates for memoryless channels with a state sequence known non-causally at the encoder. In the case of finite alphabets, an achievability result is obtained using constant-composition random coding, and by using a small fraction of the block to transmit the empirical distribution of the state sequence. For error probabilities less than 0.5, it is shown that the second-order rate improves on an existing one based on independent and identically distributed random coding. In the Gaussian case (dirty paper coding) with an almost-sure power constraint, an achievability result is obtained using random coding over the surface of a sphere, and using a small fraction of the block to transmit a quantized description of the state power. It is shown that the second-order asymptotics are identical to the single-user Gaussian channel of the same input power without a state.
- Published
- 2015
26. Orthogonal space–time block coding over dirty paper channel: Outage capacity analysis
- Author
-
Zouhair Al-qudah
- Subjects
Combinatorics ,Block code ,Channel capacity ,Single antenna interference cancellation ,Channel state information ,Computer science ,Transmitter ,MIMO ,Dirty paper coding ,Electrical and Electronic Engineering ,Topology ,Precoding ,Computer Science::Information Theory - Abstract
We analytically prove that the outage capacity of the multiple input multiple output (MIMO) which is affected by interference, that is non-causally available as well as the channel state information (CSI) for all users at the transmitter, has the free interference outage capacity. Specifically, Orthogonal space-time block coding (O-STBC) with two transmit antennas and arbitrary number of receive antennas is used for transmission and reception. We modify the random variable U which was proposed by Costa (1983) to account for the availability of the CSI at both the transmitter and receiver. Further, we use lattice dirty paper coding (DPC) to show that an interference free channel capacity can be achieved in the MIMO-OSTBC system. First, we derive the equivalent noise seen by the receiver using an equivalent lattice based dirty paper code. Then the optimal value of the power inflation factor is derived. Next, the channel capacity of the equivalent modulo lattice channel is computed. Finally, performance results in the case of various number of receive antennas are presented and showed that significant reduction in frame error probabilities can be obtained over a system that uses no interference cancellation.
- Published
- 2015
27. Metapopulation model of rock-scissors-paper game with subpopulation-specific victory rates stabilized by heterogeneity
- Author
-
Genki Ichinose, Takashi Nagatani, and Kei-ichi Tainaka
- Subjects
0301 basic medicine ,Statistics and Probability ,General Immunology and Microbiology ,Applied Mathematics ,Victory ,Metapopulation ,General Medicine ,Models, Theoretical ,Random walk ,01 natural sciences ,General Biochemistry, Genetics and Molecular Biology ,Graph ,Combinatorics ,03 medical and health sciences ,030104 developmental biology ,Game Theory ,Homogeneous ,Modeling and Simulation ,0103 physical sciences ,Neutral stability ,Computer Simulation ,010306 general physics ,General Agricultural and Biological Sciences ,Mathematics - Abstract
Recently, metapopulation models for rock-paper-scissors games have been presented. Each subpopulation is represented by a node on a graph. An individual is either rock (R), scissors (S) or paper (P); it randomly migrates among subpopulations. In the present paper, we assume victory rates differ in different subpopulations. To investigate the dynamic state of each subpopulation (node), we numerically obtain the solutions of reaction-diffusion equations on the graphs with two and three nodes. In the case of homogeneous victory rates, we find each subpopulation has a periodic solution with neutral stability. However, when victory rates between subpopulations are heterogeneous, the solution approaches stable focuses. The heterogeneity of victory rates promotes the coexistence of species.
- Published
- 2018
28. A few observations on the paper 'Maximum distance in graphs'
- Author
-
K. V. S. Sarma, Venkata Subrahmanyam Sajja, Dasari Jai Ramesh, and I. H. Nagaraja Rao
- Subjects
Combinatorics ,Cycle graph ,Complete graph ,Extension (predicate logic) ,Complete bipartite graph ,Mathematics - Abstract
Thamarai Selvi and Vaidya Nathan [2] discussed maximum distance on graphs. We made an extension of that paper [2]. We discussed about complete graph Kn, star graph Sn, the complete bipartite graph Km,n. In this paper, we studied about the cycle graph Cn (n being any interger ≥ 3) and the multi star graph Bm,n, where m, n are integers, both greater than or equal to 2.
- Published
- 2021
29. (Short Paper) How to Solve DLOG Problem with Auxiliary Input
- Author
-
Akinaga Ueda, Hayato Tada, and Kaoru Kurosawa
- Subjects
Combinatorics ,03 medical and health sciences ,0302 clinical medicine ,Coprime integers ,010201 computation theory & mathematics ,Group (mathematics) ,Computer science ,Generator (category theory) ,030220 oncology & carcinogenesis ,Short paper ,0102 computer and information sciences ,01 natural sciences - Abstract
Let \(\mathbb {G}\) be a group of prime order p with a generator g. We first show that if \(p-1=d_1 \ldots d_t\) and \(g,g^x\), \( g^{x^{(p-1)/d_1}}, \ldots , \ g^{x^{(p-1)/(d_1 \ldots d_{t-1})}}\) are given, then x can be computed in time \( O(\sqrt{d_1}+ \ldots + \sqrt{d_t} ) \) exponentiations. Further suppose that \(p-1=d_1^{e_1} \ldots d_t^{e_t}\), where \(d_1, \ldots , d_t\) are relatively prime. We then show that x can be computed in time \( O(e_1\sqrt{d_1}+\ldots + e_t\sqrt{d_t}) \) exponentiations if g and \( g^{x^{(p-1)/d_i}}, \ldots , g^{x^{(p-1)/d_i^{e_i-1}}} \) are given for \(i=1, \ldots , t\).
- Published
- 2018
30. Observation On The Paper Entitled 'Special Pairs Of Rectangles And Sphenic Number'
- Author
-
S. Vidhyalakshmi, Gopalan M A, and S. Aarthy Thangam
- Subjects
Combinatorics ,Sphenic number ,Mathematics - Abstract
This paper aims at presenting pairs of rectangles representing the same sphenic number where, in each pair, the sum of the areas is 2 times sphenic number -1
- Published
- 2019
31. Chasing convex bodies with linear competitive ratio (invited paper)
- Author
-
Guru Guruganesh, Anupam Gupta, Ziye Tang, and C. J. Argue
- Subjects
Combinatorics ,Sequence ,Competitive analysis ,Convex body ,Steiner point ,State (functional analysis) ,Function (mathematics) ,Online algorithm ,Convex function ,Mathematics - Abstract
The problem of chasing convex functions is easy to state: faced with a sequence of convex functions f t over d-dimensional Euclidean spaces, the goal of the algorithm is to output a point x t at each time, so that the sum of the function costs f t (x t ), plus the movement costs ||x t − x t − 1 || is minimized. This problem generalizes questions in online algorithms such as caching and the k-server problem. In 1994, Friedman and Linial posed the question of getting an algorithm with a competitive ratio that depends only on the dimension d. In this talk we give an O (d)-competitive algorithm, based on the notion of the Steiner point of a convex body.
- Published
- 2021
32. A remark on a paper of P. B. Djakov and M. S. Ramanujan
- Author
-
Murat Yurdakul and Elif Uyanik
- Subjects
Unbounded operator ,Combinatorics ,symbols.namesake ,Monotone polygon ,Basis (linear algebra) ,General Mathematics ,Bounded function ,Operator (physics) ,symbols ,Sequence space ,Continuous linear operator ,Ramanujan's sum ,Mathematics - Abstract
Let l be a Banach sequence space with a monotone norm in which the canonical system (e_{n}) is an unconditional basis. We show that if there exists a continuous linear unbounded operator between l-K\"{o}the spaces, then there exists a continuous unbounded quasi-diagonal operator between them. Using this result, we study in terms of corresponding K\"{o}the matrices when every continuous linear operator between l-K\"{o}the spaces is bounded. As an application, we observe that the existence of an unbounded operator between l-K\"{o}the spaces, under a splitting condition, causes the existence of a common basic subspace.
- Published
- 2019
33. Fuzzy quotient-3 cordial labeling of star related graphs- Paper I
- Author
-
P. Sumathi and J. Suresh Kumar
- Subjects
Combinatorics ,Star (graph theory) ,Fuzzy logic ,Quotient ,Mathematics - Published
- 2019
34. Communicating over the Torn-Paper Channel
- Author
-
Alireza Vahid and Ilan Shomorony
- Subjects
FOS: Computer and information sciences ,0301 basic medicine ,Computer science ,Computer Science - Information Theory ,Information Theory (cs.IT) ,Block (permutation group theory) ,020206 networking & telecommunications ,02 engineering and technology ,Combinatorics ,03 medical and health sciences ,030104 developmental biology ,Channel (programming) ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Information Theory ,Communication channel - Abstract
We consider the problem of communicating over a channel that randomly "tears" the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\rm Geometric}(p_n)$, we characterize the capacity as $C = e^{-\alpha}$, where $\alpha = \lim_{n\to\infty} p_n \log n$. Our results show that the case of ${\rm Geometric}(p_n)$-length fragments and the case of deterministic length-$(1/p_n)$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.
- Published
- 2020
35. The Analysis of Type and Expression Method for Chinese Paper-cut Sign
- Author
-
NamHojung
- Subjects
Combinatorics ,Paper cut ,medicine ,Semiotics ,General Medicine ,Type (model theory) ,Expression (computer science) ,medicine.disease ,Sign (mathematics) ,Mathematics - Published
- 2013
36. Menon-type identities again: A note on a paper by Li, Kim and Qiao
- Author
-
László Tóth, Pentti Haukkanen, Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences, and Tampere University
- Subjects
Combinatorics ,Identity (mathematics) ,Character (mathematics) ,Mathematics - Number Theory ,Simple (abstract algebra) ,General Mathematics ,Matematiikka - Mathematics ,Arithmetic function ,Function (mathematics) ,11A07, 11A25 ,Type (model theory) ,Mathematics - Group Theory ,Mathematics - Abstract
We give common generalizations of the Menon-type identities by Sivaramakrishnan (1969) and Li, Kim, Qiao (2019). Our general identities involve arithmetic functions of several variables, and also contain, as special cases, identities for gcd-sum type functions. We point out a new Menon-type identity concerning the lcm function. We present a simple character free approach for the proof., Comment: 14 pages
- Published
- 2019
37. A Remark on the Paper 'Properties of Intersecting Families of Ordered Sets' by O. Einstein
- Author
-
Sounggun Wee and Sang-il Oum
- Subjects
010102 general mathematics ,Mistake ,0102 computer and information sciences ,01 natural sciences ,Linear subspace ,Combinatorics ,Computational Mathematics ,symbols.namesake ,010201 computation theory & mathematics ,Ordered set ,FOS: Mathematics ,symbols ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Einstein ,05C35 ,Finite set ,Mathematics - Abstract
O. Einstein (2008) proved Bollob\'as-type theorems on intersecting families of ordered sets of finite sets and subspaces. Unfortunately, we report that the proof of a theorem on ordered sets of subspaces had a mistake. We prove two weaker variants., Comment: 6 pages. Improved bound for Theorem 4
- Published
- 2018
38. A Note on the Paper 'The Algebraic Structure of the Arbitrary-Order Cone'
- Author
-
Yen Chi Roger Lin, Xin-He Miao, and Jein Shan Chen
- Subjects
Pure mathematics ,021103 operations research ,Control and Optimization ,Algebraic structure ,Applied Mathematics ,0211 other engineering and technologies ,Structure (category theory) ,Order (ring theory) ,010103 numerical & computational mathematics ,02 engineering and technology ,Management Science and Operations Research ,01 natural sciences ,Cone (formal languages) ,Combinatorics ,Operator (computer programming) ,Product (mathematics) ,Light cone ,0101 mathematics ,Mathematics ,Counterexample - Abstract
In this short paper, we look into a conclusion drawn by Alzalg (J Optim Theory Appl 169:32---49, 2016). We think the conclusion drawn in the paper is incorrect by pointing out three things. First, we provide a counterexample that the proposed inner product does not satisfy bilinearity. Secondly, we offer an argument why a pth-order cone cannot be self-dual under any reasonable inner product structure on $$\mathbb {R}^n$$Rn. Thirdly, even under the assumption that all elements operator commute, the inner product becomes an official inner product and the arbitrary-order cone can be shown as a symmetric cone, we think this condition is still unreasonable and very stringent so that the result can only be applied to very few cases.
- Published
- 2017
39. Implicit Factorization of RSA Moduli Revisited (Short Paper)
- Author
-
Lei Hu, Jun Xu, Zhangjie Huang, Liqiang Peng, and Yao Lu
- Subjects
Combinatorics ,Factorization ,Homogeneous ,Computer science ,Modulo ,Short paper ,Time complexity ,Linear equation ,Moduli - Abstract
In this paper, we revisit the problem of factoring RSA moduli with implicit hint, where primes of two RSA moduli share some number of middle bits. Suppose that for two n-bit RSA moduli $$N_1=p_1q_1$$N1=p1q1 and $$N_2=p_2q_2$$N2=p2q2, $$q_1$$q1 and $$q_2$$q2 are $$\alpha n$$αn-bit primes, $$p_1$$p1 and $$p_2$$p2 share tn bits at positions from $$t_1n$$t1n to $$t_2n=t_1+tn$$t2n=t1+tn. Faug$$\grave{e}$$e`re et al. PKC 2010 showed that when $$t\ge 4\alpha $$ti¾?4α, one can factor $$N_1$$N1 and $$N_2$$N2 in polynomial time. In this paper, we improve this bound to $$t>4\alpha -3\alpha ^2$$t>4α-3α2 by presenting a new method of solving a homogeneous linear equation modulo unknown divisors. Our method is verified by experiments.
- Published
- 2015
40. Polynomial Silent Self-Stabilizing p-Star Decomposition (Short Paper)
- Author
-
Mohammed Haddad, Colette Johnen, Sven Köhler, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), University of Freiburg, Sustainability Center Freiburg, Germany, and ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010)
- Subjects
Polynomial (hyperelastic model) ,020203 distributed computing ,Degree (graph theory) ,Round complexity ,Star (game theory) ,Short paper ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Combinatorics ,010201 computation theory & mathematics ,Distributed algorithm ,0202 electrical engineering, electronic engineering, information engineering ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Algorithm ,ComputingMilieux_MISCELLANEOUS ,Mathematics - Abstract
We present a silent self-stabilizing distributed algorithm computing a maximal p-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most \(12\varDelta m + \mathcal {O}(m+n)\) moves, where m is the number of edges, n is the number of nodes, and \(\varDelta \) is the maximum node degree. Regarding the move complexity, our algorithm outperforms the previously known best algorithm by a factor of \(\varDelta \). While the round complexity for the previous algorithm was unknown, we show a \(5\left\lfloor \frac{n}{p+1} \right\rfloor +5\) bound for our algorithm.
- Published
- 2016
41. Leader Election in Rings with Bounded Multiplicity (Short Paper)
- Author
-
Lawrence L. Larmore, Karine Altisen, Stéphane Devismes, Ajoy K. Datta, and Anaïs Durand
- Subjects
Discrete mathematics ,020203 distributed computing ,Leader election ,Short paper ,Multiplicity (mathematics) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science::Multiagent Systems ,Combinatorics ,010201 computation theory & mathematics ,Bounded function ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Abstract
We study leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. We show that message-terminating leader election is impossible for any class of rings \(\mathcal K_k\) with bounded multiplicity \(k \ge 2\). However, we show that process-terminating leader election is possible in the sub-class \(\mathcal U^* \cap \mathcal K_k\), where \(\mathcal U^*\) is the class of rings which contain a process with a unique label.
- Published
- 2016
42. A close-to-capacity dirty paper coding scheme
- Author
-
S. ten Brink and Uri Erez
- Subjects
Theoretical computer science ,Quantization (signal processing) ,Detector ,Transmitter ,Vector quantization ,Data_CODINGANDINFORMATIONTHEORY ,Library and Information Sciences ,Interference (wave propagation) ,EXIT chart ,Precoding ,Computer Science Applications ,Combinatorics ,Channel capacity ,Single antenna interference cancellation ,Code (cryptography) ,Dirty paper coding ,Algorithm ,Decoding methods ,Computer Science::Information Theory ,Information Systems ,Mathematics ,Data compression - Abstract
The "writing on dirty paper"-channel model offers an information-theoretic framework for precoding techniques for canceling arbitrary interference known at the transmitter. It indicates that lossless precoding is theoretically possible at any signal-to-noise ratio (SNR), and thus dirty-paper coding may serve as a basic building block in both single-user and multiuser communication systems. We design an end-to-end coding realization of a system materializing a significant portion of the promised gains. We employ multidimensional quantization based on trellis shaping at the transmitter. Coset decoding is implemented at the receiver using "virtual bits." Combined with iterative decoding of capacity-approaching codes we achieve an improvement of 2dB over the best scalar quantization scheme. Code design is done using the EXIT chart technique.
- Published
- 2005
43. Addendum to Paper Entitled 'Do Prime Numbers Obey a Three Dimensional Double Helix?'
- Author
-
Peter Bissonnet
- Subjects
Combinatorics ,Almost prime ,Prime factor ,Twin prime ,Calculus ,Prime triplet ,Prime power ,Probable prime ,Prime k-tuple ,Mathematics ,Sphenic number - Abstract
This paper again specifies the major points of the article “Do Prime Numbers Obey a Three-Dimensional Double Helix?” [1] which was received on February 16, 2006 by Hadronic Journal. New information has been added and elucidated upon, such as why the numbers 2 and 3 are not considered true prime numbers, and why s in the following formulas for 6s - 1 and for 6s + 1 is really a composite number equal to the sum of two other numbers, suggesting that s is always to be considered as an integer. Other new information is added as well, such as how an engineer in a matter of seconds decomposed a large prime product into its constituent primes using basic software and won a contract for his firm.
- Published
- 2017
44. Local Restrictions from the Furst-Saxe-Sipser Paper
- Author
-
Osamu Watanabe and Suguru Tamaki
- Subjects
Discrete mathematics ,Computational complexity theory ,Parity function ,True quantified Boolean formula ,Boolean circuit ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Bounded function ,Theory of computation ,Isomorphism ,0101 mathematics ,Boolean satisfiability problem ,Mathematics - Abstract
In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13---27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.
- Published
- 2016
45. Modelling the folding of paper into three dimensions using affine transformations
- Author
-
Thomas C. Hull and sarah-marie belcastro
- Subjects
Paper ,Transformations ,Numerical Analysis ,Algebra and Number Theory ,Non-flat folding ,Affine ,Identity matrix ,Folding ,Folding (DSP implementation) ,Computer Science::Computational Geometry ,Vertex (geometry) ,Combinatorics ,Homogeneous ,Product (mathematics) ,Piecewise ,Discrete Mathematics and Combinatorics ,Order (group theory) ,Geometry and Topology ,Affine transformation ,Mathematics - Abstract
We model the folding of ordinary paper via piecewise isometries R 2 → R 3 . The collection of crease lines and vertices in the unfolded paper is called the crease pattern. Our results generalize the previously known necessity conditions from the more restrictive case of folding paper flat (into R 2 ); if the crease pattern is foldable, then the product (in a non-intuitive order) of the associated rotational matrices is the identity matrix. This condition holds locally in a multiple vertex crease pattern and can be adapted to a global condition. Sufficiency conditions are significantly harder, and are not known except in the two-dimensional single-vertex case.
- Published
- 2002
46. Graph paper for polygon-packed origami design
- Author
-
Robert J. Lang and Roger Alperin
- Subjects
Combinatorics ,Computer science ,Polygon ,Graph paper - Published
- 2015
47. The Byline: Thoughts on the distribution of author ranks in multiauthored papers
- Author
-
Liming Liang, Leo Egghe, and Ronald Rousseau
- Subjects
Combinatorics ,Matrix (mathematics) ,Multiauthorship matrix ,Byline ,Author productivity distribution ,Authors per paper ,Rank distribution ,Predicted rank ,Seed ,Ranking ,Distribution (number theory) ,Modeling and Simulation ,Modelling and Simulation ,Calculus ,Probability distribution ,Rank (graph theory) ,Alphabet ,Mathematics ,Computer Science Applications - Abstract
We analyze the multiauthorship matrix M, defined as the matrix where a cell M (j, @k) denotes the number of times authors with j publications are ranked as the @k^t^h author of an article. We prove that if the distribution of the number of authors per paper follows a power law, then the author rank distribution is approximately equal to this power law (more precisely, equal in Landau's big O sense). We further determine the author rank distribution in the case where authors can be characterized through a seed number; this is the probability of preceding a fixed author in the byline of an article. Such a seed is determined for alphabetical ranking of authors using the standard western alphabet.
- Published
- 2003
- Full Text
- View/download PDF
48. Remark on the paper 'On products of Fourier coefficients of cusp forms'
- Author
-
Yuk-Kam Lau, Deyu Zhang, and Yingnan Wang
- Subjects
Cusp (singularity) ,Discrete group ,Mathematics::Number Theory ,General Mathematics ,010102 general mathematics ,Mathematical analysis ,Holomorphic function ,02 engineering and technology ,01 natural sciences ,Cusp form ,Combinatorics ,Integer ,Product (mathematics) ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,0101 mathematics ,Fourier series ,Mathematics - Abstract
Let a(n) be the Fourier coefficient of a holomorphic cusp form on some discrete subgroup of \(SL_2({\mathbb R})\). This note is to refine a recent result of Hofmann and Kohnen on the non-positive (resp. non-negative) product of \(a(n)a(n+r)\) for a fixed positive integer r.
- Published
- 2016
49. Addendum and corrigenda to the paper 'Infinitary superperfect numbers'
- Author
-
Tomohiro Yamada
- Subjects
Combinatorics ,General Computer Science ,General Mathematics ,Addendum ,Mathematics - Published
- 2018
50. Short Paper: Tight Bounds for Universal and Cautious Self-stabilizing 1-Maximal Matching
- Author
-
Michiko Inoue, Sébastien Tixeuil, Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU)
- Subjects
Matching (graph theory) ,Spacetime ,Existential quantification ,0102 computer and information sciences ,02 engineering and technology ,Binary logarithm ,Space (mathematics) ,01 natural sciences ,Upper and lower bounds ,Combinatorics ,010201 computation theory & mathematics ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,ComputingMilieux_MISCELLANEOUS ,Blossom algorithm ,Mathematics - Abstract
We consider the problem of constructing a matching in an n-nodes graph in a distributed and self-stabilizing manner. We prove that there exists a lower bound in space of \(\varOmega (n\log n)\) bits for universal maximal matching algorithms, and a lower bound in time of \(\varOmega (e)\) moves for universal and cautious 1-maximal matching algorithms. A side contribution of our result is the optimality in both time and space of the self-stabilizing 1-maximal matching algorithm of Inoue et al. [8].
- Published
- 2019
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.