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
3 votes
1 answer
309 views

Problem related to Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$. Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ good if, for any $r,s,u,...
Turbo's user avatar
  • 13.7k
5 votes
1 answer
2k views

A generalized theorem of Hall's marriage theorem

We all know Hall's marriage theorem as following: A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a matching of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$. And I am ...
user avatar
0 votes
1 answer
220 views

Maximal induced cycles on $n$-clique graphs

For any set $X$ we set $[X]^2 = \big\{\{a,b\}: a, b\in X\text{ and } a\neq b\big\}$. We say a simple undirected graph $G=(V,E)$ is an $n$-clique graph if there are $S_1,\ldots,S_n\subseteq V$ such ...
Dominic van der Zypen's user avatar
1 vote
0 answers
116 views

Consecutive integers divisible by consecutive small numbers

Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...
Turbo's user avatar
  • 13.7k
5 votes
1 answer
442 views

Asymptotic enumeration of magic squares

An order-$n$ magic square is an $n \times n$ matrix over the numbers $\{1, ... ,n^2\}$, each appearing exactly once, whose row and column sums are all equal. Sometimes the sums of the diagonals are ...
Zur Luria's user avatar
  • 1,613
6 votes
0 answers
116 views

Chromatic numbers for coloring-constrained graphs

I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...
Jim Tilley's user avatar
3 votes
1 answer
281 views

Can a length n distributive lattice be embedded into Bn?

Let $\mathcal{L}$ be a finite distributive lattice, then it is known that it can be embedded into a finite boolean lattice (see theorem 8.5. p91 in this note). Let $n$ be the length of $\mathcal{...
Sebastien Palcoux's user avatar
1 vote
0 answers
70 views

Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs? Addendum: ...
Jim Tilley's user avatar
4 votes
1 answer
159 views

Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

You are given a multigraph $G$ with $n$ vertices as follows: $V := (v_1, v_2, \dots ,v_n)$ $C := \{c_1, c_2, \dots\}$, be an infinite set of colors. $f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...
Kostub Deshmukh's user avatar
1 vote
0 answers
39 views

Colorful Neighborhoods

Given: $G:=\{V= \{v_1,\ ...\ v_n\},E\subset V\times V\}, n<\infty$, a symmetric complete, simple graph $w:=\ \ E \ni e_{ij}\mapsto \mathbb{R}^+$, a weight function for the edges of $G$ $K:=\{c_1,\ ....
Manfred Weis's user avatar
  • 12.6k
1 vote
1 answer
344 views

The number of good partitions

This was also posted in stackexchange. However, I have no idea how difficult it is. All hints or references are appreciated! Consider a set $S$ of $n$ red balls and $m$ blue balls. It is well known ...
Azizi's user avatar
  • 13
2 votes
1 answer
154 views

Partitioning the vertex set of a planar bipartite graph into a tree and an independent set

Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set. Is there a characterization of such ...
hbm's user avatar
  • 1,034
3 votes
1 answer
182 views

Exact statistics in the Frobenius coin problem

The Frobenius coin problem guarantees that if $(a,b)=1$, then $$ax+by$$ does not represent exactly $\frac{(a-1)(b-1)}2$ numbers all below $g(a,b)=ab-a-b$ if $x,y\geq0$ holds. Assume $m\in[0,ab-a-b]$ ...
Turbo's user avatar
  • 13.7k
4 votes
0 answers
104 views

Weighted maximal number of disjoint singly-generated ideals in the divisibility poset for $\{1,2,\ldots,n\}$

In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual ...
kodlu's user avatar
  • 10.1k
33 votes
1 answer
1k views

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation: $$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$ $a$ is an ...
draks ...'s user avatar
  • 457
8 votes
1 answer
174 views

Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
sai's user avatar
  • 183
2 votes
3 answers
858 views

The number of submodules of $\mathbb{Z}_q^n$

Observe $\mathbb{Z}_q^n = \mathbb{Z}_q \times \cdots \times\mathbb{Z}_q$ as a module over $\mathbb{Z}_q\equiv\mathbb{Z}/q\mathbb{Z}$, for general $q$. I am interested in the following questions: How ...
aleph's user avatar
  • 503
9 votes
1 answer
207 views

A Graph-Theory Related Question

Let $n$ be a positive integer and partition a grid of $4n$ by $4n$ unit squares into $4n^2$ squares of sidelength $2$. (The squares with sidelength $2$ have all of their sides on the gridlines of the $...
J. Han's user avatar
  • 91
4 votes
2 answers
352 views

A property of uncountable almost disjoint families

Let $\mathcal{A}$ be an uncountable almost disjoint family (not necessarily maximal) of infinite subsets of $\mathbb{N}$. Denote by $\mathcal{A}_{\subseteq}=\{ B\subseteq\mathbb{N}:|B|=\omega \wedge \...
Iian Smythe's user avatar
  • 3,001
9 votes
0 answers
289 views

Weighted sum of the Simsun (Andre) permutations

Let $ c_{n,k} $ be the Simsun permutations$^1$ defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1);$ $$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, \hspace{0....
user avatar
9 votes
0 answers
294 views

An abstract zero-sum problem

I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
monkeymaths's user avatar
  • 1,169
6 votes
1 answer
506 views

Eigenvalue inequality for regular graphs

I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...
David Roberson's user avatar
7 votes
1 answer
944 views

Algorithm to count the number of perfect matchings in non planar graph

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...
Sandeep Silwal's user avatar
2 votes
0 answers
137 views

Number of multipartite partitions with odd components

For some positive integer $r$, by an $r$-vector I will mean an $r$-tuple $(a_1,a_2,\dots,a_r)$ with $a_1,\dots,a_r$ nonnegative integers not all zero, and I will call it odd if $a_1,\dots,a_r$ are all ...
Binzhou Xia's user avatar
8 votes
1 answer
1k views

A remarkable sum over partitions

While studying some seemingly unrelated topological questions, I have experimentally discovered what appears (to me) to be a remarkable sum over partitions. I was wondering if anyone knows how to ...
Julia's user avatar
  • 83
4 votes
0 answers
187 views

Fibers of torus equivariant moment maps

Given a closed (possibly singular) projective variety $V$ with a symplectic structure and a torus action, there is a moment map $\mu: V \rightarrow Lie(T)^*$. Note that the dimension of $T$ could be ...
Qiao's user avatar
  • 1,669
2 votes
0 answers
114 views

Zero-one links: how many, and how to produce?

For $m \geq 1$, define a link to be a zero-one word $w=d_0d_1 \ldots d_k$, where $d_0=0$ and $k=2^m-1$ , such that the words $$ w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k $$ ...
Clark Kimberling's user avatar
7 votes
1 answer
222 views

Unusual isoperimetry and maximizing the measure of unions of translates of a set

Let me state a standard result first. Let a $A\subset \mathbb{R}^d$ be a set of fixed volume. Define $A_t$ to be the set of all points at distance at most $t$ from $A$. Then the volume of $A_t$ is ...
TOM's user avatar
  • 2,218
4 votes
2 answers
308 views

What are bounds for the number of monotone functions $M:P\rightarrow T$ where $P$ is a finite poset and $T$ is a finite totally ordered set?

For the case where $P=\{0,1\}^n$ and $T=\{0,1\}$ the number of such functions is called the $n$-th Dedekind number and I discovered that there is large literature on determining bounds for these ...
Jan's user avatar
  • 41
16 votes
1 answer
3k views

Where did the term "additive energy" originate?

A fundamental object in modern additive combinatorics and harmonic analysis is additive energy. Given a subset $A$ of (say) an abelian group $G$ the additive energy of $A$ is defined to be the ...
Mark Lewko's user avatar
  • 11.7k
5 votes
1 answer
304 views

Coefficients of Ehrhart polynomials, in the binomial-coefficient basis

Let $P$ be the convex hull of a finite set of points in $\mathbb Z^d$, and $p(n) = \#\{nP \cap \mathbb Z^d\}$ be its Ehrhart polynomial, which is also the Hilbert polynomial of the corresponding ...
Allen Knutson's user avatar
3 votes
1 answer
463 views

Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$. Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $...
G H's user avatar
  • 123
5 votes
0 answers
135 views

What is the maximal convex hull in $\mathbb R^3$ of a tree with fixed total length?

Denote by $\mathcal T_n$ the set of all trees on $n$ nodes. For a tree $T\in\mathcal T_n$, we assign to each edge a non-negative length such that the sum of all lengths is 1. Denote by $v(T)$ the ...
Wolfgang's user avatar
  • 13.2k
5 votes
1 answer
710 views

Is there a name for this fast growing function?

Define $F(n,i)=\prod_{j=1}^nj^{j^i}$. $F(n,0)=n!$ is just the standard factorial, whereas $F(n,1)$ is the so-called hyperfactorial. Is there a term for $F(n,i)$? How fast do these grow? Is the ...
user avatar
11 votes
0 answers
234 views

Coefficients of universal Schubert polynomials

Let $e_i^j$ be the elementary symmetric polynomial in $x_1,x_2,\ldots,x_j$. Then the ordinary Schubert polynomial has an expansion of the form $$S_u(x)=\sum_{i_1,i_2,\ldots,i_n}{a^{i_1,i_2,\ldots,i_n}...
Matt Samuel's user avatar
  • 2,008
14 votes
0 answers
253 views

Is combinatorial automorphism of symmetric convex polytope always antipodal?

The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
Fedor Petrov's user avatar
1 vote
0 answers
123 views

The smallest disk containing all cirular arcs

In a comment to my recent question about covering segments by a disk, Gerhard Paseman has suggested a generalisation: replacing the segments of the original $n$-gon by a simple closed (say, convex) ...
Wolfgang's user avatar
  • 13.2k
4 votes
1 answer
158 views

Conceptual explanation for multiplicativity of theta generalization of extreme characters of U(infty)

A character of $U(\infty)$ is a continuous, positive definite class function $\chi: U(\infty) \longrightarrow \mathbb{C}$, which is normalized by $\chi(e) = 1$. Observe that the set of characters of $...
user avatar
13 votes
1 answer
252 views

Graphs with a coloring that majorizes all other colorings

By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...
Timothy Chow's user avatar
  • 78.1k
3 votes
1 answer
738 views

A version of the Weak Regularity Lemma

Definitions: Given a graph $G$ and $S$, $T \subseteq V(G)$, let $e_G(S, T)$ denote the number of edges of $G$ with one endpoint in $S$ and the other in $T$ and let $$d_G(S, T) := \frac{e_G(S, T)}{\...
Andrew Uzzell's user avatar
2 votes
1 answer
454 views

Alternating sign binomial identity [closed]

I recently noticed that for a triple of integers $k \geq 2$, $k \geq m \geq t \geq 1$, the following identity seems to hold $\sum_{j=0}^{m-t} (-1)^{m-t-j}{k \choose j}{m-1-j \choose t-1}={k-t \choose ...
Miriam's user avatar
  • 21
10 votes
1 answer
722 views

Demazure product in Coxeter and Artin groups

As a follow-up of Allen's question Coxeter exchanges in non-reduced words, I wonder whether it is known that the Demazure product is well-defined in Artin groups. This is: Let $(W,S)$ be a Coxeter ...
Christian Stump's user avatar
0 votes
0 answers
1k views

Partial sum of binomial coefficients

For some integer $z \ge 2$ and large integer $n$ and $ t=\lceil \log n\rceil $, what is an approximate value for the following partial binomial sum? $$ \sum_{i=0}^{n-t} \binom{n}{i}z^i .$$ Another ...
Aryo Z's user avatar
  • 1
6 votes
1 answer
380 views

A property of the derivatives of a function

Suppose that $f,g_1,g_2,\dots$ are functions from $\mathbb{R}$ to $\mathbb{R}$ such that $f'=f\,g_1$ and $g'_j=g_j^2-g_j g_{j+1}$. Here and in what follows, $j$ is any natural number. Then, by ...
Iosif Pinelis's user avatar
12 votes
0 answers
215 views

Do the Laver tables converge to the Sierpinski triangle with a line segment sticking out in the hyperspace topology?

Let $(\{1,...,2^{n}\},*_{n})$ denote the $n$-th Laver table. Let $$C_{n}=\{(\frac{x}{2^{n}},\frac{x*_{n}y}{2^{n}})|x,y\in\{1,2,3,...,2^{n}\}\}$$ for all $n\in\mathbb{N}$. Then since $C_{n}$ is a ...
Joseph Van Name's user avatar
7 votes
1 answer
199 views

Are the primary parallelotopes classified? (equivalently, Voronoi cells of lattices)

A primary parallelohedron is a polyhedron that can fill space with infinite translated copies. It is known (e.g., Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, pp. 29-30, 1973; or, ...
Samuel Reid's user avatar
  • 1,401
11 votes
2 answers
685 views

Pursuit-Evasion type game on graph ("Flyswatter game")

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...
minderbinder8's user avatar
15 votes
2 answers
497 views

Coxeter exchanges in non-reduced words

Let $Q$ be a word in the generators of some Coxeter group, and consider a subword $R$ (not necessarily reduced, though I might want $Q$ to be). Define the greedy or Demazure product of $R$ as follows: ...
Allen Knutson's user avatar
1 vote
2 answers
191 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
f10w's user avatar
  • 163

1
126 127
128
129 130
211