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.

1
vote
3answers
89 views

Bijective operations on finite simple graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices. I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...
24
votes
3answers
751 views

Is the Ford-Fulkerson algorithm a tropical rational function?

The Ford-Fulkerson algorithm Let me recall the standard scenario of flow optimization (for integer flows at least): Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
0
votes
0answers
41 views

Sum of Binomial Coefficients from 1 to N having specific form [on hold]

In this question I want to know how we can find the sum of the series if N = 2*I like 2C1 + 4C2 + 6C3 + …. upto N terms. [Sum of 'the first k' binomial coefficients for fixed n
6
votes
4answers
3k views

Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices

What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$? If there's no exact formula what are the nearest upper and lower bounds do you know?
7
votes
3answers
933 views

Transforming a binary matrix into triangular form using permutation matrices

I am interested in the complexity of the following problem: Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix? I am also interested in ...
-4
votes
1answer
56 views

Regular graph such that $2$ distinct vertices have same neighborhood set [on hold]

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 ...
11
votes
1answer
492 views

Frankl's conjecture restricted to finite topological spaces

A finite topological space is a finite family of finite sets that is closed under both union and intersection. Frankl's conjecture states that for any finite union-closed family of finite sets, ...
0
votes
0answers
115 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,...
45
votes
4answers
3k views

Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...
13
votes
6answers
3k views

analog of principle of inclusion-exclusion

When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...
-2
votes
0answers
57 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 ...
2
votes
2answers
121 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 ...
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?
8
votes
6answers
1k views

Proof of a combinatorial equation

How can we use elementary methods to prove that $$\sum_{i = 2}^{n}{{n \choose i} i! n^{n - i}} = \sum_{i = 1}^{n - 1}{{n \choose i}i^i (n - i)^{n - i}}$$ for any integer $n \geq 0$? The values of ...
8
votes
0answers
201 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
120 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 ...
20
votes
2answers
2k views

A Putnam problem with a twist

This question is motivated by one of the problem set from this year's Putnam Examination. That is, Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...
11
votes
1answer
281 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
1answer
138 views

On $\det[x+(\frac{i\pm j}p)]_{1\le i,j\le(p-1)/2}$ for primes $p\equiv 3\pmod 4$

I have made the followng conjecture on the basis of my computation. Conjecture. For any prime $p\equiv3\pmod4$ with $p>3$, we have $$\det\left[x+\left(\frac{i+j}p\right)\right]_{1\le i,j\le(p-1)/2}...
3
votes
0answers
49 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
89 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
111 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
107 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
110 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 ...
15
votes
1answer
277 views

Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
5
votes
1answer
104 views

An extension of the Izergin-Korepin determinant to the eight-vertex model

In the six-vertex model, edges in a square lattice are oriented so that the in-degree of each vertex is exactly two. This gives six types of allowable vertices: $$\begin{array}{cccccc} \begin{...
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 ...
18
votes
1answer
484 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)$ ...
6
votes
2answers
108 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)$ ...
2
votes
0answers
100 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$. ...
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
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?
14
votes
1answer
619 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 ...
5
votes
1answer
210 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\{...
0
votes
1answer
82 views

Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...
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 $\...
6
votes
2answers
301 views

How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?

Let $G \leq {\rm S}_n$ be a finite permutation group, and let $S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed under inversion and which does not contain the identity. The growth ...
0
votes
0answers
104 views

Probability of degree $0$ gcd between every pair of random homogeneous polynomials shifted by random primes?

Take $n,d,B\in\mathbb Z_{>0}$ with $d<n$ and denote $\mathcal M_{n,d}$ to be set of all total degree $d$ monomials in $n$ variables $x_1,\dots,x_n$ with degree $\leq1$ in each variable (...
46
votes
6answers
5k views

Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway... Consider this problem. I've been trying to find a formula to expand the "regular iteration" of "...
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
1answer
111 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 ...
3
votes
1answer
312 views

Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...
1
vote
1answer
66 views

Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
5
votes
1answer
233 views

Finding a semi-sparse vertex in a grid

Let $H$ be a $r \times r$ grid. Suppose that at most $r/10^5$ vertices of this grid are colored red. For every vertex $v \in V(H)$, let $B_i(v)$ be the ball of radius $i$ centered at $v$. (Or for ...
3
votes
1answer
324 views

Typo in Soundararajan's *Bulletin of the AMS* article on Tao's resolution of The Erdos Discrepancy Problem?

I think that there is a typo in the paper referred to in the title of the question, available here. While discussing Roth's proof of AP discrepancy, on page 2, the author states that Roth [20] ...
4
votes
1answer
185 views

Distribution of longest run locations in a random string

Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...
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 ...
5
votes
1answer
495 views

What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...
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 ...