Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

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