2,941 research outputs found
The Möbius function of the permutation pattern Poset
No full textA permutation \tau contains another permutation \sigma as a pattern if \tau has a subsequence whose elements are in the same order with respect to size as the elements in \sigma. This defines a partial order on the set of all permutations, and gives a graded poset P. We give a large class of pairs of permutations whose intervals in P have Mobius function 0. Also, we give a solution to the problem when \sigma occurs precisely once in \tau, and \sigma and \tau satisfy certain further conditions, in which case the Mobius function is shown to be either -1, 0 or 1. We conjecture that for intervals [\sigma,\tau] consisting of permutations avoiding the pattern 132, the magnitude of the Mobius function is bounded by the number of occurrences of \sigma in \tau. We also conjecture that the Mobius function of the interval [1,\tau] is -1, 0 or 1
STANLEY’S SIMPLICIAL POSET CONJECTURE, AFTER M. MASUDA
No full textAbstract. M. Masuda recently provided the missing piece proving a conjecture of R.P. Stanley on the characterization of f-vectors for Gorenstein * simplicial posets. We propose a slight simplification of Masuda’s proof. Our main result, Theorem 2, was first proved by Masuda [Mas03], completing the missing step in a conjecture of Stanley characterizing the f-vectors of Gorenstein* simplicial posets. This note gives a simplified proof of it, using elementary methods. We begin with some background on simplicial posets; see Stanley [Sta91] for more detail and explanations for assertions not justified here. A simplicial poset P is a finite poset with a minimal element ˆ0 such that every interval [ˆ0, p] for p ∈ P is a boolean algebra. We shall work instead with the associated regular cell complex Γ = Γ(P), whose face poset is P. The (closed) faces of Γ are simplices that meet pairwise in subcomplexes of their boundaries [Sta91]. For simplicity, we identify each face G of Γ (denoted G ∈ Γ in what follows) with the corresponding element of P. Let S = k[xG: G ∈ Γ] be a polynomial ring over a field k in indeterminate
The Combinatorics of Symmetric Functions: (3 + 1)-free Posets and the Poset Chain Conjecture
No full textThere are a multitude of ways to generate symmetric functions, many of which have been described previously [4]. In 1995 Richard Stanley described a method for generating a symmetric function from the set of proper colorings of a simple graph [7]. This is known as the chromatic symmetric function and has raised a number of interesting questions, particularly regarding its expansion in terms of known bases of the vector space of symmetric functions. For instance, characterization of the e-coe cients (coe cients of the elementary symmetric function expansion) is an open problem in the eld. Stanley published a conjecture (termed the Poset Chain Conjecture) which states that the e-coe cients of the chromatic symmetric function generated by the incomparability graph of a (3+1)-free poset are nonnegative [7]. This conjecture is still unproven. Here, we present results from two papers by Vesselin Gasharov and Timothy Chow which provide supporting evidence for the Poset Chain Conjecture, as well as some combinatorial insights that may aid in the search for a proof [5, 2]
On Convex Subcomplexes of Spherical Buildings and Tits’ Center Conjecture
No full textIn this thesis we study convex subcomplexes of spherical buildings. In particular, we are interested in a question of J. Tits which goes back to the 50’s, the so-called Center
Conjecture. It states that a convex subcomplex of a spherical building is a subbuilding or the building automorphisms preserving the subcomplex have a common fixed point in it.
A proof of the Center Conjecture for the buildings of classical types (An, Bn and Dn)
has been given by B. Muehlherr and J. Tits in [MT06]. The F4-case was presented by C.
Parker and K. Tent in a talk in Oberwolfach [PT08]. Both approaches use combinatorial methods from incidence geometry. B. Leeb and the author gave in [LR09] differentialgeometric proofs for the cases F4 and E6 from the point of view of the theory of metric spaces with curvature bounded from above.
In this work we develop the differential-geometric approach further. Our main result is the proof of the Center Conjecture for buildings of type E7 and E8, whose geometry
is considerably more complicated. In particular, this completes the proof of the Center Conjecture for all thick spherical buildings. We also give a short differential-geometric proof for the classical types. Finally, we show how the cases F4, E6 and E7 can be deduced
from the E8-case
Comments on the Golden Partition Conjecture
No full textWe generalize the result of Zaguia that 1/3--2/3 Conjecture is satisfied by every N-free finite poset which is not a chain: we show a wider class of posets which satisfy the Golden Partition Conjecture. We generalize the result of Pouzet that 1/3--2/3 Conjecture is satisfied by every finite poset with a non-trivial automorphism: we show that such posets satisfy the Golden Partition Conjecture
Completions of ε-Dense Partial Latin Squares
No full textA classical question in combinatorics is the following: given a partial Latin square , when can we complete to a Latin square ? In this paper, we investigate the class of textbf{-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than -many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all -dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study -dense partial Latin squares that contain no more than filled cells in total.
In Chapter 2, we construct completions for all -dense partial Latin squares containing no more than filled cells in total, given that epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}. In particular, we show that all -dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required , as well as Chetwynd and H"aggkvist, which required , even and greater than .
If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary -dense partial Latin square is NP-complete, for any .
Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph such that
begin{itemize}
item ,
item For every vertex , and
item
end{itemize}
admits a triangulation, if epsilon < frac{1}{132}, delta < frac{(1 -132epsilon)^2 }{83272}. In particular, this holds when .
This strengthens results of Gustavsson, which requires .
In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random -edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.</p
The gluing problem in the fusion systems of the symmetric, alternating and linear groups
No full textPeer reviewe
Geometric extensions and the 1/3 - 2/3 conjecture
No full textThe 1/3—2/3 Conjecture is a famous open problem that deals with partially ordered sets, called posets. Understanding the linear extensions of a poset can unlock hidden structure with interesting applications and further questions. The conjecture says that in every finite poset that is not totally ordered there is a pair x and y, such that x y in 1/3 to 2/3 of all the linear extensions. Such pairs are called balanced pairs. We develop a geometric version of the conjecture, amenable to computational analysis by considering one dimensions projections of Euclidean realizations of the poset. We confirm the geometric 1/3—2/3 conjecture for certain classes of posets, for which the original 1/3—2/3 conjecture is currently out of reach. Ultimately, we derive quantitative estimates for the number of geometrically balanced pairs for the hom poset
A general bound for the induced poset saturation problem
No full textFor a fixed poset , a family of subsets of is induced -saturated if does not contain an induced copy of , but for every subset of such that , then is an induced subposet of . The size of the smallest such family is denoted by . Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset , either or . We improve this general result showing that either or . Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset we have ; so if true this conjecture implies our result is tight up to a multiplicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset , either or . We prove that this latter conjecture is true for a certain class of posets
A general bound for the induced poset saturation problem
No full textFor a fixed poset P, a family F of subsets of [n] is induced P-saturated if F does not contain an induced copy of P, but for every subset S of [n] such that S ∉ F, then P is an induced subposet of F ∪ {S}. The size of the smallest such family F is denoted by sat* (n, P). Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset P, either sat* (n, P) = O(1) or sat* (n, P) ≥ log2n. We improve this general result showing that either sat* (n, P) = O(1) or sat* (n, P) ≥ 2√n-2. Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset ◊ we have sat* (n, ◊) = Θ(√n); so if true this conjecture implies our result is tight up to a multiplicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset P, either sat* (n, P)= O(1) or sat* (n, P) ≥ n + 1. We prove that this latter conjecture is true for a certain class of posets P. <br/
- …
