BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that for loopless 6-regular triangulations on the torus the gap between the choice number and chromatic number is at most 2. We also show that the largest gap for graphs embeddable in an orientable surface of genus g is of the order Θ(g), and moreover for graphs with chromatic number of the order o(g/log2(g)) the largest gap is of the order o(g).
A sequence $\bfx=(x_1,\ldots,x_m)$ of elements of Zn is called an \textit{A-weighted Davenport Z-sequence} if there exists $\bfa:=(a_1,\ldots,a_m)\in (A\cup\{0\})^m\setminus\bfzero_m$ such that ∑iaixi=0. Here $\bfzero_m=(0,\ldots,0)\in\Z_n^m$. Similarly, the sequence $\bfx$ is called an \textit{A-weighted Erdős Z-sequence} if there exists $\bfa:=(a_1,\ldots,a_m)\in (A\cup\{0\})^m\setminus\{\bfzero_m\}$ with $|Supp(\bfa)|=n$, such that ∑iaixi=0, where $Supp(\bfa):=\{i: a_i\ne 0\}$. A Zn-sequence $\bfx$ is called k-restricted if no element of Zn appears more than k times in $\bfx$. In this paper, we study the problem of determining the least value of m for which a k-restricted Zn-sequence of length m is an A-weighted Davenport Z-sequence (resp. anA-weighted Erdős Z-sequence). We also consider the same problem for random Zn sequences, for certain very natural choices for the set A.
The \textit{Distinguishing Chromatic Number} of a graph G, denoted χD(G), was first defined in \cite{collins} as the minimum number of colors needed to properly color G such that no non-trivial automorphism ϕ of the graph G fixes each color class of G. In this paper, we consider random Cayley graphs Γ(A,S) defined over certain abelian groups A and show that with probability at least 1−n−Ω(logn) we have, χD(Γ)≤χ(Γ)+1.
A graph G is said to be k-distinguishable if the vertex set can be colored using k colors such that no non-trivial automorphism fixes every color class, and the distinguishing number D(G) is the least integer k for which G is k-distinguishable. If for each v∈V(G) we have a list L(v) of colors, and we stipulate that the color assigned to vertex v comes from its list L(v) then G is said to be L-distinguishable where L={L(v)}v∈V(G). The list distinguishing number of a graph, denoted Dl(G), is the minimum integer k such that every collection of lists L with ∣L(v)∣=k admits an L-distinguishing coloring. In this paper, we prove that Dl(G)=D(G) when G is a Kneser graph.
The \textit{Distinguishing Chromatic Number} of a graph G, denoted χD(G), was first defined in \cite{collins} as the minimum number of colors needed to properly color G such that no non-trivial automorphism ϕ of the graph G fixes each color class of G. In this paper, 1. We prove a lemma that may be considered a variant of the Motion lemma of \cite{RS} and use this to give examples of several families of graphs which satisfy χD(G)=χ(G)+1. 2.We give an example of families of graphs that admit large automorphism groups in which every proper coloring is distinguishing. We also describe families of graphs with (relatively) very small automorphism groups which satisfy χD(G)=χ(G)+1, for arbitrarily large values of χ(G). 3. We describe non-trivial families of bipartite graphs that satisfy χD(G)>r for any positive integer r.
Let n,r,k be positive integers such that 3≤k<n and 2≤r≤k−1. Let m(n,r,k) denote the maximum number of edges an r-uniform hypergraph on n vertices can have under the condition that any collection of i edges, span at least i vertices for all 1≤i≤k. We are interested in the asymptotic nature of m(n,r,k) for fixed r and k as n→∞. This problem is related to the forbidden hypergraph problem introduced by Brown, Erdős, and Sós and very recently discussed in the context of combinatorial batch codes. In this short paper we obtain the following results. {enumerate}[(i)] Using a result due to Erdős we are able to show m(n,k,r)=o(nr) for 7≤k, and 3≤r≤k−1−⌈logk⌉. This result is best possible with respect to the upper bound on r as we subsequently show through explicit construction that for 6≤k, and k−⌈logk⌉≤r≤k−1,m(n,r,k)=Θ(nr). This explicit construction improves on the non-constructive general lower bound obtained by Brown, Erdős, and Sós for the considered parameter values. For 2-uniform CBCs we obtain the following results. {enumerate} We provide exact value of m(n,2,5) for n≥5. Using a result of Lazebnik,et al. regarding maximum size of graphs with large girth, we improve the existing lower bound on m(n,2,k) (Ω(nk−1k+1)) for all k≥8 and infinitely many values of n. We show m(n,2,k)=O(n1+⌊4k⌋1) by using a result due to Bondy and Simonovits, and also show m(n,2,k)=Θ(n3/2) for k=6,7,8 by using a result of Kövari, Sós, and Turán.
Even though mutually unbiased bases and entropic uncertainty relations play an important role in quantum cryptographic protocols they remain ill understood. Here, we construct special sets of up to 2n+1 mutually unbiased bases (MUBs) in dimension d=2^n which have particularly beautiful symmetry properties derived from the Clifford algebra. More precisely, we show that there exists a unitary transformation that cyclically permutes such bases. This unitary can be understood as a generalization of the Fourier transform, which exchanges two MUBs, to multiple complementary aspects. We proceed to prove a lower bound for min-entropic entropic uncertainty relations for any set of MUBs, and show that symmetry plays a central role in obtaining tight bounds. For example, we obtain for the first time a tight bound for four MUBs in dimension d=4, which is attained by an eigenstate of our complementarity transform. Finally, we discuss the relation to other symmetries obtained by transformations in discrete phase space, and note that the extrema of discrete Wigner functions are directly related to min-entropic uncertainty relations for MUBs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.