Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of contingency tables and the independence heuristic
201
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We obtain sharp asymptotic estimates on the number of $n times n$ contingency tables with two linear margins $Cn$ and $BCn$. The results imply a second order phase transition on the number of such contingency tables, with a critical value at ts $B_{c}:=1 + sqrt{1+1/C}$. As a consequence, for ts $B>B_{c}$, we prove that the classical emph{independence heuristic} leads to a large undercounting.
rate research
Read More
In this work we define log-linear models to compare several square contingency tables under the quasi-independence or the quasi-symmetry model, and the relevant Markov bases are theoretically characterized. Through Markov bases, an exact test to evaluate if two or more tables fit a common model is introduced. Two real-data examples illustrate the use of these models in different fields of applications.
We investigate the independence number of two graphs constructed from a polarity of $mathrm{PG}(2,q)$. For the first graph under consideration, the ErdH{o}s-Renyi graph $ER_q$, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper we consider the ErdH{o}s-Renyi hypergraph of triangles $mathcal{H}_q$. We determine the exact magnitude of the independence number of $mathcal{H}_q$, $q$ even. This solves a problem posed by Mubayi and Williford.
The analogue of Hadwigers conjecture for the immersion order states that every graph $G$ contains $K_{chi (G)}$ as an immersion. If true, it would imply that every graph with $n$ vertices and independence number $alpha$ contains $K_{lceil frac nalpharceil}$ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph $G$ contains an immersion of a clique on $bigllceil frac{chi (G)-4}{3.54}bigrrceil$ vertices. Their result implies that every $n$-vertex graph with independence number $alpha$ contains an immersion of a clique on $bigllceil frac{n}{3.54alpha}-1.13bigrrceil$ vertices. We improve on this result for all $alphage 3$, by showing that every $n$-vertex graph with independence number $alphage 3$ contains an immersion of a clique on $bigllfloor frac {n}{2.25 alpha - f(alpha)} bigrrfloor - 1$ vertices, where $f$ is a nonnegative function.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
In this paper, we establish a couple of results on extremal problems in bipartite graphs. Firstly, we show that every sufficiently large bipartite graph with average degree $Delta$ and with $n$ vertices on each side has a balanced independent set containing $(1-epsilon) frac{log Delta}{Delta} n$ vertices from each side for small $epsilon > 0$. Secondly, we prove that the vertex set of every sufficiently large balanced bipartite graph with maximum degree at most $Delta$ can be partitioned into $(1+epsilon)frac{Delta}{log Delta}$ balanced independent sets. Both of these results are algorithmic and best possible up to a factor of 2, which might be hard to improve as evidenced by the phenomenon known as `algorithmic barrier in the literature. The first result improves a recent theorem of Axenovich, Sereni, Snyder, and Weber in a slightly more general setting. The second result improves a theorem of Feige and Kogan about coloring balanced bipartite graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
