All Questions
Tagged with combinatorics or co.combinatorics
11,023 questions
3
votes
1
answer
123
views
Conjecture about separating union-closed families
Consider a separating union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.
Let $U(\mathcal{F})$ be the union of all sets in $\mathcal{F}$ (the universe). Let ...
- 1,000
3
votes
0
answers
122
views
Garnir elements basic question
Prop. 2.6.3 in Sagan's book The symmetric group discusses Garnir elements, and says:
"If $|A\cup B|$ is greater than the number of elements in column $j$ of $t$, then $g_{A,B} \mathbf{e}_t=0$.&...
- 63.9k
1
vote
0
answers
83
views
Non-vanishing of product of zero divisors in quotients modulo $n$
This might be of practical importance and even partial answer will help.
Let $n$ be odd squarefree integer with known factorization $n=\prod p_i$
with $N$ prime factors.
Later we are not asking about ...
- 25.4k
9
votes
1
answer
460
views
Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$
For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\...
- 12.9k
1
vote
1
answer
117
views
Generate all non-isomorphic caterpillar trees with $n$ vertices
A caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.
From Wikipedia, I see that their count is also available in OEIS A005418. My question is, ...
- 34.3k
7
votes
0
answers
176
views
Sumsets that contains many squares, Improvement on the bound
I'm being troubled by this problem on AoPS:
https://artofproblemsolving.com/community/c6h1998237p13955033
I searched for any literature related to it such as
Nguyen, Hoi H., and Van H. Vu., Squares ...
- 1,354
8
votes
1
answer
567
views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space).
We need to ...
- 156k
3
votes
0
answers
317
views
Prime Hadamard matrices
Assume that $n$ is a sufficiently large number. Is there a Hadamard matrix $H_{4n \times 4n}=(h_{ij})$ with the last row and the last cloumn $J$ (thet is, for every $k$, $h_{k,4n}=1$ and $h_{4n, k}=1$)...
- 696
1
vote
1
answer
452
views
About the Hadamard conjecture
On the wikipedia article about Hadamard Matrix it says that "The smallest order that cannot be constructed by a combination of Sylvester's and Paley's methods is $92$"
But it also says that ...
- 696
5
votes
0
answers
583
views
Dimension inequality for subspaces in field extensions
Let $K\subset L$ be a field extension and $A, B\subset L$ be $K$-subspaces of $L$ of finite positive dimensions. Assume further that for every $a, b \in L$ and every nontrivial proper finite ...
- 429
3
votes
1
answer
162
views
Counting equal covering sets
Definition. We call a set $C$ of sets to be an equal covering set of $S$ if the elements of $C$ are all the same size and each element of $S$ is contained an equal number of times throughout the sets ...
- 34.3k
3
votes
1
answer
131
views
Sparse "bijection-proof" subsets of $[\mathbb{N}]^2$
We call a collection ${\cal S}\subseteq {\cal P}(\newcommand{\N}{\mathbb{N}}\N)$ bijection-proof if for any bijection $\varphi:\N\to\N$ there is $T\in{\cal S}$ with $\varphi(T) \in {\cal S}$.
For any ...
- 981
15
votes
3
answers
3k
views
Noncombinatorial proofs of Ramsey's Theorem?
I know of 2(.5) proofs of Ramsey's theorem, which states (in its simplest form) that for all $k, l\in \mathbb{N}$ there exists an integer $R(k, l)$ with the following property: for any $n>R(k, l)$, ...
- 4,713
6
votes
0
answers
130
views
Bent vectors and $\pm 1$ eigenvectors with respect to non-Sylvester Hadamard matrices
A Hadamard matrix is an $n\times n$-matrix $H$ where each entry in $H$ is $\pm 1$ and where $H/\sqrt{n}$ is orthogonal. It is well-known that if $H$ is an $n\times n$-Hadamard matrix, then $n<3$ or ...
3
votes
1
answer
140
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 18.9k
12
votes
1
answer
730
views
Two remarkable weighted sums over binary words
This question builds off of the previous MO question Number of collinear ways to fill a grid.
Let $A(m,n)$ denote the set of binary words $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_{m+n-2})$ consisting ...
CommunityBot
- 1
2
votes
1
answer
105
views
"Spanning trees" for connected linear hypergraphs
Starting point. For every simple, undirected graph $G=(V,E)$ there is $E_0\subseteq E$ such that $(V,E_0)$ is minimally connected: the spanning tree. The goal of this question is to find out whether ...
- 13.4k
5
votes
1
answer
259
views
Is a weak version of the three sets Lemma provable in ZF?
The Three Sets Lemma is the following Lemma:
Lemma: Let $f(x)$ be a function from $X$ to $X$ where $f(x)$ has no fixed points. Then there exists a partition of $X$ into three disjoint sets $X_1$, $X_2$...
- 12.9k
16
votes
3
answers
10k
views
Proving that a poset is a lattice
I discovered experimentally that a certain finite poset (sorry, I cannot give its definition here) seems to be in fact a (non-distributive, non-graded) lattice. The covering relations are reasonably ...
- 4,219
0
votes
0
answers
174
views
3D generalization of Gaussian q-binomial coefficient
It is known that the coefficient of $q^t$ in Gaussian binomial coefficient $\binom{m+n}m_q$ equals the number of permutations of the multiset $\{0^m, 1^n\}$ with $t$ inversions.
Is there a closed ...
- 175
7
votes
1
answer
1k
views
Is the Gauss hypergeometric series ${}_2F_1\bigl(\frac{1}{2},\frac{1}{2};2;t\bigr)$ an elementary function?
For $\alpha,\beta\in\mathbb{C}$ and $\gamma\in\mathbb{C}\setminus\{0,-1,-2,\dotsc\}$, Gauss' hypergeometric function ${}_2F_1(\alpha,\beta;\gamma;z)$ can be defined by the series
\begin{equation}\...
- 1,053
6
votes
1
answer
402
views
Szemerédi-Trotter theorem for planes and lines
The Szemerédi-Trotter theorem states:
Theorem Let $P$ be a set of $m$ lines in $\mathbb R^2$ and let $L$ be a set of $n$ points in $\mathbb R^2$. Then
$$\#\{(p,\ell)\in P\times L:p\in\ell\}\lesssim (...
- 12.9k
1
vote
1
answer
142
views
Asymptotics on sum of product of binomial coefficients
I'm interested in the behavior of the summation
$$S(a,b)=\sum_{k\ge 0}\binom{a-k}{k}\binom{b}{k}.$$
For a fixed $\delta>0$, I would like asymptotic bounds on $S(a,\delta a)$.
With $\delta=1$, this ...
- 109k
2
votes
0
answers
147
views
Average number of cycles in a directed regular graph?
A directed random regular graph is a graph where all vertices have exactly $d_{\rm in}$ edges going in and $d_{\rm out}$ going out. If the graph is undirected, i.e. all vertices have degree $d$, then ...
- 109
9
votes
1
answer
889
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
- 12.9k
0
votes
0
answers
106
views
How can I transform every graph into one with constant out-degree?
I am working on my master thesis and try to implement a new shortest path algorithm from the following paper: https://arxiv.org/abs/2203.03456
In some of the functions (for example ScaleDown), ...
- 34.3k
1
vote
0
answers
88
views
Is there an efficient algorithm for finding a fundamental cycle basis of a graph with the fewest odd cycles? Failing that, a hardness result on this?
I can think of a greedy algorithm:
Let $B$ be a fundamental cycle basis of graph $G$ induced by spanning tree (or forest) $T$
For $e\in T$, let $n_+(e)$ ($n_-(e)$) be the number of even (odd) cycles ...
- 33
8
votes
2
answers
509
views
Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression
Let $\mathbb{N}$ denote the set of non-negative integers. We say $A\subseteq \mathbb{N}$ is a finite arithmetic progression if there are $a, n, d\in\mathbb{N}$ with $d \geq 1$ and $n \geq 2$ such that ...
- 48.9k
1
vote
0
answers
77
views
Decomposition of $BwBw^{-1}B$
Let $(B,N,W,S)$ be a Tits system with $W$ a finite coxeter group.
Let $w\in W$, consider $BwBw^{-1}B$, then by Bruhat decomposition, it is a disjoint union of some $BxB$, $x\in W$.
My question: Let $X\...
- 653
1
vote
1
answer
200
views
Sign of the permutation when I show that $\star{\star w}= (-1)^{n(n-k)} w$ for the Hodge operator
Let $w=\sum_{I} a_{I}dx_{I}$ be a $k$-form in $\Bbb R ^n$. Let us consider the Hodge operator in a combinatorial form, i.e. as an $(n-k)$ form such that
$$\star(dx_{i_{1}} \wedge \dotsb \wedge dx_{i_{...
- 6,367
4
votes
1
answer
224
views
Shrinking and expanding pairs in bijections $\varphi:\mathbb{N}\to\mathbb{N}$
Motivation. If we consider any bijection $\varphi:\newcommand{\N}{\mathbb{N}} \N \to \N$, we say integers $m\neq n$ are shrinking with respect to $\varphi$ if $|m-n|>|\varphi(m) - \varphi(n)|$, and ...
- 10.6k
4
votes
1
answer
276
views
Preserving simple-connectedness under intersection complexes
Given a simplicial complex $X$, and a family of its subcomplexes $\{U_i\}_{i\in I}$, we define the corresponding intersection complex to be the simplicial complex $X_U$ with vertex set $I$ where $A \...
- 55.9k
4
votes
2
answers
234
views
Is there always a permuted tuple of $n+1$ elements such that multiplying elementwise$\bmod n + 1$ on $(0, 1, \ldots, n)$ yields a binary $n+1$ tuple?
Allow me to explain and give examples of something I've been playing around with.
Let $A$ be the $n+1$ tuple of the form $(0, 1, 2, \ldots, n)$. Let $k = n + 1$ be the number of elements.
My question ...
- 156k
6
votes
1
answer
95
views
Minimum area of the symmetric difference of odd number of translated copies of a unit circle $C$
Let $C$ be the unit circle in a plane. Take an odd number $n$ of translated copies of $C$ and take their symmetric difference $D$. Is it true that the area of $D$ should be at least that of $C$?
If $C$...
- 6,101
6
votes
1
answer
1k
views
Jacobsthal function related to squares
The ordinary Jacobsthal function $j$ is defined by setting $j(n)$ as the smallest number $m$ such that, for each consecutive $m$ integers, at least one of the numbers is coprime to $n$. There are ...
CommunityBot
- 1
4
votes
0
answers
113
views
Find necessary & sufficient conditions for two families of sets to have $m$ pairwise disjoint common partial transversals of given sizes
Let $S$ be a finite set, $I$ a finite index set, $\mathcal A=(A_i:i\in I)$ and $\mathcal B=(B_i:i\in I)$ families of subsets of $S$.
For $J\subseteq I$, let $A(J)$ denote $\bigcup_{j\in J} A_j$.
A ...
- 19.6k
3
votes
0
answers
120
views
Number of spheres in complexes constructed from a Steiner Triple System
Let $M$ be a perfect matching on an even number of vertices $n$, and let $\mathbb{S}_n$ be the symmetric group on $n$ vertices. Next, we construct a graph $G_k := ([n], E)$ using $k$ randomly permuted ...
- 81
3
votes
1
answer
208
views
The signs of some mean-zero random variables
Let $X$ be a discrete random variable supported on $\{−5,\dots, 6\}$ in which the outcomes have the following respective probabilities: $$\begin{array}{rc}
n & p(n) \\ \hline −5 & 6/36 \\ −4 &...
- 19.7k
6
votes
1
answer
200
views
Subspaces of $\mathbb{F}_2^N$ containing many pairs of far apart vectors
Let $S$ be a subset of vectors in $\mathbb{F}_2^{3n}$ having Hamming weight $n$. Suppose that $S$ contains $m$ pairs of vectors having disjoint supports (that is, they are at Hamming distance $2n$ ...
CommunityBot
- 1
1
vote
0
answers
113
views
Representing A329369 using A358612
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\dotsc,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
CommunityBot
- 1
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 5,429
2
votes
1
answer
119
views
Asymptotic size of largest subset in $\mathbb F_p^2$ defining only lines of different slopes
Suppose that all lines defined by pairs of distinct elements in a subset of $\mathbb F_p^2$ have different slopes. How large can such a subset be asymptotically (for primes $p\rightarrow \infty$)?
...
- 10.4k
2
votes
0
answers
78
views
Partitions of bent vectors
Let $H=\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}.$ Let $A^{\otimes N}$ denote the tensor product of the matrix $A$ with itself taken $N$ times. We say that a vector $v$ of ...
1
vote
0
answers
164
views
Combinatorial question related to Hankel-type matrices
Let $\mathbb{N}$ be the set of non-negative integers. Let $n\geq 2, d$ be positive integers. I would like a lower bound on the largest integer $r$ for which the following property holds:
For any ...
- 980
1
vote
0
answers
93
views
15-game graph contains a Hamiltonian path ? Lovász conjecture for groupoids, loops, quasigroups , etc?
Typically Cayley graphs are defined for groups and generators sets S. But basically one only needs some set S and another set V and partially defined operation SxV->V, then one defines graph with ...
- 24.9k
5
votes
3
answers
959
views
A variant of set cover problem reformulated
Given a universe set $U$ and $n$ sets of sets $A_i$ ($i=1, \cdots, n$). Each set $A_i$ contains $k_i$ subsets of $U$, i.e., $A_i=\{B_{ij}: j=1, \cdots, k_i\}$ where $B_{ij}$ is a subset of $U$. I have ...
0
votes
0
answers
62
views
longest element in set $W_\gamma wW_\nu vW_\mu$
Let $(W,S)$ be a finite Coxeter group, $W_\gamma,W_\nu,W_\mu$ be three parabolic subgroups. For $w,v\in W$,
let us consider the set $W_\gamma wW_\nu vW_\mu$. Does there exixt a unique longest element (...
- 653
15
votes
3
answers
1k
views
Does anyone remember what happened to the experimental search for polynomial identities for $\pi$?
So a while back I was on the internet and had encountered a website containing an experimental search for identities for $\pi$. My memory was that the page belonged to either Jonathan Sondow or ...
- 2,836
0
votes
0
answers
96
views
"Degenerate" Schur polynomials
Let's say that a Schur polynomial is degenerate if its number of variables is less than the weight of the partition it is associated to. For example, according to Sage, the Schur polynomial of the ...
- 2,560
1
vote
0
answers
101
views
Effortless automated proofs for "simple" formulae?
From small cases to all of them. This is in the spirit of 15 theorem see https://en.wikipedia.org/wiki/15_and_290_theorems
EXAMPLE : Suppose you have the following problem: P(a)
For any fixed non ...
- 1,306