All Questions
Tagged with combinatorics or co.combinatorics
11,021 questions
0
votes
0
answers
176
views
How to find a configuration of lines
In $\mathbb{R}^3$, can anyone help find a configuration of 5 lines such that the minimum of the smallest semi-axis lengths of the ellipsoid $ \mathbf{x}^T \mathbf{A} \mathbf{x} = 1 $, where $\mathbf{A}...
- 61
6
votes
0
answers
171
views
An inequality involving integer partitions
For integers $n\ge k\ge0$, let $p(n,k)$ denote the number of ways to write $n$ as a sum of $k$ positive integers (repetition allowed). For example, $p(6,3)=3$ since
$$6=1+1+4=1+2+3=2+2+2.$$
QUESTION. ...
- 15.6k
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
2
votes
0
answers
100
views
$\liminf$ and $\limsup$ for partial sums of the Ehrenfeucht-Mycielski sequence
Let $f:\mathbb{N} \to \{0,1\}$ be the Ehrenfeucht-Mycielski sequence. The first few digits of the sequence are:
$$010011010111000100001111\ldots$$
For any $k\in\mathbb{N}$ let $s(k) = \sum_{i=0}^k f(i)...
- 48.8k
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
41
votes
3
answers
3k
views
How many natural operations on subsets are there?
How many operations are there on subsets of a set that are compatible with images of maps? Of course, we can take unions, but are these all? Spoiler: No.
To formalize this, let $P : \mathbf{Set} \to \...
- 63.1k
2
votes
0
answers
51
views
Recursion for A129179 similar to recursion for Pascal's triangle
Let $T(n,k)$ be A129179 (i.e., triangle read by rows: $T(n, k)$ is the number of Schroeder paths of semilength $n$ such that the area between the $x$-axis and the path is $k$ ($n \geqslant 0, 0 \...
- 4,928
4
votes
1
answer
371
views
Looking for a counterexample to a strengthening of the union-closed sets conjecture
[Now crossposted at math.stackexchange]
Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 8$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ ...
- 990
0
votes
0
answers
169
views
On a property of prime numbers
Let $p_i$ be the $i^{\rm th}$ prime number (i.e. $p_1=2,\ p_2=3,\ p_3=5,\cdots$)
What is the function of number of combinations of $c_1,\cdots,c_n$ in terms of $n$ such that,
$$\sum_{i=1}^{n}c_ip_i\ =\...
1
vote
1
answer
159
views
Acyclic partition of edges in tournaments
The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the ...
- 13
2
votes
0
answers
121
views
Sequences of 1s in binary expression of powers of 3
Some properties of the binary expressions of $3^n$ are known, e.g. here was proven that the only periodic expression happens at $n=1$, or here it is shown that the number of $1$s in the expression ...
- 205
3
votes
2
answers
303
views
Asymptotics of A000613
The general linear group $GL_n(\mathbb{F}_2)$ acts on the powerset $2^{{\mathbb{F}_2}^n \setminus \{0\}}$ by multiplication: $A \cdot S := \{Ax \in {\mathbb{F}_2}^n : \, x \in S\}$, for an invertible ...
- 331
4
votes
1
answer
154
views
Minimal dominating sets in thin hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $H$ is thin if for every $v\in V$ the set $E_v=\{e\in E:v\in e\}$ is finite.
A subset $D\subseteq V$ is dominating if
$\bigcup \{e\in E:e\cap D \neq \...
- 48.8k
0
votes
1
answer
118
views
Configurations of signs in a matrix under certain conditions
I have a combinatorial question which is out of my research area.
Given a $2^k\times 2^k$ matrix $A=[a_{i,j}]$ with entries in $\lbrace0,\pm1\rbrace$, where $k$ is a positive integer. Is it possible ...
- 619
8
votes
1
answer
424
views
If $P$ and $Q$ are finite, non-empty posets and the poset of order-preserving maps $P^P$ is isomorphic to $Q^Q$, must $P$ be isomorphic to $Q$?
Let $(P,\le_P)$ and $(Q,\le_Q)$ be posets. A function $f:Q\to P$ is order-preserving if whenever $q,q'\in Q$ and $q\le_Q q'$, we have $f(q)\le_P f(q')$. If there is a bijective order-preserving map ...
- 1,644
3
votes
0
answers
213
views
A family of polynomials related to integer partitions
For a positive integer $n$, let $p(n)$ be the number of partitions of $n$.
For $1\le k\le n$, let $p(n,k)$ denote the number of partitions of $n$ having exactly $k$ terms; in other words, $p(n,k)$ is ...
- 15.6k
13
votes
1
answer
536
views
Some questions related to meanders
Let $A_n$ denote the set of noncrossing fixed point free involutions
in the symmetric group $S_{2n}$. "Noncrossing" means that if
$a<b<c<d$, then not both $(a,c)$ and $(b,d)$ can be ...
- 50.8k
9
votes
1
answer
1k
views
5
votes
0
answers
183
views
On the polynomials $\sum_{k=0}^n\binom{n+k}k^m q^k$
A sequence of polynomials
$$P_0(q),\ P_1(q),\ P_2(q),\ \ldots$$
with real coefficients is called $q$-log-convex if for each $n=1,2,3,\ldots$ every coefficient of the polynomial $P_{n+1}(q)P_{n-1}(q)-...
- 15.6k
0
votes
0
answers
51
views
Inverse problem of "graph limits to graphon"
A graphon is a measurable symmetric function $W: [0,1]\to [0,1].$ By Lovasz's book "Large networks and graph limits" we know for any graph sequence $G_1, G_2, \dots G_i,\dots$ there exists a ...
- 349
0
votes
0
answers
67
views
Does Sidorenko's conjecture hold when the host graph's edge density not too small?
Does the following hold?
For every bipartite graph $H$ and every graph $G$ with $e(G)\geq 0.1(v(G))^2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as Sidorenko's conjecture ...
- 349
0
votes
0
answers
121
views
Closed form of coefficients of a finite field polynomial
I want to find a valid polynomial for a finite field $\mathbb{Z}_p[x]_{f(x)}$ with $d=deg(f(x))$. For this definition to hold, it can be deduced that $p$ must be prime and the polynomial $f(x)$ ...
- 47
3
votes
1
answer
153
views
Number of points covered by $2n$ hyperplanes in $\mathbf{F}_p^n$
For a prime $p$, fix two bases $U=\{v_1,\dots,v_n\}$ and $W=\{w_1,\dots,w_n\}$ of the vector space $V=\mathbf{F}_p^n$. We may assume $U$ is the standard basis without loss of generality.
For $s_1,\...
- 281
11
votes
1
answer
340
views
Number of odd-dimensional irreducible representations of $S_n$
In this paper the structure of odd-dimensional irreducible representations of the symmetric group is described, but what is the asymptotic behaviour of the number of such representations? (Or, if it ...
- 109k
2
votes
1
answer
215
views
Number of binary matroids of rank $r$ on a ground set with $n$ elements
How many simple binary matroids are there, up to isomorphism, of rank $r$ on an $n$-element ground set, where $r \le n < 2^r$? Write this number as $a_r(n)$. Is there somewhere where I can get this ...
- 331
3
votes
0
answers
65
views
A combinatorial Dyson-Schwinger equation, tree diagrams, and compositional inversion of a Laurent series
In "Tree hook length formulae, Feynman rules and B-series", Bradley Jones and Karen Yeats state on pg. 9:
Combinatorial Dyson-Schwinger equations are functional equations with solutions in
$...
- 10.5k
3
votes
0
answers
359
views
Combinatorial problem in $G(54,\, 5)$
I have asked (probably) easier versions of this question in the past, see MO379272 and MO380292. At the moment, it is not clear to me how the beautiful answers to those questions can be helpful here.
...
- 66.3k
1
vote
0
answers
72
views
How to understand "sparse graph limits"
For an $n$-vertex graph $G$, we say it is a sparse graph if $e(G)=o(n^2)$. Otherwise if $e(G)=\theta (n^2)$, we say it is a dense graph.
For a sequence of dense graphs $G_1,G_2,\dots,$ we know that it ...
- 349
11
votes
2
answers
425
views
Maximization of a cubic form over the $14$-dimensional sphere
For any integers $i$ and $j$ such as $1\le i<j\le6$, let $x_{ij}$ be a nonnegative real number.
Is it true that, given the condition
$$\sum_{1\le i<j\le6}x_{ij}^2=1,$$
the sum
$$\sum_{1\le i<...
- 128k
4
votes
1
answer
189
views
Equation in the conjugacy class of a free group
I will pose the question in the form in which it originally appeared to me:
Let $a,b,c,d$ be different letters in a finite alphabet $\mathcal{Z}$. Let $Q$ and $R$ be finite words with letters from $\...
- 111
2
votes
0
answers
61
views
Algorithm for main diagonal of integer coefficients associated with Schroeder numbers
Let $T_q(n, k)$ be an integer table such that
$$T_q(n, k) = \begin{cases}
1 & \textrm{if } n = 0 \vee k = 0 \\
qT_q(n-1, n-1) + T_q(n, n-1) & \textrm{if } n = k > 0 \\
T_q(n, k-1) + T_q(n-1,...
- 4,928
7
votes
0
answers
166
views
Examples of finitary problems/theorems of high logical complexity? [duplicate]
Generally, number theoretic conjectures which are well-known and easy to explain are either obviously $\Pi^0_1$ or $\Pi^0_2$, which is to say, their truth can be decided by a single membership query ...
- 1,452
1
vote
0
answers
55
views
Combinatorial structure of the entanglement spectrum and quantum error correction in finite vector spaces
Let $V$ be a finite-dimensional vector space over $\mathbb{C}$ with dimension $d$. Consider a subspace $S \subset V^{\otimes n}$ representing the code subspace of a quantum error correcting code. We ...
- 11
1
vote
0
answers
56
views
Find a set satisfying a specific condition
Let $S$ be a set of numbers of size $n$.
Let $M_S$ be the set of all multisets of size $n$ made of elements from $S$, with at least one element repeated. For example, if $S=\{1, 2, 3\}$, then $M_S = \{...
0
votes
1
answer
81
views
If the matroids associated to two finite subsets of the same vector space are isomorphic, are these two finite subsets linearly equivalent?
Let $E$ be a finite subset of ${\mathbb{F}_2}^n$, the $n$-dimensional vector space over the finite field $\mathbb{F}_2$ of $2$ elements. Let $M_E$ denote the associated matroid on $E$ where the ...
- 331
2
votes
0
answers
46
views
On A088352 as an antidiagonal sums of A129179
Let $a(n)$ be A088352. Here $a(n)$ is an integer sequence with generating function $A(x)$ such that
$$
A(x) = \cfrac{1}{1-x-\cfrac{x^2}{1-x^3-\cfrac{x^4}{1-x^5-\cfrac{x^6}{1-x^7-\cfrac{x^8}{\ddots}}}}}...
- 4,928
3
votes
1
answer
159
views
Proving that two sequences of polynomials defined over partitions are inverse to each other
For any fixed $c>0$ consider the polynomials
\begin{align*}
& p_n(X_1,X_2,\ldots) := \frac{n!}{c} \sum\limits_{b=1}^n \frac{c^b}{b!(n+1-b)!} \sum\limits_{\substack{l_1,\ldots,l_b \geq 1 \\ ...
- 1,295
0
votes
0
answers
54
views
Functional equations with coupled arguments and additive sructure
Let $G$ be a locally compact abelian group and let $f: G \to \mathbb{R}^+$ be a continuous function satisfying the functional equation
$$f(x + \phi(y)) + f(y + \phi(x)) = 1 + f(x+y)$$
for all $x, y \...
1
vote
2
answers
386
views
Lower bound for the size of a family of sets
Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:
$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$
Let $\mathcal{F} = \{A_1 \...
- 990
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
0
votes
1
answer
71
views
Forced monochromatic pairs in graphs
Starting point. Consider the "$V$-graph" on the vertex set $\{1,2,3\}$ and let the edges be $\{1,2\}$ and $\{2,3\}$. This graph is clearly bipartite. It is a trivial observation that ...
- 48.8k
2
votes
0
answers
71
views
Are the ranks of the following matrices given by these simple expressions?
The question itself is formulated in the title, so below I specify the matrices and expressions mentioned there. In case if this is something known or can be easily deduced from something known, this ...
- 321
2
votes
1
answer
310
views
Generating function for A300483 (related to Chebyshev polynomial of first kind)
Let $a(n)$ be A300483. Here
$$
a(n) = 2\int\limits_{t \geqslant 0}T_n\left(\frac{t+1}{2}\right)\exp(-t)\,dt.
$$
where $T_n(x)$ is $n$-th Chebyshev polynomial of first kind.
Let $b(n)$ be an integer ...
- 4,928
2
votes
1
answer
754
views
On a combinatorial inequality
Is it true that
\begin{gather}
\min\left(\lambda_{\min}(M_{12}), \lambda_{\min}(M_{13}), \lambda_{\min}(M_{14}), \lambda_{\min}(M_{15}), \lambda_{\min}(M_{23}), \\ \lambda_{\min}(M_{24}), \lambda_{\...
- 178
6
votes
0
answers
155
views
How to characterize this condition for commutative squares in $\Delta$
In the simplex category $\Delta$ we have the situation, that
pullbacks exist for cospans $[a] \xrightarrow{\alpha} [n] \xleftarrow{\beta} [b]$ in $\Delta_\text{mono}$ and
pushouts exist spans $[a] \...
- 1,813
5
votes
0
answers
190
views
Number of discrete Lipschitz functions with given Lipschitz constant
Fix $T, K, N \in \mathbb Z_+$. How many distinct Lipschitz functions $f: \{0, \dots, T\} \to \mathbb Z$ are there with Lipschitz constant $K$, and supremum norm at most $N$ satisfying $f(0) = 0$?
In ...
- 6,155
10
votes
1
answer
625
views
Generating function for A261041
Let $a(n)$ be A261041 (i.e., number of partitions of subsets of $\{1,2,\dotsc,n\}$, where consecutive integers are required to be in different parts).
Let $b(n)$ be an integer sequence with generating ...
- 4,928
0
votes
1
answer
82
views
Is there a stiff graph that is not a core?
By a graph, I mean a simple, undirected graph with no loops. A graph homomorphism $f : G \to H$ is a function from the vertexset of $G$ to the vertexset of $H$ such that if $u$ and $v$ are adjacent ...
- 331
5
votes
0
answers
137
views
Looking for a certain finite lattice
I don't think it actually exists, and it should be difficult proving that it doesn't (some background here), but is it possible to build a finite lattice $L$ where the only meet-irreducible elements ...
- 990
3
votes
1
answer
178
views
Algorithm for the sum with binomial coefficients and Bell numbers
Let $a(n)$ be A000110 (i.e., Bell or exponential numbers: number of ways to partition a set of $n$ labeled elements).
Let $b(n)$ be A355247 (i.e., expansion of exponential generating function $\exp(2(\...
- 4,928