Stack Exchange Network

Stack Exchange network consists of 174 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.

-4
votes
1answer
41 views

Regular graph such that $2$ distinct vertices have same neighborhood set

If $G=(V,E)$ is a simple, undirected graph and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$. Is there an integer $k>1$ and a connected $k$-regular graph $G=(V,E)$ such that there are $v\neq ...
-2
votes
0answers
53 views

Birthday Calendar Gaps [on hold]

I work at a company that posts a birthday calendar. I noticed that there was a string of four consecutive days with no birthdays. What is the probability of that happening? Problem Statement Given n ...
0
votes
0answers
113 views

Total number of collisions

Given $n$ point masses on the real axis with their initial positions and velocities, determine the total number of collisions (from $t=0$ to $t=\infty$). Here I suppose that the collisions are elastic,...
0
votes
0answers
36 views

Average distance between a random point and the closest of a set of random points

Create a set of n randomly placed points in a unit square. Then create another random point in the unit square. What is the average distance between this point and the closest of the n points?
2
votes
2answers
115 views

Infima and suprema in the “transfer” function ordering

Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...
3
votes
0answers
118 views

Combinatorics question

Let $A = (a_{ij})_{1\le i,j\le h}$ be an $h$-by-$h$ non-degenerate upper triangular matrix with entry $a_{11} = 1$. Let $\Phi = \{\alpha_1,\alpha_2,\ldots,\alpha_d\}\subseteq \{1,2,\ldots,h\}=I$ be an ...
0
votes
0answers
74 views

How to prove the exact top degree of the polynomial coming from each Feynman diagram?

Let $W=x_0+x_1+x_2+\lambda_0 \ln(x_0)+\lambda_1\ln(x_1)+\lambda_2\ln(x_2)+(\frac{x_0x_1x_2}{q})^{\frac{1}{3}}$, where $\lambda_i=\xi^i\cdot\lambda$, $\xi$ is the 3-th root of unit. For each Feynman ...
8
votes
0answers
194 views

Commuting matrix variety $[A,B]=0$ - can one geometrically explain divisibility of $F_ q$ point count by high powers of $q$?

$\DeclareMathOperator\Comm{Comm}\DeclareMathOperator\Id{Id}$Consider the variety $\Comm$ of commuting matrices $[A,B]=0$ over some field $K$. It is much studied, and interesting for various reasons. ...
3
votes
0answers
48 views

Biggest Cartesian Product Included in a Real Plane Curve

Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
1
vote
1answer
88 views

Incidences between points and circles in the plane

Suppose we have $n$ points $P$ and $m$ circles $C$ in the plane. Let $I(P,C)=\{(p,c), p \in P, c \in C, p \in c\}.$ Then what do we know about $\max_{m,n} |I(P,C)|$? Any references?
4
votes
2answers
109 views

Are cyclic codes bounded by a continuous function?

In coding theory, we know that if you take the function \begin{equation} \alpha_q(\delta) := \limsup_{n \rightarrow \infty} \ \max \{ R(C) \mid \delta(C) \ge \delta \mid C \subseteq \mathbb{F}_q^...
-1
votes
1answer
104 views

Version of Hall's marriage theorem in arbitrary finite graphs [closed]

Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge). For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\...
2
votes
0answers
109 views

Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
3
votes
0answers
117 views

Maximum number of integral roots in degree $d$ polynomial?

Given $f(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$ such that Each coefficient is bound in absolute value by $B$ Degree of each variable in any monomial is bound by $d$ Total degree is $d'$ $f(x_1,\...
2
votes
0answers
99 views

On an exercise in The Probabilistic Method : random dilate of a set in a finite field

This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following: Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...
5
votes
2answers
141 views

Enumeration of lattice paths of a specific type

One of the approaches to "Special" meanders led (in particular) to the following question: What is the number $a_{m,n}(\ell)$ of $\ell$-step paths from $(1,1)$ to $(m,n)$ using the ...
6
votes
2answers
106 views

Neighboring number of a permutation

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ ...
18
votes
1answer
481 views

Order of Conway's “look and say” recurrence

Let $L_n$ be the length of the $n$th term of Conway's "look and say" sequence (https://oeis.org/A005341). The generating function $F(x)= \sum_{n\geq 0}L_nx^n$ is a rational function, say $P(x)/Q(x)$ ...
2
votes
0answers
118 views

What kind of curve is this, from the distribution of roots of Catalan polynomials? [closed]

We consider the distribution of roots of some Catalan polynomials. And we get the following curve that the roots approach it. What kind of curve is this?
5
votes
1answer
208 views

On the “infinitely often in” relation between subsets of $\mathbb{N}$

Let ${\mathbb N}$ denote the set of positive integers, let $A,B\subseteq \mathbb{N}$. For $n\in\mathbb{N}$ we set $n+A:=\{n+a: a\in A\}$. We say that $A$ is infinitely often in $B$ if the set $$\big\{...
3
votes
1answer
109 views

Expected size of the smallest preimage set

Let $f$ a function from $\{0, 1 \}^{2n}$ to $\{0, 1 \}^{n}$ uniformly picked at random. I would like to have an estimation of the expected size of the smallest premiage set of $f$, more formally $\...
2
votes
0answers
51 views

Total Coloring Conjecture for Cayley Graphs

The total Coloring Conjecture(TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
2
votes
0answers
58 views

Algebraic description of the reduced incidence algebra of a poset

In the book "Combinatorial theory" by Martin Aigner (from 1979), the standard algebra of a poset is introduced as the subalgebra of the incidence algebra of a poset consisting of the functions that ...
2
votes
1answer
110 views

Does the likelihood of these tables exist?

Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background. Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...
14
votes
1answer
617 views

Combinatorial inequality for dominant dimension

In the following I present a conjecture on Nakayama algebras that I have for nearly 2 years now. Since I was not able to solve it and it can be stated purely combinatorically, I thought it might be ...
7
votes
0answers
83 views

Permutation groups with diameter $O(n \log n)$

I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture: Suppose that 1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
1
vote
0answers
36 views

Examples of associative inducers and other inducers

I am curious about how well the following technique can produce algebraic structures and semigroups in particular. Let $(X,\circ)$ be a semigroup. Let $Y$ be a set and let $L:X\rightarrow P(Y)$ be a ...
4
votes
1answer
95 views

Hamming representability of finite graphs

This is a follow up on an older question. We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of ...
0
votes
1answer
102 views

Conjecture on representing graphs within $\{0,1\}^n$

We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of the set $\{ i \in \{0, ..., n-1\} : x(i) \...
2
votes
1answer
99 views

How to uniformly sample a square (0,1)-matrix whose trace is 0 and whose row sums and column sums are the same?

Happy New Year! Suppose I would like to sample a $n \times n$ (0,1)-matrix whose trace is 0, and whose row sums and column sums are all $m$ with $1 \le m \le n-1.$ How can I sample this matrix ...
11
votes
1answer
276 views

To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $P$ satisfies: ...
1
vote
0answers
119 views

How often do random games of go end in illegal moves?

Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...
4
votes
2answers
179 views

How many ways to fill in a square grid with certain restrictions

Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 ...
0
votes
4answers
317 views

How to compute this series: $\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$ [closed]

How to compute this series: $$\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$$ where $C_k$ is the catalan number: $C_k=\frac{1}{k+1}{2k \choose k}$. (Further, is there any general method to treat this ...
1
vote
1answer
59 views

Enumerating isomorphic subgraphs

For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...
4
votes
1answer
297 views

Spreading $n$ points in $\{0,1\}^n$ as far as possible

Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$ We say that a positive integer $s$ is $...
5
votes
1answer
191 views

Inequality number of facets simplicial complex

In a recent preprint, Adiprasito proves that if $\Delta$ is a simplicial complex of dimension $d$ that can be embdedded in a $2d$-dimensional homology sphere (say $\Sigma$) that satisfies a version of ...
6
votes
0answers
203 views

Is the permanent of the matrix $[(\frac{i+j}{2n+1})]_{0\le i,j\le n}$ always positive?

Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by $$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$ In 2004, R. Chapman [Acta ...
0
votes
1answer
71 views

Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...
5
votes
2answers
283 views

The number of Dyck paths of length $2n$ and height exactly $k$

In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions. For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we ...
1
vote
1answer
97 views

On a theorem of Chetwynd and Hilton in Graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
1
vote
0answers
91 views

Has the “semidirect monoid of a semiring” been considered anywhere?

Given a semiring $S$, we get a monoid $M(S)$ as follows: The underlying set of $S$ is $S^2$ The identity element is $(0,1)$ The law of composition is given by $$(a,A)(b,B) = (Ba+b,AB),$$ where $a,A,b$...
1
vote
0answers
86 views

extending a partition of a number to get new partition

Let $\lambda = (k_1^{m_1}\,k_2^{m_2})$ where $0<k_1<k_2$ be a partition of $n$ in the power notation. Let $\mu = p_0^{r_0}\,p_1^{r_1}\,\cdots\, p_t^{r_t} \,(k_1^{m_1}\,k_2^{m_2})\,q_0^{s_0}\,...
-2
votes
1answer
216 views

Negative Dirichlet Pigeonhole Principle

From Dirichlet Pigeonhole Principle if $p$ is a prime and if $a,b\in\mathbb Z$ are in $(0,p/2)$ then there is a $t\in(0,p)\cap\mathbb Z$ such that $\|(x,y)\|_\infty<\lceil\sqrt p\rceil$ holds where ...
2
votes
1answer
252 views

Homogeneous van der Waerden

The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$. ...
1
vote
2answers
250 views

Prove that there exists a nonempty subset $ I$ of $ \{1,2,…,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer

Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...
4
votes
1answer
211 views

Applications of De-Bruijn Sequences in “Pure Mathematics”

I know of a few applications of De-Bruijn Sequences and De Bruijn Graphs in combinatorics, applied mathematics, Engineering and computer science. But I have only found one application of De Bruijn ...
8
votes
1answer
153 views

On the existence of a particular type of finite measure on $\mathbb N$

Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...
0
votes
0answers
46 views

Polynomial time way of testing optimality of given vertex for linear programming

Is there a fast way (polynomial complexity) of testing whether a given vertex for a linear program is optimal, without assuming non-degeneracy? I can find the optimal vertex in worst-case polynomial ...
2
votes
1answer
58 views

Stretching map of $n$ points from $\{0,1\}^n$ to $\{0,1\}^{n+1}$ with respect to their Hamming distance

Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$ Given an integer $n>0$ and a set $S\...