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,566
questions
3
votes
0
answers
69
views
$R$-recursion for the A249833 (similar to A235129)
Let $a(n)$ be A249833 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x) = 1 + \int A(x) + (A(x))^2\log A(x)\,dx
$$
The sequence begins with
$$
1, 1, 2, 7, ...
- 3,464
3
votes
0
answers
138
views
Smallest dominating set
Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
- 3,413
10
votes
1
answer
417
views
Where does the definition of ($\infty$-)groupoid cardinality come from?
The cardinality of a finite set $X$ is the number of its elements. Once you know that, you would define the groupoid cardinality of a $\infty$-groupoid $X$ as the quantity
$$\lvert X\rvert := \sum_{[x]...
- 599
11
votes
0
answers
481
views
Are there 100 points that are part of every half-density part of the plane?
Is there a configuration $P$ that consists of 100 points of the plane such that every $X\subset\mathbb R^2$ whose density is half contains an isometric copy of $P$?
I am deliberately being vague ...
- 18.4k
7
votes
1
answer
597
views
do all two manifolds admit a three-colorable triangulation?
A triangulation of a two-manifold $M$ is three-colorable if all vertices of the triangulation can be colored red, green, or blue without any two adjacent vertices having the same color.
My question: ...
- 229
1
vote
1
answer
197
views
Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$
Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...
- 12.7k
5
votes
0
answers
113
views
Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?
Let $C$ be a Hamiltonian cycle of a graph $G$.
Call an edge $e$ of $G$ a chord if $e\not\in C$.
Let each edge of $C$ be weighted $1$ and each chord be weighted $2$.
The weight of a path or cycle of ...
- 673
2
votes
0
answers
102
views
$R$-recursion for the A235129
Let $a(n)$ be A235129 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A'(x) = 1 + A(x)\exp(A(x))
$$
The sequence begins with
$$
1, 1, 3, 12, 64, 424, 3358, ...
- 3,464
0
votes
0
answers
175
views
Upper bound of number of different rows for a binary matrix
Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a measurable space, Fix $m,q \in \mathbb{N}^*$, (the $m$ $x_i$'s are i.i.d and follow distribution $\mathcal{D}$)
and $X = (x_1, \dots, x_m) \sim \mathcal{D}...
- 29
5
votes
2
answers
468
views
Minimum number of transpositions to make two multiset permutations equal
I think this problem should have a known solution, but I wasn't able to find any reference.
Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$.
...
- 690
4
votes
0
answers
212
views
Economic equilibrium and tropical geometry
There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...
- 113
3
votes
2
answers
590
views
Computing hypergeometric function at 1
I'm looking to compute
$${}_ 3F_ 2\biggl(\begin{matrix} -m-1/2,\ -m,\ k-m+1/2 \cr
1/2-m,\ k-m+3/2\end{matrix};1\biggr)$$
for $m,k > 0$ are positive integers and $0 < k < m$. I'm wondering if ...
- 299
6
votes
1
answer
273
views
Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4
Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?
- 1,130
2
votes
0
answers
56
views
Some version of graph removal lemma
I found the following statement in 'A proof of the stability of extremal graphs,
Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi:
Lemma: For any $\alpha>0$ and a graph $F$, ...
- 281
4
votes
0
answers
59
views
Existence of finite 3-dimensional hyperbolic balanced geometry
Together with @TarasBanakh we faced the problem described in the title. Let me start with definitions.
A linear space is a pair $(S,\mathcal L)$ consisting of a set $S$ and a family $\mathcal L$ of ...
- 471
0
votes
1
answer
94
views
How far is the slice rank of a tensor from its CP rank
Assume we work on any infinite field and 3-ordered tensor. Clearly for any tensor $T$, we have $\operatorname{srk}(T)\le \operatorname{rk}(T)$. Here, $\operatorname{srk}(T)$ (resp. $\operatorname{rk}(...
- 151
0
votes
0
answers
122
views
Naming convention for different type of triangulations
When studying random geometries and related mathematical/physical stuff conflicting naming convention pops up regarding the naming of the different ensemble types of triangulations (in general ...
- 75
0
votes
0
answers
145
views
Generate all non-isomorphic signed graphs
A signed graph is a graph in which each edge has a plus or minus sign. More specifically, a signed graph is a couple $S=(G, s)$, where $G=(V, E)$ is a graph with vertex set $V$ and edge set $E$, and $...
- 1,615
5
votes
2
answers
635
views
Minimum number of swaps to make multisets elements sums close
This problem was originally posted at math.stackexchange but there is no answer there, even after a (now expiring) bounty.
Choose $4$ multisets of size $n$ with elements $x \in \mathbb{R}$, $0 \le x \...
- 690
0
votes
0
answers
204
views
On characters of the symmetric group: Part 2
This question is related to my earlier MO quest.
For an integer partition $\lambda$, denote $\ell(\lambda)=$ length, $\vert\lambda\vert=$ size and $\lambda=$ conjugate of $\lambda$. Allow to write $\...
- 41.8k
6
votes
2
answers
327
views
A generalized matroid exchange property
Let $(E,I)$ be a matroid, and let $A,B \in I$ be disjoint independent sets in the matroid. Moreover, let $B_1,\ldots, B_k$ be a partition of $B$. I could not decide if the following is always true. ...
- 163
5
votes
1
answer
366
views
Closed-form for the number of partitions of $n$ avoiding the partition $(4,3,1)$
Let $a(n)$ be A309099 i.e. the number of partitions of $n$ avoiding the partition $(4,3,1)$.
We say a partition $\alpha$ contains $\mu$ provided that one can delete rows and columns from (the Ferrers ...
- 3,464
4
votes
0
answers
198
views
A probabilistic proof of van der Waerden theorem
Is there an elementary proof of van der Waerden's theorem on arithmetic progressions using probabilistic methods?
9
votes
1
answer
504
views
Reference request: number of antichains of a partially ordered set
Let $\mathbb{N}$ denote the set of all positive integers. For each $n \in \mathbb{N}$, define the set $$ P_n = \{ (a,b) \in \mathbb{N} \times \mathbb{N} : 1 \leq a \leq b \leq n \} $$ and consider the ...
- 563
1
vote
1
answer
67
views
Lower bound for the sum of the number of vertices of some subgraphs of a directed graph
Let $G$ be any simple weakly connected directed graph with vertices $V$, $\vert V \vert = n$. Let $V_1, \ldots, V_m$, $m = \binom{n}{k}$ be all subsets of $V$ of size $k$.
Let $C(V_i)$ be the union of ...
- 690
4
votes
0
answers
259
views
Place colored balls in boxes that makes it hard to pick few boxes that contains large proportion of each color
There are $n$ boxes filled with red, blue and yellow balls. A box can be empty and it can also contain more than one color. For example, a box can have three red balls, ten blue balls and one yellow ...
- 41
2
votes
0
answers
62
views
Elementary recursion for the A258173
Let $a(n)$ be A258173 i.e. sum over all Dyck paths of semilength $n$ of products over all peaks $p$ of $y_p$, where $y_p$ is the $y$-coordinate of peak $p$.
A Dyck path of semilength $n$ is a $(x,y)$-...
- 3,464
2
votes
2
answers
339
views
Why can we not find exact values for sizes of cap sets for $d>6$?
I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. ...
- 31
2
votes
0
answers
328
views
On characters of the symmetric group: Part 1
Given an integer partition $\lambda$, denote $\ell(\lambda)=$ length, $\vert\lambda\vert=$ size and $\lambda=$ conjugate of $\lambda$. Allow to write $\lambda\vdash n$ either as $(\lambda_1,\dots,\...
- 41.8k
2
votes
1
answer
125
views
Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$
Suppose a bipartite graph with two parts $A, B$, for every $b \in B$ we know $\deg(b) \ge 1$.
Prove there exists an adjacent $a \in A, b \in B$ such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$.
- 149
3
votes
1
answer
660
views
binomial coefficients are integers because numerator and denominator form pairs?
I've heard of a claim that when calculating the binomial formula with integer input:
$\mathrm{Bin}(n,k):=\prod^k_{i=1}\frac{n+1-i}{i}\in \mathbb{N}\ (\forall n,k\in\mathbb N)$
each denominator divides ...
- 187
1
vote
2
answers
83
views
Hardness of a Hybrid problem combining knapsack and scheduling
I am trying to prove whether the following problem is NP-hard or not:
Items with a certain length arrive in a fixed sequence and must be assigned to one of two containers which are constrained in ...
- 21
3
votes
3
answers
408
views
Maximal set of $n$-bit strings that does not span $\mathbb{R}^n$
I am trying to find out the maximum-sized subset $S\subseteq \{0,1\}^n$ of $n$-bit strings that does not span $\mathbb{R}^n$.
It is easy to show that $S$ has size at least $2^{n-1}$ when $S$ exactly ...
- 45
4
votes
1
answer
395
views
Inequality of inclusion-exclusion term
This question was initially posted on math.stackexchange.com but did not receive any answers for half a week.
While analyzing the properties of an algorithm I am working on (I'm a computer scientist), ...
- 45
1
vote
1
answer
85
views
Existence of a strongly regular vertex ordering on cubic graphs
Definition: Let $G=(V,E)$ be a cubic (i.e. $3$-regular) graph, and $<$ a total order on $V$. For $v\in V$ let $v^\downarrow$ denote the set of nodes $w\in V$ such that $w<v$, and let $\alpha(v) =...
- 191
3
votes
0
answers
163
views
Factorization of symmetric polynomials
Let $\Lambda_n$ be the algebra of all symmetric polynomials in $n$ variables, which we also consider as an infinite-dimensional vector $\mathbb{Q}$-space, whose basis is the Schur polynomials.
The ...
- 546
7
votes
1
answer
374
views
Large sets of nearly orthogonal integer vectors
This question is motivated by the Question 5 from the 2017 Asia Pacific Mathematical Olympiad. To paraphrase, the question asks what is the largest cardinality of a set $S \subset \mathbb{Z}^n$ such ...
- 25.5k
2
votes
1
answer
111
views
A problem about the existence of increasing coloring groups
Got stuck on this one for months.
Given a sequence of non decreasing positive integers $a_1, .., a_n$, let there be $a_i$ balls labeled the number i, for each $1 \leq i \leq n$. Suppose there is a k ...
- 4,354
3
votes
1
answer
144
views
Creating mazes with colored tiles
Consider the following approach to constructing a maze: Create a rectangular grid of identical square tiles, each colored by one of N colors on a color wheel. For any pair of adjacent tiles, there is ...
- 75
3
votes
1
answer
344
views
Electricity division and bin packing
In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$.
The problem is that $s &...
- 3,585
4
votes
1
answer
286
views
Why should we expect this odd behavior of negative binomial distributions?
In independent Bernoulli trials with probability $p$ of success on each trial, let $X$ be the number of failures before the $n$th success. Then
$$
\Pr(X=x) = \binom{-n}{\phantom{+}x} (-q)^x p^n \text{ ...
- 11.9k
15
votes
1
answer
1k
views
Is this a typo in Macdonald's paper "The Poincaré Series of a Coxeter Group"?
I have a question about the proof of lemma 2.14 in Macdonald's paper The Poincaré Series of a Coxeter Group [1], where he used induction on $l(w)$ to prove that if $|E|=|R(w)|$, then $E=R(w)$. The ...
- 545
2
votes
0
answers
107
views
Inequality for 2-associated Stirling numbers of the second kind
Let $S_2(n,k)$ denote the 2-associated Stirling number of the second kind for $n$ objects and $k$ blocks, with $n$ being at least two. That is, we partition $n$ labeled objects into $k$ unlabeled ...
7
votes
0
answers
225
views
Chip firing on hypergraphs
A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...
- 19.3k
1
vote
1
answer
45
views
The edit distance from a large complete $p$-partite graph to the Turán graph
Let $K=K(V_1,V_2,\cdots,V_p)$ be a $p$-partite complete graph on $n$ vertices and $T_p(n)$ be the Turán graph.
Show that: if $e(K)\geq e(T_r(n))-t$ then $$\sum_{k=1}^p\left(|V_k|-\frac{n}{p}\right)^2\...
- 13
7
votes
1
answer
237
views
Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?
I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...
- 516
0
votes
0
answers
49
views
Kernel perfection in some powers of cycles
Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
- 2,027
2
votes
0
answers
176
views
Truncating the high degree part of a positive boolean function doesn't change the distance to positive functions too much
Given $\displaystyle n\in\mathbb{Z}^{+}$, suppose $\displaystyle f:\{-1,1\}^n\to[0,1], $ then $f$ has a Fourier expansion:
$\displaystyle f(x)=\sum_{S\subseteq[n]} \tilde{f}(S)x^S,$ where $\...
- 49
7
votes
2
answers
325
views
Matrices over $\mathbb{F}_p$ that have nonzero determinant under any element permutation
$\DeclareMathOperator\GL{GL}$A few months ago, the following discussion took place on AoPS, concerning matrices that have nonzero determinant under any permutation of their entries: https://...
- 437
9
votes
0
answers
165
views
Are there fast rank and unrank algorithms for integer vectors under the action of a permutation group?
We are distributing $m$ indistinguishable balls in $k$ numbered boxes $S=\{1,2,\ldots,k\}$. A distribution is a tuple of nonnegative integers $a=(a_1,\ldots,a_k)$ whose sum is $m$. We also have a ...
- 3,964