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
2 votes
3 answers
464 views

Alternating sum over collections of sets

Let $\mathbf{P}$ be a collection of subsets of a finite set $X$. Let $\mathscr{S}$ be the set of all subsets $\mathbf{S}\subset \mathbf{P}$ such that $\bigcup_{S\in \mathbf{S}} S = X$. Can one give a ...
H A Helfgott's user avatar
  • 19.3k
6 votes
1 answer
235 views

An eigenvalue upper bound for 1-walk-regular graphs

Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular). Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct ...
M. Winter's user avatar
  • 12.5k
3 votes
0 answers
140 views

Acyclic extensions of acyclic simplicial complexes

Say an abstract simplicial complex $X$ is acyclic if its reduced integral simplicial homology groups $\tilde{\mathrm{H}}^{\Delta}_p(X)$ vanish for all $p\geq 0$. Is it the case that, for any $n>0$, ...
bergfalk's user avatar
2 votes
0 answers
56 views

Antipodal vertices in spectral graph embeddings

Suppose your are given an antipodal graph $G=(V,E)$, that is, for every vertex $v\in V$ there is a unique maximally distant vertex $v'\in V$. Under which condistions does the following hold: If $\...
M. Winter's user avatar
  • 12.5k
1 vote
1 answer
121 views

Bound on the chromatic number of square of bipartite graphs

In continuation of the previous question, what is a strict upper bound on the chromatic number of the square of a bipartite graph? I think the chromatic number number of the square of the bipartite ...
vidyarthi's user avatar
  • 2,007
9 votes
2 answers
400 views

Alternating sum over collections closed under containment

Let $\mathscr{C}$ be a collection of subsets of a finite set $P$. Assume $\mathscr{C}$ is closed under containment: if $S\subset P$ is in $\mathscr{C}$, then every set $S'\subset P$ containing $S$ is ...
H A Helfgott's user avatar
  • 19.3k
5 votes
0 answers
351 views

Self avoiding walks and context free languages

Let $G$ be an infinite, locally finite, connected graph whose arcs (oriented edges) are labelled by letters in a finite alphabet $\Sigma$ such that arcs starting in the same vertex are labelled by ...
Florian Lehner's user avatar
0 votes
2 answers
155 views

"Arithmetically diverse" infinite binary string

For $a,b \in \omega$ with $a > 0$, let $f_{a,b}: \omega\to\omega$ be defined by $n \mapsto an+b$. What is an example of an infinite binary string $s:\omega\to\{0,1\}$ with the following property? ...
Dominic van der Zypen's user avatar
1 vote
1 answer
376 views

Integer partitions into restricted parts

Given a linear diophantine equation $$x_1+\dots+x_n=m\leq nn'$$ how many solutions does it have with each $x_i\in[0,n']\cap\mathbb Z$? Looking for asymptotics that parametrizes well with both $n$ and $...
VS.'s user avatar
  • 1,816
7 votes
0 answers
119 views

A question regarding an analog of Young symmetrizer: the product row and column preserving subgroups without sign representation

Consider a rectangular Young diagram $\lambda$ with $n = pq$ boxes, with $p$ rows and $q$ columns. If $C$ is the column preserving subgroup of $\lambda$ and $R$ is the row preserving subgroup, then we ...
Sepehrius's user avatar
  • 121
1 vote
1 answer
378 views

System of equations - Proof that a solution exists

Let $ a = (a_1,a_2, \ldots,a_{10})\in \{ 0,1\}^{10}$ be a binary vector of length $10$. Question: Without using a computer-aided method, how to prove that there exists binary vectors $x_{i,j} \in \{ ...
user avatar
3 votes
1 answer
413 views

Chromatic number of square of a tree

What is an upper bound on the chromatic number of the square of a tree on $n$ vertices? Note that the power of the graph is considered in this sense. If the tree were a path, then it is easy to see ...
vidyarthi's user avatar
  • 2,007
0 votes
1 answer
78 views

how to prove the binomial equation below [closed]

I tried to open up all binomial expressions but things got more complicated. I could not find an appropriate solution.I'm just stuck and trying to find a solution for like 2 hours.I would be very ...
MikeJohnson's user avatar
2 votes
1 answer
298 views

Is this model of converting integers to Gray code correct?

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim. Here is some ...
Γιώργος Πλούσος's user avatar
2 votes
0 answers
109 views

Can a generic rope exert the same force as a rope with loops?

This is a spin-off of my previous question. I will take a moment to reintroduce the notation. The problem concerns elastic "ropes" in $\mathbb{R}^3$, which are modeled as sequences of ...
felipeh's user avatar
  • 337
4 votes
0 answers
103 views

Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ...
Antoine Labelle's user avatar
5 votes
1 answer
394 views

Sum involving determinants of binomial coefficients, indexed by partitions

I would appreciate some help proving a conjecture related to combinatorics and representation theory. Given an integer partition $\lambda\vdash n$, define a polynomial in $N$ whose roots are the ...
Marcel's user avatar
  • 2,510
8 votes
1 answer
291 views

Is there discrete Morse theory on acyclic categories?

Forman introduced discrete Morse theory on finite regular cell complexes. Minian introduced a version of discrete Morse theory for posets which generalizes Forman's original Morse theory https://arxiv....
T. John's user avatar
  • 81
0 votes
1 answer
88 views

Maximum number of edges in "square" hypergraph

For any set $X$ and any cardinal $\kappa$, let $[X]^\kappa$ denote the subsets of $X$ having cardinality $\kappa$. A linear hypergraph is a hypergraph such that for all $e\neq e_1 \in E$ we have $|e\...
Dominic van der Zypen's user avatar
1 vote
1 answer
140 views

Bound for multinomial expansion involving Poisson random variables

Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write: $$ E\left(\...
user124297's user avatar
3 votes
1 answer
127 views

Problem about two elastic ropes in equilibrium

I have an elementary geometric problem that has thus far resisted all efforts from my end. The problem concerns "elastic ropes" which I model as a sequence of points $\gamma=(x_1,x_2,\dots,...
felipeh's user avatar
  • 337
2 votes
1 answer
828 views

Interpretation of probability statements in Nina Zubrilina's paper

I asked this question on Math.stackexchange but got no answer. In the paper Zubrilina - Asymptotic behavior of the edge metric dimension of the random graph (MR, the main result is $$\operatorname{...
mahmoud314's user avatar
0 votes
0 answers
78 views

Minimizing coefficients in a product related to the Rogers Ramanujan identity

Start with the product for partitions into parts congruent to $1$ or $4$ modulo $5$: $(1 + x + x^2 + x^3 + ...)(1 + x^4 + x^8 + x^{12} +...)(1 + x^6 + x^{12} + x^{18} +...)$... Now replace some of the ...
moshe noiman's user avatar
7 votes
0 answers
224 views

"Oddity" in counting intervals of the Tamari lattice

Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Recall, in particular, that $C_n$ is odd iff $n=2^h-1$. A combinatorial proof is given by Deutsch and Sagan in Congruences for Catalan and ...
T. Amdeberhan's user avatar
1 vote
0 answers
95 views

How to combine two $d$-degenerate subgraphs into a $d$-degenerate graph?

A graph is $d$-degenerate if every its subgraph has a vertex of degree at most $d$. Suppose that $G$ is a graph and $G_1,G_2$ are two subgraphs of $G$ that are $d$-degenerate. Is there any way to ...
Xin Zhang's user avatar
  • 1,130
6 votes
2 answers
842 views

3-colored triangulations of the sphere $S^2$, and Sperner's Lemma

I noticed something about colored triangulations of the topological sphere $S^2$ and have a question about this. Observation. If you triangulate the sphere $S^2$ and color the vertices with three ...
Claus's user avatar
  • 6,777
1 vote
1 answer
478 views

Combinatorics of multivariate Faà di Bruno formula

This question is a followup on this one on stackoverflow where i implement in python this issue. I am applying the Faà di Bruno formula to obtain the $\mathbf{i}$th derivatives of the function $f = ln ...
lrnv's user avatar
  • 686
6 votes
1 answer
112 views

Subdivision of closed homology manifold reference request

I am interested in the barycentric subdivision of closed homology manifolds. Definition A (finite) simplicial complex $K$ is a closed homology manifold of dimension $n$ if for every $k$-simplex, its ...
D1811994's user avatar
  • 909
2 votes
1 answer
252 views

Limited rook moves

I have an algebra problem, that could be solved if I could answer the following combinatorial problem. Let $S$ and $T$ be two nonempty sets. We think of $S\times T$ as the index set for the squares ...
Pace Nielsen's user avatar
7 votes
0 answers
116 views

A conjecture on circular permutations of n elements in an abelian group of odd order

In 2013 I formulated the following conjecture in additive combinatorics. Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is ...
Zhi-Wei Sun's user avatar
  • 14.4k
5 votes
1 answer
255 views

Lower bound for diagonal Ramsey numbers —- reference request

Using the first moment method, in 1947 Erd\H{o}s gave a lower bound on the diagonal Ramsey numbers $R(k,k)$: $$ R(k,k) \geq (1+o(1))\frac{k}{e\sqrt{2}} 2^{k/2}. $$ In 1975 Spenser used the Lov\’asz ...
David Galvin's user avatar
  • 1,112
2 votes
1 answer
271 views

Combinatorial optimization problem on sums of differences between real numbers

We are given an increasing sequence $S$ of positive real numbers $x_1, x_2, \ldots, x_n$, such that $$x_{i+2}-x_{i+1} \ge c\,(x_{i+1}-x_i)$$ for all $i=1, 2, \ldots n-2$, where $c\ge 1$ is constant. ...
Penelope Benenati's user avatar
6 votes
0 answers
316 views

An inequality related to the numbers of faces of polytopes with d+2 facets

I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below. Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...
Guillermo Pineda-Villavicencio's user avatar
11 votes
11 answers
1k views

Lattices on classical combinatorial families

I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs. I am mosty interested in lattices ...
Martin Rubey's user avatar
  • 5,533
8 votes
2 answers
685 views

Seeking a combinatorial proof for a binomial identity

Let $n\geq m\geq0$ be two integers. The below binomial identity is provable by other means: $$\sum_{j=0}^m(-1)^j\binom{n+1}j2^{m-j} =\sum_{j=0}^m(-1)^j\binom{n-m+j}j.$$ QUESTION. Can you provide a ...
T. Amdeberhan's user avatar
10 votes
3 answers
1k views

Number of permutations with longest increasing subsequences of length at most $n$

Is there a known expression for, or a nontrivial upper bound on, the number of permutations in $S_k$ with longest increasing subsequence of length at most $n$? Let $l(\sigma)$ denote the length of the ...
4xion's user avatar
  • 201
6 votes
1 answer
307 views

Invertible matrix and 0-1 vector

Let $n\ge 1$ and $A$ be any $n\times n$ real invertible matrix. Can we always find a 0-1 vector $b\in\{0,1\}^n$ such that each entry of $Ab$ is nonzero? For example, if $A$ is the identity matrix, ...
W. Wang's user avatar
  • 437
1 vote
2 answers
650 views

What is a bipartite hypergraph?

Bipartite graphs are very useful, and I am looking for a generalization of this concept to hypergraphs. I found two different definitions of bipartite hypergraphs: In the Wikipedia page Hypergraph, a ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
30 views

Maximum nonintersecting interval pick

This surely has been solved in the context of scheduling already! (Shall I ask on some computer SE instead?) Assume we have a set of closed "intervals" on $\mathbb Z$ ($\mathbb R$ isn't ...
Hauke Reddmann's user avatar
10 votes
1 answer
484 views

is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?

It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively. However, I wonder ...
Martin Rubey's user avatar
  • 5,533
8 votes
3 answers
397 views

Identifying a subset with as few tests as possible

Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
Gro-Tsen's user avatar
  • 29.9k
15 votes
0 answers
256 views

Lie theoretic meaning to $e^{\text{cycle}} = \text{permutation}$?

It is well known that exponentiating the EGF(exponential generating function) for cycles gives the EGF for permutations: link here. Usually summarized under the catchy slogan ...
Siddharth Bhat's user avatar
5 votes
2 answers
2k views

Canon in algebraic combinatorics and how to study

1) In subjects such as algebraic geometry, algebraic topology there is a very basic standard canonical syllabus of things one learns in order to get to reading research papers. Is there a similar ...
nobody's user avatar
  • 407
4 votes
0 answers
134 views

Is a group determined by the number of ways its elements multiply to the identity under some ordering?

Let $G$ be a group, and for each ordered $n$ tuple $(g_1,...g_n)$ of elements of $G$, consider the function $f_n$ that outputs the number of permutations $\sigma\in S_n$ for which $g_{\sigma(1)}g_{\...
Chris H's user avatar
  • 1,854
7 votes
1 answer
964 views

Bounding the probability that two binomials are equal

Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question. Let $B_{n,p}$ denote the usual binomial random ...
Pat Devlin's user avatar
  • 2,660
1 vote
1 answer
177 views

Is the bound of Spencer on discrepancy tight?

Suppose $\mathcal{S} = \{S_1,\ldots,S_m\}$ is a set system in $[n]=\{1,\ldots,n\}$, which means that for each $i$, $S_i\subset [n].$ Define the discrepancy of $\mathcal{S}$ by $$disc(\mathcal{S})=\...
Nate's user avatar
  • 131
0 votes
1 answer
78 views

Estimate an expression about probability about Bernoulli random variables

Given $v_{ij} \in \{0,1\}$, $i \in \{1,2\}$, $j \in \{1,2,\ldots,n\}$. Let $X_1, X_2, \ldots, X_n$ be random variables, $P[X_i=1]=P[X_i=0]=1/2$, $i \in \{1,\ldots, n\}$. By checking many examples, I ...
Jianrong Li's user avatar
  • 6,101
1 vote
0 answers
94 views

Balls and bins, with cardinality constraints

Suppose I have $n$ sets of $k$ balls each, with each one of the $nk$ balls distributed uniformly at random among $m$ bins. Further suppose that I have a probability vector $p=(p_1,\dots,p_m)$. I am ...
Tom Solberg's user avatar
  • 3,929
31 votes
1 answer
2k views

Is this formal noncommutative power series identity known?

I recently discovered the following cute formal noncommutative power series identity: if $(x_i)_{i \in I}$ is some finite collection of noncommuting variables, then the formal power series $$ 1 + \...
Terry Tao's user avatar
  • 108k
3 votes
1 answer
212 views

Inequality for difference of consecutive atom probabilities for binomial distribution

Edit: This post was originally two questions, the first of which has been answered, but a reference would still be appreciated if existent. The second question has been removed and migrated to its ...
Pat Devlin's user avatar
  • 2,660

1
56 57
58
59 60
211