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.

Filter by
Sorted by
Tagged with
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{...