Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Publication
- Publication Type
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter
Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter
Dartmouth Scholarship
The permutation π of length n, written in one-line notation as π (1)π (2)· · · π (n), is said to contain the permutation σ if π has a subsequence that is order isomorphic to σ, and each such subsequence is said to be an occurrence of σ in π or simply a σ pattern. For example, π = 491867532 contains σ = 51342 because of the subsequence π (2)π (3)π (5)π (6)π (9) = 91672. Permutation containment is easily seen to be a partial order on the set of all (finite) permutations, which we simply denote by ≤. If …
Submodular Percolation, Graham R. Brightwell, Peter Winkler
Submodular Percolation, Graham R. Brightwell, Peter Winkler
Dartmouth Scholarship
Let $f:{\cal L}\to\mathbb{R}$ be a submodular function on a modular lattice ${\cal L}$; we show that there is a maximal chain ${\cal C}$ in ${\cal L}$ on which the sequence of values of f is minimal among all paths from 0 to 1 in the Hasse diagram of ${\cal L}$, in a certain well-behaved partial order on sequences of reals. One consequence is that the maximum value of f on ${\cal C}$ is minimized over all such paths—i.e., if one can percolate from 0 to 1 on lattice points X with $f(X)\le b$, then one can do so along a …
The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz
The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz
Faculty Publications & Research
Erdős and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.
Discrete Mathematics With Proof Second Edition, Eric Gossett
Discrete Mathematics With Proof Second Edition, Eric Gossett
Faculty Books
Discrete mathematics has become increasingly popular in recent years due to its growing applications in the field of computer science. Discrete Mathematics with Proof, Second Edition continues to facilitate an up-to-date understanding of this important topic, exposing readers to a wide range of modern and technological applications. The book begins with an introductory chapter that provides an accessible explanation of discrete mathematics. Subsequent chapters explore additional related topics including counting, finite probability theory, recursion, formal models in computer science, graph theory, trees, the concepts of functions, and relations.
The Number Of Permutations Realized By A Shift, Sergi Elizalde
The Number Of Permutations Realized By A Shift, Sergi Elizalde
Dartmouth Scholarship
A permutation $\pi$ is realized by the shift on N symbols if there is an infinite word on an N-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as $\pi$. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [J. M. Amigó, S. Elizalde, and M. B. Kennel, J. Combin. Theory Ser. A, 115 (2008), pp. 485–504] that the shortest forbidden patterns of the shift on N symbols have length $N+2$. In this paper we give …
The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz
The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz
Noah Prince
Erdös and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.