Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA spectral bound on hypergraph discrepancy
167
0
0.0
(
0
)
Added by
Aditya Potukuchi
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Aditya Potukuchi
Ask ChatGPT about the research
No Arabic abstract
Let $mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m times n$ incidence matrix of $mathcal{H}$ and let us denote $lambda =max_{v perp overline{1},|v| = 1}|Mv|$. We show that the discrepancy of $mathcal{H}$ is $O(sqrt{t} + lambda)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m geq n$ edges is almost surely $O(sqrt{t})$ as $n$ grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
rate research
Read More
We study hypergraph discrepancy in two closely related random models of hypergraphs on $n$ vertices and $m$ hyperedges. The first model, $mathcal{H}_1$, is when every vertex is present in exactly $t$ randomly chosen hyperedges. The premise of this is closely tied to, and motivated by the Beck-Fiala conjecture. The second, perhaps more natural model, $mathcal{H}_2$, is when the entries of the $m times n$ incidence matrix is sampled in an i.i.d. fashion, each with probability $p$. We prove the following: 1. In $mathcal{H}_1$, when $log^{10}n ll t ll sqrt{n}$, and $m = n$, we show that the discrepancy of the hypergraph is almost surely at most $O(sqrt{t})$. This improves upon a result of Ezra and Lovett for this range of parameters. 2. In $mathcal{H}_2$, when $p= frac{1}{2}$, and $n = Omega(m log m)$, we show that the discrepancy is almost surely at most $1$. This answers an open problem of Hoberg and Rothvoss.
This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble methods. We also give a detailed sketch of some aspects of the recent proof of the ErdH{o}s-Faber-Lov{a}sz conjecture.
For a graph $G=(V,E)$, $kin mathbb{N}$, and a complex number $w$ the partition function of the univariate Potts model is defined as [ {bf Z}(G;k,w):=sum_{phi:Vto [k]}prod_{substack{uvin E phi(u)=phi(v)}}w, ] where $[k]:={1,ldots,k}$. In this paper we give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any $Deltain mathbb{N}$ and any $kgeq eDelta+1$, there exists an open set $U$ in the complex plane that contains the interval $[0,1)$ such that ${bf Z}(G;k,w) eq 0$ for any $win U$ and any graph $G$ of maximum degree at most $Delta$. (Here $e$ denotes the base of the natural logarithm.) For small values of $Delta$ we are able to give better results. As an application of our results we obtain improved bounds on $k$ for the existence of deterministic approximation algorithms for counting the number of proper $k$-colourings of graphs of small maximum degree.
Let $H$ be connected $m$-uniform hypergraph and $mathcal{A}(H)$ be the adjacency tensor of $H$. The stabilizing index of $H$, denoted by $s(H)$, is exactly the number of eigenvectors of $mathcal{A}(H)$ associated with the spectral radius, and the cyclic index of $H$, denoted by $c(H)$, is the number of eigenvalues of $mathcal{A}(H)$ with modulus equal to the spectral radius. Let $bar{H}$ be a $k$-fold covering of $H$. Then $bar{H}$ is isomorphic to a hypergraph $H_B^phi$ derived from the incidence graph $B_H$ of $H$ together with a permutation voltage assignment $phi$ in the symmetric group $mathbb{S}_k$. In this paper, we first characterize the connectedness of $bar{H}$ by using $H_B^phi$ for subsequent discussion. By applying the theory of module and group representation, we prove that if $bar{H}$ is connected, then $s(H) mid s(bar{H})$ and $c(H) mid c(bar{H})$. In the situation that $bar{H}$ is a $2$-fold covering of $H$, if $m$ is even, we show that regardless of multiplicities, the spectrum of $mathcal{A}(bar{H})$ contains the spectrum of $mathcal{A}(H)$ and the spectrum of a signed hypergraph constructed from $H$ and the covering projection; if $m$ is odd, we give an explicit formula for $s(bar{H})$.
We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
