All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
12
votes
2
answers
744
views
Looking for a counterexample for a conjecture about union-closed families of sets
(I have posted a corrected version of this question. The limit $\lceil n/2 \rceil$ must be replaced with $\lceil (n+1)/2 \rceil$.)
I have already asked basically the same question here, but now I have ...
- 1,000
2
votes
0
answers
148
views
Nilpotent polynomial matrices over $F_q$ - polynomial count variety ? ( Nilpotent cone for Hitchin-Gaudin like integrable system)
Context: Number of nilpotent $n\times n $ matrices over $F_q$ is $q^{n(n-1)}$ classical result due to Ph.Hall, M.Gerstenhaber (see very nice exposition by T.Leinster at n-cat-cafe/arxiv) which have ...
- 24.9k
2
votes
1
answer
200
views
Subset in $[0,1]^k$ with positive density
Given a positive constant $0<\gamma<1$, does there exists integer $k_0>0$ such that for any integer $k\geq k_0$ the following holds?:
For any $A\subseteq\left[0,1\right]^k$ with the measure ...
CommunityBot
- 1
0
votes
0
answers
52
views
Does "epsilon-regular" equal to "cut distance less than epsilon"?
Let $G$ be a bipartite graph (vertex number sufficient large) with bipartition $(U,W)$ and edge density $d$. Does these two statement equal?
$G$ is $\varepsilon$-regular, i.e. $\big|e_G(X,Y)-d|X||Y|\...
- 349
6
votes
1
answer
244
views
Linear independence over field of rational functions
To prove that functions $f_1(x), \dots, f_n(x)$ with $x \in \mathbb R$ are linearly independent, we only need to show that the Wronskian of these functions is non-zero at a certain value of $x$. Now ...
- 91.8k
18
votes
4
answers
915
views
Arrow's theorem and the postseason
There are a number of instances of sports teams intentionally losing matches in order to secure a more favorable situation in a playoff round. While this doesn't happen terribly often, when it does it'...
- 1,446
1
vote
0
answers
158
views
Is there a better/newer list of Kazhdan-Lusztig polynomials?
I am essentially just re-asking this question, as it's now over a decade old, and I'm hoping that more extensive lists exist. I've started looking at the papers cited in the previous question, and ...
- 12.9k
1
vote
2
answers
74
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\...
- 101
2
votes
1
answer
423
views
Conjecture about semigroups
Let $G$ be a finite semigroup with order $n$ odd. Let $S_i \in G, i=1,\ldots,\binom{n}{(n+1)/2}$ be all the subsets of $G$ of size $(n+1)/2$.
Let $E(S_i)$ be the set obtained "expanding" $...
- 14.6k
8
votes
1
answer
174
views
Pick a homogeneous set of size $n$
Assume that the natural numbers have been colored with two colors: lavender and periwinkle. You don't know the coloring. You may sample as many (possibly overlapping) sets of size $n$ as you would ...
- 23.7k
3
votes
0
answers
121
views
Closed form from a slightly modified recursion for transposed Catalan triangle
Let $a_1(n)$ be A000108, i.e. Catalan numbers. Here
$$
a_1(n)=\frac{1}{n+1}\binom{2n}{n}
$$
Let $a_2(n)$ be A059715, i.e. number of multi-directed animals on the triangular lattice. From OEIS page we ...
- 175
0
votes
0
answers
49
views
Minimum value of maximal number of complete bipartite subgraphs
We define $F(n,m,k)$ as the family of bipartie graphs $G$ with two disjoint independent (vertex) sets $U$ and $V$ satisfying that
the cardinality of $U$ is $|U|=n$ and the cardinality of $V$ is $|V|=...
- 12.9k
0
votes
1
answer
403
views
Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?
In the paper [1] below, among other things, Carlitz introduced weighted Stirling numbers of the second kind $R(n,k,r)$. He also proved that the numbers $R(n,k,r)$ can be generated by
\begin{equation*}%...
- 1,091
6
votes
1
answer
393
views
Test for pair of odd primes $(p, 2p^2-1)$
Let $a(n)$ be A106483 (i.e., primes $p$ such that $2p^2-1$ is also prime).
Let $b(n)$ be an integer sequence such that $b(n) = B$ after the whole transformation where we start with $A = n$, $B = 1$, $...
- 35.5k
11
votes
0
answers
492
views
Connection properties of a single stone on an infinite Hex board
This includes a series of questions.
One of the most typical examples is shown as the picture below.
An half-infinite Hex board with an one row of black stones. Black stones are separated by one ...
- 631
1
vote
1
answer
250
views
Secondary fan and KN strata
Let $\mathbb{G}_m^r$ act on the affine space $\mathbb{A}^n$ through an embedding into the open dense torus. Is there a way to calculate the 1-parameter subgroups that determine the KN strata from the ...
CommunityBot
- 1
0
votes
0
answers
73
views
Maximal number of partitions of vertex
Let $E$ be a finite vertex set of cardinality $n$. Let $F$ be a finite vertex set of cardinality $m$. For each element $x$ in $E$, there are $k$ edges connected to $k$ different elements in $F$. Now ...
- 675
0
votes
0
answers
49
views
Property of edge-vertex transitive graphs
Recently I am reading a paper (https://arxiv.org/abs/1504.00858) with respect to edge-vertex transitive graphs. What is the property of the graph that is edge transitive and vertex transitive? I know ...
- 349
21
votes
1
answer
1k
views
Tiling rectangle with trominoes — an invariant
There are two types of trominoes, straight shapes and L-shaped. Suppose a rectangle $R$ admits at least one tiling using trominoes, with an even number of L-trominoes.
EDIT: we do not admit ALL ...
CommunityBot
- 1
2
votes
1
answer
112
views
When are the 3-colorings of vertex subsets uncorrelated?
Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$.
For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...
- 695
1
vote
0
answers
189
views
The existence of solutions to linear systems of equations over the integer ring $\mathbb{Z}$
There are already detailed results on the solutions of linear equations over fields, but I'd like to inquire about any good conclusions regarding the solutions of linear equations over the integer ...
- 30.1k
3
votes
1
answer
154
views
Does Sidorenko's conjecture hold when the host graph's maxdegree/mindegree is a constant?
Does the following holds?
For every bipartite graph $H$ and every graph $G$ with $\frac{\Delta(G)}{\delta(G)}\leq 2$,
$$t(H,G)\geq t(K_2, G)^{e(H)}.$$
If not sure, is this a equal question as ...
- 891
4
votes
1
answer
431
views
"Infinity": A card game based on prime factorization and a question
I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
- 1,887
3
votes
1
answer
342
views
counting patterns in a word
Do algorithms exist to find all the patterns in a word?
I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5}
such as "...
- 1,446
6
votes
1
answer
367
views
On A057985 and A287066
Let $a(n)$ be A057985 (i.e., start with $0$ and repeatedly substitute: $0 \to 01$, $1 \to 12$, $2 \to 0$).
Let $b(n)$ be A287066 (i.e., start with $1$ and repeatedly substitute: $0 \to 01$, $1 \to 12$...
- 3,028
5
votes
1
answer
213
views
Partition an $(2n+1)$-permutation into two parts in which there are no three consective elements in given sequences
Let $a_1a_2\ldots a_{2n+1}$ ($n\geq 2$) be a given permutation of the numbers from $1$ to $2n+1$ and let
$\alpha_i=\{i,i+1,i+2\},~1\leq i\leq 2n-1$
$\alpha_{2n}=\{2n,2n+1,1\}$
$\alpha_{2n+1}=\{2n+1,1,...
- 34.3k
3
votes
1
answer
170
views
Eigenvalues of the Jack polynomials for the Calogero-Sutherland operator
The Calogero-Sutherland operator on the space of homogeneous symmetric polynomials in $n$ variables is defined by
$$
\frac{\alpha}{2}\sum_{i=1}^n x_i^2\frac{\partial^2}{\partial x_i^2} + \frac{1}{2}\...
- 188k
0
votes
1
answer
158
views
Generalized Multinomial Formula
During a computation, the following came up, and I was wondering if there is a generalized multinomial formula which can handle expressions of the following form:
Let $n\in \mathbb{N}_+$ and $w_1,\...
- 34.3k
6
votes
0
answers
268
views
A matroid parity exchange property
As part of my research, I encountered the following problem. Let $M = (E,I)$ be a matroid and let $P = \{P_1,\ldots,P_n\}$ be a partition of $E$ into (disjoint) pairs. For $A \subseteq P$, we say that ...
- 173
2
votes
0
answers
164
views
Motivations/spin-offs of the Kontsevich conjecture (1997) on polynomial count varieties related to graph polynomials
"Kontsevich conjectured that the number f(G,q) of zeros over the finite field with q elements of a certain polynomial connected with the spanning trees of a graph G is polynomial function of q.&...
- 24.9k
9
votes
1
answer
497
views
Quantum probabilistic method?
The probabilistic method uses arguments from probability to prove deterministic statements. This has been applied to diverse fields such as combinatorics, topology and number theory. In this method, ...
- 188k
16
votes
1
answer
804
views
Existence of a faithful irreducible representation using Möbius function
Let $G$ be a finite group, $L(G)$ its subgroup lattice and $\mu$ the Möbius function.
Consider the Euler totient of $G$ defined as follows:
$$ \varphi(G) = \sum_{H \le G}\mu(H,G) |H| $$
Let $X=\{M_1, \...
- 4,219
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
0
votes
0
answers
60
views
Getting lower bounds for the Hamming weight of solutions to the Frobenius equation
We have two vectors $A=\{a_{1},...,a_{z}\},X=\{x_{1},...,x_{z}\}\in\mathbb{N}^{z}$ and $n\in\mathbb{N}$ with $A\cdot X=n$ as their normal Euclidean inner product.
The values of $A$ and $n$ are known ...
- 97
4
votes
3
answers
347
views
Minimal data required to determine a convex polytope
Let $P\subset \Bbb R^d$ be a convex polytope.
Suppose that I know
its combinatorial type (aka. the face-lattice),
the length $\ell_i$ of each edge, and
the distance $r_i$ of each vertex from the ...
- 13.6k
3
votes
1
answer
91
views
Asymptotic growth rate for primitve S-adic systems
It is known that for a primitive substitution $S:\mathcal{A}\to \mathcal{A}^+$, there exists constants $c,C>0$ such that
$$ c\theta_S^n \leq \vert S^n(a)\vert \leq C \theta_S^n \quad \text{for all} ...
- 2,621
1
vote
1
answer
77
views
Sequence derived from transform of a given vector (with Fibonacci as partial sums)
Let F_n be A000045 (i.e., Fibonacci numbers). Here
$$
F_n = F_{n-1} + F_{n-2}, \\
F_0 = 0, F_1 = 1
$$
Let $\operatorname{wt}(n)$ be A000120 (i.e., number of ones in the binary expansion of $n$). ...
- 7,226
7
votes
1
answer
286
views
When is a Schreier coset graph vertex transitive
When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?
It is well known that when $H$ is normal, the Schreier coset graph ...
- 343
0
votes
0
answers
61
views
Combinatorial counting question related to count (anti)commuting N-tuples of matrices (more generally $(X_1,...X_n): F(X_i,X_j)=0$ - only one F)
Consider some finite set $S$ (can be matrices over $F_p$), consider some symmetric relation $F(s1,s2)$ which values are True or False (for example - matrices (anti)commutate or not).
Question 1: can ...
- 24.9k
2
votes
1
answer
184
views
Count N-tuples of commuting matrices over $F_q$ is given by polynomials with pattern $\sum q^{A_i(N)} P_{i}(q) $, where $P_i$ - do not depend on $N$?
Count pairs of $k \times k$ commuting matrices over finite field $F_q$ is given by certain polynomials in $q$ (which is quite rare phenomena for algebraic varieties) and have interesting generating ...
- 24.9k
3
votes
2
answers
453
views
Guess the next polynoms in the sequence (MO vs. AI :), count anticommuting $F_p$-matrices, P. Hrubeš conjecture
Here is a sequence of polynoms - (presumably) counting N-tuples of ANTI-commuting 2x2 matrices over $F_p, p>2$. (That is just the case of 2x2 matrices, and (surprisingly) it is not so easy to see a ...
- 2,178
10
votes
0
answers
609
views
A robust version of Harper's theorem
Let $S$ be subset of $\{0,1\}^n$ with cardinality $k$.
Denote by $\Gamma_r(S)$ the union of all Hamming balls with centers in $S$ and radius $r$.
Harpers's theorem states that $\Gamma_d(S)$ is minimal ...
- 2,576
6
votes
1
answer
545
views
Balancing act for infinite walks
Think of a one-dimensional infinite walk as a map $$w\colon \mathbb{N}\to \{-1,1\}.$$ (If it is more convenient, you can think of a walk as a subset of $\mathbb{N}$, or as a binary word, or as any ...
- 981
2
votes
1
answer
252
views
On a A089039 and pair of sequences with simple recursion
Let $a(n)$ be A089039 (i.e., number of circular permutations of $2n$ letters that are free of jealousy). Here
$$
a(n) = \sum\limits_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!(n-k-1)!^2}{(k-...
- 34.3k
3
votes
2
answers
1k
views
How many semidirect products are there?
This question was initially proposed to me by two friends. Given an integer $n$, how many isomorphism classes are there for semidirect products $\mathbb{Z}/n\mathbb{Z}\rtimes\mathbb{Z}/2\mathbb{Z}$?
...
- 63.9k
6
votes
3
answers
236
views
Refinement-minimal intersecting covers
Motivation. Yesterday I was sitting idly in the train, contemplating the train network. I noticed that a lot of lines (not all) intersected, and some pairs of lines intersected in quite a few stations....
- 41.9k
2
votes
0
answers
41
views
graphs which have polynomial bounded number of cycles
How does the graph class defined as those graphs which have polynomial (or quasi polynomial) bounded number of cycles look? (in number of vertices)
I suspect it will rather non-interesting as ...
- 129
6
votes
2
answers
661
views
Cut locus in a graph
I am wondering if the concept of a cut locus has been defined and explored in discrete graphs, rather than their usual home on manifolds?
The Wikipedia definition (which I believe I (co-?)authored) is:...
- 63.9k
3
votes
0
answers
91
views
Existence of a $p$-regular subgraph: is it true for $p=6$?
It's well known that any loopless graph $G = (V,E)$ with average degree bigger than $2p − 2$ and maximum degree at most $2p − 1$ contains a $p$-regular subgraph for any prime power $p$.
But we don't ...
- 63.9k
17
votes
1
answer
924
views
List of problems that Erdős offered money for?
Is there a list somewhere of all the problems that Erdős offered cash awards for, including both solved and unsolved problems? One would think that the answer is yes, but so far I have had no luck ...
- 24.2k