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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
3answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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 ...
