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
-5 votes
0 answers
31 views

Graph Theory Assignment [closed]

An n by n matrix with nonnegative real entries is called nice if each row and each column sums to 1. An n-by-n matrix is called a permutation matrix it has exactly one 1 in each row and column and has ...
  • 1
1 vote
0 answers
37 views

Graph removal lemma

The graph removal lemma says that for any graph $H$ and any $\epsilon>0$, there is a $\delta>0$ such that any $n$-vertex graph which contains at most $\delta n^{v(H)}$ copies of $H$ can be made $...
  • 171
1 vote
0 answers
42 views

When do two path algebras share an underlying graph?

Suppose $Q$ and $Q'$ are two quivers. I am curious as to what relation $\mathbb{C}Q$ bears to $\mathbb{C}Q'$ when $Q$ and $Q'$ share the same underlying graph and only differ by direction. Since ...
  • 304
0 votes
0 answers
45 views

Derive an expression for $a_n$ [migrated]

I started studying on the subject of discrete Mathematics and I came across the following question: Let $a_n := \lvert\{\pi \in S_n : \text{$\pi(i) \neq i$ for all odd $i$}\}\rvert$ and we denote the ...
1 vote
1 answer
101 views

Number of distinct entries in a rotation invariant cube

I have a cube $X\in \mathbb R^{N\times N\times N}$ such that no matter how the cube is rotated by $90^\circ$ along any of the axes, the result is unchanged. What is the maximum number of distinct ...
1 vote
1 answer
93 views

What properties are preserved by quasi-isometries

Recently, I came across the notion of quasi-isometries, while thinking of "discrete spaces which are surrogates for approximate continuous ones". What (metric)/geometric properties are ...
  • 4,973
2 votes
0 answers
29 views

A variant of the regularity lemma that depends on the number of vertices

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side. For sets $X \subseteq U$ and $Y \subseteq V$, let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...
  • 327
2 votes
1 answer
81 views

"Combined" chromatic number of $2$ graphs glued together with $2$ edges per vertex

If $X$ is any set, we let $[X]^2:=\big\{\{x,y\}:x\neq y\in X\big\}$. If $G=(V,E)$ is an undirected graph and $v\in V$, we define $N_G(v) = \{w\in V:\{v,w\}\in E\}$. For $i =1,2$, let $G_i=(V_i,E_i)$ ...
2 votes
1 answer
135 views

Matching polynomial, but $K_2$ is replaced by $K_3$. Have these been studied?

Given a simple graph $G=(V,E)$, we can consider matchings, $M\subseteq E$, where $M$ is a matching iff no vertex is shared between different edges. The number of edges in $M$ is denoted $|M|$. The ...
2 votes
0 answers
67 views

Question about sparse graph [closed]

We call a graph $G=(V,E)$ $k$-sparse if there is a partition $E = \bigcup_{i = 1}^k E_i$ of the edges into $k$ disjoint parts such that each graph $(V,E_i)$ is a forest. I am trying to prove that $k \...
6 votes
1 answer
315 views

Conjecture on the existence of centrosymmetric Hadamard matrices

I work with centrosymmetric matrices and recently have started exploring the question of the existence of centrosymmetric Hadamard matrices. Definition: An $n \times m$ matrix $A = (a_{i,j})$ is ...
7 votes
0 answers
391 views

Mistakes in Logan and Shepp's famous paper on Young Tableaux?

In their landmark paper from 1977 named "A Variational Problem for Random Young Tableaux" Logan and Shepp obtained a number of results concerning asymptotic properties of Young Diagrams ...
  • 106
1 vote
0 answers
86 views

Khovanov $A_\infty$ algebra

Let $L$ be a link in $\mathbb{R}^3$, with $D, D'$ be diagrams in $\mathbb{R}^2$ representing $L$. Khovanov constructed two graded chain complexes $$C_{D} = (Ch_{D}, d_{D}) \quad C_{D'}=(Ch_{D'}, d_{D'}...
  • 4,415
-4 votes
0 answers
79 views

Number of rooted spanning trees [closed]

Given a complete graph $K_n$. The rooted spanning tree is a directed spanning tree where each vertex has out-degree exactly 1 and the root vertex has out-degree zero. What exactly is the number of ...
  • 1
5 votes
0 answers
77 views

Sum of Schur functions associated to self-conjugate partitions

The $\tau$-function $H^\circ \big(t ;\vec{x} \big)$ associated with counting simple Hurwitz numbers is the formal power series \begin{equation} (\dagger) \quad H^\circ \big(t ;\vec{x} \big) \, = \, \...
  • 1,685
3 votes
0 answers
146 views
+100

Genus of polyhedron

I have constructed two polyhedrons as follows: There are $\binom{6}{3}$ triangles and $\binom{6}{2}$ squares. Every triangle is connected via an edge with $3$ distinct squares (one for each vertex of ...
8 votes
2 answers
162 views

Commutation classes of reduced decompositions of the longest element of the Weyl group with one element

For the symmetric group on $n$ objects $S_n$ the question of how to write its longest element $w_0$ as a reduced decomposition is an important combinatorical problem. As example, in this question the ...
0 votes
0 answers
81 views

A question on lexicographic order and change of indices [closed]

Consider a vector of components which are listed in lexicographic order: $\boldsymbol{z} = (z_{1,2},z_{1,3},\dotsc,z_{1,K}, z_{2,3},z_{2,4},\dotsc,z_{2,K},\dotsc,z_{i,i+1},z_{i,i+2},\dotsc,z_{i,K},\...
2 votes
0 answers
76 views

Closed form for coefficients related to excedance set of permutation

Working on suitable closed form for A329369, I discovered very useful coefficients, which have the following recurrence relation: $$T(0,1)=T(0,2)=1$$ $$T(n,1)=1, n>0$$ $$T(0,k)=0, k>2$$ $$T(2n+1,...
0 votes
0 answers
45 views

VC dimension of axis-parallel boxes [closed]

Let $A$ be the family of axis-parallel boxes in the $d$-dimensional unit cube $[0,1]^d$ having one vertex at the origin. It is known that the VC dimension of $A$ is $d$. Let $B$ be the family of all ...
  • 101
4 votes
0 answers
62 views

Asymptotic expansion for the number of self-avoiding random walks

This question is cross-posted from https://math.stackexchange.com/questions/4580314/asymptotic-expansion-for-the-number-of-self-avoiding-random-walks. Let $c_n$ be the number of self-avoiding random ...
  • 441
2 votes
0 answers
91 views

Closed form for $a(2^m(2^n-2^p-1))$

Let $q(n)$ be A007814, i.e., the number of trailing zeros in the binary representation of $n$. Here $$q(2n+1)=0, q(2n)=q(n)+1$$ Let $a(n)$ be A329369. Here $$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(...
1 vote
1 answer
81 views

Graphs with $n$ vertices and $m$ edges and more probable property

Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail. Given the positive integers $n$ ...
  • 312
3 votes
1 answer
162 views

'Trivial' lower bounds for pattern complexity of aperiodic subshifts

I recently asked in this thread about lower bounds on the complexity in the case where we have an aperiodic subshift. If I denote $c_n(\Omega)$ as the number of possible patterns on $Q_n= \big\{ 0,...,...
1 vote
1 answer
71 views

Recombining set elements with no duplicated pairing of elements

This question arises from a request for an algorithm to do such, from 9 sets of 12 elements, arrange 12 groups of the 9 elements, selecting 1 element from each set Given a set, $S$, of sets, $S_i$, $\...
1 vote
2 answers
176 views

Do all graphs with $n$ vertices and $m$ edges have a special property?

Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$. For which values of $n$ and $m$ does the following requirement hold: $\forall G \in \...
  • 312
1 vote
1 answer
228 views

How many ways to pick k integers with fixed sum and product

We are given $1\leq S \leq 10^9$ and $1 \leq P \leq 10^9$. We need to pick $k$ integers $x_1, x_2, \dotsc, x_k$ (all of which have to be $>1$) such that $\sum_k{x_k}=S$ and $\prod_k{x_k}=P$. What ...
2 votes
1 answer
99 views

Counting numerical semigroups by largest element of minimal generating set

For a given integer $n$, I am interested in the number of different numerical semigroups one can make with a generating set consisting only of integers in $[n]$. I have done some small examples. For $...
0 votes
1 answer
149 views

Number of couples of columns "connecting" top to bottom of a matrix

This question is on the same topic of this one, but simpler, and I have also included some numerical tests here. Consider a $h \times (n-1-h)$ matrix $A$ with all entries $a_{ij}$, $1 \le i \le h$, $1 ...
  • 312
3 votes
0 answers
77 views

The matrix representation of an interval graph

It is well-known that many classes of graphs have matrix representations that can be written concisely. For example, The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
  • 3,828
9 votes
1 answer
279 views

One question on circulant $(-1,1)$-matrices

Let $n > 13$ be a positive integer. Is there any $n\times n$ circulant $(-1,1)$-matrix $A$ satisfying the following property: $$AA^T=(n-1)I+J$$ where $I$ is the $n\times n$ identity matrix and $J$ ...
11 votes
2 answers
856 views

Not very transitive actions

Suppose $m$ is a positive integer. I am looking for finite sets with group actions such that the action is transitive on the set of $m$-element subsets, but NOT transitive on the set of $(m+1)$-...
1 vote
1 answer
76 views

The quantity of poset with a given number of pairs of incomparable elements

$\DeclareMathOperator\inc{inc}$Let $|X|=n$ and $\inc(X,\leq)=\{\{x,y\} : \neg (x\leq y)\wedge \neg (y\leq x)\}$, where $(X,\leq)$ is poset (possibly unconnected). Define the function: $$\pi(n,m):=|\{(...
  • 77
1 vote
1 answer
102 views

Number of sets of columns "connecting" top to bottom of a matrix

(See also this similar question). Consider a $h \times 4n-h$ binary matrix (a matrix with all entries $a_{ij}$, $1 \le i \le h$, $1 \le j \le 4n-h$, equal to $0$ or $1$). We know that each row has $2n$...
  • 312
4 votes
0 answers
86 views

How many diagrams interlace a given Young diagram?

For a fixed partition $\lambda=(\lambda_1\geq\dots\geq \lambda_n)$ we say $\mu=(\mu_1\geq \dots \geq \mu_{n-1})$ $\textit{interlaces}$ $\lambda$ iff $$\lambda_1\geq \mu_1\geq \dots \geq \mu_{n-1}\geq \...
0 votes
0 answers
22 views

Size of the second largest strongly connected component in random directed graphs with fixed in- and out-degree sequences

It has been known for long (Molloy and Reed 1995) that in a supercritical undirected configuration model, that is when $E[D(D-2)]>0$, $D$ degree of a uniform vertex, the size of the second largest ...
  • 56
3 votes
0 answers
169 views

Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets

Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
11 votes
1 answer
276 views

Why are these graphs coming from 9-dimensional alternating trilinear forms so symmetric?

Let $\phi(x,y,z)$ be an alternating trilinear form on a space $V$ over a field $K$. Let $u \in \mathbb{P}(V)$ be a projective point over $V$, then we say that the rank of $u$ is equal to the rank of ...
0 votes
0 answers
92 views

One variable recurrence relation and two variable recurrence relation

Let $q(n)$ be A007814, i.e., number of trailing zeros in the binary representation of $n$. Here $$q(2n+1)=0, q(2n)=q(n)+1$$ Let $a(n)$ be A329369. Here $$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(2n-2^{...
1 vote
0 answers
70 views

Keller's cubing conjecture but with arbitrary cubes of side $1$

These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...
  • 5,172
1 vote
0 answers
54 views

Probability of (single) connecting paths in Erdos-Renyi graphs

In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of there ...
  • 129
5 votes
1 answer
192 views

Which finite projective planes can have a symmetric incidence matrix?

As the title says. Which finite projective planes admit a symmetric incidence matrix? I am not an expert in the field at all, but I consulted with one. He claimed that $PG(2, \mathbb F_q)$ can always ...
  • 165
8 votes
1 answer
518 views

When the Littlewood-Richardson rule gives only irreducibles?

Given the famous Littlewood-Richardson rule, in terms of Schur polynomials: $$s_\mu s_\nu=\sum_\lambda c^{\lambda}_{\mu\nu} s_\lambda,$$ is there a classification of the cases where the LR ...
0 votes
0 answers
62 views

The real part of roots to iterated forward differences on monomials

For $\triangle f(x) = f(x + 1) - f(x)$ and $\triangle^{m}f(x) = \triangle(\triangle^{m - 1}f(x))$ (for $m$ a positive integer), is it true that $\triangle^{m}x^{n} = 0 \implies Re(x) = -\frac{m}{2}$ (...
  • 1
1 vote
1 answer
73 views

Algorithm for finding a minimum weight circuit in a weighted binary matroid

For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times. Also for a matroid $M = (E, I)$ one can use the ...
1 vote
0 answers
80 views

Rado graph and linear algebra

Let $V = \mathbb{Z}_{\geq 0}$ be the set of integers and let $\mathcal{G} = (V, E)$ be an (undirected) Rado graph on $V$. Let $W = \bigoplus_{i = 0}^{\infty} \mathbb{F}_2$ and write $x_i$ for the $i$-...
7 votes
0 answers
137 views

Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets

We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
2 votes
1 answer
183 views

Computational complexity and commuting functions, examples and conjectures

History of the question. I was proposing a conjecture here, called Prop. 1. Fedor Pakhomov showed a counter-example. Here I am proposing a slightly weaker version of the conjecture, Prop. 2, that ...
3 votes
0 answers
136 views

Transitive action on domino tilings

Fix a $n \times m$ rectangle and consider the set $S_{n,m}$ of all its dominos tilings. Here are examples with $n=m=8$. The set $S_{n,m}$ is empty if and only if $nm$ is odd, and for small $nm$, its ...
8 votes
1 answer
190 views

Computational complexity and commuting functions

EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. In this new question I propose a slightly weaker conjecture that holds even for that example and ...

1
2 3 4 5
189