# 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.

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

9,553
questions

4
votes

0
answers

134
views

We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...

1
vote

0
answers

143
views

is there any upper bound for the number of self-conjugate partitions, or equivalently the number of partitions with distinct odd parts?
P.S.: I didn't get why my question has been moved to Math Stack ...

0
votes

1
answer

84
views

Let $f : 2^n \to \mathbb{R}$ be a nondecreasing submodular function, where $2^n$ is the powers of $\{1, \dots, n\}$. Here nondecreasing means that $f(S) \le f(T)$ for all $S \subseteq T$. And ...

1
vote

1
answer

143
views

For a positive integer $n$, let an $n$-shuffle be a multiset
$S=[(S_i,d_i)|i=1,\ldots,n]$ of pairs $(S_i,d_i)$, where each
$S_i$ is a multiset of $n$ numbers containing the number $d_i$.
A realization ...

0
votes

1
answer

97
views

I'm aware of the replies to this question, but I was not able to apply the suggested methods in my case.
I would like to compute the asymptotics of the resulting sum $S$ when computing the number of ...

5
votes

1
answer

139
views

Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...

4
votes

1
answer

173
views

Let $V$ be an $n$-dimensional vector space over a finite field $F$ (of order $q$). Denote by $\mathrm{AGL}(V)$ the group of invertible affine transformations of $V$; so $\mathrm{AGL}(V)$ consists of ...

0
votes

0
answers

86
views

It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the ...

1
vote

2
answers

188
views

This might be related to counting hamiltonian cycles.
@Peter Taylor gave negative result about the one dimensional case, but we believe his attack is
not directly applicable to this question.
Given ...

4
votes

0
answers

191
views

I have a technical question on the commutativity of diagrams (2.11) and (2.12) in the paper "Birational geometry of cluster algebras" by Gross-Hacking-Keel:
For the leftmost square in (2.11),...

11
votes

1
answer

284
views

Problem. Several circles are drawn on the plane and all points of their
intersection or touching are marked. For which $n$ it is possible that each circle contains exactly $n$ marked points and each ...

5
votes

0
answers

91
views

To start with, consider some abstract $3$-dimensional simplicial complex $\Delta$ representing a manifold without boundary, for simplicity. Then, there is this well-known construction of the "(...

1
vote

0
answers

121
views

Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its
adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[...

4
votes

0
answers

141
views

For $a,b,c \in \mathbb{N}$ let $[a] := \{1,...,a\}$ and suppose a map $h: [a] \rightarrow [c]$ is given. How many choices $(f,g)$ for maps $f: [a] \rightarrow [b]$ and $g: [b] \rightarrow [c]$ are ...

0
votes

0
answers

30
views

Being strongly regular graphs, different Paulus graphs cannot be distinguished using a 3-WL test. Is it known whether they can be distinguished using a 4-WL test?

2
votes

0
answers

49
views

Problem 1. Let several non-overlapping spheres in $\mathbb{R^3}$ are given. For which $n$ it is possible that each sphere is tangent to exactly $n$ other spheres?
Consider the smallest sphere. Since ...

5
votes

1
answer

202
views

Can there be applications of graph theory, combinatorics etc. in PDEs mainly hydrodynamics?
Tried my luck with Google's search engine, didn't show much info.
I guess you can try to use these features ...

2
votes

1
answer

226
views

Let $W$ be the Weyl group of a semisimple algebraic group $G$. $I$ be the simple roots. $J\subset I$ generate a parabolic subgroup of $W$ denote by $W_J$. $w^J$
is the shortest representative of $w$ ...

7
votes

1
answer

136
views

Let ${\left\langle\matrix {n \cr k}\right\rangle}_r$ denote the $r-$Hoggatt binomials defined by
$${{\left\langle\matrix {n \cr k}\right\rangle}_r=\frac{\langle n \rangle_r!}{\langle k \rangle_r! \...

5
votes

1
answer

245
views

Let G be a graph with $n \ge 3$ nodes and with average degree $3\le k\le n$. What are the largest and smallest girth G can have?

1
vote

1
answer

163
views

The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as
$$
\operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)}
$$
The sum here extends over all ...

2
votes

1
answer

97
views

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically ...

2
votes

0
answers

78
views

In a paper on a proximity test for Reed-Solomon codes the authors state an "extremely optimistical" conjecture on the list decodability of Reed-Solomon codes (over prime fields $\mathbb F_q$)...

3
votes

0
answers

66
views

Inspired by this (now closed) question, I was wondering the following: What is the smallest possible cardinality of a set $P$ of points in the plane such that
no three points in $P$ are collinear,
...

6
votes

0
answers

164
views

Cross-posted from MSE. The question has remained unanswered for six years but I still like it!
One can show using zeta functions that the number of (monic)square-free polynomials of degree $n$ over a ...

1
vote

0
answers

78
views

Suppose $(a_k)_{k\geq0}$ is a sequence of real numbers. Consider the operator $\mathcal{L}a_k=a_k^2-a_{k-1}a_{k+1}$.
We say $(a_k)_k$ is log-concave (resp. log-convex) provided $\mathcal{L}a_k\geq0$ (...

0
votes

0
answers

40
views

Wegner proves that let $K$ be a finite family of convex sets in $\mathbb{R}^d$, then the Nerve of $K$, which is a simplicial complex and is defined as
$$D=N(K):=\{ \{S_1,\dots, S_k\}: S_i\in K \text{ ...

1
vote

0
answers

128
views

I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07.
Q. Does ...

4
votes

0
answers

138
views

The following arose from a question in model theory (specifically in the model theory of modules).
Fix an arity $k$. Let $[\mathbb{Q}]^k$ denote the set of all subsets of $\mathbb{Q}$ of cardinality $...

5
votes

0
answers

159
views

The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...

1
vote

0
answers

51
views

We have seen in class a polynomials based construction that builds in $O(n^k)$ time, $n$ random variables, $k$-wise independent, over a field with $n$ elements. More specifically, you generate all the ...

2
votes

0
answers

99
views

This question is related to my last question and is originally motivated by recent advances in quantum physics.
I am looking for combinatorial characterizations of some algebraically defined families ...

4
votes

0
answers

169
views

This is a follow-up question of my SO post I'll briefly mention it here.
So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...

12
votes

2
answers

459
views

A corner of an integer partition is a location at where a box can be added to its Ferrers diagram to give a new partition.
E.g. the partition $\{1,1,1\}$ has two corners, and $\{1,2\}$ has three ...

3
votes

1
answer

131
views

Let $C$ be a simplicial complex on a finite set $V$: that means $C$ is a collection of subsets of $V$ such that if $\sigma\in C$ and $\tau\subseteq \sigma$, then $\tau\in C$.
The Alexander dual $D(C)$ ...

12
votes

0
answers

271
views

The $q$-binomial theorem states that
$$
\prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k.
$$
This identity is a $q$-analogue of the binomial theorem
$$
(1+t)^n = \sum_{k=0}^n \...

7
votes

1
answer

126
views

Let $G$ be a countable amenable group with a (left) Følner sequence $(F_n)$. Let $\Gamma$ be a subset of $G$ that has density $1$ with respect to $(F_n)$, in the sense that
$$
\lim_{n \to \infty} \...

0
votes

0
answers

416
views

Consider next determinant that we want to expand around $h=1$
\begin{eqnarray}
Z_q \ = \ h^{N N_f} \ \ \left ( \prod_{n=1}^{N} \ \sum_{l_n=0}^{N_f -q} \ h^{2l_n+q} \ \binom{N_f}{l_n} \right ) \ \...

2
votes

0
answers

76
views

I started with the the following four-variable function, $f(s,x,y,u)$, expressed as a summation involving the product of Hermite polynomials.
$f(s,x,y,u)=\sum_{n=0}^{\infty}\frac{H_{n}(x)H_{n}(y)}{(n-...

3
votes

0
answers

93
views

This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...

11
votes

1
answer

304
views

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...

1
vote

1
answer

193
views

Let $[n]_q!=\prod_{j=1}^n\frac{1-q^j}{1-q}$ with $[0]_q!:=1$ and the Gaussian polynomials $\binom{n}k_q=\frac{[n]_q!}{[k]_q!\,\cdot\,[n-k]_q!}$. Adopt the convention that $\binom{n}k_q=0$ whenever $k&...

0
votes

0
answers

117
views

Consider the following version of Szemeredi's regularity lemma found in the Fox and Lovasz paper, "A tight lower bound for Szemeredi's regularity lemma", arXiv: 1403.1768v1 [math.CO] 7 Mar ...

2
votes

1
answer

82
views

Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...

7
votes

1
answer

183
views

I am curious about the following result concerning the Robinson-Schensted insertion procedure. I can formulate a proof via the Schützenberger evacuation operator, but I have struggled to find such an ...

2
votes

0
answers

90
views

It is a well-known result that a bipartite graph can be decomposed into edge-disjoint perfect matchings if and only if it is regular. Now here comes the question. Given a bipartite regular graph, is ...

5
votes

1
answer

306
views

Let $p \equiv 1 \pmod 4$ be a prime and $E_n$ denote the $n$-th Euler number. While investigating $E_{p-1} \pmod{p^2}$ I have encountered this summation (modulo $p$)
\begin{align*}
\sum_{k =1}^{\frac{...

2
votes

0
answers

72
views

Let ${\mathbb A}^n_q$ and ${\mathbb P}^n_q$ be affine and projective spaces of dimension $n$ over a field of order $q$.
Say that a subset of either ${\mathbb A}^n_q$ or ${\mathbb P}^n_q$ is generic if ...

2
votes

1
answer

148
views

Given positive integer $n$, we are looking for a set
of $n$ positive integers $a_i$.
The following linear integer program must have only
the trivial integer solution of all ones.
$0 \le x_i \le \frac{...

1
vote

0
answers

44
views

I have a set of edge weighted trees, each tree rooted at some vertex. Consider these trees are hung from the roots and vertices are arranged in some levels. I wish to design an algorithm (...