# 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,166
questions

0
votes

0
answers

70
views

### How to write down the contrapositive of a statement and prove if it's right or not [closed]

I have been battling with my professor over this question for months. Every time I come
up with an answer she tells me wrong.
Question:
Consider the following proposition concerning an integer n ≥ 2. ...

1
vote

2
answers

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

-2
votes

0
answers

23
views

### How many strings of octal numbers of length n are “good”? [closed]

A string of octal numbers of length n is called “good” if k=n(0)+n(7) and l=n(3)+n(4) are odd numbers, where n(i), i=0, 1, …, 7, represents the number of i’s found in the string. How many strings of ...

2
votes

3
answers

222
views

### Maximal set of $n$-bits 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 ...

4
votes

1
answer

348
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), ...

1
vote

1
answer

65
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) =...

3
votes

0
answers

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

2
votes

0
answers

130
views

### A set inequality problem [migrated]

There is two different sets called set $a$ and $b$.Let $t$ be a positive integer,and put $t$ objects in another set called set $c$ ,and label the $t$ objects $c^1$,$c^2$...$c^t$.
Next,you put the ...

3
votes

0
answers

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

2
votes

1
answer

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

3
votes

1
answer

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

2
votes

0
answers

122
views

+50

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

4
votes

1
answer

267
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{ ...

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

2
votes

0
answers

54
views

### Inequality for 2-associated Stirling numbers of the second kind

Let $S(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 blocks ...

6
votes

0
answers

162
views

+50

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

1
vote

1
answer

38
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\...

7
votes

1
answer

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

0
votes

0
answers

44
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
votes

0
answers

160
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 $\...

6
votes

2
answers

293
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://...

3
votes

0
answers

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

1
vote

0
answers

96
views

### Higman's lemma and well-quasi-ordering theory [closed]

Higman's Lemma is basic to well-quasi-ordering (WQO) theory, but has many specific forms, for example: the Cartesian product of two WQOs is a WQO. Any new extensions?
Usually proved by minimal bad ...

3
votes

0
answers

51
views

### A question about the existence of surjective contractions

A few years ago I was doing some research in origami, and was motivated to as the following questions:
Consider $\mathbb{R}^2$ with the Euclidean metric and Lebesgue measure. Does there exist a ...

0
votes

0
answers

24
views

### Does there exist an axiomatic unsupervised approach for Link prediction based on either distances or matrices?

Does there exist an axiomatic unsupervised approach for Link prediction based on either distances (in my pasted link - related to the Graph theory's Closeness centrality) or matrices (i.e., if we fake ...

4
votes

0
answers

290
views

### Regular solids and $\mathbb{Z}_5$

The mapping from the regular solids to $\mathbb{Z}_5$ given by the number of faces in the solid mod 5, interestingly, is a bijection. Any geometers or algebraists know if there is a significant ...

2
votes

0
answers

114
views

### Generalizing Hall's marriage theorem to non-perfect matchings

Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$.
A matching $M \subseteq E$ is a subset of disjoint edges
(i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...

7
votes

1
answer

115
views

### Nearest neighbors on random complete graph

Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random
order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...

3
votes

1
answer

116
views

### Elements of length 0 in extended affine Weyl group for GL(n)

As part of my research, I would like to understand the possible pairs of $(v,\sigma)\in \mathbb Z^n\times S_n$ satisfying the following condition: For $1\le i < j \le n$, we have $\sigma(i) < \...

0
votes

1
answer

114
views

### Concentration inequalities for random sampling without replacement

Let a population $C$ consist of $N$ values $c_1, c_2, \cdots, c_N$, with $c_i\in \{0,1\}$. Let $X_1, X_2, \cdots, X_n$ denote a random sample without replacement from $C$ and let $Y_1, Y_2, \cdots, ...

0
votes

1
answer

186
views

### How far does a random walker travel before returning to the origin?

Consider a (continuous time) simple symmetric random walk on $\mathbb Z$, starting from the origin. Let us denote this random walk by $\{X_t: t\geq 0\} $. It is well known that this random walk is ...

0
votes

0
answers

27
views

### Consider the probability of connecting the terminal vertices using Binary Decision Diagram with length constraint

Definitions
Given an undirected graph $G=(V,E,p),p:E \to [0,1]$ where $V$ is the set of vertices, $E$ is the set of edges and $m=|E|$, and $p$ represents the probability that an edge functions. A set ...

0
votes

0
answers

85
views

### Dividing balls into two bins and comparing the weight

Let $S$ be a set of $N$ balls $\{b_1, \cdots, b_N\}$, each with weight $w(b_j), j = 1, \cdots, N$. For a subset $A \subseteq S$, define
$$\displaystyle W(A) = \sum_{a \in A} w(a).$$
Initially, $S$ is ...

1
vote

0
answers

95
views

### On the derivation of some asymptotic expressions involving combinatorics

My questions come from the supplementary material in a recent preprint Nonequilibrium statistical mechanics of money/energy exchange models. My first question comes from page 35. Specifically, suppose ...

14
votes

4
answers

690
views

### Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$.
I have verified the statement for $n \leq 4$ with a Mathematica code.
I have ...

2
votes

1
answer

73
views

### Finite pair-splitting family of $\mathbb{N}$

This is a kind of "dual" of an older question.
Is there a finite family ${\frak F}\subseteq {\cal P}(\mathbb{N})$ such that for all $a\neq b\in\mathbb{N}$ there is $S\in{\frak F}$ with $|S\...

0
votes

0
answers

44
views

### Why do we have this equality regarding subgroup indices? [migrated]

Let $H_1, H_2$ be groups (can be non commutative), let $K$ be a subgroup of $H_1 \times H_2$. Let us denote $p$ the projection from $H_1 \times H_2$ to $H_1$ defined by $p(x, y) = x$ and let $L = \...

0
votes

0
answers

25
views

### Condition for invertibility of the transition matrix obtained via discretization

Consider two continuous random variables $X,Y$ with joint, conditional, and marginal intensity $f(x,y),f(y|x),f(x)$, respectively. Discretize $X,Y$ to $\tilde{X},\tilde{Y}$, respectively, by binning (...

2
votes

1
answer

188
views

### Finite $k$-set-respecting splitting of $\mathbb{N}$

Motivation. My sons participated in a large football tournament recently; everyone wanted to be in a team with everyone else at least once. Tricky!
Formulation of the question. For any positive ...

1
vote

0
answers

56
views

### subsets of $\mathbb{N}$ whose shifts have finite intersection property in density

I am interested in proving the statement:
Let $S\subseteq\mathbb{N}$ such that for every $r\in\mathbb{N}$ and for every $k_{1}$, $k_{2}$, $\ldots$, $k_{r}\in\mathbb{N}$, the set $\big(S-k_{1}\big) \...

2
votes

1
answer

96
views

### Finding an easy example appying the general Lovász local lemma

Is there any easy application for the generanl local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set ...

2
votes

1
answer

126
views

### Bounding the size of subspaces of $\mathbb{Z}^n$

For a subgroup $V$ of $\mathbb{Z}^n$, define $\Vert V \Vert$ to be the smallest $k$ such that $V$ is generated by its intersection with the closed $k$-ball around the origin in $\mathbb{R}^n$. Also, ...

4
votes

0
answers

125
views

### Major indices of standard tableaux of shapes obtained from addable cells of a given Young diagram

I have a "very" indirect proof that the following fact is true for every Young diagram $\lambda \vdash n$ and every $r \in \{0,\dotsc,n\}$:
\begin{equation}
d_\lambda = \sum_{a \in \mathrm{...

2
votes

0
answers

75
views

### Isomorphism and counting for tree quivers

Let $Q$ be a quiver which is a connected tree and let $A=KQ/I$ be a quiver algebra with $I$ an admissible ideal, meaning that $I$ is generated by paths of length $\geq 2$. Let $n$ be the number of ...

2
votes

0
answers

214
views

### Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.
Let $P_n$ be the number of three-connected planar ...

3
votes

0
answers

78
views

### Commutant of irrep of $S_n$ (over local field)

Let $k$ be a field of characteristic zero and let $(V, \rho)$ be a finite-dimensional representation over $k$ of the symmetric group $S_n$. I would like to understand the commutant $\operatorname{End}...

5
votes

1
answer

410
views

### How can I evaluate the following sum?

While studying sequences and series, I came across summations of geometric series. I am able to derive the sum of a geometric progression and that of arithmetico–geometric sequence.
But taking a step ...

0
votes

1
answer

107
views

### Length of truncated Farey sequence

Farey sequence $F_n$ of order $n$ is defined as a sequence of completely reduced fractions $a/b$ such that $0 \le a \le b \le n$.
$$ F_1 = \frac{0}{1}, \ \frac{1}{1}$$
$$ F_2 = \frac{0}{1}, \ \frac{...

0
votes

0
answers

67
views

### Bramble with order 5 for the Wagner graph

For treewidth $3$, there are four forbidden minors: K5, the graph of the octahedron, the pentagonal prism graph, and the Wagner graph.
This implies that the Wagner graph should have tree-width at ...

2
votes

0
answers

78
views

### Constructing Hamiltonian circuits in acyclic digraphs

Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...