Skip to main content
added 151 characters in body
Source Link
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

I think randomRandom graphs might show that this parameter can be at least as large as $n/ \log n$. As is often the case there are some details to be checked, but I'd try the following.

Let $G \sim G_{n,1/2}$. Then the clique and independence number of $G$ are both around $2\log_2 n$ with high probability, and the chromatic number is around $n / 2\log_2 n$. Bollobás's proof of this fact goes by showing that the independence number of $G$ remains around $2\log_2 n$ even after we've already removed a large number of independent sets of that size. So I expect $G$ to contain about $n / 2\log_2 n$ disjoint maximal cliques, giving $|T| \geq n / 2\log_2 n$. (And $|A| \leq 2\log_2 n$ as are there are no larger independent sets in $G$.)

The main thing to check isIt seems unlikely that the maximal cliques don't conspireare conspiring to share vertices. More worrying is that the maximal cliques might not all have the same size, but that seems unlikelyperhaps enough of them do, or can be fixed up without doing too much damage to the independence number.

I think random graphs show that this parameter can be at least as large as $n/ \log n$. As is often the case there are some details to be checked, but I'd try the following.

Let $G \sim G_{n,1/2}$. Then the clique and independence number of $G$ are both around $2\log_2 n$ with high probability, and the chromatic number is around $n / 2\log_2 n$. Bollobás's proof of this fact goes by showing that the independence number of $G$ remains around $2\log_2 n$ even after we've already removed a large number of independent sets of that size. So I expect $G$ to contain about $n / 2\log_2 n$ disjoint maximal cliques, giving $|T| \geq n / 2\log_2 n$. (And $|A| \leq 2\log_2 n$ as are there are no larger independent sets in $G$.)

The main thing to check is that the maximal cliques don't conspire to share vertices, but that seems unlikely.

Random graphs might show that this parameter can be at least as large as $n/ \log n$. As is often the case there are some details to be checked, but I'd try the following.

Let $G \sim G_{n,1/2}$. Then the clique and independence number of $G$ are both around $2\log_2 n$ with high probability, and the chromatic number is around $n / 2\log_2 n$. Bollobás's proof of this fact goes by showing that the independence number of $G$ remains around $2\log_2 n$ even after we've already removed a large number of independent sets of that size. So I expect $G$ to contain about $n / 2\log_2 n$ disjoint maximal cliques, giving $|T| \geq n / 2\log_2 n$. (And $|A| \leq 2\log_2 n$ as are there are no larger independent sets in $G$.)

It seems unlikely that the maximal cliques are conspiring to share vertices. More worrying is that the maximal cliques might not all have the same size, but perhaps enough of them do, or can be fixed up without doing too much damage to the independence number.

Source Link
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

I think random graphs show that this parameter can be at least as large as $n/ \log n$. As is often the case there are some details to be checked, but I'd try the following.

Let $G \sim G_{n,1/2}$. Then the clique and independence number of $G$ are both around $2\log_2 n$ with high probability, and the chromatic number is around $n / 2\log_2 n$. Bollobás's proof of this fact goes by showing that the independence number of $G$ remains around $2\log_2 n$ even after we've already removed a large number of independent sets of that size. So I expect $G$ to contain about $n / 2\log_2 n$ disjoint maximal cliques, giving $|T| \geq n / 2\log_2 n$. (And $|A| \leq 2\log_2 n$ as are there are no larger independent sets in $G$.)

The main thing to check is that the maximal cliques don't conspire to share vertices, but that seems unlikely.