Journal articles on the topic 'Other theoretical computer science and computational mathematics, n.e.c'
To see the other types of publications on this topic, follow the link: Other theoretical computer science and computational mathematics, n.e.c.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Other theoretical computer science and computational mathematics, n.e.c.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
OUYANG, YONGZHONG, ZHONGHAI TANG, and YIZENG LIANG. "DENSITY FUNCTIONAL THEORY STUDY ON THE DECOMPOSITION MECHANISMS OF POLYNITROTRIPRISMANES: C6H6-n (NO2)n (n = 2, 4, 6)." Journal of Theoretical and Computational Chemistry 09, no. 03 (June 2010): 561–71. http://dx.doi.org/10.1142/s0219633610005852.
Full textAbstract:
Density functional theory (DFT) has been carried out to predict some possible decomposition pathways of polynitrotriprismanes C 6 H 6-n ( NO 2)n (n = 2, 4, 6) at B3LYP/6-31 + G (d, p) level. The calculated results (BDE298) suggest that the most preferred dissociation reaction for these compounds involves an initial rupture of C–C bond in the triprismane cage skeleton, followed by an opening of the second C–C bond of the intermediate to form nitro Dewar benzene, which has a similar reaction pathway as that of octanitrocubane. In addition, the predicted reaction energy shows that the whole decomposition reaction is exothermic, and the rupture of the second C–C bond is mainly the energy origin of these compounds. The predicted dissociation route for three selected PNNPs will be very helpful not only for synthesis of PNNPs, but also for characterization of other nitro-substituted high energy density materials (HEDMs).
2
Flajolet, Philippe, Zhicheng Gao, Andrew Odlyzko, and Bruce Richmond. "The Distribution of Heights of Binary Trees and Other Simple Trees." Combinatorics, Probability and Computing 2, no. 2 (June 1993): 145–56. http://dx.doi.org/10.1017/s0963548300000560.
Full textAbstract:
The number, , of rooted plane binary trees of height ≤ h with n internal nodes is shown to satisfyuniformly for δ−1(log n)−1/2 ≤ β ≤ δ(log n)1/2, where and δ is a positive constant. An asymptotic formula for is derived for h = cn, where 0 < c < 1. Bounds for are also derived for large and small heights. The methods apply to any simple family of trees, and the general asymptotic results are stated.
3
HARRINGTON, PAUL, COLM Ó. DÚNLAING, and CHEE K. YAP. "OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS." International Journal of Computational Geometry & Applications 17, no. 06 (December 2007): 555–93. http://dx.doi.org/10.1142/s0218195907002483.
Full textAbstract:
This paper presents a worst-case optimal algorithm for constructing the Voronoi diagram for n disjoint convex and rounded semi-algebraic sites in 3 dimensions. Rather than extending optimal 2-dimensional methods,32,16,20,2 we base our method on a suboptimal 2-dimensional algorithm, outlined by Lee and Drysdale and modified by Sharir25,30 for computing the diagram of circular sites. For complexity considerations, we assume the sites have bounded complexity, i.e., the algebraic degree is bounded as is the number of algebraic patches making up the site. For the sake of simplicity we assume that the sites are what we call rounded. This assumption simplifies the analysis, though it is probably unnecessary. Our algorithm runs in time O(C(n)) where C(n) is the worst-case complexity of an n-site diagram. For spherical sites C(n) is θ(n2), but sharp estimates do not seem to be available for other classes of site.
4
Łuczak, Tomasz, and László Pyber. "On Random Generation of the Symmetric Group." Combinatorics, Probability and Computing 2, no. 4 (December 1993): 505–12. http://dx.doi.org/10.1017/s0963548300000869.
Full textAbstract:
We prove that the probability i(n, k) that a random permutation of an n element set has an invariant subset of precisely k elements decreases as a power of k, for k ≤ n/2. Using this fact, we prove that the fraction of elements of Sn belong to transitive subgroups other than Sn or An tends to 0 when n → ∞, as conjectured by Cameron. Finally, we show that for every ∈ > 0 there exists a constant C such that C elements of the symmetric group Sn, chosen randomly and independently, generate invariably Sn with probability at least 1 − ∈. This confirms a conjecture of McKay.
5
BARLOW, MARTIN T., JIAN DING, ASAF NACHMIAS, and YUVAL PERES. "The Evolution of the Cover Time." Combinatorics, Probability and Computing 20, no. 3 (February 15, 2011): 331–45. http://dx.doi.org/10.1017/s0963548310000489.
Full textAbstract:
The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovász and Vu [25] yielded a (log logn)2 polynomial time approximation. We refine the upper bound of [25], and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdős–Rényi random graph G(n, c/n) in the supercritical regime with c > 1 fixed, is asymptotic to ϕ(c)nlog2n, where ϕ(c) → 1 as c ↓ 1. However, our new bound implies that the cover time for the critical Erdős–Rényi random graph G(n, 1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0, 1}n, on high-girth expanders, and on tori ℤdn for fixed large d. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on k vertices is of order k3/2. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman [45], is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.
6
BUCKNUM, MICHAEL J., CHRIS J. PICKARD, IOAN STAMATIN, and EDUARDO A. CASTRO. "ON THE STRUCTURE OF i-CARBON." Journal of Theoretical and Computational Chemistry 05, no. 02 (June 2006): 175–85. http://dx.doi.org/10.1142/s0219633606002209.
Full textAbstract:
In the carbon science literature, there have been various reports over the past few decades of potentially novel crystalline forms of carbon emerging as nanometer scale fragments recovered from the explosive remnants of heated, shock compressed graphite and other precursors of C . Two nanometric and crystalline forms of C that are particularly prominent in these studies are known as n-diamond and i-carbon forms. In our previous work, we have shown that the commonly observed diffraction pattern of n-diamond nanocrystals, recorded by several research groups around the world, is consistent with the calculated diffraction pattern of a novel form of carbon that we propose to call glitter. Glitter is a tetragonal allotrope of carbon with a calculated density of ~3.08g/cm3, and the density functional theory (DFT) optimized lattice parameters given as a = 0.2560 nm and c = 0.5925 nm. In addition to the diffraction evidence for n-diamond having the glitter structure, the DFT calculated band structure of glitter shows it to be metallic, like the observed electrical characteristics of n-diamond. In this communication, we report on a comparison of the diffraction pattern observed for nanocrystalline i-carbon by the investigative team of Yamada et al. in 1994, with the calculated diffraction pattern of glitter based upon the optimized lattice parameters. The close fit of the latter dataset to that observed for i-carbon, as reported herein, suggests that indeed i-carbon may be of the same structure as n-diamond, and that they both may have the tetragonal glitter structure.
7
JU, XUE-HAI, and HE-MING XIAO. "A DENSITY FUNCTIONAL THEORY INVESTIGATION ON THE TAUTOMERS AND CRYSTAL OF 2-DIAZO-4,6-DINITROPHENOL." Journal of Theoretical and Computational Chemistry 03, no. 04 (December 2004): 599–607. http://dx.doi.org/10.1142/s0219633604001239.
Full textAbstract:
Density functional method was applied to the study of the highly efficient primary explosive 2-diazo-4,6-dinitrophenol (DDNP) in both gaseous tautomers and its bulk state. Two stable tautomers were located. It was found that the structure (I) with open diazo, i.e. with linear CNN, is more stable than that with diazo ring tautomer (II) of DDNP. The structure I is in good agreement with the structure in the bulk. The lattice energy is -89.01 kJ/mol, and this value drops to -83.29 kJ/mol when a 50% correction of the basis set superposition error was adopted. The frontier bands are quite flat. The carbon atoms in DDNP make up the upper valence bands. While the lower conduction bands mainly consist of carbon and diazo N atoms. The bond populations of C–N bonds (both C–Nitro and C–Diazo) are much less than those of the other bonds and the detonation may be initiated through the breakdown of C–N bonds.
8
Arunachalam, Srinivasan, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald De Wolf. "Improved Bounds on Fourier Entropy and Min-entropy." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–40. http://dx.doi.org/10.1145/3470860.
Full textAbstract:
Given a Boolean function f:{ -1,1} ^{n}→ { -1,1, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f ˆ (S) 2 . The Fourier Entropy-influence (FEI) conjecture of Friedgut and Kalai [28] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C > 0 such that H(f ˆ2 ) ≤ C ⋅ Inf (f), where H (fˆ2) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f In this article, we present three new contributions toward the FEI conjecture: (1) Our first contribution shows that H(f ˆ2 ) ≤ 2 ⋅ aUC ⊕ (f), where aUC ⊕ (f) is the average unambiguous parity-certificate complexity of f . This improves upon several bounds shown by Chakraborty et al. [20]. We further improve this bound for unambiguous DNFs. We also discuss how our work makes Mansour's conjecture for DNFs a natural next step toward resolution of the FEI conjecture. (2) We next consider the weaker Fourier Min-entropy-influence (FMEI) conjecture posed by O'Donnell and others [50, 53], which asks if H ∞ fˆ2) ≤ C ⋅ Inf(f), where H ∞ fˆ2) is the min-entropy of the Fourier distribution. We show H ∞ (fˆ2) ≤ 2⋅C min ⊕ (f), where C min ⊕ (f) is the minimum parity-certificate complexity of f . We also show that for all ε≥0, we have H ∞ (fˆ2) ≤2 log(∥f ˆ ∥1,ε/(1−ε)), where ∥f ˆ ∥1,ε is the approximate spectral norm of f . As a corollary, we verify the FMEI conjecture for the class of read- k DNFs (for constant k ). (3) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2 ω(d) can 1/3-approximate a Boolean function. This conjecture is known to be true assuming FEI, and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.
9
ADDARIO-BERRY, LOUIGI, SVANTE JANSON, and COLIN McDIARMID. "On the Spread of Random Graphs." Combinatorics, Probability and Computing 23, no. 4 (June 13, 2014): 477–504. http://dx.doi.org/10.1017/s0963548314000248.
Full textAbstract:
The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n,d), for Erdős–Rényi random graphs Gn,p in the supercritical range p>1/n, and for a ‘small world’ model. For supercritical Gn,p, we show that if p=c/n with c>1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p=(1+o(1))/n. Further, we show that for d large, with high probability the spread of G(n,d) becomes arbitrarily close to that of the complete graph $\mathsf{K}_n$.
10
Jiang, Tao, and Liana Yepremyan. "Supersaturation of even linear cycles in linear hypergraphs." Combinatorics, Probability and Computing 29, no. 5 (June 23, 2020): 698–721. http://dx.doi.org/10.1017/s0963548320000206.
Full textAbstract:
AbstractA classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in an n-vertex graph not containing C2k, the cycle of length 2k, is O(n1+1/k). Simonovits established a corresponding supersaturation result for C2k’s, showing that there exist positive constants C,c depending only on k such that every n-vertex graph G with e(G)⩾ Cn1+1/k contains at least c(e(G)/v(G))2k copies of C2k, this number of copies tightly achieved by the random graph (up to a multiplicative constant).In this paper we extend Simonovits' result to a supersaturation result of r-uniform linear cycles of even length in r-uniform linear hypergraphs. Our proof is self-contained and includes the r = 2 case. As an auxiliary tool, we develop a reduction lemma from general host graphs to almost-regular host graphs that can be used for other supersaturation problems, and may therefore be of independent interest.
11
Hamm, A., and J. Kahn. "On Erdős–Ko–Rado for random hypergraphs I." Combinatorics, Probability and Computing 28, no. 06 (June 25, 2019): 881–916. http://dx.doi.org/10.1017/s0963548319000117.
Full textAbstract:
AbstractA family of sets is intersecting if no two of its members are disjoint, and has the Erdős–Ko–Rado property (or is EKR) if each of its largest intersecting subfamilies has non-empty intersection.Denote by ${{\cal H}_k}(n,p)$ the random family in which each k-subset of {1, …, n} is present with probability p, independent of other choices. A question first studied by Balogh, Bohman and Mubayi asks: \begin{equation} {\rm{For what }}p = p(n,k){\rm{is}}{{\cal H}_k}(n,p){\rm{likely to be EKR}}? \end{equation} Here, for fixed c < 1/4, and $k \lt \sqrt {cn\log n} $ we give a precise answer to this question, characterizing those sequences p = p(n, k) for which \begin{equation} {\mathbb{P}}({{\cal H}_k}(n,p){\rm{is EKR}}{\kern 1pt} ) \to 1{\rm{as }}n \to \infty . \end{equation}
12
SEIF, AHMAD, ASADOLLAH BOSHRA, MAHMOUD MIRZAEI, and MEHRAN AGHAIE. "CARBON-SUBSTITUTING IN (4,4) BORON NITRIDE NANOTUBE: DENSITY FUNCTIONAL STUDY OF BORON-11 AND NITROGEN-14 ELECTRIC FIELD GRADIENT TENSORS." Journal of Theoretical and Computational Chemistry 07, no. 03 (June 2008): 447–55. http://dx.doi.org/10.1142/s021963360800385x.
Full textAbstract:
Density functional theory (DFT) study is performed to investigate the influence of carbon substituting in a representative model of armchair boron nitride nanotubes (BNNTs). To this aim, the electric field gradient (EFG) tensors at the sites of11B and11N nuclei are calculated in two models of (4,4) single-walled BNNT. Model one (raw) consists of 36 B and 36 N atoms with 12 saturating H atoms of two mouths while 7 B and 7 N atoms are substituted by 14 C atoms like a wire in model two ( C -substituted). The converted EFG tensors to measurable nuclear quadrupole resonance (NQR) parameters, quadrupole coupling constant (CQ) and asymmetry parameter (ηQ), reveal that the CQvalues in the length of raw BNNT are divided into some layers with equal magnitude and among them the mouth layers have the largest CQmagnitudes. In the C -substituted model, in addition to the mouth layers, the CQof those B and N nuclei directly bonded to C atoms are increased to the magnitudes as large as those mouth nuclei meaning that the active sites are increased in the C -substituted BNNT model. It is worth noting that the NQR parameters of other nuclei rather than those directly bonded to C and also those in the first neighborhood of C atoms are almost in equal values in the two models. Comparing the results with a recent study on zigzag BNNT (Mirzaei M et al., Z. Naturforsch A62:56, 2007) reveals that armchair and zigzag BNNTs show almost similar electronic properties. However, there is a significant difference in the electronic properties of those B and N atoms located at the mouth of the two BNNTs whose mouths are similar in armchair, whereas there are two different mouths ( B -mouth and N -mouth) in zigzag BNNT.
13
Barger, Artem, and Dan Feldman. "Deterministic Coresets for k-Means of Big Sparse Data †." Algorithms 13, no. 4 (April 14, 2020): 92. http://dx.doi.org/10.3390/a13040092.
Full textAbstract:
Let P be a set of n points in R d , k ≥ 1 be an integer and ε ∈ ( 0 , 1 ) be a constant. An ε-coreset is a subset C ⊆ P with appropriate non-negative weights (scalars), that approximates any given set Q ⊆ R d of k centers. That is, the sum of squared distances over every point in P to its closest point in Q is the same, up to a factor of 1 ± ε to the weighted sum of C to the same k centers. If the coreset is small, we can solve problems such as k-means clustering or its variants (e.g., discrete k-means, where the centers are restricted to be in P, or other restricted zones) on the small coreset to get faster provable approximations. Moreover, it is known that such coreset support streaming, dynamic and distributed data using the classic merge-reduce trees. The fact that the coreset is a subset implies that it preserves the sparsity of the data. However, existing such coresets are randomized and their size has at least linear dependency on the dimension d. We suggest the first such coreset of size independent of d. This is also the first deterministic coreset construction whose resulting size is not exponential in d. Extensive experimental results and benchmarks are provided on public datasets, including the first coreset of the English Wikipedia using Amazon’s cloud.
14
Janzing, D., and P. Wocjan. "A promiseBQP-complete string rewriting problem." Quantum Information and Computation 10, no. 3&4 (March 2010): 234–57. http://dx.doi.org/10.26421/qic10.3-4-5.
Full textAbstract:
We consider the following combinatorial problem. We are given three strings s, t, and t' of length L over some fixed finite alphabet and an integer $m$ that is polylogarithmic in L. We have a symmetric relation on substrings of constant length that specifies which substrings are allowed to be replaced with each other. Let $\Delta (n)$ denote the difference between the numbers of possibilities to obtain $t$ from $s$ and $t'$ from $s$ after $n \in\N$ replacements. The problem is to determine the sign of $\Delta(m)$. As promises we have a gap condition and a growth condition. The former states that $|\Delta (m)| \geq \epsilon\,c^m$ where $\epsilon$ is inverse polylogarithmic in $L$ and $c>0$ is a constant. The latter is given by $\Delta (n) \leq c^n$ for all $n$. We show that this problem is PromiseBQP-complete, i.e., it represents the class of problems that can be solved efficiently on a quantum computer.
15
KRIVELEVICH, MICHAEL, BENNY SUDAKOV, and DAN VILENCHIK. "On the Random Satisfiable Process." Combinatorics, Probability and Computing 18, no. 5 (September 2009): 775–801. http://dx.doi.org/10.1017/s0963548309990356.
Full textAbstract:
In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas. randomly permute all $2^k\binom{n}{k}$ possible clauses over the variables x1,. . .,xn, and starting from the empty formula, go over the clauses one by one, including each new clause as you go along if, after its addition, the formula remains satisfiable. We study the evolution of this process, namely the distribution over formulas obtained after scanning through the first m clauses (in the random permutation's order).Random processes with conditioning on a certain property being respected are widely studied in the context of graph properties. This study was pioneered by Ruciński and Wormald in 1992 for graphs with a fixed degree sequence, and also by Erdős, Suen and Winkler in 1995 for triangle-free and bipartite graphs. Since then many other graph properties have been studied, such as planarity and H-freeness. Thus our model is a natural extension of this approach to the satisfiability setting.Our main contribution is as follows. For m ≥ cn, c = c(k) a sufficiently large constant, we are able to characterize the structure of the solution space of a typical formula in this distribution. Specifically, we show that typically all satisfying assignments are essentially clustered in one cluster, and all but e−Ω(m/n)n of the variables take the same value in all satisfying assignments. We also describe a polynomial-time algorithm that finds w.h.p. a satisfying assignment for such formulas.
16
COLLIER-CARTAINO, CLAYTON, NATHAN GRABER, and TAO JIANG. "Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers." Combinatorics, Probability and Computing 27, no. 3 (November 2, 2017): 358–86. http://dx.doi.org/10.1017/s0963548317000530.
Full textAbstract:
Anr-uniform hypergraph is called anr-graph. A hypergraph islinearif every two edges intersect in at most one vertex. Given a linearr-graphHand a positive integern, thelinear Turán numberexL(n,H) is the maximum number of edges in a linearr-graphGthat does not containHas a subgraph. For each ℓ ≥ 3, letCrℓdenote ther-uniform linear cycle of length ℓ, which is anr-graph with edgese1, . . .,eℓsuch that, for alli∈ [ℓ−1], |ei∩ei+1|=1, |eℓ∩e1|=1 andei∩ej= ∅ for all other pairs {i,j},i≠j. For allr≥ 3 and ℓ ≥ 3, we show that there exists a positive constantc=cr,ℓ, depending onlyrand ℓ, such that exL(n,Crℓ) ≤cn1+1/⌊ℓ/2⌋. This answers a question of Kostochka, Mubayi and Verstraëte [30]. For even ℓ, our result extends the result of Bondy and Simonovits [7] on the Turán numbers of even cycles to linear hypergraphs.Using our results on linear Turán numbers, we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constantsa=am,randb=bm,r, depending only onmandr, such that\begin{equation} R(C^r_{2m}, K^r_t)\leq a \Bigl(\frac{t}{\ln t}\Bigr)^{{m}/{(m-1)}} \quad\text{and}\quad R(C^r_{2m+1}, K^r_t)\leq b t^{{m}/{(m-1)}}. \end{equation}
17
ZHU, WEI-WEI, SHAO-WEN ZHANG, and YI-HONG DING. "OXIDATION MECHANISM OF THE BUTADIYNYL RADICAL, C4H: ANALOGUE OF C2H OR NOT?" Journal of Theoretical and Computational Chemistry 12, no. 06 (September 2013): 1340002. http://dx.doi.org/10.1142/s0219633613400026.
Full textAbstract:
Reactions of the carbon-chain radicals are of great importance in the combustion and astrophysical processes. The kinetics of the butadiynyl radical, C 4 H , has received recent attention. While there has been sufficient knowledge concerning the oxidation of the ethynyl radical, C 2 H , oxidation of the higher even-numbered members C 2n H (n > 1) is hardly known. In this paper, to enrich the C 4 H -chemistry, we report the first study of the oxidation mechanism of C 4 H . At the CCSD(T)/aug-cc-pVTZ//B3LYP/6-311++G(d,p)+ZPVE level, the potential energy surface (PES) survey is presented covering various product channels P1( CO + HC 3 O ) (-152.7 kcal/mol), P2( C 3 H + CO 2) (-117.9), P3( HCO + C 3 O ) (-108.5), P4( HC 4 O +3 O ) (-45.2), and P5( OH + C 4 O ) (-33.2) accompanied by the master equation rate constant calculations. Despite the similarity in the PES, the kinetics of C 4 H +3 O 2 differs dramatically from that of the analogous C 2 H +3 O 2 reaction. For the C 4 H +3 O 2 reaction, the O -abstraction product P4( HC 4 O +3 O ) is almost the exclusive product, whereas the lowest C , O -exchange product P1( CO + HC 3 O ) and other products have little importance. By contrast, the C 2 H +3 O 2 reaction favors the C , O -exchange product HCO + CO . Being overall barrierless and mainly associated with the molecular → atomic oxygen conversion, the C 4 H +3 O 2 reaction should play an important role in the soot formation and interstellar chemistry where C 4 H is involved.
18
Marton, Katalin. "Logarithmic Sobolev inequalities in discrete product spaces." Combinatorics, Probability and Computing 28, no. 06 (June 13, 2019): 919–35. http://dx.doi.org/10.1017/s0963548319000099.
Full textAbstract:
AbstractThe aim of this paper is to prove an inequality between relative entropy and the sum of average conditional relative entropies of the following form: for a fixed probability measure q on , ( is a finite set), and any probability measure on , (*) $$D(p||q){\rm{\le}}C \cdot \sum\limits_{i = 1}^n {{\rm{\mathbb{E}}}_p D(p_i ( \cdot |Y_1 ,{\rm{ }}...,{\rm{ }}Y_{i - 1} ,{\rm{ }}Y_{i + 1} ,...,{\rm{ }}Y_n )||q_i ( \cdot |Y_1 ,{\rm{ }}...,{\rm{ }}Y_{i - 1} ,{\rm{ }}Y_{i + 1} ,{\rm{ }}...,{\rm{ }}Y_n )),} $$ where pi(· |y1, …, yi−1, yi+1, …, yn) and qi(· |x1, …, xi−1, xi+1, …, xn) denote the local specifications for p resp. q, that is, the conditional distributions of the ith coordinate, given the other coordinates. The constant C depends on (the local specifications of) q.The inequality (*) ismeaningful in product spaces, in both the discrete and the continuous case, and can be used to prove a logarithmic Sobolev inequality for q, provided uniform logarithmic Sobolev inequalities are available for qi(· |x1, …, xi−1, xi+1, …, xn), for all fixed i and fixed (x1, …, xi−1, xi+1, …, xn). Inequality (*) directly implies that the Gibbs sampler associated with q is a contraction for relative entropy.In this paper we derive inequality (*), and thereby a logarithmic Sobolev inequality, in discrete product spaces, by proving inequalities for an appropriate Wasserstein-like distance.
19
Balakrishnan, AbhayRam, R. Shankar, and S. Vijayakumar. "Reduced bond length alternation and helical molecular orbitals in donor and acceptor substituted linear carbon chains." Journal of Theoretical and Computational Chemistry 17, no. 08 (December 2018): 1850049. http://dx.doi.org/10.1142/s0219633618500499.
Full textAbstract:
Increasing chain length and end group substitution of polyynes play a crucial role in molecular electronics and nanomaterials. The studies on linear carbon chains are lesser when compared to other carbon allotropes like graphene, fullerenes, nanotube, etc. This prompted us to study the linear carbon chains of different lengths and substitutions. The electronic and optical properties of X–C[Formula: see text]–X ([Formula: see text]–15 and [Formula: see text], NH2, CN, OH) molecules have been studied by using CAM-B3LYP/6-31G* level of theory of DFT methods. Linear carbon chains with odd values of n show lower bond length alternation (BLA) values similar to that of cumulenes and may have metallic property, but the substitution of donor/acceptor molecules does not decrease the BLA significantly. Molecular orbital analysis of linear carbon chains shows that NH2 or NO2 substituted polyynes have helical molecular orbitals for smaller chain lengths which may make a good candidate for molecular wires in molecular devices. As the chain length increases, the helicity decreases and finally disappears. Also, it is seen that for smaller odd values of [Formula: see text] for donor, substituted polyynes have a singlet ground, whereas all the odd [Formula: see text] values of acceptor substitution have triplet ground state.
20
Sardharwalla, Imdad S. B., Sergii Strelchuk, and Richard Jozsa. "Quantum conditional query complexity." Quantum Information and Computation 17, no. 7&8 (May 2017): 541–67. http://dx.doi.org/10.26421/qic17.7-8-1.
Full textAbstract:
We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n/e) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.
21
Horn, Paul S. "A First Course in Order Statistics (Barry C. Arnold, N. Balakrishnan, and H. N. Nagaraja)." SIAM Review 35, no. 3 (September 1993): 525. http://dx.doi.org/10.1137/1035120.
Full text
22
Notz, William I. "Optimum Experimental Designs (A. C. Atkinson and A. N. Donev)." SIAM Review 36, no. 2 (June 1994): 315–16. http://dx.doi.org/10.1137/1036083.
Full text
23
Kaper, Hans G. "Ordinary Differential Equations in $R^n $—Problems and Methods (L. C. Piccinini, G. Stampacchia and G. Vidossich)." SIAM Review 27, no. 4 (December 1985): 596–98. http://dx.doi.org/10.1137/1027168.
Full text
24
ADEGEEST, JOHN, MARK OVERMARS, and JACK SNOEYINK. "MINIMUM-LINK C-ORIENTED PATHS: SINGLE-SOURCE QUERIES." International Journal of Computational Geometry & Applications 04, no. 01 (March 1994): 39–51. http://dx.doi.org/10.1142/s0218195994000045.
Full textAbstract:
We consider paths composed of a minimum number of line segments parallel to a fixed set of c orientations that avoid a set of obstacles in the plane. We preprocess n line segment obstacles with disjoint interiors and a starting point A into a data structure using O(cn) space. With this data structure, we can determine the minimum number of line segments l of a path from A to a query point B in O(c log n) time and construct a path in additional O(l) time. Preprocessing takes O(c2n log n) time and space or O(c2n log 2 n) time and O(c2n) space. Usually c is a constant — as an example, c = 2 for rectilinear paths.
25
ZHENG, WENXU, CHUNG WING LEUNG, ZHONGYUAN ZHOU, CHAK PO LAU, and ZHENYANG LIN. "STRUCTURE DETERMINATION OF TpRu(PPh3){κ2-N, O-NH=C(Ph)N=C(Ph)O}: A STORY OF HOW COMPUTATIONAL STUDIES CONTRIBUTE TO THE STRUCTURAL CHARACTERIZATION PROCESS." Journal of Theoretical and Computational Chemistry 08, no. 03 (June 2009): 417–22. http://dx.doi.org/10.1142/s021963360900471x.
Full textAbstract:
In this paper, we described the process involved in the structure determination of TpRu ( PPh 3){κ2-N, O- NH = C ( Ph ) N = C ( Ph ) O } and demonstrated the tremendous help of computational chemistry in the molecular structure elucidation.
26
AHN, HEE-KAP, MOHAMMAD FARSHI, CHRISTIAN KNAUER, MICHIEL SMID, and YAJUN WANG. "DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES." International Journal of Computational Geometry & Applications 20, no. 01 (February 2010): 69–87. http://dx.doi.org/10.1142/s0218195910003207.
Full textAbstract:
Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log 3 n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a (1 - ϵ)-approximation to the dilation of every path C \{e}, for all edges e of C, can be computed in O(n log n) total time.
27
GÖRKE, ROBERT, CHAN-SU SHIN, and ALEXANDER WOLFF. "CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER." International Journal of Computational Geometry & Applications 18, no. 04 (August 2008): 275–94. http://dx.doi.org/10.1142/s0218195908002623.
Full textAbstract:
Given a set P of n point sites in the plane, the city Voronoi diagram subdivides the plane into the Voronoi regions of the sites, with respect to the city metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axis-parallel line segments. We describe an algorithm that constructs the city Voronoi diagram (including quickest path information) using O((c+n) polylog (c+n)) time and storage by means of a wavefront expansion. For [Formula: see text] our algorithm is faster than an algorithm by Aichholzer et al., which takes O(n log n + c2 log c) time.
28
TANG, ZHENG-XIN, XIAO-HONG LI, RUI-ZHOU ZHANG, and XIAN-ZHOU ZHANG. "THEORETICAL STUDIES ON HEATS OF FORMATION OF PYRIDINE N-OXIDES USING DENSITY FUNCTIONAL THEORY AND COMPLETE BASIS METHOD." Journal of Theoretical and Computational Chemistry 08, no. 04 (August 2009): 541–49. http://dx.doi.org/10.1142/s0219633609004897.
Full textAbstract:
The heats of formation (HOFs) for 11 pyridine N-oxide compounds are calculated by employing the hybrid density functional theory (B3LYP, B3PW91, B3P86, PBE1PBE) methods with 6-31G** basis set and ab initio CBS-4M method. It is demonstrated that the B3PW91 method is accurate to compute the reliable HOFs for pyridine N-oxide compounds. It is also noted that the HOF is the smallest for the pyridine N-oxide which has the substituent group on the para-position, such as 4-NC–c- C 5 H 4 NO , 4- H 2 NOC – C 5 H 4 N – O , and 4- HO 2 C –c- C 5 H 4 NO . In addition, we think that the HOF of 2- HO 2 C –c- C 5 H 4 NO is much larger than that of 3- HO 2 C –c- C 5 H 4 NO and 4- HO 2 C –c- C 5 H 4 NO , which may be the result of intramolecular hydrogen bond formation and further measurements are needed to reexamine the HOFs for 2- HO 2 C –c- C 5 H 4 NO , 3- HO 2 C –c- C 5 H 4 NO , and 4- HO 2 C –c- C 5 H 4 NO .
29
LIU, MIN HSIEN, and GEN FA ZHENG. "COMPUTATIONAL STUDY OF UNIMOLECULAR DECOMPOSITION MECHANISM OF RDX EXPLOSIVE." Journal of Theoretical and Computational Chemistry 06, no. 02 (June 2007): 341–51. http://dx.doi.org/10.1142/s0219633607002952.
Full textAbstract:
This study investigated the RDX (1,3,5-Trinitro-1,3,5-triazine) molecule to elucidate its possible decomposition species and the corresponding energies by performing the density-functional theory (DFT) calculations. Reasonable decomposition mechanisms are proposed based on the bond energy calculated using the differential overlap (INDO) program, which yields the weakest bonding site for reference and determines the site of easy cleavage. Computational results indicate that the activation energy of direct cis-form HONO elimination is lower than that of direct trans-form HONO elimination and that of a two-stage elimination of two forms of HONO ( N – N bond fission combined with C – H bond breaking) in the initial decomposition step, which are 213.9 kJ/mol and 93.8–101.8 kJ/mol, respectively. Two possible pathways are proposed; (1) N – N bond homolytic cleavage followed by elimination of cis-form HONO, and (2) N – N bond homolytic cleavage followed by elimination of trans-form HONO.
30
Kölbig, K. S. "Calculation of Special Functions, the Gamma Function, the Exponential Integrals and Error-Like Functions (C. G. van der Laan and N. M. Temme)." SIAM Review 29, no. 4 (December 1987): 660–61. http://dx.doi.org/10.1137/1029138.
Full text
31
Shahrokhi, F., O. Sýkora, L. A. Székely, and I. Vrt'o. "Intersection of Curves and Crossing Number of C m × C n on Surfaces." Discrete & Computational Geometry 19, no. 2 (February 1998): 237–47. http://dx.doi.org/10.1007/pl00009343.
Full text
32
LENHOF, HANS-PETER, and MICHIEL SMID. "AN OPTIMAL CONSTRUCTION METHOD FOR GENERALIZED CONVEX LAYERS." International Journal of Computational Geometry & Applications 03, no. 03 (September 1993): 245–67. http://dx.doi.org/10.1142/s0218195993000166.
Full textAbstract:
Let P be a set of n points in the Euclidean plane and let C be a convex figure. In 1985, Chazelle and Edelsbrunner presented an algorithm, which preprocesses P such that for any query point q, the points of P in the translate C+q can be retrieved efficiently. Assuming that constant time suffices for deciding the inclusion of a point in C, they provided a space and query time optimal solution. Their algorithm uses O(n) space. A query with output size k can be solved in O( log n+k) time. The preprocessing step of their algorithm, however, has time complexity O(n2). We show that the usage of a new construction method for layers reduces the preprocessing time to O(n log n). We thus provide the first space, query time and preprocessing time optimal solution for this class of point retrieval problems. Besides, we present two new dynamic data structures for these problems. The first dynamic data structure allows on-line insertions and deletions of points in O(( log n)2) time. In this dynamic data structure, a query with output size k can be solved in O( log n+k( log n)2) time. The second dynamic data structure, which allows only semi-online updates, has O(( log n)2) amortized update time and O( log n+k) query time.
33
RAMALHO, TEODORICO C., ELAINE F. F. DA CUNHA, FERNANDO C. PEIXOTO, and JOSÉ DANIEL FIGUEROA-VILLAR. "COMPUTATIONAL NMR INVESTIGATION OF RADIOSENSITIZER IN SOLUTION." Journal of Theoretical and Computational Chemistry 07, no. 01 (February 2008): 37–52. http://dx.doi.org/10.1142/s0219633608003575.
Full textAbstract:
15 N and 13 C NMR chemical shifts for four radiosensitizers have been calculated and compared with experimental data. The thermal and solvent effects on NMR spectra were simulated with the polarizable continuum model and an alternative molecular dynamics/quantum mechanics methodology. Magnetic shielding tensors were evaluated at the GIAO-B3LYP and GIAO-OPBE level using II' and 6-311+(2D,P) basis sets, showing that it is essential to incorporate the dynamics and solvent effects on NMR calculations in condensed phases.
34
Dell, Holger, and John Lapinskas. "Fine-Grained Reductions from Approximate Counting to Decision." ACM Transactions on Computation Theory 13, no. 2 (June 2021): 1–24. http://dx.doi.org/10.1145/3442352.
Full textAbstract:
In this article, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus, we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a foundational result of Sipser (STOC 1983) and Stockmeyer (SICOMP 1985) in the polynomial-time setting, and a similar result of Müller (IWPEC 2006) in the FPT setting. Using our framework, we obtain such reductions for some of the most important problems in fine-grained complexity: the Orthogonal Vectors problem, 3SUM, and the Negative-Weight Triangle problem (which is closely related to All-Pairs Shortest Path). While all these problems have simple algorithms over which it is conjectured that no polynomial improvement is possible, our reductions would remain interesting even if these conjectures were proved; they have only polylogarithmic overhead and can therefore be applied to subpolynomial improvements such as the n 3 / exp(Θ (√ log n ))-time algorithm for the Negative-Weight Triangle problem due to Williams (STOC 2014). Our framework is also general enough to apply to versions of the problems for which more efficient algorithms are known. For example, the Orthogonal Vectors problem over GF( m ) d for constant m can be solved in time n · poly ( d ) by a result of Williams and Yu (SODA 2014); our result implies that we can approximately count the number of orthogonal pairs with essentially the same running time. We also provide a fine-grained reduction from approximate #SAT to SAT. Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for some 1 < c < 2 and all k there is an O ( c n )-time algorithm for k -SAT. Then we prove that for all k , there is an O (( c + o (1)) n )-time algorithm for approximate # k -SAT. In particular, our result implies that the Exponential Time Hypothesis (ETH) is equivalent to the seemingly weaker statement that there is no algorithm to approximate #3-SAT to within a factor of 1+ɛ in time 2 o ( n )/ ɛ 2 (taking ɛ > 0 as part of the input).
35
Li, Lei, Hongwei Fan, Hezhuan Wei, Shengli An, and Guixiao Jia. "[2+1] Additions of (n,0)(n=6−10) single-walled carbon nanotubes with di-vacancies based on defect curvature: A first-principles study." Journal of Theoretical and Computational Chemistry 18, no. 01 (February 2019): 1950004. http://dx.doi.org/10.1142/s0219633619500044.
Full textAbstract:
Binding energies ([Formula: see text], geometric and electronic structures for [[Formula: see text]](O/[[Formula: see text]]) additions of O atom on ([Formula: see text])([Formula: see text] − 10) single-walled carbon nanotubes with di-vacancies are studied using a GGA-PBE method, and defect curvature ([Formula: see text]) is used to predict reactivities of different C—C bonds at defect area. Calculated results show that the C—C bonds can be divided into two types: broken C—C bonds corresponding to adducts with a C—O—C configuration structure and unbroken C—C bonds corresponding to adducts with a closed-3MR structure. [Formula: see text] of O/[[Formula: see text]] additions for the adduct with the C—O—C configuration structure monotonously increases with the increase of [Formula: see text] in any ([Formula: see text],0)([Formula: see text]) tube and decreases with the increase of [Formula: see text] in ([Formula: see text],0)([Formula: see text], 7, 10) tubes. Besides the fact that [Formula: see text] value is mainly determined by the defect curvature, it is also affected by band gaps, bonding characteristic of C—C bonds in the highest occupied molecular orbital (HOMO) and geometric structures. The study would provide a theoretical basis for surface modifications of carbon nanotubes with atomic vacancy defects.
36
Klazar, Martin. "On Growth Rates of Permutations, Set Partitions, Ordered Graphs and Other Objects." Electronic Journal of Combinatorics 15, no. 1 (May 31, 2008). http://dx.doi.org/10.37236/799.
Full textAbstract:
For classes ${\cal O}$ of structures on finite linear orders (permutations, ordered graphs etc.) endowed with containment order $\preceq$ (containment of permutations, subgraph relation etc.), we investigate restrictions on the function $f(n)$ counting objects with size $n$ in a lower ideal in $({\cal O},\preceq)$. We present a framework of edge $P$-colored complete graphs $({\cal C}(P),\preceq)$ which includes many of these situations, and we prove for it two such restrictions (jumps in growth): $f(n)$ is eventually constant or $f(n)\ge n$ for all $n\ge 1$; $f(n)\le n^c$ for all $n\ge 1$ for a constant $c>0$ or $f(n)\ge F_n$ for all $n\ge 1$, $F_n$ being the Fibonacci numbers. This generalizes a fragment of a more detailed theorem of Balogh, Bollobás and Morris on hereditary properties of ordered graphs.
37
Vyas, Nikhil, and R. Ryan Williams. "Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms." Theory of Computing Systems, November 4, 2022. http://dx.doi.org/10.1007/s00224-022-10106-8.
Full textAbstract:
AbstractWe continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ Quasi - NP = NTIME [ n ( log n ) O ( 1 ) ] and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes $\mathcal { C}$ C , by showing that $\mathcal { C}$ C admits non-trivial satisfiability and/or # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial # SAT algorithm for a circuit class ${\mathcal C}$ C . Say that a symmetric Boolean function f(x1,…,xn) is sparse if it outputs 1 on O(1) values of ${\sum }_{i} x_{i}$ ∑ i x i . We show that for every sparse f, and for all “typical” $\mathcal { C}$ C , faster # SAT algorithms for $\mathcal { C}$ C circuits imply lower bounds against the circuit class $f \circ \mathcal { C}$ f ∘ C , which may be stronger than $\mathcal { C}$ C itself. In particular: # SAT algorithms for nk-size $\mathcal { C}$ C -circuits running in 2n/nk time (for all k) imply NEXP does not have $(f \circ \mathcal { C})$ ( f ∘ C ) -circuits of polynomial size. # SAT algorithms for $2^{n^{{\varepsilon }}}$ 2 n ε -size $\mathcal { C}$ C -circuits running in $2^{n-n^{{\varepsilon }}}$ 2 n − n ε time (for some ε > 0) imply Quasi-NP does not have $(f \circ \mathcal { C})$ ( f ∘ C ) -circuits of polynomial size. Applying # SAT algorithms from the literature, one immediate corollary of our results is that Quasi-NP does not have EMAJ ∘ ACC0 ∘ THR circuits of polynomial size, where EMAJ is the “exact majority” function, improving previous lower bounds against ACC0 [Williams JACM’14] and ACC0 ∘THR [Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.
38
Klazar, Martin. "Counting Pattern-free Set Partitions II: Noncrossing and Other Hypergraphs." Electronic Journal of Combinatorics 7, no. 1 (May 23, 2000). http://dx.doi.org/10.37236/1512.
Full textAbstract:
A (multi)hypergraph ${\cal H}$ with vertices in ${\bf N}$ contains a permutation $p=a_1a_2\ldots a_k$ of $1, 2, \ldots, k$ if one can reduce ${\cal H}$ by omitting vertices from the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to ${\cal H}_p=(\{i, k+a_i\}:\ i=1, \ldots, k)$. We formulate six conjectures stating that if ${\cal H}$ has $n$ vertices and does not contain $p$ then the size of ${\cal H}$ is $O(n)$ and the number of such ${\cal H}$s is $O(c^n)$. The latter part generalizes the Stanley–Wilf conjecture on permutations. Using generalized Davenport–Schinzel sequences, we prove the conjectures with weaker bounds $O(n\beta(n))$ and $O(\beta(n)^n)$, where $\beta(n)\rightarrow\infty$ very slowly. We prove the conjectures fully if $p$ first increases and then decreases or if $p^{-1}$ decreases and then increases. For the cases $p=12$ (noncrossing structures) and $p=21$ (nonnested structures) we give many precise enumerative and extremal results, both for graphs and hypergraphs.
39
Meagher, Karen, and Lucia Moura. "Erdős-Ko-Rado theorems for uniform set-partition systems." Electronic Journal of Combinatorics 12, no. 1 (August 25, 2005). http://dx.doi.org/10.37236/1937.
Full textAbstract:
Two set partitions of an $n$-set are said to $t$-intersect if they have $t$ classes in common. A $k$-partition is a set partition with $k$ classes and a $k$-partition is said to be uniform if every class has the same cardinality $c=n/k$. In this paper, we prove a higher order generalization of the Erdős-Ko-Rado theorem for systems of pairwise $t$-intersecting uniform $k$-partitions of an $n$-set. We prove that for $n$ large enough, any such system contains at most $${1\over(k-t)!} {n-tc \choose c} {n-(t+1)c \choose c} \cdots {n-(k-1)c \choose c}$$ partitions and this bound is only attained by a trivially $t$-intersecting system. We also prove that for $t=1$, the result is valid for all $n$. We conclude with some conjectures on this and other types of intersecting partition systems.
40
Dvořák, Vojtěch. "$P_{n}$-Induced-Saturated Graphs Exist for all $n \geqslant 6$." Electronic Journal of Combinatorics 27, no. 4 (December 11, 2020). http://dx.doi.org/10.37236/9579.
Full textAbstract:
Let $P_{n}$ be a path graph on $n$ vertices. We say that a graph $G$ is $P_{n}$-induced-saturated if $G$ contains no induced copy of $P_{n}$, but deleting any edge of $G$ as well as adding to $G$ any edge of $G^{c}$ creates such a copy. Martin and Smith (2012) showed that there is no $P_{4}$-induced-saturated graph. On the other hand, there trivially exist $P_{n}$-induced-saturated graphs for $n=2,3$. Axenovich and Csikós (2019) ask for which integers $n \geqslant 5$ do there exist $P_{n}$-induced-saturated graphs. Räty (2019) constructed such a graph for $n=6$, and Cho, Choi and Park (2019) later constructed such graphs for all $n=3k$ for $k \geqslant 2$. We show by a different construction that $P_{n}$-induced-saturated graphs exist for all $n \geqslant 6$, leaving only the case $n=5$ open.
41
Bender, Edward A., and E. Rodney Canfield. "Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities." Electronic Journal of Combinatorics 17, no. 1 (October 29, 2010). http://dx.doi.org/10.37236/417.
Full textAbstract:
We study compositions $c_1,\dots,c_k$ of the integer $n$ in which adjacent parts may be constrained to satisfy some periodic inequalities, for example $$ c_{2i}>c_{2i+1} < c_{2i+2} \mbox{(alternating compositions).} $$ The types of inequalities considered are $ < $, $\le$, $>$, $\ge$ and $\ne$. We show how to obtain generating functions from which various pieces of asymptotic information can be computed. There are asymptotically $Ar^{-n}$ compositions of $n$. In a random uniformly selected composition of $n$, the largest part and number of distinct parts are almost surely asymptotic to $\log_{1/r}(n)$. The length of the longest run is almost surely asymptotic to $C\log_{1/r}(n)$ where C is an easily determined rational number. Many other counts are asymptotically normally distributed. We present some numerical results for the various types of alternating compositions.
42
Han, Jie, Yoshiharu Kohayakawa, and Yury Person. "Near-perfect clique-factors in sparse pseudorandom graphs." Combinatorics, Probability and Computing, December 11, 2020, 1–21. http://dx.doi.org/10.1017/s0963548320000577.
Full textAbstract:
Abstract We prove that, for any $t \ge 3$ , there exists a constant c = c(t) > 0 such that any d-regular n-vertex graph with the second largest eigenvalue in absolute value λ satisfying $\lambda \le c{d^{t - 1}}/{n^{t - 2}}$ contains vertex-disjoint copies of k t covering all but at most ${n^{1 - 1/(8{t^4})}}$ vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo (Combinatorica24 (2004), pp. 403–426) that (n, d, λ)-graphs with n ∈ 3ℕ and $\lambda \le c{d^2}/n$ for a suitably small absolute constant c > 0 contain triangle-factors. Our arguments combine tools from linear programming with probabilistic techniques, and apply them in a certain weighted setting. We expect this method will be applicable to other problems in the field.
43
Gessel, Ira M., and Seunghyun Seo. "A Refinement of Cayley's Formula for Trees." Electronic Journal of Combinatorics 11, no. 2 (February 8, 2006). http://dx.doi.org/10.37236/1884.
Full textAbstract:
A proper vertex of a rooted tree with totally ordered vertices is a vertex that is the smallest of all its descendants. We count several kinds of labeled rooted trees and forests by the number of proper vertices. Our results are all expressed in terms of the polynomials $$P_n(a,b,c)= c\prod_{i=1}^{n-1}(ia+(n-i)b +c),$$ which reduce to $(n+1)^{n-1}$ for $a=b=c=1$. Our study of proper vertices was motivated by Postnikov's hook length formula $$(n+1)^{n-1}={n!\over 2^n}\sum _T \prod_{v}\left(1+{1\over h(v)}\right),$$ where the sum is over all unlabeled binary trees $T$ on $n$ vertices, the product is over all vertices $v$ of $T$, and $h(v)$ is the number of descendants of $v$ (including $v$). Our results give analogues of Postnikov's formula for other types of trees, and we also find an interpretation of the polynomials $P_n(a,b,c)$ in terms of parking functions.
44
Frieze, Alan, and Wesley Pegden. "Between 2- and 3-Colorability." Electronic Journal of Combinatorics 22, no. 1 (February 16, 2015). http://dx.doi.org/10.37236/4673.
Full textAbstract:
We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n$, $1<c\leq 4$. We show that for any positive integer $\ell$, there exists $\epsilon=\epsilon(\ell)$ such that if $c=1+\epsilon$ then w.h.p. $G_{n,p}$ has a homomorphism from $G_{n,p}$ to $C_{2\ell+1}$ so long as its odd-girth is at least $2\ell+1$. On the other hand, we show that if $c=4$ then w.h.p. there is no homomorphism from $G_{n,p}$ to $C_5$. Note that in our range of interest, $\chi(G_{n,p})=3$ w.h.p., implying that there is a homomorphism from $G_{n,p}$ to $C_3$. These results imply the existence of random graphs with circular chromatic numbers $\chi_c$ satisfying $2<\chi_c(G)<2+\delta$ for arbitrarily small $\delta$, and also that $2.5\leq \chi_c(G_{n,\frac 4 n})<3$ w.h.p.
45
Kari, Jarkko, and Etienne Moutot. "Decidability and Periodicity of Low Complexity Tilings." Theory of Computing Systems, October 28, 2021. http://dx.doi.org/10.1007/s00224-021-10063-8.
Full textAbstract:
AbstractIn this paper we study colorings (or tilings) of the two-dimensional grid ${\mathbb {Z}}^{2}$ ℤ 2 . A coloring is said to be valid with respect to a set P of n × m rectangular patterns if all n × m sub-patterns of the coloring are in P. A coloring c is said to be of low complexity with respect to a rectangle if there exist $m,n\in \mathbb {N}$ m , n ∈ ℕ and a set P of n × m rectangular patterns such that c is valid with respect to P and |P|≤ nm. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. If Nivat’s conjecture is true, all valid colorings with respect to P such that |P|≤ mn must be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle. After that, we prove that the nm bound is multiplicatively optimal for the decidability of the domino problem, as for all ε > 0 it is undecidable to determine if there exists a valid coloring for a given $m,n\in \mathbb {N}$ m , n ∈ ℕ and set of rectangular patterns P of size n × m such that |P|≤ (1 + ε)nm. We prove a slightly better bound in the case where m = n, as well as constructing aperiodic SFTs of pretty low complexity. This paper is an extended version of a paper published in STACS 2020 (Kari and Moutot 12).
46
Clearman, Samuel, Matthew Hyatt, Brittany Shelton, and Mark Skandera. "Evaluations of Hecke Algebra Traces at Kazhdan-Lusztig Basis Elements." Electronic Journal of Combinatorics 23, no. 2 (April 15, 2016). http://dx.doi.org/10.37236/5021.
Full textAbstract:
For irreducible characters $\{ \chi_q^\lambda \,|\, \lambda \vdash n \}$, induced sign characters $\{ \epsilon_q^\lambda \,|\, \lambda \vdash n \}$, and induced trivial characters $\{ \eta_q^\lambda \,|\, \lambda \vdash n \}$ of the Hecke algebra $H_n(q)$, and Kazhdan-Lusztig basis elements $C'_w(q)$ with $w$ avoiding the patterns 3412 and 4231, we combinatorially interpret the polynomials $\smash{\chi_q^\lambda(q^{\ell(w)/2} C'_w(q))}$, $\smash{\epsilon_q^\lambda(q^{\ell(w)/2} C'_w(q))}$, and $\smash{\eta_q^\lambda(q^{\ell(w)/2} C'_w(q))}$. This gives a new algebraic interpretation of chromatic quasisymmetric functions of Shareshian and Wachs, and a new combinatorial interpretation of special cases of results of Haiman. We prove similar results for other $H_n(q)$-traces, and confirm a formula conjectured by Haiman.
47
Isgur, Abraham, David Reiss, and Stephen Tanny. "Trees and Meta-Fibonacci Sequences." Electronic Journal of Combinatorics 16, no. 1 (October 31, 2009). http://dx.doi.org/10.37236/218.
Full textAbstract:
For $k>1$ and nonnegative integer parameters $a_p, b_p$, $p = 1..k$, we analyze the solutions to the meta-Fibonacci recursion $C(n)=\sum_{p=1}^k C(n-a_p-C(n-b_p))$, where the parameters $a_p, b_p$, $p = 1..k$ satisfy a specific constraint. For $k=2$ we present compelling empirical evidence that solutions exist only for two particular families of parameters; special cases of the recursions so defined include the Conolly recursion and all of its generalizations that have been studied to date. We show that the solutions for all the recursions defined by the parameters in these families have a natural combinatorial interpretation: they count the number of labels on the leaves of certain infinite labeled trees, where the number of labels on each node in the tree is determined by the parameters. This combinatorial interpretation enables us to determine various new results concerning these sequences, including a closed form, and to derive asymptotic estimates. Our results broadly generalize and unify recent findings of this type relating to certain of these meta-Fibonacci sequences. At the same time they indicate the potential for developing an analogous counting interpretation for many other meta-Fibonacci recursions specified by the same recursion for $C(n)$ with other sets of parameters.
48
Sulanke, Robert A. "Generalizing Narayana and Schröder Numbers to Higher Dimensions." Electronic Journal of Combinatorics 11, no. 1 (August 23, 2004). http://dx.doi.org/10.37236/1807.
Full textAbstract:
Let ${\cal C}(d,n)$ denote the set of $d$-dimensional lattice paths using the steps $X_1 := (1, 0, \ldots, 0),$ $ X_2 := (0, 1, \ldots, 0),$ $\ldots,$ $ X_d := (0,0, \ldots,1)$, running from $(0,\ldots,0)$ to $(n,\ldots,n)$, and lying in $\{(x_1,x_2, \ldots, x_d) : 0 \le x_1 \le x_2 \le \ldots \le x_d \}$. On any path $P:=p_1p_2 \ldots p_{dn} \in {\cal C}(d,n)$, define the statistics ${\rm asc}(P) := $$|\{i : p_ip_{i+1} = X_jX_{\ell}, j < \ell \}|$ and ${\rm des}(P) := $$|\{i : p_ip_{i+1} = X_jX_{\ell}, j>\ell \}|$. Define the generalized Narayana number $N(d,n,k)$ to count the paths in ${\cal C}(d,n)$ with ${\rm asc}(P)=k$. We consider the derivation of a formula for $N(d,n,k)$, implicit in MacMahon's work. We examine other statistics for $N(d,n,k)$ and show that the statistics ${\rm asc}$ and ${\rm des}-d+1$ are equidistributed. We use Wegschaider's algorithm, extending Sister Celine's (Wilf-Zeilberger) method to multiple summation, to obtain recurrences for $N(3,n,k)$. We introduce the generalized large Schröder numbers $(2^{d-1}\sum_k N(d,n,k)2^k)_{n\ge1}$ to count constrained paths using step sets which include diagonal steps.
49
Pittel, Boris, and Ji-A. Yeum. "How Frequently is a System of $2$-Linear Boolean Equations Solvable?" Electronic Journal of Combinatorics 17, no. 1 (June 29, 2010). http://dx.doi.org/10.37236/364.
Full textAbstract:
We consider a random system of equations $x_i+x_j=b_{(i,j)} ({\rm mod }2)$, $(x_u\in \{0,1\},\, b_{(u,v)}=b_{(v,u)}\in\{0,1\})$, with the pairs $(i,j)$ from $E$, a symmetric subset of $[n]\times [n]$. $E$ is chosen uniformly at random among all such subsets of a given cardinality $m$; alternatively $(i,j)\in E$ with a given probability $p$, independently of all other pairs. Also, given $E$, ${\rm Pr}\{b_{e}=0\}={\rm Pr}\{b_e=1\}$ for each $e\in E$, independently of all other $b_{e\prime}$. It is well known that, as $m$ passes through $n/2$ ($p$ passes through $1/n$, resp.), the underlying random graph $G(n,\#{\rm edges}=m)$, ($G(n,{\rm Pr}({\rm edge})=p)$, resp.) undergoes a rapid transition, from essentially a forest of many small trees to a graph with one large, multicyclic, component in a sea of small tree components. We should expect then that the solvability probability decreases precipitously in the vicinity of $m\sim n/2$ ($p\sim 1/n$), and indeed this probability is of order $(1-2m/n)^{1/4}$, for $m < n/2$ ($(1-pn)^{1/4}$, for $p < 1/n$, resp.). We show that in a near-critical phase $m=(n/2)(1+\lambda n^{-1/3})$ ($p=(1+\lambda n^{-1/3})/n$, resp.), $\lambda=o(n^{1/12})$, the system is solvable with probability asymptotic to $c(\lambda)n^{-1/12}$, for some explicit function $c(\lambda)>0$. Mike Molloy noticed that the Boolean system with $b_e\equiv 1$ is solvable iff the underlying graph is $2$-colorable, and asked whether this connection might be used to determine an order of probability of $2$-colorability in the near-critical case. We answer Molloy's question affirmatively and show that, for $\lambda=o(n^{1/12})$, the probability of $2$-colorability is ${}\lesssim 2^{-1/4}e^{1/8}c(\lambda)n^{-1/12}$, and asymptotic to $2^{-1/4}e^{1/8}c(\lambda)n^{-1/12}$ at a critical phase $\lambda=O(1)$, and for $\lambda\to -\infty$.
50
Spiro, Sam. "Saturation Games for Odd Cycles." Electronic Journal of Combinatorics 26, no. 4 (October 11, 2019). http://dx.doi.org/10.37236/8113.
Full textAbstract:
Given a family of graphs $\mathcal{F}$, we consider the $\mathcal{F}$-saturation game. In this game, two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that creates a subgraph that lies in $\mathcal{F}$. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $\textrm{sat}_g(\mathcal{F};n)$ denote the number of edges that are in the final graph when both players play optimally.
The $\{C_3\}$-saturation game was the first saturation game to be considered, but as of now the order of magnitude of $\textrm{sat}_g(\{C_3\},n)$ remains unknown. We consider a variation of this game. Let $\mathcal{C}_{2k+1}:=\{C_3,\ C_5,\ldots,C_{2k+1}\}$. We prove that $\textrm{sat}_g(\mathcal{C}_{2k+1};n)\ge(\frac{1}{4}-\epsilon_k)n^2+o(n^2)$ for all $k\ge 2$ and that $\textrm{sat}_g(\mathcal{C}_{2k+1};n)\le (\frac{1}{4}-\epsilon'_k)n^2+o(n^2)$ for all $k\ge 4$, with $\epsilon_k<\frac{1}{4}$ and $\epsilon'_k>0$ constants tending to 0 as $k\to \infty$. In addition to this we prove $\textrm{sat}_g(\{C_{2k+1}\};n)\le \frac{4}{27}n^2+o(n^2)$ for all $k\ge 2$, and $\textrm{sat}_g(\mathcal{C}_\infty\setminus C_3;n)\le 2n-2$, where $\mathcal{C}_\infty$ denotes the set of all odd cycles.