1,720,972 research outputs found
A relationship between generalized Davenport-Schinzel sequences and interval chains
No full textLet an (r,s)-formation be a concatenation of s permutations of r distinct letters, and let a block of a sequence be a subsequence of consecutive distinct letters. A k-chain on [1,m] is a sequence of k consecutive, disjoint, nonempty intervals of the form [a[subscript 0],a[subscript 1]][a[subscript 1] + 1,a[subscript 2]]…[a[subscript k−1] + 1,a[subscript k]] for integers 1 ≤ a[subscript 0] ≤ a[subscript 1] <…< a[subscript k] ≤ m, and an s-tuple is a set of s distinct integers. An s-tuple stabs an interval chain if each element of the s-tuple is in a different interval of the chain. Alon et al. (2008) observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause.
We show for all r ≥ 1 and 1 ≤ s ≤ k ≤ m that the maximum number of distinct letters in any sequence S on m + 1 blocks avoiding every (r,s + 1)-formation such that every letter in S occurs at least k + 1 times is the same as the maximum size of a collection X of (not necessarily distinct) k-chains on [1,m] so that there do not exist r elements of X all stabbed by the same s-tuple.
Let D[subscript s,k](m) be the maximum number of distinct letters in any sequence which can be partitioned into m blocks, has at least k occurrences of every letter, and has no subsequence forming an alternation of length s. Nivasch (2010) proved that D[subscript 5,2d+1](m) = Θ(mα[subscript d](m)) for all fixed d ≥ 2. We show that D[subscript s+1,s](m) = ([m - [s/2] over [s/2]]) for all s ≥ 2. We also prove new lower bounds which imply that D[subscript 5,6](m) = Θ(mloglogm) and D[subscript 5,2d+2](m) = Θ(mαd(m)) for all fixed d ≥ 3.National Science Foundation (U.S.). Graduate Research Fellowship (Grant 1122374
Reconfiguration graphs of zero forcing sets
Get PDFThis paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph G, its zero forcing graph, Z(G), is the graph whose vertices are the minimum zero forcing sets of G with an edge between vertices B and B′ of Z(G) if and only if B can be obtained from B′ by changing a single vertex of G. It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are either a path or the complete graph, and show that the star cannot be a zero forcing graph. We show that computing Z(G) takes 2Θ(n) operations in the worst case for a graph G of order n.This is a pre-print of the article Geneson, Jesse, Ruth Haas, and Leslie Hogben. "Reconfiguration graphs of zero forcing sets." arXiv preprint arXiv:2009.00220 (2020).
https://doi.org/10.48550/arXiv.2009.00220.Published as Geneson, Jesse, Ruth Haas, and Leslie Hogben. "Reconfiguration graphs of zero forcing sets." Discrete Applied Mathematics 329 (2023): 126-139. https://doi.org/10.1016/j.dam.2023.01.027</p
Bounding sequence extremal functions with formations
Get PDFAn (r,s)-formation is a concatenation of s permutations of r letters. If u is a sequence with r distinct letters, then let Ex(u,n) be the maximum length of any r-sparse sequence with n distinct letters which has no subsequence isomorphic to u. For every sequence u define fw(u), the formation width of u, to be the minimum s for which there exists r such that there is a subsequence isomorphic to u in every (r,s)-formation. We use fw(u) to prove upper bounds on Ex(u,n) for sequences u such that u contains an alternation with the same formation width as u.
We generalize Nivasch's bounds on Ex((ab)[superscript t],n) by showing that fw((12…l)[superscript t]) = 2t − 1 and Ex((12…l)[superscript t],n) = n2[superscript [1 over (t−2)!]α(n)t−2±O(α(n)t−3)] for every l ≥ 2 and t ≥ 3, such that α(n) denotes the inverse Ackermann function. Upper bounds on Ex((12…l)[superscript t],n) have been used in other papers to bound the maximum number of edges in k-quasiplanar graphs on n vertices with no pair of edges intersecting in more than O(1) points.
If u is any sequence of the form avav′a such that a is a letter, v is a nonempty sequence excluding a with no repeated letters and v′ is obtained from v by only moving the first letter of v to another place in v, then we show that fw(u) = 4 and Ex(u,n) = Θ(nα(n)). Furthermore we prove that fw(abc(acb)[superscript t]) = 2t + 1 and Ex(abc(acb)[superscript t],n) = n2[superscript [1 over (t−1)!]α(n)t−1±O(α(n)t−2)] for every t ≥ 2.National Science Foundation (U.S.). Graduate Research Fellowship (Grant 1122374
Propagation time for probabilistic zero forcing
Get PDFZero forcing is a coloring game played on a graph that was introduced more than ten years ago in several different applications. The goal is to color all the vertices blue by repeated use of a (deterministic) color change rule. Probabilistic zero forcing was introduced by Kang and Yi in [Probabilistic zero forcing in graphs, Bull. Inst. Combin. Appl. 67 (2013), 9--16] and yields a discrete dynamical system, which is a better model for some applications. Since in a connected graph any one vertex can eventually color the entire graph blue using probabilistic zero forcing, the expected time to do this is a natural parameter to study. We determine expected propagation time exactly for paths and cycles, establish the asymptotic value for stars, and present asymptotic upper and lower bounds for any graph in terms of its radius and order. We apply these results to obtain values and bounds on ℓ-round probabilistic zero forcing, throttling number for probabilistic zero forcing, and confidence levels for propagation time.This is a pre-print of the article Geneson, Jesse, and Leslie Hogben. "Propagation time for probabilistic zero forcing." arXiv preprint arXiv:1812.10476 (2018). Posted with permission.</p
Expected propagation time for probabilistic zero forcing
Get PDFZero forcing is a coloring process on a graph that was introduced more than fifteen years ago in several different applications. The goal is to color all the vertices blue by repeated use of a (deterministic) color change rule. Probabilistic zero forcing was introduced by Kang and Yi in [Bull. Inst. Combin. Appl. 67 (2013), 9–16] and yields a discrete dynamical system, which is a better model for some applications. Since in a connected graph any one vertex can eventually color the entire graph blue using probabilistic zero forcing, the expected time to do this is a natural parameter to study. We determine expected propagation time exactly for paths and cycles, establish the asymptotic value for stars, and present asymptotic upper and lower bounds for any graph in terms of its radius and order. We apply these results to obtain values and bounds on ℓ-round probabilistic zero forcing and confidence levels for propagation time.This article is published as Geneson, Jesse, and Leslie Hogben. "Expected propagation time for probabilistic zero forcing." Australasian Journal of Combinatorics 83 (2022): 397
Almost all permutation matrices have bounded saturation functions
Get PDFSaturation problems for forbidden graphs have been a popular area of research for many decades, and recently Brualdi and Cao initiated the study of a saturation problem for 0-1 matrices. We say that a 0-1 matrix A is saturating for the forbidden 0-1 matrix P if A avoids P but changing any zero to a one in A creates a copy of P . Define sat(n, P ) to be the minimum possible number of ones in an n × n 0-1 matrix that is saturating for P . Fulek and Keszegh proved that for every 0-1 matrix P, either sat(n, P ) = O(1) or sat(n, P ) = Θ(n). They found two 0-1 matrices P for which sat(n, P ) = O(1), as well as infinite families of 0-1 matrices P for which sat(n, P ) = Θ(n). Their results imply that sat(n, P ) = Θ(n) for almost all k × k 0-1 matrices P . Fulek and Keszegh conjectured that there are many more 0-1 matrices P such that sat(n, P ) = O(1) besides the ones they found, and they asked for a characterization of all permutation matrices P such that sat(n, P ) = O(1). We affirm their conjecture by proving that almost all k × k permutation matrices P have sat(n, P ) = O(1). We also make progress on the characterization problem, since our proof of the main result exhibits a family of permutation matrices with bounded saturation functions
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Bounds on extremal functions of forbidden patterns
No full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015.Cataloged from PDF version of thesis.Includes bibliographical references (pages 63-66).Extremal functions of forbidden sequences and 0 - 1 matrices have applications to many problems in discrete geometry and enumerative combinatorics. We present a new computational method for deriving upper bounds on extremal functions of forbidden sequences. Then we use this method to prove tight bounds on the extremal functions of sequences of the form (12 ... 1)t for 1 >/= 2 and t >/= 1, abc(acb)t for t >/= 0, and avav'a, such that a is a letter, v is a nonempty sequence excluding a with no repeated letters and v' is obtained from v by only moving the first letter of v to another place in v. We also prove the existence of infinitely many forbidden 0 - 1 matrices P with non-linear extremal functions for which every strict submatrix of P has a linear extremal function. Then we show that for every d-dimensional permutation matrix P with k ones, the maximum number of ones in a d-dimensional matrix of sidelength n that avoids P is 20(k) nd-1by Jesse Geneson.Ph. D
- …
