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
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 ...
- 21
-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 ...
- 35
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), ...
- 45
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) =...
- 191
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 ...
- 546
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 ...
- 149
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 ...
- 24.9k
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 ...
- 4,352
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 ...
- 75
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 &...
- 3,525
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{ ...
- 11.4k
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 ...
- 435
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 ...
- 19k
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\...
- 11
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 ...
- 496
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....
- 1,841
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 $\...
- 49
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://...
- 313
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 ...
- 3,914
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 ...
- 354
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 ...
- 1
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$ ...
- 121
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 ...
- 206
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) < \...
- 315
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, ...
- 105
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 ...
- 49
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 ...
- 1
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 ...
- 24.9k
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 ...
- 700
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 ...
- 143
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\...
- 44.4k
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 (...
- 109
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 ...
- 44.4k
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) \...
- 111
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 ...
- 1,068
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, ...
- 23
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{...
- 133
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 ...
- 25.3k
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 ...
- 5,473
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}...
- 291
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{...
- 335
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 ...
- 101
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 ...
- 3,898