A hereditary class H of graphs is $χ$-bounded if there is a $χ$-binding function f such that for every $G$ in $H$, $χ(G)$ less than or equal to $f(ω(G))$. Here we prove that if a graph $G$ is free of 1. {Chair; P$_4$+K$_1$} or 2. {Chair; HVN}, then $χ(G)$ is linearly bounded by maximum clique size of G. We further prove that if $G$ is free of 3. {P$_4$+K$_1$; P$_3$ $\cup$ K$_1$} or 4. {P4+K1; K$_2$ $\cup$ 2K$_1$} or 5. {HVN; P$_3$ $\cup$ K$_1$} or 6. {HVN; K$_2$ $\cup$ 2K$_1$} or 7. {K$_{5-e}$; P$_3$ $\cup$ K$_1$} or 8. {K$_{5-e}$; K$_2$ $\cup$ 2K$_1$}, then there is a tight linear $χ$-bound for $G$.
We present two results, the first on the distribution of the roots of a polynomial over the ring of integers modulo n and the second on the distribution of the roots of the Sylvester resultant of two multivariate polynomials. The second result has application to polynomial GCD computation and solving polynomial diophantine equations.
We study random knotting by considering knot and link diagrams as decorated, (rooted) topological maps on spheres and sampling them with the counting measure on from sets of a fixed number of vertices n. We prove that random rooted knot diagrams are highly composite and hence almost surely knotted (this is the analogue of the Frisch-Wasserman-Delbruck conjecture) and extend this to unrooted knot diagrams by showing that almost all knot diagrams are asymmetric. The model is similar to one of Dunfield, et al.
The following long-standing problem in combinatorics was first posed in 1993 by Gessel and Reutenauer. For which multisubsets $B$ of the symmetric group $\fS_n$ is the quasisymmetric function $$Q(B) = \sum_{π\in B}F_{\Des(π), n}$$ a symmetric function? Here $\Des(π)$ is the descent set of $π$ and $F_{\Des(π), n}$ is Gessel's fundamental basis for the vector space of quasisymmetric functions. The purpose of this paper is to provide a useful characterization of these multisets. Using this characterization we prove a conjecture of Elizalde and Roichman. Two other corollaries are also given. The first is a short new proof that conjugacy classes are symmetric sets, a well known result first proved by Gessel and Reutenauer. Our second corollary is a unified explanation that both left and right multiplication of symmetric multisets, by inverse $J$-classes, is symmetric. The case of right multiplication was first proved by Elizalde and Roichman.
We study the mean-median map as a dynamical system on the space of finite sets of piecewise-affine continuous functions with rational coefficients. We determine the structure of the limit function in the neighbourhood of a distinctive family of rational points, the local minima. By constructing a simpler map which represents the dynamics in such neighbourhoods, we extend the results of Cellarosi and Munday (arXiv:1408.3454v1 [math.CO]) by two orders of magnitude. Based on these computations, we conjecture that the Hausdorff dimension of the graph of the limit function of the set $[0,x,1]$ is greater than 1.
Let $S\neq\mathbb N$ be a numerical semigroup generated by $e$ elements. In his paper (A Circle-Of-Lights Algorithm for the "Money-Changing Problem", Amer. Math. Monthly 85 (1978), 562--565), H.~S.~Wilf raised the following question: Let $Ω$ be the number of positive integers not contained in $S$ and $c-1$ the largest such element. Is it true that the fraction $\fracΩc$ of omitted numbers is at most $1-\frac1e$? Let $B\subseteq\mathbb N^{e-1}$ be the complement of an artinian $\mathbb N^{e-1}$-ideal. Following a concept of A.~Zhai (An asymptotic result concerning a question of Wilf, arXiv:1111.2779v1 [math.CO]) we relate Wilf's problem to a more general question about the weight distribution on $B$ with respect to a positive weight vector. An affirmative answer is given in special cases, similar to those considered by R.~Fröberg, C.~Gottlieb, R.~Häggkvist (On numerical semigroups, Semigroup Forum, Vol.~35, Issue 1, 1986/1987, 63--83) for Wilf's question.
Let $S$ be a numerical semigroup of embedding dimension $e$ and conductor $c$. The question of Wilf is, if $\#(\mathbb N\setminus S)/c\leq e-1/e$. \noindent In (An asymptotic result concerning a question of Wilf, arXiv:1111.2779v1 [math.CO], 2011, Lemma 3), Zhai has shown an analogous inequality for the distribution of weights $x\cdotγ$, $x\in\mathbb N^d$, w.\,r. to a positive weight vector $γ$: \noindent Let $B\subseteq\mathbb N^d$ be finite and the complement of an $\mathbb N^d$-ideal. Denote by $\operatorname{mean}(B\cdotγ)$ the average weight of $B$. Then \[\operatorname{mean}(B\cdotγ)/\max(B\cdotγ)\leq d/d+1.\] $\bullet$ For the family $Δ_n:=\{x\in\mathbb N^d|x\cdotγ<n+1\}$ of such sets we are able to show, that $\operatorname{mean}(Δ_n\cdotγ)/\max(Δ_n\cdotγ)$ converges to $d/d+1$, as $n$ goes to infinity. $\bullet$ Applying Zhai's Lemma 3 to the Hilbert function of a positively graded Artinian algebra yields a new class of numerical semigroups satisfying Wilf's inequality.
Let $P$ be a Poisson structure on a finite-dimensional affine real manifold. Can $P$ be deformed in such a way that it stays Poisson? The language of Kontsevich graphs provides a universal approach -- with respect to all affine Poisson manifolds -- to finding a class of solutions to this deformation problem. For that reasoning, several types of graphs are needed. In this paper we outline the algorithms to generate those graphs. The graphs that encode deformations are classified by the number of internal vertices $k$; for $k \leqslant 4$ we present all solutions of the deformation problem. For $k \geqslant 5$, first reproducing the pentagon-wheel picture suggested at $k=6$ by Kontsevich and Willwacher, we construct the heptagon-wheel cocycle that yields a new unique solution without $2$-loops and tadpoles at $k=8$.
Gwendal Collet, Élie de Panafieu, Danièle Gardy
et al.
We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, including the case of constrained degrees. Our approach relies heavily on analytic combinatorics and on the notion of patchwork to describe the possible overlapping of copies. This paper is a version, extended to include proofs, of the paper with the same title to be presented at the Eurocomb 2017 meeting.
Duško Jojić, Wacław Marzantowicz, Siniša T. Vrećica
et al.
The partition number $π(K)$ of a simplicial complex $K\subset 2^{[m]}$ is the minimum integer $ν$ such that for each partition $A_1\uplus\ldots\uplus A_ν= [m]$ of $[m]$ at least one of the sets $A_i$ is in $K$. A complex $K$ is $r$-unavoidable if $π(K)\leq r$. We say that a complex $K$ is globally $r$-non-embeddable in $\mathbb{R}^d$ if for each continuous map $f: | K| \rightarrow \mathbb{R}^d$ there exist $r$ vertex disjoint faces $σ_1,\ldots, σ_r$ of $| K|$ such that $f(σ_1)\cap\ldots\cap f(σ_r)\neq\emptyset$. Motivated by the problems of Tverberg-Van Kampen-Flores type we prove several results (Theorems 3.6, 3.9, 4.6) which link together the combinatorics and topology of these two classes of complexes. One of our central observations (Theorem 4.6), summarizing and extending results of G. Schild, B. Grünbaum and many others, is that interesting examples of (globally) $r$-non-embeddable complexes can be found among the joins $K = K_1\ast\ldots\ast K_s$ of $r$-unavoidable complexes.
This paper uses the theory of dual equivalence graphs to give explicit Schur expansions to several families of symmetric functions. We begin by giving a combinatorial definition of the modified Macdonald polynomials and modified Hall-Littlewood polynomials indexed by any diagram $δ ⊂ \mathbb{Z} \times \mathbb{Z}$, written as $\widetilde H_δ (X;q,t)$ and $\widetilde P_δ (X;t)$, respectively. We then give an explicit Schur expansion of $\widetilde P_δ (X;t)$ as a sum over a subset of the Yamanouchi words, as opposed to the expansion using the charge statistic given in 1978 by Lascoux and Schüztenberger. We further define the symmetric function $R_γ ,δ (X)$ as a refinement of $\widetilde P_δ$ and similarly describe its Schur expansion. We then analysize $R_γ ,δ (X)$ to determine the leading term of its Schur expansion. To gain these results, we associate each Macdonald polynomial with a signed colored graph $\mathcal{H}_δ$ . In the case where a subgraph of $\mathcal{H}_δ$ is a dual equivalence graph, we provide the Schur expansion of its associated symmetric function, yielding several corollaries.
This paper considers the representation theory of towers of algebras of $\mathcal{J} -trivial$ monoids. Using a very general lemma on induction, we derive a combinatorial description of the algebra and coalgebra structure on the Grothendieck rings $G_0$ and $K_0$. We then apply our theory to some examples. We first retrieve the classical Krob-Thibon's categorification of the pair of Hopf algebras QSym$/NCSF$ as representation theory of the tower of 0-Hecke algebras. Considering the towers of semilattices given by the permutohedron, associahedron, and Boolean lattices, we categorify the algebra and the coalgebra structure of the Hopf algebras $FQSym , PBT$ , and $NCSF$ respectively. Lastly we completely describe the representation theory of the tower of the monoids of Non Decreasing Parking Functions.
Using bijections between pattern-avoiding permutations and certain full rook placements on Ferrers boards, we give short proofs of two enumerative results. The first is a simplified enumeration of the 3124, 1234-avoiding permutations, obtained recently by Callan via a complicated decomposition. The second is a streamlined bijection between 1342-avoiding permutations and permutations which can be sorted by two increasing stacks in series, originally due to Atkinson, Murphy, and Ruškuc.
Problem of finding an optimal upper bound for a chromatic no. of 3K1-free graphs is still open and pretty hard. Here we find a tight chromatic upper bound for {3K1, C5}-free graphs. We prove that if G is {3K1, C5}-free, then the chromatic no. <= (3ω-1)/2 where ω is the size of a maximum clique in G and show with examples that the bound is tight.
Jean-Christophe Aval, Adrien Boussicault, Philippe Nadeau
In this work we introduce and study tree-like tableaux, which are certain fillings of Ferrers diagrams in simple bijection with permutation tableaux and alternative tableaux. We exhibit an elementary insertion procedure on our tableaux which gives a clear proof that tableaux of size n are counted by n!, and which moreover respects most of the well-known statistics studied originally on alternative and permutation tableaux. Our insertion procedure allows to define in particular two simple new bijections between tree-like tableaux and permutations: the first one is conceived specifically to respect the generalized pattern 2-31, while the second one respects the underlying tree of a tree-like tableau.
Free cumulants are nice and useful functionals of the shape of a Young diagram, in particular they give the asymptotics of normalized characters of symmetric groups $\mathfrak{S}(n)$ in the limit $n \to \infty$. We give an explicit combinatorial formula for normalized characters of the symmetric groups in terms of free cumulants. We also express characters in terms of Frobenius coordinates. Our formulas involve counting certain factorizations of a given permutation. The main tool are Stanley polynomials which give values of characters on multirectangular Young diagrams.
The aim of this work is to enumerate alternating sign matrices (ASM) that are quasi-invariant under a quarter-turn. The enumeration formula (conjectured by Duchon) involves, as a product of three terms, the number of unrestrited ASm's and the number of half-turn symmetric ASM's.