Questions tagged [extremal-combinatorics]
This tag is for questions asking for combinatorial structures of maximum or minimum possible size under some constraints. Typical questions ask for bounds or the exact value of the extremal size, or for the structure of extremal configurations.
852 questions
3
votes
0
answers
90
views
Cases $n=7,8$ of a conjecture on semigroups
[Crossposted at mathoverflow and AoPS].
I would like to prove cases $n=7,8$ of this conjecture (general question asked here): given any commutative semigroup $S$ of order $n \ge 1$, there exist $a, b \...
- 2,405
6
votes
1
answer
140
views
Finding $\lim_{n \to \infty} \frac{l(n)}{n^2}$ for minimal vertex coloring satisfying a property for all $k \times k$ sub-squares
I am working on the following grid coloring problem and am stuck on finding the general form of $l(n)$.
The Problem
Some of the vertices of the unit squares of an $n \times n$ chessboard are colored ...
- 964
2
votes
1
answer
226
views
Looking for a certain combinatorial design
[Crossposted from mathoverflow]
Let $\mathcal{F} = \{\{x_1, x_2\} : 1 \le x_1 \lt x_2 \le n \}$, $n \ge 2$, and let $\mathcal{G} = \{G_1, \ldots, G_n\}$ be a partition of $\mathcal{F}$ in $n$ parts. ...
- 2,405
1
vote
0
answers
58
views
Maximum number of edges $(u,v)$ in a bipartite graph with $\deg(u)>\deg(v)$
Question: Let $G=(U,V,E)$ be a bipartite graph with $|U|=25$, $|V|=26$, and $|E|=105$.
Assume every vertex is incident to at least one edge (i.e., $\deg(w)\ge 1$ for all $w\in U\cup V$).
We call an ...
- 31
7
votes
1
answer
270
views
Dance at a marriage party featuring PUTNAM $1965$ $A 4$
Problem (Putnam 1965 A4)
At a marriage party, no boy dances with every girl, but each girl dances with at least one boy. Prove that there are two girl-boy couples $g_1b_1$ and $g_2b_2$ who dance such ...
- 3,478
1
vote
1
answer
219
views
Maximum value for a sequentially defined function on permutations of 5-tuples
I am trying to solve the following problem:
The Problem
Assume $S_n$ is the set of all ordered $n$-tuples of 0 and 1 and let $A_1, A_2, \ldots, A_{32}$ be a permutation of the elements of $S_5$. Also ...
- 964
4
votes
0
answers
68
views
Maximum number of imbalanced edges of a graph
Let $G=(V,E)$ be a graph with $n$ vertices. We call an edge $(i,j)\in E$ is imbalanced if $d_i\neq d_j$. What is the maximum number of imbalanced edge of $G$?
A candidate type of graph that attain the ...
- 273
0
votes
0
answers
45
views
Is the Coxeter group $W_{n-1}=S_{n-1}$ the quotient of $S_n$ by a simple reflection?
I believe the following three formulations are equivalent:
Is the associahedron $A_{n-1}$ the quotient of $A_n$ by one of its largest faces?
Are the triangulations of an $n-1$-gon the quotient of ...
- 9,768
-1
votes
1
answer
61
views
Optimal combinatorial game
Background:
I am trying to solve some subproblem related to an original question of mine.
Question:
Let $n$ be a positive integer, $n \ge 3$. Let $m = \lfloor (n+1)/2 \rfloor$. Let $S = [n] \times [n]$...
- 2,405
5
votes
1
answer
150
views
Coloring of $n$ $n$-element subsets of a large set
Let $n$ be a positive integer, and let $S$ be a set with $|S| = n^2+n-1$.
Suppose that all $n$-element subsets of $S$ are colored in two colors (say, red and blue).
Prove that there exist $n$ pairwise ...
user1299769
3
votes
2
answers
198
views
Find the minimal $|S|$ where $S\subseteq\mathcal{P}[n]$ such that for all $i\in[n]$, there exists $A\subseteq S$ such that $\bigcap_{a\in A}{a}=\{i\}$
Given a positive integer $n$. Let $S$ be a subset of the
power set of $\{ 1,2,...,n\}$ such that, for each $i\in \{
1,2,...,n\}$, there exists $A\subseteq S$ such that $$\bigcap_{a\in
A}{a}=\{ i\}$$ ...
- 92.5k
0
votes
0
answers
47
views
Trouble in computing the minimum number of $K_{r+1}$ subgraphs given the number of vertices and $K_r$ subgraphs
It is known that a simple graph with $n$ vertices and $m$ edges has at least $\frac{m}{3n}(4m - n^2)$ triangles. Some proofs can be found here.
Here I repeat what I have understood (hopefully ...
- 2,405
0
votes
0
answers
36
views
A generalization of a problem of upper bounding number of points which have large pairwise distance.
While working on a problem related to communication complexity, I came across the following interesting problem related to combinatorics of sets.
Given $A$, a subset of $\{0,1\}^n$, and $S$, a subset ...
2
votes
1
answer
110
views
Number of hypercube graph vertices with given in-degrees
Is there always an orientation of the edges of the hypercube graph $Q_d$ so that there are $\big\lfloor \frac {d2^{d-1}}k\big\rfloor$ vertices each with in-degree at least $k\in(\frac d2,d)$?
- 10.5k
0
votes
1
answer
123
views
Asymptotics of bipartite extremal numbers
Relevant definitions: This problem concerns how $\text{ex}(n,n,H)$ (the maximum number of edges in an $H$-free subgraph of $K_{n,n}$) and $\text{ex}_B(n,H)$ (the maximum number of edges in an $H$-free ...
- 31