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,515
questions
1
vote
1
answer
282
views
A combinatorial problem about partitions [closed]
A partition of $n$ is a unordered list, whose sum is exactly $n$.
The total number of $2$’s in all partitions of $n$ is equal to the total
number of singletons in all partitions of $n−1$. A singleton ...
2
votes
2
answers
232
views
Number of edge-disjoint cycles in a holey graph
Let $\Gamma$ be a connected graph with $H^1(\Gamma) \cong \mathbb{Z}^d$. Can we give a lower bound (preferably of the form $\gg d$) on the maximal number of edge-disjoint cycles one can find in $\...
9
votes
1
answer
505
views
Shortest almost trivial element of free group [duplicate]
Let $F_n$ be the free group with $n$ generators $\gamma_1,\dots,\gamma_n$.
Consider the homomorphisms $h_i\colon F_n\to F_{n-1}$ defined by adding the relation $\gamma_i=1$ in $F_n$.
What is the ...
51
votes
0
answers
2k
views
Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
A very specific case of Reed's Conjecture
Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
4
votes
0
answers
195
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 ...
1
vote
1
answer
164
views
Lower bound on outdegree/indegree in oriented graph to guarantee cycle of length at least $k$
An oriented graph is a digraph without any self-loops, multiple arcs, or 2-cycles. What is the smallest minimum outdegree of an oriented graph on $n$ vertices that ensures there will always be a cycle ...
2
votes
0
answers
103
views
Proof that a pandiagonal Latin square of order $n$ exists iff $n$ is not a multiple of $2$ or $3$?
A pandiagonal Latin square of order $n$ is an assignment of the numbers $\{0,\ldots,n-1\}$ to the cells of an $n \times n$ grid such that no row, column, or diagonal of any length contains the same ...
1
vote
2
answers
202
views
Relationship between fixed points and inversions in permutations
Inversions in a permutation $Y$ are defined as pairs where $Y_a < Y_b$ but $a > b$, while fixed points in $Y$ are defined as elements where $Y_a = a$ (i.e., 1-cycles). Let $S_\alpha$ be the set ...
2
votes
1
answer
298
views
Maximum number of leaf blocks in 3-regular (cubic) graph
The definition of block is
Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.
Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in ...
0
votes
2
answers
93
views
Points based partial ranking
I want to rank a population $P=\{P_1,\ldots,P_n\}$. I am given a set $R=\{R_1,\ldots,R_k\}$ of partial rankings. The partial rankings may have varying sizes (e.g. the first ranking ranks only 8 ...
5
votes
1
answer
139
views
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3-connected?
Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find
Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (...
0
votes
0
answers
70
views
Graphs where any cycles are adjacent
Graphs with minimum degree three that any two cycles have common vertex, have been characterized by Lovász. I see this result from the Plumer article (On the cyclic connectivity of planar graphs (...
12
votes
2
answers
396
views
Regularizing graphs
Let $G$ be a simple graph (undirected, no loops or parallel edges), with maximum degree $\Delta(G)$. I would like to add edges to the graph to make it regular, without increasing the maximum degree.
...
8
votes
0
answers
148
views
Inversions for parity preserving presentations
I've gotten stuck on a slightly random combinatorial question, and I'm doing a bit of a shot in the dark here to see if someone else has thoughts about it. I'm interested in studying a permutation of ...
17
votes
11
answers
4k
views
Applications of measure, integration and Banach spaces to combinatorics
I'm going to be teaching a Master's level analysis course (measure theory, Lebesgue integration, Banach and Hilbert spaces, and if there's time, some spectral or PDE stuff) in the fall. My problem is ...
3
votes
1
answer
201
views
Partition numbers and Gaussian binomial coefficient
Let $a(n)$ be A000041 i.e. the number of partitions of $n$ (the partition numbers).
Let $T(n, k)$ be A083906. Here
$$
T(n, k) = [q^k]\sum\limits_{m=0}^{n} \binom{n}{m}_q
$$
where $\binom{n}{m}_q$ ...
6
votes
3
answers
573
views
Reference for partial Hadamard matrices
Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
0
votes
1
answer
333
views
Log associahedra and log noncrossing partitions--raising ops and symmetric function theory for $A_n$ (references)
Where do the following three sets $[LA]$, $[ILA]$, and $[LN]$ of partition polynomials appear in the literature?
There are two sets of partition polynomials, not in the OEIS, that serve as the ...
2
votes
0
answers
62
views
cocycle datum for principal $G$-bundle over base space Delta set
Let $X$ be topological realization of a (finite)
Delta set, $G$ a finite group and $p: P \to X$ a
principal $G$-bundle.
Let's recall the standard fact that more generally any
numerable principal G-...
2
votes
1
answer
299
views
q-polynomials in terms of a basis
Consider the polynomials
$$f_n(q)=\prod_{j=1}^n(1+q^j) \qquad \text{and} \qquad g_m(q)=1+q+q^2+\cdots+q^m.$$
I'll list a few examples to motivate my question. Direct calculations show that
$$f_1=g_1, \...
2
votes
1
answer
215
views
Name for generalization of trees to digraphs
One definition of tree in graph theory could be as follows:
A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices.
This suggest a possible ...
1
vote
0
answers
81
views
Interpreting multiple property tests at different values of $\epsilon,\delta$ [closed]
I am doing some work in the area of Property Testing, as in Goldreich, Goldwasser, and Ron (2008) or the textbook Introduction to Property Testing (Goldreich). In this framework, I run a test to see ...
22
votes
4
answers
2k
views
What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?
So I know that error-correcting codes are sphere packings in the Hamming metric, and that intuition and technical tools from the Euclidean case can often be applied to the finite-field case and vice ...
9
votes
2
answers
446
views
Are there more paths exiting a box in $\mathbb{Z}^2$ to the right if I remove some edges to the left
Suppose that I am given the graph $G = (V,E)$ where
$V = \{ 1, 2, \dots 2N+1 \} \times \{ 1, 2, \dots 2N+1 \} $
and there is an edge between two vertices $(n,m)$ and $(n',m')$ if and only if
$\vert n-...
7
votes
2
answers
1k
views
Planar layouts of bipartite graphs
Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.
It would be very convenient if there was a ...
11
votes
1
answer
676
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 ...
2
votes
1
answer
171
views
Optimal prefix-free code design with a complex objective function
We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...
5
votes
1
answer
266
views
Expected number of coin flips before you see a $k$-term arithmetic progression of heads
Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...
1
vote
1
answer
108
views
A bound on the number of partial transversals of a latin square
A Latin Square (LS) of order $n$ is an $n$ on $n$ matrix, each entry contains one of the symbols $1,2,\ldots,n$, and every row and every column contains each symbol exactly once. A (complete) ...
1
vote
1
answer
283
views
Trees and spans of edge labels
Let $T$ be a rooted tree with $m$ leaves. Label every edge with a label of the form $x_i$ or $-x_i$, for some letter $x_i$. For each leaf in the tree, consider the formal linear combination $v$ ...
2
votes
1
answer
142
views
$R$-recursion for the A143017
Let $a(n)$ be A143017 i.e. number of $\{2-1-3, 2'^e-31\}$-avoiding permutations of size $n$ (see definition in the Elizalde paper). Here
$$
a(n) = \frac{1}{n}\sum\limits_{k=0}^{\left\lfloor\frac{n}{...
4
votes
1
answer
277
views
What are bit strings where all non-trivial rotations match at a minimum number of places called?
Basically, I'm trying to figure out the name of the thing I want to look up. All the terms I've looked up so far have been related, but not close enough to be useful.
I'm trying to find bit strings ...
2
votes
0
answers
99
views
The fluctuations of a random path
Suppose I have a $n \times n$ square grid and for each square, I assign 1 with probability $\frac{1}{2}$ and 0 with probability $\frac{1}{2}$. On the boundary, I put 1s on the lower half and 0s on the ...
15
votes
1
answer
866
views
Scrambling a “Connections” grid
Given a 4-by-4 array of distinct words, is it possible to scramble the array in four different ways in such a fashion that each possible word-pair appears adjacently in one of the five arrays (the ...
4
votes
1
answer
307
views
The upper bound of edges of the generalized cactus graphs
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple ...
0
votes
1
answer
181
views
Constructing a family of $3$-wise independence functions from $\mathbb{Z}_p^n \rightarrow \mathbb{Z}_p$
A family of function hash functions $\mathcal{H}:\{h:N\rightarrow M\}$ is call $k$-wise independent if whenenver $h$ is drawn uniformly from $\mathcal{H}$, let $x_1,\ldots,x_k$ be distinct elements of ...
1
vote
0
answers
115
views
On a Fibonacci and binary
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
$$
\ell(n) = \left\lfloor\log_2 n\right\rfloor
$$
Let
$$
T(n, k) = \left\lfloor\frac{n}{2^k}\...
26
votes
6
answers
2k
views
Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?
This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the ...
9
votes
0
answers
278
views
Inequality for symmetric polynomial functions of log concave variables
Let $(x_i)_{i \ge 1}$ be a log-concave (resp. log-convex) sequence of non-negative real variables. In other words, for $i \ge 2$, we have $x_i^2 \ge x_{i-1}x_{i+1}$ (resp. $x_i^2 \le x_{i-1}x_{i+1}$).
...
7
votes
1
answer
140
views
Set-theoretic solutions of YBE for $n=3$
Is there a list of all set theoretic solutions $S:X \times X \to X \times X$ of the YBE for $X=\{1,2,3\}$? Or is it known how many solutions there are? I mean, $S_9$ is big but maybe not too big to ...
16
votes
1
answer
684
views
Unbalancing lights in higher dimensions
In ''The Probabilistic Method'' by Alon and Spencer, the following unbalancing lights problem is discussed. Given an $n \times n$ matrix $A = (a_{ij})$, where $a_{ij} = \pm 1$, we want to maximise the ...
5
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 ...
7
votes
0
answers
128
views
How many simplicial spheres with $n$ vertices and $N$ facets?
Let $s_d(n,N)$ be the number of different $d$-dimensional simplicial spheres on $n$ labelled vertices and $N$ facets (= $d$-simplices). I am in search for the best know upper bounds, especially for $d\...
0
votes
0
answers
55
views
How many rigid 4-regular graphs are there?
I am interested in any formulas for the number of globally rigid 4-regular graphs, or Laman graphs of degree at most 4, on $n$ vertices. The bound can be for graphs with labeled or unlabeled vertices.
0
votes
0
answers
75
views
High probability bound on number of sparse solutions to Gaussian linear system
Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{...
1
vote
1
answer
308
views
Khovanskii's theorem on iterated sumsets
I was watching Gowers video lectures "Introduction to Additive Combinatorics" (my question is about the statement he made at the 21st minute) and came across wonderful theorem due to ...
2
votes
0
answers
81
views
Splitting natural numbers into subsets with sums equal to A066258
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 $a(n)$ be A066258 i.e.
$$
a(n) = F(n)^2F(n+1)
$$
Let $b(n)$ be A345253 i.e. maximal ...
6
votes
2
answers
1k
views
Acyclic matching property in $\mathbb{Z}/p\mathbb{Z}$
Let $B$ be a finite subset of the group $G$ which does not contain the neutral element. For any subset $A$ in $G$ with the same cardinality as $B$, a matching from $A$ to $B$ is defined to be a ...
30
votes
7
answers
67k
views
Notation for the all-ones vector [closed]
What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, having length one? The zero vector is frequently ...
11
votes
2
answers
620
views
Can we balance $2$-powers?
If a sequence of reals $-1<x_1,\dots,x_k<1$ satisfies
\begin{equation*}
x_{i+1}=
\begin{cases}
2x_i, & \text{if } 2|x_i|<1 \\
2x_i-2, & \text{...