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

**-1**

votes

**1**answer

89 views

### Discrepancy in non-homogeneous arithmetic progressions

I have a doubt, Roth's discrepancy theorem [1] says that there is a subset of arithmetic progressions $A \in [n]$ where any function $f:N\rightarrow \left \{ -1,1 \right \} $ implies
$ \left | \...

**4**

votes

**1**answer

60 views

### Optimal pseudotransversals

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**0**

votes

**1**answer

151 views

### Is it true that $\sum_{k=m}^n\frac{\sigma(k)}k\not\in\mathbb Z$ for all derangements $\sigma\in S_n$ and $1\le m\le n$?

Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
Recall that a permutation $\sigma\in S_n$ is called a derangemnt if $\sigma(k)\not=k$ for all $k=1,\ldots,n$.
Motivated ...

**2**

votes

**0**answers

60 views

### Bivariate power series as rational function

Suppose we have a bivariate power series of the form
$$\sum_{i}\sum_j a_{i,j} t^i s^j,$$
where for every fixed value of $i$ the corresponding univariate power series in $s$ is a rational function. Are ...

**1**

vote

**1**answer

59 views

### Asymptotic upper bound for partial binomial-like sum

I want to upper bound the quantity $$\sum_{i\le \alpha n} \binom{n}{i}\lambda^i$$, where ${\lambda>1}$, $0<\alpha<1$. It is not the same as partial sum of binomial coefficients. An asymptotic ...

**0**

votes

**1**answer

96 views

### Expected values of two non-negative, integer-valued random variables related to an urn problem

Consider an urn containing $c$ distinguishable balls, $\alpha$ of which are red, $\beta$ of which are blue, and $\gamma$ of which are green, and $\alpha+\beta+\gamma=c$. We assume $\alpha,\beta,\gamma&...

**4**

votes

**0**answers

126 views

### Is there a permutation $\pi\in S_n$ with $\sum\limits_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0$ for each $n>7$?

Let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each $n=8,9,\ldots$ we have
$$\sum_{0<k<n}\frac1{\pi(k)^2-\pi(k+1)^2}=0\tag{$*$}$$
for ...

**-1**

votes

**1**answer

263 views

### Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun.
Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$.
Is it true that, for every $n \ge 8$, there is at least one even permutation $\...

**3**

votes

**0**answers

32 views

### Finding linear order of set maximising number of consecuitive subsets

I have the following combinatorial optimisation problem of which I think someone has probably solved it before. Has someone come across this problem before, maybe in a different setting than in the ...

**2**

votes

**0**answers

140 views

### On the set $\{\sum_{k=1}^n \lambda_ka_k:\ a_1,\ldots,a_k\ \text{are distinct elements of}\ A\}$

For a field $F$ let $p(F)=p$ if the characteristic of $F$ is a prime $p$, and $p(F)=+\infty$ if $F$ is of characteristic zero.
In 2007 I considered the linear extension of the Erdos-Heilbronn ...

**3**

votes

**0**answers

154 views

### A conjectural lower bound for $|\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}|$

Motivated by Question 315568 of mine, I'm interested in the set
$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$
It is easy to see that
$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...

**12**

votes

**1**answer

253 views

### Is there a Giambelli identity with dual representations?

For natural numbers $a,b$ with $b\leq n-1$, let $V_{ (a|b)}$ be the irreducible representation of $GL_n$ with highest weight vector $(a+1, 1^b, 0^{n-b-1})$ where the exponentiation denotes repetition. ...

**1**

vote

**1**answer

154 views

### Derangements and unit fractions

Motivated by a recent question of Zhi-Wei Sun and its nice answer by Zhao Shen, here are two related questions.
Let $S_n$ be the group of permutations on $\{1, 2, \ldots, n\}$.
a. For each $n \ge ...

**6**

votes

**0**answers

112 views

### Sets $X,Y$ of natural numbers such that any natural $n$ writes uniquely $n=x+y$ [duplicate]

There are many pairs $X, Y$ of infinite subsets of $\mathbb{N}:=\{0,1,2\dots\}$ such that any $n\in\mathbb{N}$ writes uniquely as $n=x+y$, with $x\in X$ and $y\in Y$. An example of such a pair is $(X,...

**0**

votes

**0**answers

104 views

### Probability of degree $0$ gcd between every pair of random homogeneous polynomials shifted by random primes?

Take $n,d,B\in\mathbb Z_{>0}$ with $d<n$ and denote $\mathcal M_{n,d}$ to be set of all total degree $d$ monomials in $n$ variables $x_1,\dots,x_n$ with degree $\leq1$ in each variable (...

**0**

votes

**2**answers

112 views

### Vertex Connectivity of the Hypercube [closed]

I am revising my lecture notes about connectivity, but I am stuck regarding proof of $κ(Q_d) = d$ Then I took a look of the proof by induction in D. West's book. For $d\leq1$, $Q_d$ is a clique with $...

**3**

votes

**2**answers

123 views

### Satisfier-Falsifier games

In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...

**4**

votes

**1**answer

144 views

### existence of a certain subset of vertices in a graph

Take an undirected graph $G=(V,E)$. For any subset $M\subseteq V$, we define ${\rm deg}_M(v)=|\{k\in M:(v,k)\in E\}|$, namely, the number of neighbors of $v$ in $M$.
Is it true that, there exists a ...

**4**

votes

**0**answers

176 views

### Forcing scalar products to avoid prescribed values

Let $p$ be a prime, and $n\ge 1$ an integer number. Suppose that the (not necessarily distinct) vectors $v_1,\dotsc,v_N \in{\mathbb F}_p^n$ satisfy the following condition:
\begin{gather}
\text{For ...

**-1**

votes

**0**answers

93 views

### Ulam Sequence and Primes

The Ulam sequence is defined as 1,2,3,4,6,8,11,... where, after 2, a number is added to the sequence if and only if it is expressible as a sum of two distinct preceding numbers in a unique way.
It ...

**10**

votes

**1**answer

272 views

### An upper bound for the largest Laplacian eigenvalue of a graph in terms of its diameter

Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture:
Conjecture: If G has ...

**6**

votes

**0**answers

116 views

### Can the partition function $p(n)$ take perfect power values?

Recall that the perfect powers are those integers $m^k$ with $k,m\in\{2,3,\ldots\}$. I don't consider $0$ or $1$ as a perfect power.
Y. Bugeaud, M. Mignotte and S. Siksek [Annals of Math., 2006] ...

**1**

vote

**1**answer

81 views

### Number of sequences of edges that contain at least one subsequence which is a walk between vertex $i$ and $j$

Typically a walk is defined as a vertex-edge sequence, e.g. $(v_1, e_1, v_2, e_2, v_3)$, but suppose we are working in the undirected simple graph setting. Instead, let's say an edge-sequence $(e_1, ...

**0**

votes

**0**answers

33 views

### When is the set of faces of a convex polytope algebraically independent?

This is related to another question of mine
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in ...

**3**

votes

**0**answers

68 views

### The ring generated by a convex polytope and its faces

Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in $V$ with multiplication induced by Minkowski ...

**2**

votes

**2**answers

105 views

### Clique Size in “Triangle Regular” Graphs

Let $G(V,E)$ be a connected, simple and undirected graph with the additional constraint, that each edge is contained in the same number $k_T$ of triangles; i.e. that $G$ is regular w.r.t. to that ...

**1**

vote

**0**answers

73 views

### One-point partition

Let following be the partition function in infinitely many variables $x_i$ the linear coordinates on the vector space $V$.
$$
\mathcal{Z}=exp\Big(\sum_{\substack{g\geq 0\\n\geq 1}}\frac{h^{g-1}}{n!}\...

**2**

votes

**0**answers

112 views

### Maximal number of $S_n$-conjugates living in a hyperplane

Let $v=(a_1,\dots,a_n)\in\mathbb{R}^n$ where the $a_i$ are distinct and positive. For $\sigma\in S_n$, let $\sigma(v)=(a_{\sigma(1)},\dots,a_{\sigma(n)})$. For any hyperplane $H$ through the origin, ...

**11**

votes

**0**answers

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

**1**

vote

**2**answers

98 views

### Given an integer lattice, how to count the number of points whose norm is smaller than some bound $M$?

Let $\mathbf{b}_1, \mathbf{b}_2, ..., \mathbf{b}_n$ be linearly independent $m$-dimensional vectors whose entries belong to $[0, M] \cap \mathbb{Z}$, for some $M \in \mathbb{N}^*$. Of course, $n \le ...

**2**

votes

**0**answers

108 views

### Chen primes and permutations

In 1973 the Chinese mathematician J.-R. Chen proved that there are infinitely many primes $p$ such that $p+2$ is a product of at most two primes. Nowadays such primes $p$ are called Chen primes.
For $...

**19**

votes

**1**answer

613 views

### Permutations $\pi\in S_n$ with $\sum_{k=1}^n\frac1{k+\pi(k)}=1$

Let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
Motivated by Question 315568 (http://mathoverflow.net/questions/315568), here I pose the following question.
QUESTION: Is ...

**5**

votes

**1**answer

298 views

### Criterion for acyclicity of flag complexes

Let $\Delta$ be a flag complex on $n$ vertices. Let $r$ be the smallest size of the facets of $\Delta$. Suppose that $2r>n$. Must $\Delta$ be acyclic?

**0**

votes

**0**answers

103 views

### Exponential generating function for k^n / n

The ordinary generating function for $k^n/n$ is $-\log(1-kx)$. Is there a closed-form exponential generating function for this sequence?

**0**

votes

**0**answers

115 views

### Permutations $\pi\in S_n$ with $p_k+p_{\pi(k)}+1$ prime for all $k=1,\ldots,n$

As usual, let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$.
QUESTION: Is my following conjecture true?
Conjecture. For any positive integer $n$, there is a permutation $\pi\...

**1**

vote

**1**answer

67 views

### Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...

**1**

vote

**1**answer

208 views

### Odd permutations $\tau\in S_n$ with $\sum_{k=1}^nk\tau(k)$ an odd square

For any positive integer $n$, as usual we let $S_n$ be the symmetric group of all the permutations of $\{1,\ldots,n\}$.
QUESTION: Is it true that for each integer $n>3$ there is an odd permutation ...

**4**

votes

**1**answer

75 views

### Separate the trivial partition by a linear hyperspace

Let $e=[1,1,\ldots,1]\in\mathbb{Z}^n$. I am looking for a way to find a vector $a\in\mathbb{Z}^n$ such that:
$\langle a,e\rangle=0$ and
for every nonnegative $v\in\mathbb{Z}^n$ such that $\langle e,v\...

**3**

votes

**1**answer

117 views

### Minimal vertex cover

Definition:
Let $G$ be a graph. A subset $C \subseteq V(G)$ is a vertex cover of
$G$ if for each $e \in E(G)$, $e\cap C \neq \phi$. If $C$ is minimal
with respect to inclusion, then $C$ is called ...

**3**

votes

**0**answers

90 views

### Integer partitions under divisibility constraint

Consider integer partitions of $x \in \mathbb{N}$ of size $k$ under the constraint that the partition elements are distinct and the ratio of any element to each smaller element is a natural number.
...

**2**

votes

**1**answer

84 views

### Upper bound on the number of induced subgraphs of the square lattice with all degrees even

An induced subgraph of a graph $G$ is defined by a subset of vertices of $G$ together with all edges in $G$ that connect vertices from the chosen subset.
Consider now an $n\times m$ square lattice. ...

**3**

votes

**1**answer

81 views

### Cliques in Cayley graph on $n$-cycles

Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....

**8**

votes

**0**answers

112 views

### $n$-fold tensor products of $D(A)$ for finite dimensional algebras

Let $A$ be a finite dimensional quiver algebra over a field $K$ and let $D(-):=Hom_K(-,K)$ denote the natural duality (assume algebras are connected).
Define $\psi_A:=sup \{ n \geq 1 | D(A)^{\otimes ...

**0**

votes

**1**answer

98 views

### Number partitions [closed]

(I'm trying to solve a problem for computer programming. Don't have much of a math background, so I hope I am using the right terminology)
Is there a formula for getting the partitions of a number ...

**1**

vote

**0**answers

47 views

### Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Subset

I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed.
...

**17**

votes

**1**answer

2k views

### A mysterious connection between primes and squares

Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares.
...

**3**

votes

**0**answers

262 views

### Primes arising from permutations (II)

In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging.
Here I pose a new question in this direction which does ...

**19**

votes

**1**answer

941 views

### Is there an accessible exposition of Gelfand-Tsetlin theory?

I'm hoping to start an undergraduate on a project that involves understanding a bit of Gelfand-Tsetlin theory, and have been tearing my hair out looking for a good reference for them to look at. ...

**8**

votes

**1**answer

425 views

### Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...

**2**

votes

**1**answer

192 views

### Triangular conjecture (that implies the Frankl conjecture)

Let $M$ be a $n\times n$ triangular matrix, that entries are $0$ and $1$ , and such that diagonal entries are $1$. A row or a column will be said to be small, if its numer of $1$ is at most $(n+1)/2$. ...