# 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.

6,658 questions

**0**

votes

**0**answers

16 views

### Shifts-induced group of a toroidal cube

Consider $[n]^d$ -- a $d$-dimensional toroidal cube with side length $n$ divided into $n^d$ unit cubes. Define $k$-shift as a following permutation type on unit cubes: choose $S \subset [n]$ with $|S| ...

**1**

vote

**1**answer

25 views

### Finite sequences realizable by degree difference in digraphs

Let $n>0$ be an integer, and let $[n] = \{1,\ldots,n\}$. A function $f:[n]\to \mathbb{Z}$ is said to be in- and out-degree-realizable (or io-realizable for short) if there is a directed graph $G = (...

**1**

vote

**1**answer

52 views

### Intersection of quadratic equations with planted solutions?

Suppose we have two quadratic equations in $\mathbb R[x_1,\dots, x_n]$. What is the expected dimension of their intersection?
In general what can we say about intersection of $k$ quadratics? How many ...

**4**

votes

**1**answer

81 views

### A closed formula for $\det(\partial/\partial U)^p\prod_{i=1}^n\prod_{j=1}^p U_{i\sigma_j(i)}$

This is a continuation of this question. Is there a simple formula for
$$I(\sigma_1,\cdots,\sigma_p)=(-1)^\sigma\left(\left(\det\left(\frac{\partial}{\partial U_{ij}}\right)_{i,j=1}^n\right)^p \prod_{...

**2**

votes

**0**answers

72 views

### Tiling rectangles using all squares of sides 1, 2, 3, …, n

Do integers n greater than 2 exist such that all the squares of sides 1, 2, 3, ..., n can be partitioned into two or more sets each of whose squares can be used to tile a rectangle?

**4**

votes

**1**answer

98 views

### RSK and crystal operators

Is there a good reference on how RSK (and the 3 other variants)
interact with crystal operators on the semi-standard tableaux $(P,Q)$ in the image?
That is, we have biwords, $W$ which are in ...

**5**

votes

**1**answer

117 views

### Strict unfriendly partitions

Given a graph $G$, an unfriendly partition of $G$ is a partition of $V(G)$ into two classes, such that for every class, every vertex has at least as many neighbors in the other class as in its own ...

**5**

votes

**3**answers

146 views

### Non-containing subsets of two sizes

Let $T=\{1,2,\dots,2n+1\}$. What is the largest $k$ such that we can choose $k$ subsets of size $n$ and $k$ subsets of size $n+1$ of $T$ so that no chosen subset contains another?
$k=\binom{2n}{n-1}$ ...

**5**

votes

**0**answers

106 views

### A question about dominating circuits in cubic graphs

Let $G$ be a 3-connected cubic graph with a dominating circuit $C$, that is, a circuit such that all edges in $G$ have at least one endvertex in $C$. Let $D$ be another circuit and let the symmetric ...

**4**

votes

**0**answers

68 views

### Discrepancy of the finite approximation of the Lebesgue measure

Let $\mu$ be a probabilistic measure on the unit square $Q$ which is the average of $N$ delta-measures in some points in this square; let $\lambda$ denote the Lebesgue measure on $Q$. What is the rate ...

**2**

votes

**1**answer

87 views

### Edge colorability and Hamiltonicity of certain classes of cubic graphs (MO graphs)

Let $G$ be a simple cubic graph (that is, 3-regular). A dominating circuit of $G$ is a circuit $C$ such that each edge of $G$ has an endvertex in $C$. The circuit $C$ is chordless if no edge which is ...

**14**

votes

**1**answer

168 views

### Finding a plane numerically

Suppose I have three large finite sets $\{x_i\}$, $\{y_i\}$ and $\{z_i\}$;
they are obtained by measuring coordinates of a collection of vectors in $\mathbb{R}^3$, but I do not know which triples ...

**2**

votes

**1**answer

110 views

### Spectral radius of Markov averaging operator on graphs

The definition of Markov operator which I am familiar with:
For a graph $G=(V,E)$, Markov's operator upon a function
$\varphi:V\rightarrow\mathbb{C}$ , $\varphi\in L^2(G,\nu)$ ($\nu(v):=\deg(v)$) ...

**2**

votes

**0**answers

59 views

### Generalization of Cauchy's eigenvalue interlacing theorem?

Cauchy's Interlacing Theorem says that given an $n \times n$ symmetric matrix $A$, let $B$ be an $(n-1) \times (n-1)$ principal submatrix of it, then the eigenvalues of $A$ and those of $B$ interlace.
...

**6**

votes

**0**answers

181 views

### Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...

**6**

votes

**1**answer

226 views

### Taylor's polynomials and loss of real roots

Real-rootedness, log-concavity, and unimodality are intertwined properties. It's in this light that I was prompted to ask the question below.
Suppose the roots of a polynomial $p(x)$ are all real and ...

**2**

votes

**1**answer

142 views

### History of algebraic graph theory

I need a source about the history of algebraic graph theory. I mean for solving which problems or responding to what needs it was created?
Indeed, I want to write a note about the history of the ...

**5**

votes

**1**answer

122 views

### Large dominating sets in tournaments

It is known that in any tournament with $n$ vertices, there is a dominating set of size no more than $\lceil \log_2 n\rceil$. (See Fact 2.5 here.)
What are tournaments such that any dominating set ...

**0**

votes

**1**answer

39 views

### Circular (bracelets) permutations with alike things(reflections are equivalent) using polya enumeration

Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+..... = N?
A similar question exists but it doesn't address the case ...

**5**

votes

**1**answer

156 views

### Intuition for the expected number of returns of a Dyck path

It is known that the expected number of returns of a Dyck path of semilength $n$ to the $x$-axis is $3n/(n+2)$, so it tends to 3 as $n\to\infty$. (This was proved in the Dyck path context by Deutsch ...

**3**

votes

**1**answer

118 views

### Multiplication in $Z(\mathbb{C}S_n)$ [duplicate]

I am trying to multiply two generators of center $Z(\mathbb{C}[S_n])$ of ring algebra of symmetric group of $n$ elements. We know that these generators are given by sums of conjugacy classes in $S_n,$ ...

**2**

votes

**0**answers

41 views

### Optimal $f$-vector properties of translationally invariant 3-honeycombs for error correction of a photonic quantum computer

In terms of the $f$-vector for a translationally invariant (in $\Bbb R^3$) honeycomb define
$$
\begin{split}
v &= \max\left( \frac{f_1}{f_0}, \frac{f_2}{f_3}\right), \\
f &= \max\left( \frac{...

**10**

votes

**1**answer

341 views

### Coincidences between average Catalan tableaux

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices:
$$
P_n \, := \, \frac{1}{C_n} \, \...

**4**

votes

**1**answer

137 views

### Edge coloring a cycle plus triangles graph and a stronger problem

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that ...

**1**

vote

**1**answer

46 views

### Injective edge choice functions in linear hypergraphs

A linear hypergraph is a hypergraph $H=(V,E)$ such that
for $e\in E$ we have $|e|\geq 2$, and
if $e\neq e_1\in E$, then $|e\cap e_1| \leq 1$.
An injective edge choice function of a linear ...

**2**

votes

**1**answer

46 views

### Number of distinct perfect matchings/near perfect matchings in an induced subgraph

Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is ...

**6**

votes

**1**answer

93 views

### Restricted independent set of the cycle graph $C_{3n}$

Let $V$ be the vertices of the cycle graph $C_{3n}$. Suppose there is a partition of $V$ into sets of $3$, i.e. $V=\cup_{k=1}^{n}{V_k}$ where $|V_k|=3$ for $k$ in $1..n$.
QUESTION: Is it possible ...

**5**

votes

**1**answer

188 views

### Conjecture about infinite word

Let $w=a_1a_2a_3...$ be an infinite word over a finite alphabet and $\epsilon>0$. Do there exist integers $n,k$ such that $\frac{d(a_1a_2...a_n,a_{k+1}a_{k+2}...a_{k+n})}{n}<\epsilon$ ?
($d(u,v)$...

**0**

votes

**1**answer

114 views

### Greatest Common Divisor of two specified sequences of numbers (search for equality)

I consider two sequences of numbers $A=\{a_1,...,a_n\}$ and $B=\{k-a_1,...,k-a_n\}$, where $a_1 \le a_2 \le ... \le a_n \le k$.
I am looking for such conditions under which: $gcd(a_1,...,a_n) = gcd(k-...

**0**

votes

**1**answer

60 views

### All even order graphs with $\Delta\ge\frac{n}{2}$ is Class 1

Are all even order graphs with maximum degree $\ge\frac{|V(G)|}{2}$ Class 1(edge-colorable(chromatic index) with $\delta(G)$ colors)? Here, $|V(G)|$ detnotes the number of vertices in the graph.
I ...

**-1**

votes

**1**answer

104 views

### Collapsed partitions and ordinary partitions

Adopt the standard notation for integer partitions, writing $\lambda_1^{a_1} \cdots \lambda_k^{a_k}$ as shorthand for the partition $a_1 \lambda_1 + \cdots + a_k \lambda_k$ with parts $\lambda_1 > \...

**4**

votes

**0**answers

70 views

### Panyushev's conjectured duality for root poset antichains

In his 2004 paper "ad-nilpotent ideals of a Borel subalgebra: generators and duality" (https://www.sciencedirect.com/science/article/pii/S0021869303006380), Panyushev conjectured (Conjecture 6.1) the ...

**3**

votes

**1**answer

95 views

### p-adic valuation of coefficients of generating function

Let $p$ be a prime and suppose that $g(t)$ is the generating function $g(t) = 1/p\,g(t)^p + t$ with low order terms $g(t) = t + O(t^p)$. An easy induction shows that the coefficient of $t^n$ in $g(t)$...

**3**

votes

**1**answer

117 views

### Some sums related to a quadratic polynomial over $\mathbb{F}_2^n$

For any $c \in \mathbb{F}_2^n$ define $\sigma_c: \mathbb{F}_2^n \to \mathbb{F}_2$ the quadratic polynomial defined for $v = (v_1,v_2,...,v_n)$ by:
$$ \sigma_c (v) = \sum_{i=1}^n v_iv_{i+1} + c_iv_i $...

**5**

votes

**3**answers

148 views

### Disjunction number of a graph

Let $S\neq \emptyset$ be a set. We make its powerset ${\cal P}(S)$ into a simple, undirected graph by saying that $A, B\in{\cal P}(S)$ form an edge if and only if $A\cap B=\emptyset$.
The ...

**4**

votes

**2**answers

121 views

### Cycles of length $8$

There is a construction of a bipartite graph $G=(V_1 \cup V_2, E),$ where $|V_1|=|V_2|=n,$ $|E| \geq \Omega(n^{6/5}),$ such that $G$ does not cotain any cycle of length $8.$
I was wondering if ...

**5**

votes

**1**answer

143 views

### How many permutations are there at a given Cayley distance from the identity?

Permutations $\sigma$ in the symmetric group $S_n$ can be characterized by their Cayley distance $C_\sigma$, being the minimal number of transpositions needed to convert $\{1,2,3,\ldots n\}$ into $\...

**5**

votes

**0**answers

55 views

### Kac-Moody groups for non-crystallographic root systems

Given a finite-dimensional crystallographic root system, we can construct an associated Kac-Moody group, with a corresponding flag variety and Littlewood-Richardson coefficients. Between a pair of ...

**3**

votes

**1**answer

221 views

### Counting the forests obtainable by removing subtrees from binary trees

Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...

**5**

votes

**0**answers

57 views

### Minimize number of lattice paths below a given path

Every north-east lattice path (NE-path) $v$ from $(0,0)$ to $(k, a)$ can be identified with a sequence $0 \le \lambda_1 \le \lambda_2 \le . . . \le \lambda_k\le a$, that represent the hight of each ...

**1**

vote

**1**answer

22 views

### Coloring cliques of a clique decomposition of the complete graph

Let $G=K_k$, the complete graph on $k$ vertices. Consider the cliques induced by the sets of edges of a clique decomposition of $G$. Can you $k$-color the edges of $G$ so that each of the cliques in ...

**0**

votes

**0**answers

26 views

### Counting triangles with small intersection in a complete graph

Let $G=K_k$ be the complete graph on $k$ vertices. Consider triangles (subgraphs induced by three vertices) which intersect pairwise in at most one vertex. What is the maximum number of these that ...

**2**

votes

**1**answer

69 views

### The expectation of partition times needed separate two elements in a set

I met a problem which can be formulated as set partition.
Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set ...

**4**

votes

**2**answers

292 views

### How many $\mathbb{Q}$-bases of $\langle\log(1),\dotsc,\log(n)\rangle$ can be built from the set of vectors $\log(1),\cdots,\log(n)$?

How many $\mathbb{Q}$-bases of $\langle\log(1),\dotsc,\log(n)\rangle$ can be built from the set of vectors $\log(1),\dotsc,\log(n)$?
Data for $n=1,2,3,\dotsc$ computed with Sage:
$$1, 1, 1, 2, 2, 5, ...

**0**

votes

**0**answers

26 views

### Metric conversion in trees?

Say you have a balanced binary decision tree with depth $L$ and we know the sequence $p_1$ of $0/1$ decisions we need to make from root to one of the leaves $\ell_1$. This $0/1$ string is what I call ...

**1**

vote

**0**answers

75 views

### Coloring triples in trees

Definitions
Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ ...

**4**

votes

**1**answer

126 views

### Information for discovering an item-colour assignment in a combinatorial game

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...

**1**

vote

**1**answer

93 views

### Uniform partitioning of regular graphs

Consider a symmetric or arc-transitive graph except the odd cycle. Then, is it true that the graph could be partitioned into distinct parts such that each part has equal number of vertices except for ...

**4**

votes

**1**answer

128 views

### Generating bitstring combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...

**1**

vote

**2**answers

86 views

### How to use probability to find a matching in a family of graphs?

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...