All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 21
1
vote
1
answer
73
views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$.
If $A,B$ are any sets, let $A \,\triangle \, B ...
- 24.2k
4
votes
0
answers
67
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
1
vote
1
answer
76
views
Determinant formula for a certain parametrized M-matrix
Let $P_{ij}$ be variables, and let $A \in \mathbb{R}^{n\times n}$ be the matrix defined by
$$
A_{ij} = \begin{cases}
-P_{ij} & i \neq j,\\
P_{i1} + P_{i2} + \dots + P_{in} & i=j.
\end{cases}
$$...
- 20.2k
26
votes
0
answers
512
views
A non-self-intersecting unit side length polygon in a unit square has odd number of sides unless it is the square itself
This is the same question as here in SE.
I have a conjecture, it is like this:
Suppose there is a non-self-intersecting polygon lies inside a closed square of length $1$. The polygon has every side ...
- 843
1
vote
1
answer
324
views
Want to show that this sum vanishes modulo p
Let $p\ge 5$ be a prime number, and consider the following sum:
\begin{align}
S &= \sum_{v_0 = 1}^{p - 2} \binom{p - 2}{v_0} \, \theta^{v_0 - 1}(Y) \cdot \theta^{p - 2 - v_0}(Y) \\
&+ \frac{1}{...
- 18.4k
2
votes
1
answer
147
views
What is the analogue of a Block-Cut Tree Decomposition in directed graphs?
Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
- 5,407
0
votes
0
answers
52
views
Reference request for the determinant of a matrix constructed from Pascal's triangle
One can prove by induction that the matrix $M^{(n)}$ given by
$$ \begin{pmatrix}
1 & 1 & 1 & 1 & \dots & \binom{n}{0} \\
1 & 2 & 3 & 4 & \dots & \binom{n+1}{1} \...
- 5,546
21
votes
7
answers
14k
views
A balls-and-colours problem
A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
81
votes
10
answers
9k
views
Existence of a zero-sum subset
Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
- 109k
4
votes
0
answers
115
views
Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?
Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
- 24.9k
39
votes
3
answers
3k
views
Is there a finite family of functions such that the max of any two functions can be dominated by a third?
Is it true that for every $t$ there is an $n$ and there exists a finite function
family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different
values) and for any $f_1, \ldots, ...
- 18.8k
1
vote
1
answer
232
views
Looking for q-analog of derangement anagrams for a word
I have already known QPermutationDerangement:
It describes the distribution
$$
d_n(q)=\sum_{\sigma \in D_n} q^{\operatorname{maj}(\sigma)}
$$
Where we sum over all derangements of an $n$ element set.
...
CommunityBot
- 1
6
votes
1
answer
940
views
Does the likelihood of these tables exist?
Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.
Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...
CommunityBot
- 1
0
votes
0
answers
44
views
Lattice points in the boundary of a Minkowski sum of two convex lattice polygons
Let $P$ and $Q$ be two convex lattice polygons in $\mathbb{R}_+^2$ and let $P+Q$ be their Minkowski sum. Given a set $S \subset \mathbb{R}^2$, we let $L(S) =\#( S \bigcap \mathbb{Z}^2)$.
The equality $...
- 183
8
votes
0
answers
244
views
Strengthening of Frankl's union-closed sets conjecture: An algebraic approach
Let $\mathcal F$ be a union-closed family of subsets of $[n]=\{1,2,...n\}$ and $n$ real numbers $x_1,x_2,...,x_n\geq 1$.
Conjecture: There exists $k\in [n]$ such that:
$$\sum_{k\in A,A\in \mathcal F}\...
- 1,462
4
votes
1
answer
119
views
Proving Equal Set Sizes in Sequential Point Selection on a Real Interval with Variable-Length Intervals
I'm here as an engineer working on a point sampling algorithm and I've noticed that when I perform the algorithm on an ordered set of points in one direction it selects the exact same number of points ...
- 151
2
votes
0
answers
67
views
$R$-recursion for A006351
Let $a(n)$ be A006351 (i.e., number of series-parallel networks with n labeled edges. Also called yoke-chains by Cayley and MacMahon). Here exponential generating function is $A(x)$ such that $B(x) = ...
- 175
4
votes
2
answers
609
views
Ask for a generating function or an explicit expression of a triangle of positive integers
Preliminaries
I encountered the following triangle of positive integers:
$c_{n,k}$
$n=1$
$n=2$
$n=3$
$n=4$
$n=5$
$n=6$
$n=7$
$n=8$
$k=0$
$1$
$3$
$15$
$105$
$315$
$3465$
$45045$
$45045$
$k=1$
$5$
$...
- 1,091
3
votes
0
answers
101
views
Tuple rearrangement: a combinatoric problem emerging from the Hurwitz action on Coxeter groups
I am working on Artin Groups, so called Dual Artin groups and the conjecture that they are isomorphic. Tuples of $n$ group elements can be acted on by the braid group $B_n$ in a particular way called ...
- 31
0
votes
0
answers
166
views
Combine two types of permutations in a Young diagram?
Given a Young diagram $Y$, for each row $R$ choose a permutation $\sigma_R$ of $\{1,\dots, |R|\}$, where $|R|$ is the size of row $R$. Let $\sigma_R(i)$ be the “row coordinate” of the $i$th cell in ...
- 281
1
vote
1
answer
134
views
A distributive identity for products of partition functions
An $r$-composition of a non-negative integer $s$ is an expression $s=s_1+s_2+\cdots+s_r$ where the $s_i$ are also non-negative integers. Define $k(r,s):=\sum \pi(s_1)\pi(s_2) \cdots \pi(s_r)$ where ...
- 161
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
0
votes
1
answer
98
views
Only special permutations result in a constant expression when permuting coefficients in a sum involving binomials?
Fix $n\geq 1$ and let $p_k(x) := x^k(x-1)^{n-k}$.
Suppose $\pi$ is a permutation on $\{0,1,\dotsc,n\}$, such that
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} p_{\pi(k)}(x) \text{ is a constant}.
$$
Must it be ...
- 13.2k
0
votes
0
answers
56
views
Does Forcing conjecture equals to assume the host graph is regular?
Given two graphs $H$ and $G$, the homomorphism density $t(H, G)$ is defined as the proportion of mappings from the vertices of $H$ to the vertices of $G$ that preserve adjacency. Formally,
$$
t(H, ...
- 349
9
votes
3
answers
1k
views
Examples of combinatorial problems where the only known solutions, or most "natural" solutions, use representation theory?
In Solution of two difficult combinatorial problems with linear algebra, Robert Proctor presents two simply stated combinatorial problems, and gives solutions to them using a linear algebraic approach ...
- 12.9k
3
votes
1
answer
855
views
Infinite dimensional lattice for integers and the Riemann hypothesis?
It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers.
We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$.
...
CommunityBot
- 1
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
9
votes
1
answer
1k
views
Bounding the probability that two binomials are equal
Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question.
Let $B_{n,p}$ denote the usual binomial random ...
CommunityBot
- 1
2
votes
1
answer
137
views
Reconstructing a matroid by its minors
Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. ...
- 500
2
votes
1
answer
208
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 349
1
vote
1
answer
77
views
Enumeration of permutations with prescribed numbers of fixed points and excedance/deficiency statistics
Consider the following refinement of permutation statistics. For $π ∈ S_n$, let:
$\mathrm{fix}(π) = |\{i : π(i) = i\}|$ (number of fixed points)
$\mathrm{exc}(π) = |\{i : π(i) > i\}|$ (number of ...
- 18.4k
13
votes
3
answers
3k
views
Koebe–Andreev–Thurston theorem - where can I find a proof?
Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
- 13.6k
0
votes
0
answers
60
views
Bounding number of commutators of a certain type
Say I have a vector space $V$ over $\mathbb{C}$, generated by $2n$-letters, $(x_1,...,x_n,y_1,...,y_n)$. Let $C_d$ denote the commutators on $V$ of length $d$, and let $(B_1,...,B_r)$ denote a basis ...
- 2,907
2
votes
1
answer
287
views
Double estimates relating Ruzsa distance and doubling constant
I am trying to solve the following exercise (2.3.16) from Tao-Vu book.
Let $A,B$ be additive sets with common ambient group $Z$. Show that
$\sigma[A\cup B]\leq e^{d(A,B)}+2e^{4d(A,B)}$. In the ...
CommunityBot
- 1
2
votes
0
answers
59
views
$R$-recursion for A338193
Let $a(n)$ be A338193. Here generating function is $A(x)$ such that
$$
A(x) = 1 + \int\frac{\left(\frac{x}{A(x)}\right)'}{\left(\frac{x}{(A(x))^2}\right)'} \, dx.
$$
Let
$$
R(n, q) = \begin{cases}
1 &...
- 4,938
0
votes
0
answers
61
views
Searching another example related to the union-closed sets conjecture
Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.
Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (...
- 1,000
1
vote
1
answer
138
views
Recognizability/unique composition property for substitution tiling
This may be a very basic question, but I have not found an answer to it so far in my search. The question is whether there is an "algorithmic" way to check unique-composition/recognizability ...
CommunityBot
- 1
2
votes
1
answer
71
views
APs in sumsets of exponential growing sequences
I posted this initially on SE, but after I didn't found a particular reference on it, I decided it would be more appropriate to post it here. A friend shared this observation with me and I thought ...
- 23.7k
-2
votes
1
answer
142
views
Solution to Erdos-Ulam problem [closed]
I have solved the Erdos-Ulam problem (see link) and can construct a set that satisfies the conditions (dense in R2 with all interpoint distances rational). I have expanded the solution from two ...
- 3,068
3
votes
0
answers
169
views
Basis of Specht module of symmetric groups
I am reading the construction of the Specht module from James's book. The Specht module of a symmetric group corresponding to a partition $\lambda$ is spanned by all polytabloids $e_{t}$ associated ...
- 12.9k
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 ...
CommunityBot
- 1
6
votes
1
answer
173
views
$\omega$-de-Bruijn sequences
Let $\omega$ denote the set of non-negative integers. For which integers $n>1$ is there a sequence $b_n: \omega\to\omega$ with the following property?
Whenever $v\in\omega^n$ there is a unique $...
- 651
4
votes
1
answer
389
views
The existence of a specific kind of independent set in a connected graph satisfying the following property
Suppose $G$ is a connected finite graph satisfying that every edge $uv$ of $G$ belongs to a "triangle" $uvw$ such that $uv,uw\in E(G),\ vw\notin E(G)$ or $uv,vw\in E(G),\ uw\notin E(G)$(in other words,...
CommunityBot
- 1
5
votes
0
answers
140
views
Combinatorial rule for Schubert times Coxeter-Schubert
For $w \in S_n$, let $\mathfrak{S}_w$ be the Schubert polynomial. For geometric reasons, we know that $\mathfrak{S}_u \mathfrak{S}_v = \sum c_{uv}^w \mathfrak{S}_w$ for some nonnegative integers $c_{...
- 156k
1
vote
0
answers
98
views
Simplicial complexes on $[n] := \{0,\ldots,n\}$ that are identical under any contraction of consecutive vertices
For $n\in\mathbb{N}$, let us denote by $\Omega(n)$ the set of all (possibly empty) “abstract” simplicial complexes on $[n] := \{0,\ldots,n\}$ (“on $[n]$” means “labeled by the elements of $[n]$”). To ...
- 12.9k
2
votes
1
answer
210
views
Maximum number of ones in a full rank matrix with a restriction
Consider $n \times n$ binary matrices. I am interested in the largest number of ones possible in an $n \times n$ binary matrix with full rank over the field of integers mod 2 with the following ...
- 23.7k
10
votes
0
answers
287
views
Coefficients of polynomials vs trigonometric product
Let's consider the family of sequences of coefficients in the expansion
$$\prod_{i=0}^{n-1}(1+x^{3^i}+x^{3^{i+1}})=\sum_{k\geq0}a_n(k)\, x^k.$$
Remark. Evidently, the RHS is a finite sum.
Here is a ...
- 43.2k
1
vote
1
answer
75
views
Probability of correctly guessing the maximum event probability of a multinomial distribution
I have a sample from multinomial distribution with $n$ trials, and $k=3$ options. I know that one of the event probabilities $p_i$ is larger than the two others (who are equal). I'm trying to guess ...
- 258
6
votes
2
answers
723
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 13.6k