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.
10,515
questions
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 ...