Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

Filter by
Sorted by
Tagged with
5 votes
0 answers
129 views

Exponential bound for very weak sunflowers?

Call $r$ sets diverse if for every $0\le i\le r$ there is an element contained in exactly $i$ of them. A family of sets is r-diverse if any $r$ of its members are diverse. Is there for every $r\ge 3$ ...
34 votes
1 answer
3k views

Updates to Stanley's 1999 survey of positivity problems in algebraic combinatorics?

[I am a co-moderator of the recently started Open Problems in Algebraic Combinatorics blog and as a result starting doing some searching for existing surveys of open problems in algebraic ...
16 votes
1 answer
585 views

Spanning trees: the last darn $1/4$

Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991), if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning tree with $\geq n/4+2$ leaves, where $n$ is the number of ...
10 votes
0 answers
490 views

Kruskal-Katona type question for union-closed families of sets

Question: Let $n,k$ be two positive integers with $n \geq k$. Let $\mathcal{F}$ be a family of $C(n,k)$ sets, each of size $k$, and let $\langle\mathcal{F}\rangle$ denote the union-closed family ...
13 votes
1 answer
479 views

What's the dimension of the Lie algebra generated by transpositions on $n$ objects?

Define a Lie bracket on the group algebra of the permutation group $S_n$ in the following way: $$[\sigma, \tau] = \sigma\circ\tau - \tau\circ\sigma,$$ where $\sigma, \tau \in S_n$, and the ...
3 votes
2 answers
264 views

Planar graph of high valence

A classic result in graph theory tells us that any planar graph must have at least one vertex with valence no bigger than 5. On the other hand, there exist examples of planar graphs that are 5-regular ...
2 votes
1 answer
55 views

Extending spanning sets on contractions of matroids

Suppose you have a matroid, and $T$ is a subset of a spanning set $S$. Now consider the contraction of the matroid to the set $T$ and suppose $X$ is a spanning subset of $T$ with respect to that ...
4 votes
3 answers
319 views

Minimal data required to determine a convex polytope

Let $P\subset \Bbb R^d$ be a convex polytope. Suppose that I know its combinatorial type (aka. the face-lattice), the length $\ell_i$ of each edge, and the distance $r_i$ of each vertex from the ...
12 votes
1 answer
403 views

Quantitatively characterizing the failure of the converse of Dirac's theorem

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately. I am currently in a combinatorics and graph theory class and recently we have ...
-2 votes
1 answer
148 views

Combinatoric Problem [closed]

Let $2\leq k\leq r\leq n$ are positive integers and $r=kt$. I construct sets such that $\cup_{i=1}^n A_i=\{1,2,3,\dots,n\}=X$, this union is disjoint and if $x\in A_i$ and $y\in A_j$ for all $i\leq j$...
10 votes
2 answers
259 views

Maximal in-degree in directed voting graph

Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about ...
4 votes
3 answers
3k views

Number of binary arrays of length n with k consecutive 1's [closed]

What is the number of binary arrays of length $n$ with at least $k$ consecutive $1$'s? For example, for $n=4$ and $k=2$ we have $0011, 0110, 1100, 0111, 1110, 1111$ so the the number is $6$.
3 votes
2 answers
478 views

Question about a new pseudo-random number generator

While investigating non-periodic RNG's (random number generators) for irrational numbers, I came up with a version that actually produces pseudo-random words consisting of $N$ bits, where $N$ is ...
0 votes
1 answer
201 views

What is the most likely sequence? [closed]

I have a jar containing n numbered marbles, where 1...x marbles are red and marbles x+1...n ...
4 votes
1 answer
321 views

Minimally separating graphs

We say that a simple, undirected graph $G=(V,E)$ is separating if for all $x\neq y\in V$ there are $e_x,e_y\in E$ such that $x\in e_x$ and $y\in e_y$, and $e_x\cap e_y = \varnothing$. We say $G$ is ...
5 votes
0 answers
178 views

Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph

This question is very important for my research, which is why I ask it here. I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
11 votes
1 answer
2k views

Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants

Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
3 votes
1 answer
156 views

Transversals and almost transversals of a finite family of sets

The following is a purely combinatorial problem that I came across in the course of research in non-classical logic. It sounds to me like the kind of question that someone may very well have ...
1 vote
0 answers
99 views

What can be said about a class of incidence structures closed under duals and complements?

Note that I do not work in combinatorics, and so this question might be a bit naive. The question is inspired by some structures that arise in my research within representation theory. Recall that an ...
0 votes
0 answers
252 views

Expected position in random permutation

Let $S$ be a set of $n$ numbers, and $\pi(x):S\rightarrow \left\{ 1,\ldots,n\right\}$ define a permutation. The position $p(x, \pi)$ of an element $x \in S$ in a given permutation $\pi$ is the sum of ...
1 vote
0 answers
88 views

Diophantine system

Consider a sequence of integers $n_i,\ i=1,\ldots, N$ and $\nu_k=\sum_{i=k}^N n_i$. Consider a sequence $\Delta_i,\ i=0,\ldots, N+1$ with $\Delta_i\in \{0,1\}$ and $\Delta_0=\Delta_{N+1}=0$. For $i=0,\...
7 votes
2 answers
229 views

Fixed point for a map from $\{0,1\}^N$ to itself

Let $N\geq2.$ Let $F$ be a function from $\left\{ 0,1\right\} ^{N}$ to itself dreceasing for the product order defined by $$ (x_1,x_2,\ldots,x_N)\leq (y_1,\ldots,y_N)\ \text{ if and only if for all }...
4 votes
2 answers
242 views

Relationship between minimum vertex cover and matching width

Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in E(H)\}$). Question: Is $\...
6 votes
0 answers
152 views

When are Hamming codes cyclic?

I've asked this question on math.stackexchange before, but it has not been solved. The following statement appears to be true: The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is ...
4 votes
1 answer
492 views

I want to know the name of or any references for a matrix in the book "The representation theory of the symmetric groups" by Gordon James

$\DeclareMathOperator{\Ind}{\operatorname{Ind}}$I'm reading "The representation theory of the symmetric groups" written by Gordon James. I found the matrix $B$ in the chapter 6 ("The ...
0 votes
0 answers
235 views

How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?

It is well known that for any graph G following holds $\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...
7 votes
0 answers
253 views

Is there a practically useful or concrete representation theory/Fourier analysis on finite groupoids?

Fourier analysis on finite groups is well known to be useful for probability theory and combinatorics — consider for example the Fourier analysis on $(\mathbb Z/2\mathbb Z)^n$ which can be used to get ...
5 votes
0 answers
137 views

How does a map from permutahedra to associahedra factor through multiplihedra?

Let $P_i$ denote permutahedra, $K_i$ associahedra and $J_i$ multiplihedra. In their famous paper on operadic diagonals, Saneblidze and Umble use a projection $p_i: P_i \to K_{i+1}$ which factors as $...
12 votes
1 answer
356 views

An averaging game on finite multisets of integers

The following procedure is a variant of one suggested by Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of integers. A move consists of choosing two elements $a\neq b$ of $M$ of the same ...
9 votes
0 answers
443 views

Measuring the randomness of texts

The question concerns statistic properties of random words in a finite alphabet $A$. By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$. ...
4 votes
1 answer
478 views

Higher-order derivatives of $(e^x + e^{-x})^{-1}$

I am currently trying to build the derivatives of $$f(x) = \frac{1}{e^x+e^{-x}}.$$ It is fairly straightforward to obtain $$ \frac{d^n f}{dx^n} = \frac{P_n(e^x)}{e^{(n-1)\cdot x} (e^x+e^{-x})^{n+1}}, $...
6 votes
1 answer
209 views

Why does the number of permutations of $n-1$ adjacent transpositions where the outputs are different equal $2^{n-2}$?

Maybe I'm wrong, but I just noticed that the different permutations of $(1,2)(2,3)(3,4),\dots,(n-1,n)$ seem to be $2^{n-2}$ and I don't know why this is true. Can someone help if I'm right about this ...
9 votes
3 answers
805 views

A positive formula for the dimensions of homogeneous components of free Lie algebras

The homogeneous component of degree $k$ in the free Lie algebra $\mathfrak{Lie}(x_1,\dots,x_n)$ in $n$ letters is of dimension $$g_n(k)=\frac{1}{k}\sum_{d|k}\mu(d)n^{k/d}.$$ This is also the number of ...
2 votes
1 answer
420 views

Number of permutations of a set given arbitrary precedence constraints

I am trying to find a mathematical relationship between the size of a tree (or - in other terms - the cardinality of set or permutations) for a set of elements which are subject to precedence ...
2 votes
0 answers
64 views

Are stable matchings (noise-)stable?

Suppose a group of computer scientists have entrusted their dating lives to a computer. Specifically, there are $n$ men and $n$ women, all of whom are cis-het. Being educated people, they of course ...
2 votes
0 answers
83 views

Motivation for proof of local lemma/construction version

I am interested in finding intuition to the bounds and proof of the asymmetric local lemma. I think the $k$-SAT is fairly intuitive, but I would like to understand the general version. One good ...
12 votes
1 answer
651 views

Is there Matrix-Tree theorem for counting the bases of a connected matroid?

The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...
2 votes
0 answers
108 views

List total chromatic number of complete graphs

Since for an odd integer $n$, a complete graph on $n$ vertices is list-edge-$n$ choosable, and the total chromatic number is $n$, it is easy to see that the list total chromatic number is bounded ...
7 votes
1 answer
433 views

Combinatorial meaning of Kazhdan-Lusztig-Stanley polynomial

This question is motivated by Why do combinatorial abstractions of geometric objects behave so well? The algebraic geometry of Kazhdan-Lusztig-Stanley polynomials Kazhdan-Lusztig-Stanley polynomials ...
8 votes
2 answers
264 views

A link between hooks, contents and parts of a partition

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$. ...
4 votes
0 answers
131 views

A combinatorial proof of an identity of partitions (Macdonald I.5)

This is a statement from Symmetric Functions and Hall Polynomials by Macdonald: $\sum_{x\in \lambda} (h(x)^2-c(x)^2)=|\lambda|^2$ where $\lambda$ denotes a partition or a Young diagram, and for each ...
2 votes
0 answers
100 views

Cartan matrices of combinatorial algebras

Call a quiver algebra $A=kQ/I$ with connected acyclic $Q$ combinatorial when the following two conditions are satisfied: For any two points $i,j$ in the quiver of $A$ there is at most one path from $...
8 votes
1 answer
252 views

Perfect sphere packings (as opposed to perfect ball packings)

I came across this question when I was discussing the rather wonderful Devil's Chessboard Problem with my colleague, Francis Hunt. We realised that there is a nice connection to a packing question in $...
7 votes
3 answers
3k views

Can American Math. Monthly be used to publish hard research?

My question pertains to the journal "American Mathematical monthly" published by the MAA. I wish to ask whether a paper as a part of a PhD thesis (subject: Combinatorics ) can be submitted ...
3 votes
0 answers
95 views

Cohomology of higher codimensional arrangements

Hyperplane arrangements are classical objects of study and there is a large literature on this subject, e.g. dealing with computing the cohomology of the complement. I am looking for similar results ...
2 votes
1 answer
185 views

Question involving an incidence geometry theorem from Larry Guth's book Polynomial Methods in Combinatorics [2016]

At the very beginning of Chapter 11 of Larry Guth's book, we are given the following theorem which is supposed to be proved within the chapter: Theorem 11.1. There is a constant K so that the ...
7 votes
0 answers
307 views

Estimating the alternating sum $\sum_{j \ge 1} (-1)^j e^{-j^2} j^k$

I have been trying to get a lower bound on the following alternating sum but without much success: $$ \sum_{j=1}^T (-1)^j e^{-j^2} j^k . $$ For small values of $k$, this is easy because the first term ...
12 votes
1 answer
598 views

Order polynomial of shifted double staircase

This question is related to my earlier question looking for posets with product formulas for their order polynomials. Recall that the order polynomial $\Omega_P(m)$ of a finite poset $P$ is defined ...
10 votes
1 answer
481 views

Number of bounded Dyck paths with "negative length"

Let $c(n,k)$ denote the number of Dyck paths of semilength $n$ which are contained in the strip $0 \leq y \leq 2k + 1.$ They satisfy the recursion $\sum_{j=0}^{k+1}(-1)^j \binom{2k+2-j}{j}c(n-j,k)=0$ ...
1 vote
1 answer
99 views

$\ell^1$-bound on graph laplacian with weight

Consider the $\mathbb Z^2$ lattice, we then define for $u=(u_{ij})_{i,j \in \mathbb Z}$ the discrete Laplacian $$(\Delta u)_{i,j}=u_{i+1,j}+u_{i-1,j}+ u_{i,j+1}+u_{i,j-1}$$ and the weight which pushes ...

1
65 66
67
68 69
211